Wsrtjtyk

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.

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.

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