按顺序范围循环映射 [英] 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 上找到的都是 (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:

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

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 个不同的(数据)类型那个功能.

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)包装成一个新类型并为其提供方法，并隐藏map和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 设置为值，并且您必须将其链接到前一个(最后一个)对.要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
    }
}

使用它是一样的.在 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()中你可以改变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

You may choose first and last fields to be of type *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结构.所以如果你需要移除一个元素，你可以超快速地找到包装器(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.

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

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