golang数据结构_Go数据结构：集-白红宇

golang数据结构_Go数据结构：集

阅读量：2505 次

发布时间：2019-05-11

本文共 13784 字，大约阅读时间需要 45 分钟。

golang数据结构

A Set is a collection of values. You can iterate over those values, add new values, remove values and clear the set, get the set size, and check if the set contains an item. A value in the set might only be stored once, duplicates are not possible.

集合是值的集合。您可以遍历这些值，添加新值，删除值并清除集合，获取集合大小并检查集合中是否包含项目。集合中的值只能存储一次，不能重复。

第一次实施 (First implementation)

Here is a simple implementation of the set, not yet concurrency safe, without locking resources for the benefit of simplicity and understanding. I’ll add locking later in the article.

这是集合的一种简单实现，但尚未并发安全，没有为了简单和理解而锁定资源。我将在文章后面添加锁定。

Notice the second line, which allows us to use the Set for any type we want, by .

注意第二行，它通过，使我们可以将Set用于所需的任何类型。

set.go

set.go

// Package set creates a ItemSet data structure for the Item typepackage setimport "github.com/cheekybits/genny/generic"// Item the type of the Settype Item generic.Type// ItemSet the set of Itemstype ItemSet struct {    items map[Item]bool}// Add adds a new element to the Set. Returns a pointer to the Set.func (s *ItemSet) Add(t Item) *ItemSet {    if s.items == nil {        s.items = make(map[Item]bool)    }    _, ok := s.items[t]    if !ok {        s.items[t] = true    }    return s}// Clear removes all elements from the Setfunc (s *ItemSet) Clear() {    s.items = make(map[Item]bool)}// Delete removes the Item from the Set and returns Has(Item)func (s *ItemSet) Delete(item Item) bool {    _, ok := s.items[item]    if ok {        delete(s.items, item)    }    return ok}// Has returns true if the Set contains the Itemfunc (s *ItemSet) Has(item Item) bool {    _, ok := s.items[item]    return ok}// Items returns the Item(s) storedfunc (s *ItemSet) Items() []Item {    items := []Item{}    for i := range s.items {        items = append(items, i)    }    return items}// Size returns the size of the setfunc (s *ItemSet) Size() int {    return len(s.items)}

测试实施 (Testing the implementation)

Here is the test suite for the above code, which explains how to use it in detail, and the expected results for any operation:

这是上述代码的测试套件，它解释了如何详细使用它以及任何操作的预期结果：

set_test.go

set_test.go

package setimport (    "fmt"    "testing")func populateSet(count int, start int) *ItemSet {    set := ItemSet{}    for i := start; i < (start + count); i++ {        set.Add(fmt.Sprintf("item%d", i))    }    return &set}func TestAdd(t *testing.T) {    set := populateSet(3, 0)    if size := set.Size(); size != 3 {        t.Errorf("wrong count, expected 3 and got %d", size)    }    set.Add("item1") //should not add it, already there    if size := set.Size(); size != 3 {        t.Errorf("wrong count, expected 3 and got %d", size)    }    set.Add("item4") //should not add it, already there    if size := set.Size(); size != 4 {        t.Errorf("wrong count, expected 4 and got %d", size)    }}func TestClear(t *testing.T) {    set := populateSet(3, 0)    set.Clear()    if size := set.Size(); size != 0 {        t.Errorf("wrong count, expected 0 and got %d", size)    }}func TestDelete(t *testing.T) {    set := populateSet(3, 0)    set.Delete("item2")    if size := set.Size(); size != 2 {        t.Errorf("wrong count, expected 2 and got %d", size)    }}func TestHas(t *testing.T) {    set := populateSet(3, 0)    has := set.Has("item2")    if !has {        t.Errorf("expected item2 to be there")    }    set.Delete("item2")    has = set.Has("item2")    if has {        t.Errorf("expected item2 to be removed")    }    set.Delete("item1")    has = set.Has("item1")    if has {        t.Errorf("expected item1 to be removed")    }}func TestItems(t *testing.T) {    set := populateSet(3, 0)    items := set.Items()    if len(items) != 3 {        t.Errorf("wrong count, expected 3 and got %d", len(items))    }    set = populateSet(520, 0)    items = set.Items()    if len(items) != 520 {        t.Errorf("wrong count, expected 520 and got %d", len(items))    }}func TestSize(t *testing.T) {    set := populateSet(3, 0)    items := set.Items()    if len(items) != set.Size() {        t.Errorf("wrong count, expected %d and got %d", set.Size(), len(items))    }    set = populateSet(0, 0)    items = set.Items()    if len(items) != set.Size() {        t.Errorf("wrong count, expected %d and got %d", set.Size(), len(items))    }    set = populateSet(10000, 0)    items = set.Items()    if len(items) != set.Size() {        t.Errorf("wrong count, expected %d and got %d", set.Size(), len(items))    }}

并发安全版本 (Concurrency safe version)

The first version is not concurrency safe because a routine might add an item to the set while another routine is getting the list of items, or the size.

第一个版本不是并发安全的，因为一个例程可能将一个项目添加到集合中，而另一个例程正在获取项目列表或大小。

The following code adds a sync.RWMutex to the data structure, making it concurrency safe. The above tests are running fine without any modification to this implementation as well.

以下代码将sync.RWMutex添加到数据结构中，使其并发安全。上面的测试运行良好，无需对此实现进行任何修改。

The implementation is very simple and we’re good with adding a lock and unlocking with a defer. Since we’ll generate the code for specific implementations which might be more than one in the same file, we need to either add the lock inside the struct, or add the generic type into the lock name (Itemlock). I chose the first option:

实现非常简单，我们擅长添加锁和使用defer解锁。由于我们将为特定的实现生成代码，而该实现可能在同一文件中不止一个，因此我们需要在结构内部添加锁，或在锁名( Itemlock )中添加泛型类型。我选择了第一个选项：

set.go

set.go

// Package set creates a ItemSet data structure for the Item typepackage setimport (    "sync"    "github.com/cheekybits/genny/generic")// Item the type of the Settype Item generic.Type// ItemSet the set of Itemstype ItemSet struct {    items map[Item]bool    lock  sync.RWMutex}// Add adds a new element to the Set. Returns a pointer to the Set.func (s *ItemSet) Add(t Item) *ItemSet {    s.lock.Lock()    defer s.lock.Unlock()    if s.items == nil {        s.items = make(map[Item]bool)    }    _, ok := s.items[t]    if !ok {        s.items[t] = true    }    return s}// Clear removes all elements from the Setfunc (s *ItemSet) Clear() {    s.lock.Lock()    defer s.lock.Unlock()    s.items = make(map[Item]bool)}// Delete removes the Item from the Set and returns Has(Item)func (s *ItemSet) Delete(item Item) bool {    s.lock.Lock()    defer s.lock.Unlock()    _, ok := s.items[item]    if ok {        delete(s.items, item)    }    return ok}// Has returns true if the Set contains the Itemfunc (s *ItemSet) Has(item Item) bool {	s.lock.RLock()	defer s.lock.RUnlock()    _, ok := s.items[item]    return ok}// Items returns the Item(s) storedfunc (s *ItemSet) Items() []Item {	s.lock.RLock()	defer s.lock.RUnlock()    items := []Item{}    for i := range s.items {        items = append(items, i)    }    return items}// Size returns the size of the setfunc (s *ItemSet) Size() int {	s.lock.RLock()	defer s.lock.RUnlock()    return len(s.items)}

创建具体的集合数据结构 (Creating a concrete set data structure)

Install if you don’t have it already.

如果尚未安装，请安装它。

Run

跑

//generate a `StringSet` set of `string`sgenny -in set.go -out set-string.go gen "Iten=string Value=int"//generate a `IntSet` set of `int`sgenny -in set.go -out set-int.go gen "Item=int"

Here’s an example of the set-string.go generated file:

这是set-string.go生成的文件的示例：

// This file was automatically generated by genny.// Any changes will be lost if this file is regenerated.// see https://github.com/cheekybits/genny// Package set creates a StringSet data structure for the string typepackage setimport "sync"// StringSet the set of Stringstype StringSet struct {    items map[string]bool    lock  sync.RWMutex}// Add adds a new element to the Set. Returns a pointer to the Set.func (s *StringSet) Add(t string) *StringSet {    s.lock.Lock()    defer s.lock.Unlock()    if s.items == nil {        s.items = make(map[string]bool)    }    _, ok := s.items[t]    if !ok {        s.items[t] = true    }    return s}// Clear removes all elements from the Setfunc (s *StringSet) Clear() {    s.lock.Lock()    defer s.lock.Unlock()    s.items = make(map[string]bool)}// Delete removes the string from the Set and returns Has(string)func (s *StringSet) Delete(item string) bool {    s.lock.Lock()    defer s.lock.Unlock()    _, ok := s.items[item]    if ok {        delete(s.items, item)    }    return ok}// Has returns true if the Set contains the stringfunc (s *StringSet) Has(item string) bool {	s.lock.RLock()	defer s.lock.RUnlock()    _, ok := s.items[item]    return ok}// Strings returns the string(s) storedfunc (s *StringSet) Strings() []string {	s.lock.RLock()	defer s.lock.RUnlock()    items := []string{}    for i := range s.items {        items = append(items, i)    }    return items}// Size returns the size of the setfunc (s *StringSet) Size() int {	s.lock.RLock()	defer s.lock.RUnlock()    return len(s.items)}// Package set creates a IntSet data structure for the int type// IntSet the set of Intstype IntSet struct {    items map[int]bool    lock  sync.RWMutex}// Add adds a new element to the Set. Returns a pointer to the Set.func (s *IntSet) Add(t int) *IntSet {    s.lock.Lock()    defer s.lock.Unlock()    if s.items == nil {        s.items = make(map[int]bool)    }    _, ok := s.items[t]    if !ok {        s.items[t] = true    }    return s}// Clear removes all elements from the Setfunc (s *IntSet) Clear() {    s.lock.Lock()    defer s.lock.Unlock()    s.items = make(map[int]bool)}// Delete removes the int from the Set and returns Has(int)func (s *IntSet) Delete(item int) bool {    s.lock.Lock()    defer s.lock.Unlock()    _, ok := s.items[item]    if ok {        delete(s.items, item)    }    return ok}// Has returns true if the Set contains the intfunc (s *IntSet) Has(item int) bool {	s.lock.RLock()	defer s.lock.RUnlock()    _, ok := s.items[item]    return ok}// Ints returns the int(s) storedfunc (s *IntSet) Ints() []int {	s.lock.RLock()	defer s.lock.RUnlock()    items := []int{}    for i := range s.items {        items = append(items, i)    }    return items}// Size returns the size of the setfunc (s *IntSet) Size() int {	s.lock.RLock()	defer s.lock.RUnlock()    return len(s.items)}

添加更多设置操作 (Add more Set operations)

Our Set is an interesting data structure at this point, but it can be improved a lot more by implementing some common mathematical set operations: union, intersection, difference and subset.

我们的设置是在这一点上一个有趣的数据结构，但它可以有很多更通过实施一些常见的数学集合运算进行改进： union ， intersection ， difference和subset 。

联盟 (Union)

// Union returns a new set with elements from both// the given setsfunc (s *ItemSet) Union(s2 *ItemSet) *ItemSet {	s3 := ItemSet{}	s3.items = make(map[Item]bool)	s.lock.RLock()	for i := range s.items {		s3.items[i] = true	}	s.lock.RUnlock()	s2.lock.RLock()	for i := range s2.items {		_, ok := s3.items[i]		if !ok {			s3.items[i] = true		}	}	s2.lock.RUnlock()	return &s3}

测试 (Test)

func TestUnion(t *testing.T) {    set1 := populateSet(3, 0)    set2 := populateSet(2, 3)    set3 := set1.Union(set2)    if len(set3.Items()) != 5 {        t.Errorf("wrong count, expected 5 and got %d", set3.Size())    }    //don't edit original sets    if len(set1.Items()) != 3 {        t.Errorf("wrong count, expected 3 and got %d", set1.Size())    }    if len(set2.Items()) != 2 {        t.Errorf("wrong count, expected 2 and got %d", set2.Size())    }}

路口 (Intersection)

// Intersection returns a new set with elements that exist in// both setsfunc (s *ItemSet) Intersection(s2 *ItemSet) *ItemSet {	s3 := ItemSet{}	s3.items = make(map[Item]bool)	s.lock.RLock()	s2.lock.RLock()	defer s.lock.RUnlock()	defer s2.lock.RUnlock()	for i := range s2.items {		_, ok := s.items[i]		if ok {			s3.items[i] = true		}	}	return &s3}

测试 (Test)

func TestIntersection(t *testing.T) {    set1 := populateSet(3, 0)    set2 := populateSet(2, 0)    set3 := set1.Intersection(set2)    if len(set3.Items()) != 2 {        t.Errorf("wrong count, expected 2 and got %d", set3.Size())    }    //don't edit original sets    if len(set1.Items()) != 3 {        t.Errorf("wrong count, expected 3 and got %d", set1.Size())    }    if len(set2.Items()) != 2 {        t.Errorf("wrong count, expected 2 and got %d", set2.Size())    }}

区别 (Difference)

// Difference returns a new set with all the elements that// exist in the first set and don't exist in the second setfunc (s *ItemSet) Difference(s2 *ItemSet) *ItemSet {	s3 := ItemSet{}	s3.items = make(map[Item]bool)	s.lock.RLock()	s2.lock.RLock()	defer s.lock.RUnlock()	defer s2.lock.RUnlock()	for i := range s.items {		_, ok := s2.items[i]		if !ok {			s3.items[i] = true		}	}	return &s3}

测试 (Test)

func TestDifference(t *testing.T) {    set1 := populateSet(3, 0)    set2 := populateSet(2, 0)    set3 := set1.Difference(set2)    if len(set3.Items()) != 1 {        t.Errorf("wrong count, expected 2 and got %d", set3.Size())    }    //don't edit original sets    if len(set1.Items()) != 3 {        t.Errorf("wrong count, expected 3 and got %d", set1.Size())    }    if len(set2.Items()) != 2 {        t.Errorf("wrong count, expected 2 and got %d", set2.Size())    }}

子集 (Subset)

// Subset returns true if s is a subset of s2func (s *ItemSet) Subset(s2 *ItemSet) bool {	s.lock.RLock()	s2.lock.RLock()	defer s.lock.RUnlock()	defer s2.lock.RUnlock()	for i := range s.items {		_, ok := s2.items[i]		if !ok {			return false		}	}	return true}

测试 (Test)

func TestSubset(t *testing.T) {	set1 := populateSet(3, 0)	set2 := populateSet(2, 0)	if set1.Subset(set2) {		t.Errorf("expected false and got true")	}	//don't edit original sets	if len(set1.Items()) != 3 {		t.Errorf("wrong count, expected 3 and got %d", set1.Size())	}	if len(set2.Items()) != 2 {		t.Errorf("wrong count, expected 2 and got %d", set2.Size())	}	//try real subsets	set1 = populateSet(2, 0)	if !set1.Subset(set2) {		t.Errorf("expected true and got false")	}	set1 = populateSet(1, 0)	if !set1.Subset(set2) {		t.Errorf("expected true and got false")	}}