doupa9062
doupa9062
2018-11-16 03:19
浏览 40
已采纳

我想知道如何将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?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • doupeng6890
    doupeng6890 2018-11-16 04:20
    已采纳

    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.

    点赞 评论
  • dongtiaozhou4914
    dongtiaozhou4914 2018-11-16 03:42

    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

    点赞 评论
  • dth42345
    dth42345 2018-11-16 03:51

    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.

    点赞 评论

相关推荐