Myujth

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