如何将结构体作为映射键实现

小伙伴们对Golang编程感兴趣吗？是否正在学习相关知识点？如果是，那么本文《如何将结构体作为映射键实现》，就很适合你，本篇文章讲解的知识点主要包括。在之后的文章中也会多多分享相关知识点，希望对大家的知识积累有所帮助！

我想在 golang 上使用 set 作为映射值。所以我这样编码：

import (
   "fmt"
   "reflect"
)

type testset struct {
   items []test
}

func (ts *testset) add(t *test) {
   ok := true
   for _, item := range ts.items {
      if item.equal(t) {
         ok = false
         break
      }
   }
   if ok {
      ts.items = append(ts.items, *t)
   }
}

type test struct {
   phonenumber string
   name        string
   friends     []string // i add this field! (**edit**)
}

func (t *test) equal(t2 *test) bool {
   if t.phonenumber != t2.phonenumber || t.name != t2.name {
      return false
   }
   if !reflect.deepequal(t.friends, t2.friends) {
      return false
   }
   return true
}

我想使用如下代码所示的结构：

val := make(map[int]*TestSet)
val[1] = &TestSet{}
val[1].Add(&Test{phoneNumber: "8210", name: "minji", friends: []string{"myself"})

但是我的 testset 始终必须迭代整个项目才能存在其值。所以 add() 时间复杂度为 o(n)。

我想将时间复杂度降低到 o(1)。 （比如python set in）

但是，我不知道该怎么办。我应该使用另一张地图吗？

有什么好的想法吗？

解决方案

Sets are often implemented as maps with no value。 struct{} 在 go 中实际上是空的。

type empty struct {}

type testset struct {
   set map[test]empty
}

为了使其正常工作，test 必须为 comparable。

如果结构体的所有字段都可比较，则结构体值也可比较。如果两个结构体值对应的非空白字段相等，则它们相等。

因此 test 具有可比性。

package main;

import (
    "fmt"
)

type empty struct {}

type testset struct {
    set map[test]empty
}

func (ts *testset) add(t test) bool {
    if _, present := ts.set[t]; present {
        return false
    } else {
        ts.set[t] = empty{}
        return true
    }
}

type test struct {
    phonenumber string
    name        string
}

func main() {
    set := testset{ set: make(map[test]empty) }
    test1 := test{ phonenumber: "555-555-5555", name: "yarrow hock" }
    test2 := test{ phonenumber: "555-555-5555", name: "yarrow hock" }
    test3 := test{ phonenumber: "123-555-5555", name: "yarrow hock" }
    if set.add( test1 ) {
        fmt.println("added 1")
    }
    if set.add( test2 ) {
        fmt.println("added 2")
    }
    if set.add( test3 ) {
        fmt.println("added 3")
    }

    for test := range set.set {
        fmt.println(test.phonenumber)
    }
}

您还可以使用 the golang-set library。

您可以通过将值类型设置为 struct{}，使用映射来模拟 golang 中的集合。 test 结构的一些示例代码：

package main

import "fmt"

type TestSet map[Test]struct{}

func (ts TestSet) Add(t Test) {
    ts[t] = struct{}{}
}

type Test struct {
    phoneNumber string
    name string
}

func main() {
    ts := TestSet{}
    t1 := Test{"a", "b"}
    t2 := Test{"a", "b"}
    ts.Add(t1)
    ts.Add(t2)

    fmt.Println(ts) // Output: map[{a b}:{}]
}

这与您的函数签名不完全匹配，因为我使用值而不是引用。这意味着我不必像您所做的那样定义自定义 equals 函数。此外，通过将参数作为值传递，映射会检查结构本身是否相等，而不是引用。

需要注意的是，此方法仅在结构具有可比性时才有效。更多信息请参见引用该规范的 StackOverflow answer。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《如何将结构体作为映射键实现》文章吧，也可关注golang学习网公众号了解相关技术文章。