小编典典

映射订单范围循环

go

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

Golang规范指出以下内容:

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

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

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

我找到的解决方案是:

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

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

你有什么建议?


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

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

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

这不是字典,因此与@gramme.ninja问题不同:

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


阅读 503

收藏
2020-07-02

共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

  • 您可以选择firstlast字段为类型*valueWrapper

  • 您可以选择next类型*valueWrapper

比较方式

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

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

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

2020-07-02