按顺序映射范围循环 [英] Map in order range loop

问题描述

我正在寻找一种确定的方法来按顺序覆盖 Go map.

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

Golang 规范 声明如下:

未指定地图上的迭代顺序，并且不能保证从一次迭代到下一次迭代是相同的.如果在迭代过程中删除了尚未到达的地图条目，则不会产生相应的迭代值.如果映射条目是在迭代期间创建的，则该条目可能会在迭代期间产生或可能被跳过.对于创建的每个条目以及从一个迭代到下一个迭代，选择可能会有所不同.如果map为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 和 Google 上找到的所有(恕我直言)我不喜欢的解决方法.

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:

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

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

这不是字典式的，因此不同于 @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)包装成一个新类型并为其提供方法，并隐藏地图和切片.这样就不会发生数据错位.

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()

在 Go Playground 上试试.

另一种方法是将值包装起来，并沿着实际值存储下一个/上一个键.

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 设置为值，并且您必须将其链接到前一个(最后一个)对.要链接，您必须将最后一个包装器的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
    }
}

使用也是一样的.在 Go Playground 上试试.

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()你可以改变nextcode> 字段而无需分配新的 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

You may choose first and last fields to be of type *valueWrapper

您可以选择 next 类型为 *valueWrapper

You may choose next to be of type *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 结构.所以如果你需要删除一个元素，你可以超快速地找到包装器(O(1))，更新 prev 和 next 包装器(相互指向)，并执行一个简单的 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).

请注意，第一个解决方案(带切片)中的删除仍然可以通过使用 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.

查看相关问题:为什么Go不能在插入中迭代maps订购?

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