loops - 按顺序范围循环映射

Question

我正在寻找一种明确的方法来按顺序遍历 Go map。

Golang spec陈述如下:

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 和谷歌搜索上找到的都是(恕我直言)我不喜欢的解决方法。

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

我找到的解决方案是:

• 在两个单独的 slice 中跟踪键和值:这听起来像“不要使用 map ”，失去了使用 map 的所有优势。

• 使用映射但跟踪不同 slice 中的键:这意味着数据重复可能导致数据未对齐并最终可能带来大量错误和痛苦的调试。

你有什么建议？

---

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

我的问题与提供的问题( this question 和 this one )之间存在细微差别，这两个问题都要求按照键的字典顺序循环遍历 map ；相反，我特别询问了:

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

它不是字典序的，因此不同于 @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?

Answer 1

如果您需要 map 和按顺序排列的键，那是两种不同的东西，您需要两种不同的(数据)类型来提供该功能。

有键 slice

实现此目的的最简单方法是在不同的 slice 中维护键顺序。每当您将新对放入 map 时，首先检查 key 是否已经在其中。如果不是，则将新 key 添加到单独的 slice 中。当你需要按顺序排列元素时，你可以使用 keys slice 。当然，当你删除一对时，你也必须从 slice 中删除它。

键 slice 只需要包含键(而不是值)，因此开销很小。

将这个新功能(map+keys slice)包装成一个新类型并为其提供方法，并隐藏map和slice。这样就不会发生数据错位。

示例实现:

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 上试试.

使用值包装器实现链表

另一种方法是包装值，并且——沿着真实值——也存储下一个/上一个键。

例如，假设您想要一个类似 map[Key]Value 的 map :

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

无论何时向 map 添加一对，都将 valueWrapper 设置为值，并且必须将其链接到前一个(最后一个)对。要链接，您必须将最后一个包装器的next 字段设置为指向这个新键。为了轻松实现这一点，建议还存储最后一个 key (以避免必须搜索它)。

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

示例实现:

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 上试用.

注意:您可以根据自己的喜好改变一些东西:

• 你可以像 m map[Key]*valueWrapper 这样声明内部映射，所以在 Set() 中你可以改变 next 字段，而无需分配新的 valueWrapper。

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

• 您可以选择 next 类型为 *valueWrapper

比较

带有附加 slice 的方法更简单、更清晰。但是，如果映射变大，从中删除元素可能会变慢，因为我们还必须在 slice 中找到“未排序”的键，因此它的复杂度为 O(n)。

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

请注意，第一个解决方案(带 slice )中的删除仍然可以通过使用一个额外的映射来加速，该映射将从键映射到 slice 中键的索引 (map[Key]int), 所以删除操作仍然可以在O(1)中实现，换取更大的复杂度。另一个加快速度的选择可能是将映射中的值更改为包装器，它可以保存 slice 中键的实际值和索引。

参见相关问题:Why can't Go iterate maps in insertion order?