按顺序范围循环映射

Question

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

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.

我在 Whosebug 和谷歌搜索上找到的都是（恕我直言）我不喜欢的解决方法。

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

我找到的解决方案是：

在两个单独的切片中跟踪键和值：听起来像 "Do not use a map"，失去了使用映射的所有优势。
使用映射但跟踪不同切片中的键：这意味着数据重复可能导致数据未对齐并最终可能带来大量错误和痛苦的调试。

你有什么建议？

针对可能的重复标记进行编辑。

我的问题与提供的问题 (this question, but also this one) 略有不同，这两个问题都要求按照键的字典顺序循环遍历地图；相反，我特别询问了：

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 和键，这是两种不同的东西，您需要两种不同的（数据）类型来提供该功能。

带键切片

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

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

将这个新功能（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 上试试。

使用值包装器实现 linked-list

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

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

的地图

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

每当你在地图上添加一对时，你设置一个valueWrapper作为值，你必须link这个到前一个（最后）对。要 link，您必须将最后一个包装器的 next 字段设置为指向这个新密钥。为了轻松实现这一点，建议还存储最后一个密钥（以避免必须搜索它）。

当你想按插入顺序遍历元素时，你从第一个开始（你必须存储它），它的关联 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

比较

带有附加切片的方法更简单、更清晰。但是如果映射变大，从中删除一个元素可能会变慢，因为我们还必须在切片中找到键 "unsorted"，所以它是 O(n) 复杂度。

如果您还将 prev 字段添加到 valueWrapper结构。所以如果你需要删除一个元素，你可以超快地找到包装器（O(1)），更新上一个和下一个包装器（指向彼此），并执行一个简单的 delete() 操作，这是 O(1).

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

参见相关问题：

按顺序范围循环映射

Map in order range loop

loops

dictionary

go

hashmap

for-range

带键切片

使用值包装器实现 linked-list

比较