4

我正在寻找一种确定的方式来确定Go map有序范围。

Golang 规范声明如下：

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

我在 StackOverflow 和谷歌上找到的所有东西都是我不喜欢的（恕我直言）解决方法。

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

我找到的解决方案是：

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

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

你有什么建议？

编辑以响应可能的重复标志。

我的问题和提供的问题（这个问题，还有这个问题）之间存在细微差别，这两个问题都要求按照键字典顺序循环遍历地图；相反，我特别问：

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

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

我怎样才能让键按顺序排列/对地图进行排序，以便键按顺序排列并且值对应？

4

1 回答 1

10

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

带键切片

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

键切片只需包含键（而不是值），因此开销很小。

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

示例实现：

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
}

每当您将一对添加到地图时，您都将 a 设置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 中的链表方法以支持快速元素删除。所以如果你需要移除一个元素，你可以超快的找到包装器O(1)（delete()O(1)

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

请参阅相关问题：为什么不能按插入顺序迭代地图？

于 2016-09-12T12:34:30.157 回答