我想知道如何将set struct实现为地图值[关闭]

I want to use set as map value on golang. So I coded like this:

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
}

And I want to use structure like below code:

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

However my TestSet always has to iterate over the entire item to exist its value. So Add() time complexity O(n).

I want to reduce that time complexity to O(1). (like python set in)

But, I do not know what to do. Should I use another map?

Any good ideas?

Sets are often implemented as maps with no value. A struct{} is effectively empty in Go.

type Empty struct {}

type TestSet struct {
   set map[Test]Empty
}

In order for this to work, Test must be comparable.

Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.

So Test is comparable.

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)
    }
}

You can also use the golang-set library.

Perhaps, something like this:

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() {}

Playground: https://play.golang.org/p/48fVQcvp3sW

You can use a map to emulate a set in golang by making the value type struct{}. Some example code for your Test struct:

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}:{}]
}

This doesn't match your function signatures exactly, as I use values rather than references. This means that I don't have to define a custom Equals functions as you have done. Also, by passing in the argument as a value, the map checks the structs themselves for equality rather than the references.

A thing to note is that this method will only work if the structs are comparable. More info is in this StackOverflow answer which quotes the spec.