按顺序循环映射

Question

我正在寻找一种确定Go map的有序范围.

Golang规范说明如下:

未指定地图上的迭代顺序,并且不保证从一次迭代到下一次迭代是相同的.如果在迭代期间删除了尚未到达的映射条目,则不会生成相应的迭代值.如果在迭代期间创建了映射条目,则可以在迭代期间生成该条目,或者可以跳过该条目.对于创建的每个条目以及从一次迭代到下一次迭代,选择可能不同.如果映射为nil,则迭代次数为0.

我在StackOverflow和Google上找到的所有内容都是(imho)我不喜欢的解决方法.

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

我发现的解决方案是:

• 在两个单独的切片中跟踪键和值:听起来像"不要使用地图",失去了使用地图的所有优点.

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

你有什么建议？

---

编辑以响应可能的重复标记.

我的问题和提供的问题(这个问题,但也是这个问题)之间存在细微的差别,这两个问题都要求在按键字典顺序之后循环遍历地图; 相反,我特别问过:

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

这不是词典,因此不同于@gramme.ninja问题:

如何让键按顺序/排序地图,以便键按顺序排列并且值对应？

Answer 1

如果您需要map按顺序键和键,这些是两个不同的东西,您需要2种不同的(数据)类型来提供该功能.

带钥匙片

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

键片只需要包含键(而不是值),因此开销很小.

将此新功能(map + keys 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
}

每当您向地图添加一对时,您将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)),更新prev和下一个包装器(指向彼此),然后执行一个简单的delete()操作O(1).

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

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