Is there an easy way to iterate over a map in order?

This is a variant of the venerable "why is my map printing out of order" question.

I have a (fairly large) number of maps of the form map[MyKey]MyValue, where MyKey and MyValue are (usually) structs. I've got "less" functions for all the key types.

I need to iterate over the maps in order. (Specifically, the order defined by the less function on that type.) Right now, my code looks like this:

type PairKeyValue struct {
    MyKey
    MyValue
}

type PairKeyValueSlice []Pair

func (ps PairKeyValueSlice) Len() int {
    return len(ps)
}

func (ps PairKeyValueSlice) Swap(i,j int) {
    ps[i], ps[j] = ps[j], ps[i]
}

func (ps PairKeyValueSlice) Less(i,j int) {
    return LessKey(ps[i].MyKey, ps[j].MyKey)
}

func NewPairKeyValueSlice(m map[MyKey]MyValue) (ps PairKeyValueSlice) {
    ps = make(PairKeyValueSlice, len(m))
    i := 0
    for k,v := range m {
        ps[i] = PairKeyValue{k,v}
        i++
    }
    sort.Sort(ps)
}

And then, any time I want an in-order iteration, it looks like:

var m map[MyKey]MyValue
m = GetMapFromSomewhereUseful()
for _, kv := range NewPairKeyValueSlice(m) {
    key := kv.MyKey
    value := kv.MyValue
    DoUsefulWork(key, value)
}

And this appears to largely work. The problem is that it is terribly verbose. Particularly since the problem at hand really has very little to do with implmenting ordered maps and is really about the useful work in the loop.

Also, I have several different keys and value types. So, every time I want to iterate over a map in order, I copy/paste all that code and do find/replace MyKey with the new key and MyValue with the new value. Copy/paste on that magnitude is... "smelly". It has already become a hassle, since I've already made a few errors that I had to fix several times.

This technique also has the downside that it requires making a full copy of all the keys and values. That is undesirable, but I don't see a way around it. (I could reduce it to just the keys, but it doesn't change the primary nature of the problem.)

This question is attempting the same thing with strings. This question does it with strings and ints. This question implies that you need to use reflection and will have to have a switch statement that switches on every possible type, including all user-defined types.

But with the people who are puzzled that maps don't iterate deterministically, it seems that there has got to be a better solution to this problem. I'm from an OO background, so I'm probably missing something fundamental.

So, is there a reasonable way to iterate over a map in order?

Update: Editing the question to have more information about the source, in case there's a better solution than this.

I have a lot of things I need to group for output. Each grouping level is in a structure that looks like these:

type ObjTypeTree struct {
    Children map[Type]*ObjKindTree
    TotalCount uint
}
type ObjKindTree struct {
    Children map[Kind]*ObjAreaTree
    TotalCount uint
}
type ObjAreaTree struct {
    Children map[Area]*ObjAreaTree
    TotalCount uint
    Objs []*Obj
}

Then, I'd iterate over the children in the ObjTypeTree to print the Type groupings. For each of those, I iterate over the ObjKindTree to print the Kind groupings. The iterations are done with methods on the types, and each kind of type needs a little different way of printing its grouping level. Groups need to be printed in order, which causes the problem.

Don't use a map if key collating is required. Use a B-tree or any other/similar ordered container.

I second jnml's answer. But if you want something shorter than you have and are willing to give up compile time type safety, then my library might work for you. (It's built on top of reflect.) Here's a full working example:

package main

import (
	"fmt"

	"github.com/BurntSushi/ty/fun"
)

type OrderedKey struct {
	L1 rune
	L2 rune
}

func (k1 OrderedKey) Less(k2 OrderedKey) bool {
	return k1.L1 < k2.L1 || (k1.L1 == k2.L1 && k1.L2 < k2.L2)
}

func main() {
	m := map[OrderedKey]string{
		OrderedKey{'b', 'a'}: "second",
		OrderedKey{'x', 'y'}: "fourth",
		OrderedKey{'x', 'x'}: "third",
		OrderedKey{'a', 'b'}: "first",
		OrderedKey{'x', 'z'}: "fifth",
	}

	for k, v := range m {
		fmt.Printf("(%c, %c): %s\n", k.L1, k.L2, v)
	}
	fmt.Println("-----------------------------")

	keys := fun.QuickSort(OrderedKey.Less, fun.Keys(m)).([]OrderedKey)
	for _, k := range keys {
		v := m[k]
		fmt.Printf("(%c, %c): %s\n", k.L1, k.L2, v)
	}
}

Note that such a method will be slower, so if you need performance, this is not a good choice.