戈兰地图在顺序范围循环 [英] Golang map in order range loop

问题描述

我正在寻找一个确定的方式来超越 Go map in-order。

Golang spec 指出以下内容：

地图上的迭代顺序未指定，不能保证从一个迭代到下一个迭代相同。如果在迭代期间删除尚未到达的映射条目，则不会生成相应的迭代值。如果在迭代期间创建映射条目，则可能会在迭代期间生成该条目，也可能会被跳过。每个创建的条目和从一个迭代到下一个条目的选择可能会有所不同。如果地图为零，迭代次数为0。

我在StackOverflow和Google搜索这里找到的都是（ imho ）我不喜欢的解决方法。

有没有一种坚实的方法来迭代地图并按照他们的顺序检索项目插入？

我找到的解决方案是：

• 在两个单独的片段中跟踪键和值：这听起来像不要使用地图，失去使用地图的所有优点。




• 使用地图，但跟踪键在不同的切片：这意味着可能导致数据不对齐的数据重复，最终可能会带来大量的错误和痛苦的调试。

你建议什么？

解决方案

如果你需要一个和键顺序，这是两个不同的东西，你需要2种不同的（数据）类型来提供这个功能。

使用键切片

实现此目的的最简单方法是在不同的切片中维护关键顺序。每当你将新的对放入地图时，首先检查钥匙是否已经在其中。如果没有，请将新密钥添加到单独的切片。当您需要元素的顺序时，您可以使用键切片。当然，当你删除一对，你也必须从切片中删除它。

键切片只需要包含键（而不是值），所以开销很小。

将这个新功能（map + keys slice）包装成一个新的类型，并为它提供方法，并隐藏地图和切片。那么数据不对齐就不会发生。

示例实现：

  int //键类型
类型值int //值类型
 
类型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：= mm [k]; ！ok {
 m.keys = append（m.keys，k）
} 
 mm [k] = v 
} 
 
 func *地图）Range（）{
 for _，k：= range m.keys {
 fmt.Println（mm [k]）
} 
} 
  

使用它：

  m：= New（）
 m.Set（1，11）
 m.Set（2，22）
 m.Range（）
  

尝试在去游乐场

使用实现链表的值包装

另一种方法是包含值，以及-along的实际价值 - 也存储下一个/上一个键。

例如，假设你想要一个地图，如 map [Key] Value ：

  type valueWrapper struct {
 value Value 
下一个*键//下一个键
} 
  

无论何时向地图添加一对，你设置一个 valueWrapper 作为值，你有到链接这到上一（最后）对。要链接，您必须将最后一个包装器的下一个字段设置为指向该新密钥。为了方便实现，建议您存储最后一个密钥（避免搜索）。

当您想以插入顺序迭代元素时，您将开始从第一个（你必须存储这个），它的相关联的 valueWrapper 会告诉你下一个键（按插入顺序）。

示例实现：

 类型Key int //键类型
类型值int //值类型
 
 type valueWrapper struct {
v Value 
 next * Key 
} 
 
类型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：= mm [k]; ！ok&&& m.last！= nil {
 w2：= mm [* m.last] 
 mm [* m.last] = valueWrapper {w2.v，& k} 
} 
w：= valueWrapper {v：v} 
 mm [k] = w 
如果m.first == nil {
 m.first =& k 
} 
 m.last =& k 
} 
 
 func（m * Map）Range（）{
 for k：= m.first; k！= nil {
w：= mm [* k] 
 fmt.Println（wv）
k = w.next 
} 
} 
  

使用它是一样的。尝试在 Go游乐场。

注意：您可能会根据自己的喜好改变一些事情：

• 您可以声明内部地图，如 m map [Key] * valueWrapper 等等在 Set（）中，您可以更改 next 字段，而无需分配新的 valueWrapper 。



• p>您可以选择首先和最后一个字段为类型的值* valueWrapper




• 您可以选择下一个为 valueWrapper

比较

附加切片的方法更容易和更清洁。但是，如果地图变大，那么删除元素可能会变慢，因为我们还必须在切片中找到未排序的键，所以它是 O（n）复杂性

在value-wrapper中使用linked-list的方法可以轻松扩展，以支持快速删除元素，即使地图很大，如果您还添加了 prev 字段到 valueWrapper struct。所以如果你需要删除一个元素，你可以超级快速找到包装器（ O（1）），更新prev和next包装器（指向对方） ，并执行简单的 delete（）操作，它的 O（1）。

请注意，第一个解决方案（带切片）中的删除仍然可以通过使用1个附加映射来加速，该映射将从密钥映射到切片中的密钥索引（映射） [Key] int ），所以删除操作仍然可以在 O（1）中实现，以换取更大的复杂性。

查看相关问题：为什么不要以插入顺序迭代地图？

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

Golang spec states the following:

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.

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?

The solutions I've found are:

• 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 pain debugging.

What do you suggest?

解决方案

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

With a keys slice

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.

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.

Example implementation:

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])
    }
}

Using it:

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

Try it on the Go Playground.

With a value-wrapper implementing a linked-list

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

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

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

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 searching for it).

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

Example implementation:

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:

• 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.

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

• You may choose next to be of type *valueWrapper

Comparison

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.

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

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.

See related question: Why can't Go iterate maps in insertion order?

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