我想在 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）但是，我不知道该怎么办。我应该使用另一张地图吗？有什么好主意吗？
3 回答
慕森王
TA贡献1777条经验 获得超3个赞
集合通常作为没有值的映射来实现。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 库。
白猪掌柜的
TA贡献1893条经验 获得超10个赞
也许，像这样：
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
扬帆大鱼
TA贡献1799条经验 获得超9个赞
您可以通过将值类型设为 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像您那样定义自定义函数。此外，通过将参数作为值传递，映射检查结构本身的相等性而不是引用。
需要注意的是，此方法仅在结构具有可比性时才有效。
- 3 回答
- 0 关注
- 65 浏览
添加回答
举报
0/150
提交
取消