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

Question

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?

Answer 1

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.