我想知道如何将 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 main

type 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 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像您那样定义自定义函数。此外，通过将参数作为值传递，映射检查结构本身的相等性而不是引用。

需要注意的是，此方法仅在结构具有可比性时才有效。