映射订单范围循环

Question

我正在寻找一种确定范围的方法Go map。

Golang规范指出以下内容：

未指定地图的迭代顺序，并且不能保证每次迭代之间都相同。如果在迭代过程中删除尚未到达的映射条目，则不会生成相应的迭代值。如果映射条目是在迭代过程中创建的，则该条目可能在迭代过程中产生或可以被跳过。对于创建的每个条目以及从一个迭代到下一个迭代，选择可能有所不同。如果映射为nil，则迭代次数为0。

我在StackOverflow和Googling上找到的所有方法都是（ imho ）我不喜欢的解决方法。

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

我找到的解决方案是：

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

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

你有什么建议？

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

我的问题和所提供的问题之间有细微的差别，两个问题都要求按照字典顺序来遍历地图。相反，我特别问过：

有没有一种可靠的方法可以遍历地图并按 插入顺序检索项目 ？

这不是字典，因此与@gramme.ninja问题不同：

我如何才能使键按顺序排列/对地图进行排序，以使键按顺序排列并且值对应？

Answer 1

如果您需要map依次按和键，那么这是2种不同的东西，则需要2种不同的（数据）类型来提供该功能。

带钥匙片

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

键片仅包含键（而不包含值），因此开销很小。

将此新功能（map + keys slice）包装为新类型，并为其提供方法，然后隐藏地图和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：

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

每当将一对添加到地图时，都将设置valueWrapper为值，并且必须将其 链接 到上一个（最后一个）对。要 链接
，您必须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

比较方式

带有额外切片的方法更容易，更清洁。但是，如果地图变大，则从元素中删除元素可能会变得很慢，因为我们还必须在切片中找到“未排序”的键，因此它很O(n)复杂。

即使您将映射添加prev到valueWrapper结构中，即使映射很大，也可以轻松扩展value-wrapper中具有link-
list的方法以支持快速元素删除。因此，如果您需要删除一个元素，则可以超快速找到wrapper（O(1)），更新prev和next包装器（指向彼此），并执行一个简单的delete()操作，即O(1)。

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