我想知道如何将 set struct 实现为映射值

Question

我想在 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)。（像蟒蛇集 in）

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

有什么好主意吗？

Answer 1

集合通常作为没有值的映射来实现。Astruct{}在 Go 中实际上是空的。type Empty struct {}type TestSet struct {   set map[Test]Empty}为了使其起作用，Test必须具有可比性。如果结构值的所有字段都具有可比性，则结构值是可比的。如果两个结构值对应的非空白字段相等，则它们相等。所以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)    }}您还可以使用golang-set 库。

Answer 2

也许，像这样：package maintype Test struct {    phoneNumber string    name        string}type TestSet struct {    Items map[string]bool}func (ts *TestSet) Add(t *Test) {    ts.Items[t.phoneNumber+"\x80"+t.name] = true}func main() {}游乐场：https://play.golang.org/p/48fVQcvp3sW

Answer 3

您可以通过将值类型设为 map 来模拟 golang 中的集合struct{}。您的结构的一些示例代码Test：package mainimport "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像您那样定义自定义函数。此外，通过将参数作为值传递，映射检查结构本身的相等性而不是引用。需要注意的是，此方法仅在结构具有可比性时才有效。