映射订单范围循环 [英] Map in order range loop

问题描述

我正在寻找一种确定的方式来按顺序排列Go map.

I'm looking for a definitive way to range over a Go map in-order.

Golang规范指出以下内容:

未指定映射的迭代顺序，并且不能保证每次迭代之间都相同.如果在迭代过程中删除尚未到达的映射条目，则不会生成相应的迭代值.如果映射条目是在迭代过程中创建的，则该条目可能在迭代过程中产生或可以被跳过.对于创建的每个条目以及从一个迭代到下一个迭代，选择可能有所不同.如果映射为nil，则迭代次数为0.

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If map entries that have not yet been reached are removed during iteration, the corresponding iteration values will not be produced. If map entries are created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the number of iterations is 0.

我在StackOverflow和Googling上找到的所有都是我不喜欢的( imho )解决方法.

All I've found here on StackOverflow and Googling are (imho) workarounds that I don't like.

是否有一种可靠的方法来遍历地图并按插入顺序检索项目?

Is there a solid way to iterate through a map and retrieve items in the order they've been inserted?

我找到的解决方案是:

• 在两个单独的片段中跟踪键和值:听起来像不使用地图"，失去了使用地图的所有优势.

• Keep track of keys and values in two separate slices: which sounds like "Do not use a map", losing all the advantages of using maps.

使用地图，但要跟踪不同切片中的键:这意味着数据重复可能导致数据未对齐，并最终可能带来大量错误和痛苦的调试工作.

Use a map but keep track of keys in a different slice: this means data duplication which might lead to data misalignment and eventually may bring loads of bugs and painful debugging.

您有什么建议?

根据可能的重复标记进行编辑.

Edit in response to the possible duplicate flag.

我的问题与所提供的问题(此问题，而且此)，这两个问题都要求按照键顺序按字母顺序遍历地图；相反，我特别问过:

There's a slight difference between my question and the one provided (this question, but also this one), both questions asked for looping through the map following the keys lexicographic order; I, instead, have specifically asked:

是否有可靠的方法来遍历地图并按插入顺序检索项目?

并非字典，因此与 @gramme.ninja问题不同:

which is not lexicographic and thus different from @gramme.ninja question:

我如何才能使键按顺序排列/对地图进行排序，以使键按顺序排列并且值相对应?

How can I get the keys to be in order / sort the map so that the keys are in order and the values correspond?

推荐答案

如果需要按顺序按map和键，则这是2种不同的东西，则需要2种不同的(数据)类型来提供该功能.

If you need a map and keys in order, those are 2 different things, you need 2 different (data) types to provide that functionality.

带有键片

最简单的方法是在其他片中保持键顺序.每当您在地图中放入新的货币对时，请先检查密钥是否已在其中.如果不是，则将新密钥添加到单独的片中.当您需要按顺序排列元素时，可以使用按键片.当然，当您移除一对时，您也必须将其也从切片中移除.

The easiest way to achieve this is to maintain key order in a different slice. Whenever you put a new pair into the map, first check if the key is already in it. If not, add the new key to the separate slice. When you need elements in order, you may use the keys slice. Of course when you remove a pair, you also have to remove it from the slice too.

键片只需包含键(而不是值)，因此开销很小.

The keys slice only has to contain the keys (and not the values), so the overhead is little.

将此新功能(map + keys slice)包装为新类型并为其提供方法，然后隐藏地图和slice.这样就不会发生数据未对齐的情况.

Wrap this new functionality (map+keys slice) into a new type and provide methods for it, and hide the map and slice. Then data misalignment cannot occur.

示例实现:

type Key int   // Key type
type Value int // Value type

type Map struct {
    m    map[Key]Value
    keys []Key
}

func New() *Map {
    return &Map{m: make(map[Key]Value)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok {
        m.keys = append(m.keys, k)
    }
    m.m[k] = v
}

func (m *Map) Range() {
    for _, k := range m.keys {
        fmt.Println(m.m[k])
    }
}

使用它:

m := New()
m.Set(1, 11)
m.Set(2, 22)
m.Range()

在游乐场上尝试一下.

另一种方法是包装值，并且-与实际值一起-存储下一个/上一个键.

Another approach would be to wrap the values, and –along the real value– also store the next/previous key.

例如，假设您要使用类似map[Key]Value的地图:

For example, assuming you want a map like map[Key]Value:

type valueWrapper struct {
    value Value
    next  *Key // Next key
}

每当您在地图上添加一个对时，就将valueWrapper设置为值，并且必须将其 link 链接到上一个(最后一个)对.要 link ，您必须将最后一个包装器的next字段设置为指向此新密钥.为了轻松实现此功能，建议还存储最后一个键(以避免搜索它).

Whenever you add a pair to the map, you set a valueWrapper as the value, and you have to link this to the previous (last) pair. To link, you have to set next field of the last wrapper to point to this new key. To easily implement this, it's recommended to also store the last key (to avoid having to search for it).

当您要按插入顺序遍历元素时，请从第一个开始(必须存储此元素)，其关联的valueWrapper会告诉您下一个键(按插入顺序).

When you want to iterate over the elements in insertion order, you start from the first (you have to store this), and its associated valueWrapper will tell you the next key (in insertion order).

示例实现:

type Key int   // Key type
type Value int // Value type

type valueWrapper struct {
    v    Value
    next *Key
}

type Map struct {
    m           map[Key]valueWrapper
    first, last *Key
}

func New() *Map {
    return &Map{m: make(map[Key]valueWrapper)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok && m.last != nil {
        w2 := m.m[*m.last]
        m.m[*m.last] = valueWrapper{w2.v, &k}
    }
    w := valueWrapper{v: v}
    m.m[k] = w
    if m.first == nil {
        m.first = &k
    }
    m.last = &k
}

func (m *Map) Range() {
    for k := m.first; k != nil; {
        w := m.m[*k]
        fmt.Println(w.v)
        k = w.next
    }
}

使用相同.在游乐场上进行尝试.

Using it is the same. Try it on the Go Playground.

注意事项:您可能会根据自己的喜好改变几件事:

Notes: You may vary a couple of things to your liking:

• 您可以声明内部映射，例如m map[Key]*valueWrapper，因此在Set()中，您可以更改next字段，而不必分配新的valueWrapper.

• You may declare the internal map like m map[Key]*valueWrapper and so in Set() you can change the next field without having to assign a new valueWrapper.

您可以选择first和last字段为*valueWrapper

您可以选择next为*valueWrapper

带有附加切片的方法更容易，更清洁.但是，如果地图变大，则从元素中删除元素可能会变得很慢，因为我们还必须在切片中找到未排序"的键，因此这是O(n)复杂性.

The approach with an additional slice is easier and cleaner. But removing an element from it may become slow if the map grows big, as we also have to find the key in the slice which is "unsorted", so it's O(n) complexity.

即使您将prev字段也添加到valueWrapper结构中，即使映射很大，也可以轻松地扩展value-wrapper中具有链表的方法以支持快速元素删除.因此，如果需要删除元素，则可以超快速找到包装器(O(1))，更新上一个包装器和下一个包装器(指向彼此)，并执行简单的delete()操作，它是O(1)

The approach with linked-list in value-wrapper can easily be extended to support fast element removal even if the map is big, if you also add the prev field to the valueWrapper struct. So if you need to remove an element, you can super-fast find the wrapper (O(1)), update the prev and next wrappers (to point to each other), and perform a simple delete() operation, it's O(1).

请注意，第一个解决方案(带有分片)中的删除仍可以通过使用一个附加映射来加快，该映射将在分片中的键到键的索引之间映射(map[Key]int)，因此删除操作仍然可以在O(1)中实现，以换取更大的复杂性.加快速度的另一种方法是将映射中的值更改为包装器，该包装器可以保留切片中键的实际值和索引.

Note that deletion in the first solution (with slice) could still be sped up by using 1 additional map, which would map from key to index of the key in the slice (map[Key]int), so delete operation could still be implemented in O(1), in exchange for greater complexity. Another option for speeding up could be to change the value in the map to be a wrapper, which could hold the actual value and the index of the key in the slice.

请参阅相关问题:为什么不能插入插入式地图点菜吗?

这篇关于映射订单范围循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！