Go的数据结构与实现【Set】

介绍

Set是值的集合，可以迭代这些值、添加新值、删除值并清除集合、获取集合大小并检查集合是否包含值，集合中的一个值只存储一次，不能重复。
本文代码地址为go-store

简单实现

这是集合的一个简单实现，还不是并发安全的，为了简单和容易理解而没有引入锁资源。
set.go

package set

type T int

type Set struct {
   sets map[T]bool
}

// Add adds a new element to the Set. Returns true if t is not in set.
func (s *Set) Add(t T) bool {
   if s.sets == nil {
      s.sets = make(map[T]bool)
   }

   _, ok := s.sets[t]
   if !ok {
      s.sets[t] = true
   }

   return !ok
}

// Clear removes all elements from the Set
func (s *Set) Clear() {
   s.sets = make(map[T]bool)
}

// Delete removes the Item from the Set and returns true if t is in set
func (s *Set) Delete(t T) bool {
   _, ok := s.sets[t]
   if ok {
      delete(s.sets, t)
   }

   return ok
}

// Contains returns true if the Set contains the t
func (s *Set) Contains(t T) bool {
   _, ok := s.sets[t]
   return ok
}

// All returns the all items stored
func (s *Set) All() []T {
   var ret []T
   for t := range s.sets {
      ret = append(ret, t)
   }

   return ret
}

// Size returns the size of the set
func (s *Set) Size() int {
   return len(s.sets)
}

单元测试

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

set_test.go

package set

import "testing"

var (
   t1 T = 1
   t2 T = 2
   t3 T = 3
)

func InitSet() *Set {
   set := &Set{}
   set.Add(t1)
   set.Add(t2)
   return set
}

func TestSet_Add(t *testing.T) {
   set := InitSet()
   ok := set.Add(t1)
   if ok {
      t.Errorf("There is already %d in set!", t1)
   }

   ok = set.Add(t3)
   if !ok {
      t.Errorf("There should be %d in set!", t3)
   }
}

func TestSet_Clear(t *testing.T) {
   set := InitSet()
   set.Clear()
   if size := set.Size(); size != 0 {
      t.Errorf("wrong count, expected 0 and got %d", size)
   }
}

func TestSet_Delete(t *testing.T) {
   set := InitSet()
   ok := set.Delete(t1)
   if !ok {
      t.Errorf("There should be %d in set!", t1)
   }

   ok = set.Delete(t3)
   if ok {
      t.Errorf("There should not be %d in set!", t3)
   }
}

func TestSet_Contains(t *testing.T) {
   set := InitSet()
   ok := set.Contains(t1)
   if !ok {
      t.Errorf("There should be %d in set!", t1)
   }

   ok = set.Contains(t2)
   if !ok {
      t.Errorf("There should be %d in set!", t2)
   }

   ok = set.Contains(t3)
   if ok {
      t.Errorf("There should not be %d in set!", t3)
   }
}

func TestSet_All(t *testing.T) {
   set := InitSet()
   items := set.All()
   if len(items) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", len(items))
   }

   if items[0] != t1 && items[1] != t2 {
      t.Errorf("There should be %d and %d in set!", t1, t2)
   }
}

func TestSet_Size(t *testing.T) {
   set := InitSet()
   size := set.Size()
   if size != 2 {
      t.Errorf("wrong count, expected 2 and got %d", size)
   }

   set.Add(t3)
   size = set.Size()
   if size != 3 {
      t.Errorf("wrong count, expected 3 and got %d", size)
   }

   set.Delete(t3)
   size = set.Size()
   if size != 2 {
      t.Errorf("wrong count, expected 2 and got %d", size)
   }

   set.Delete(t2)
   size = set.Size()
   if size != 1 {
      t.Errorf("wrong count, expected 1 and got %d", size)
   }

   set.Delete(t1)
   size = set.Size()
   if size != 0 {
      t.Errorf("wrong count, expected 0 and got %d", size)
   }
}

并发安全

第一个版本不是并发安全的，因为一个goroutine可能将一个值添加到集合中，而另一个goroutine正在获取集合列表或大小。
以下代码在数据结构中添加了一个sync.RWMutex，使其并发安全，实现非常简单，只需要在每个方法中添加Lock()和defer UnLock()。上面的测试运行良好，无需对此实现进行任何修改。

package set

import (
   "sync"
)

type T int

type Set struct {
   sync.RWMutex
   sets map[T]bool
}

// Add adds a new element to the Set. Returns true if t is not in set.
func (s *Set) Add(t T) bool {
   s.Lock()
   defer s.Unlock()

   if s.sets == nil {
      s.sets = make(map[T]bool)
   }

   _, ok := s.sets[t]
   if !ok {
      s.sets[t] = true
   }

   return !ok
}

// Clear removes all elements from the Set
func (s *Set) Clear() {
   s.Lock()
   defer s.Unlock()

   s.sets = make(map[T]bool)
}

// Delete removes the Item from the Set and returns true if t is in set
func (s *Set) Delete(t T) bool {
   s.Lock()
   defer s.Unlock()

   _, ok := s.sets[t]
   if ok {
      delete(s.sets, t)
   }

   return ok
}

// Contains returns true if the Set contains the t
func (s *Set) Contains(t T) bool {
   s.RLock()
   defer s.RUnlock()

   _, ok := s.sets[t]
   return ok
}

// All returns the all items stored
func (s *Set) All() []T {
   s.RLock()
   defer s.RUnlock()

   var ret []T
   for t := range s.sets {
      ret = append(ret, t)
   }

   return ret
}

// Size returns the size of the set
func (s *Set) Size() int {
   s.RLock()
   defer s.RUnlock()

   return len(s.sets)
}

// Union returns a new set with elements from both
// the given sets
func (s *Set) Union(t *Set) *Set {
   ret := &Set{}

   s.RLock()
   for i := range s.sets {
      ret.sets[i] = true
   }
   s.RUnlock()

   t.RLock()
   for i := range t.sets {
      if _, ok := ret.sets[i]; !ok {
         ret.sets[i] = true
      }
   }
   t.RUnlock()

   return ret
}

添加更多集合操作

Set还可以通过实现一些常见的数学集合操作得到更多改进：并集、交集、差集和子集。

并集

在这里插入图片描述

// Union returns a new set with elements from both
// the given sets
func (s *Set) Union(t *Set) *Set {
   ret := &Set{}

   s.RLock()
   for i := range s.sets {
      ret.sets[i] = true
   }
   s.RUnlock()

   t.RLock()
   for i := range t.sets {
      if _, ok := ret.sets[i]; !ok {
         ret.sets[i] = true
      }
   }
   t.RUnlock()

   return ret
}

单元测试：

func TestSet_Union(t *testing.T) {
   set1 := InitSet(t1, t2)
   set2 := InitSet(t1, t3)

   set3 := set1.Union(set2)
   if len(set3.All()) != 3 {
      t.Errorf("wrong count, expected 3 and got %d", set3.Size())
   }
   //don't edit original sets
   if len(set1.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set1.Size())
   }
   if len(set2.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set2.Size())
   }
}

交集

在这里插入图片描述

func (s *Set) Intersection(t *Set) *Set {
   ret := &Set{}
   ret.sets = make(map[T]bool)

   s.RLock()
   t.RLock()
   defer s.RUnlock()
   defer t.RUnlock()

   for i := range t.sets {
      if _, ok := s.sets[i]; ok {
         ret.sets[i] = true
      }
   }

   return ret
}

单元测试：

func TestSet_Intersection(t *testing.T) {
   set1 := InitSet(t1, t2)
   set2 := InitSet(t1, t3)

   set3 := set1.Intersection(set2)
   if len(set3.All()) != 1 {
      t.Errorf("wrong count, expected 1 and got %d", set3.Size())
   }
   //don't edit original sets
   if len(set1.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set1.Size())
   }
   if len(set2.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set2.Size())
   }
}

差集

在这里插入图片描述

func (s *Set) Difference(t *Set) *Set {
   ret := &Set{}
   ret.sets = make(map[T]bool)

   s.RLock()
   t.RLock()
   defer s.RUnlock()
   defer t.RUnlock()

   for i := range t.sets {
      if _, ok := s.sets[i]; !ok {
         ret.sets[i] = true
      }
   }

   return ret
}

单元测试：

func TestSet_Difference(t *testing.T) {
   set1 := InitSet(t1, t2)
   set2 := InitSet(t1, t3)

   set3 := set1.Difference(set2)
   if len(set3.All()) != 1 {
      t.Errorf("wrong count, expected 1 and got %d", set3.Size())
   }
   //don't edit original sets
   if len(set1.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set1.Size())
   }
   if len(set2.All()) != 2 {
      t.Errorf("wrong count, expected 2 and got %d", set2.Size())
   }
}

子集

在这里插入图片描述

func (s *Set) Subset(t *Set) bool {
   s.RLock()
   t.RLock()
   defer s.RUnlock()
   defer t.RUnlock()

   for i := range s.sets {
      if _, ok := t.sets[i]; !ok {
         return false
      }
   }

   return true
}

单元测试：

func TestSet_Subset(t *testing.T) {
   set1 := InitSet(t1, t2)
   set2 := InitSet(t1, t3)

   ret := set2.Subset(set1)
   if ret {
      t.Errorf("(t1, t2) is not the subset of (t1, t3), but got %t", ret)
   }

   set3 := InitSet(t1)
   ret = set3.Subset(set1)
   if !ret {
      t.Errorf("(t1) is the subset of (t1, t3), but got %t", ret)
   }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/497498.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【tensorflow框架神经网络实现鸢尾花分类】

【tensorflow框架神经网络实现鸢尾花分类】

文章目录 1、数据获取2、数据集构建3、模型的训练验证可视化训练过程 1、数据获取 从sklearn中获取鸢尾花数据，并合并处理 from sklearn.datasets import load_iris import pandas as pdx_data load_iris().data y_data load_iris().targetx_data pd.DataFrame…
阅读更多...
kubernetes K8s的监控系统Prometheus升级Grafana,来一个酷炫的Node监控界面(二)

kubernetes K8s的监控系统Prometheus升级Grafana,来一个酷炫的Node监控界面(二)

上一篇文章《kubernetes K8s的监控系统Prometheus安装使用(一)》中使用的监控界面总感觉监控的节点数据太少，不能快算精准的判断出数据节点运行的状况。 今天我找一款非常酷炫的多维度数据监控界面，能够非常有把握的了解到各节点的数据，以及运…
阅读更多...
快速上手Spring Cloud 七：事件驱动架构与Spring Cloud

快速上手Spring Cloud 七：事件驱动架构与Spring Cloud

快速上手Spring Cloud 一：Spring Cloud 简介 快速上手Spring Cloud 二：核心组件解析 快速上手Spring Cloud 三：API网关深入探索与实战应用 快速上手Spring Cloud 四：微服务治理与安全 快速上手Spring Cloud 五：Spring …
阅读更多...
AOP切入点表达式基本格式

AOP切入点表达式基本格式

版权声明 本文原创作者：谷哥的小弟作者博客地址：http://blog.csdn.net/lfdfhl 官方地址 https://docs.spring.io/spring-framework/reference/core/aop/ataspectj/pointcuts.html AOP切入点表达式基本格式如下： execution(modifiers-patte…
阅读更多...
竞赛 python+opencv+深度学习实现二维码识别

竞赛 python+opencv+深度学习实现二维码识别

0 前言 🔥 优质竞赛项目系列，今天要分享的是 🚩 pythonopencv深度学习实现二维码识别 🥇学长这里给一个题目综合评分(每项满分5分) 难度系数：3分工作量：3分创新点：3分 该项目较为新颖&…
阅读更多...
ES6 学习（三）-- es特性

ES6 学习（三）-- es特性

文章目录 1. Symbol1.1 使用Symbol 作为对象属性名1.2 使用Symbol 作为常量 2. Iterator 迭代器2.1 for...of循环2.2 原生默认具备Interator 接口的对象2.3 给对象添加Iterator 迭代器2.4 ... 解构赋值 3. Set 结构3.1 初识 Set3.2 Set 实例属性和方法3.3 遍历3.4 相关面试题 4…
阅读更多...
RabbitMQ3.x之四_RabbitMQ角色说明及创建用户与授权

RabbitMQ3.x之四_RabbitMQ角色说明及创建用户与授权

RabbitMQ3.x之四_角色说明及创建用户与授权 文章目录 RabbitMQ3.x之四_角色说明及创建用户与授权1. 访问和授权1. Tags说明2. 命令行示例 2. 管理界面新建用户及访问授权1. 管理界面新建用户2. 管理界面中的授权说明3. guest用户不能远程登录提示 3. 创建用户1. 基本命令2. 实际…
阅读更多...
新网站收录时间是多久，新建网站多久被百度收录

新网站收录时间是多久，新建网站多久被百度收录

对于新建的网站而言，被搜索引擎收录是非常重要的一步，它标志着网站的正式上线和对外开放。然而，新网站被搜索引擎收录需要一定的时间，而且时间长短受多种因素影响。本文将探讨新网站收录需要多长时间，以及新建网站多久…
阅读更多...
微信小程序更换头像的功能

微信小程序更换头像的功能

微信小程序开发&#xff0c;个人中心中更换头像的更能使用频率很高&#xff0c;这里记录下实现方式&#xff1a; <view class"setting-list avatar-container"><text>头像</text><view class"avatar"><button hover-class"…
阅读更多...
华为云使用指南02

华为云使用指南02

5.​​使用GitLab进行团队及项目管理​​ GitLab旨在帮助团队进行项目开发协作&#xff0c;为软件开发和运营生命周期提供了一个完整的DevOps方案。GitLab功能包括&#xff1a;项目源码的管理、计划、创建、验证、集成、发布、配置、监视和保护应用程序等。该镜像基于CentOS操…
阅读更多...
ZK友好代数哈希函数安全倡议

ZK友好代数哈希函数安全倡议

1. 引言 前序博客&#xff1a; ZKP中的哈希函数如何选择ZK-friendly 哈希函数&#xff1f;snark/stark-friendly hash函数Anemoi Permutation和Jive Compression模式&#xff1a;高效的ZK友好的哈希函数Tip5&#xff1a;针对Recursive STARK的哈希函数 随着Incrementally Ve…
阅读更多...
STM32 字符数组结束符 “\0”

STM32 字符数组结束符 “\0”

STM32 字符数组结束符 “\0” 使用字符数组使用printf&#xff0c;string参考 使用字符数组 使用STM32的串口发送数据&#xff0c;核心代码如下&#xff1a; char str[] "hello world!\n\r";while(1) {HAL_UART_Transmit(&huart2, str, sizeof (str), 10);HAL…
阅读更多...
构建一个基础的大型语言模型（LLM）应用程序

构建一个基础的大型语言模型（LLM）应用程序

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
Radio Silence for mac 好用的防火墙软件

Radio Silence for mac 好用的防火墙软件

Radio Silence for Mac是一款功能强大的网络防火墙软件&#xff0c;专为Mac用户设计&#xff0c;旨在保护用户的隐私和网络安全。它具备实时网络监视和控制功能&#xff0c;可以精确显示每个网络连接的状态&#xff0c;让用户轻松掌握网络活动情况。 软件下载&#xff1a;Radio…
阅读更多...
图扑数字孪生智慧城市，综合治理一屏统览

图扑数字孪生智慧城市，综合治理一屏统览

现代城市作为一个复杂系统&#xff0c;牵一发而动全身&#xff0c;城市化进程中产生新的矛盾和社会问题都会影响整个城市系统的正常运转。智慧城市是应对这些问题的策略之一。领导曾在中央城市工作会议上指出&#xff0c;城市工作要树立系统思维&#xff0c;从构成城市诸多要素…
阅读更多...
探索数据库mysql--------------mysql主从复制和读写分离

探索数据库mysql--------------mysql主从复制和读写分离

目录 前言 为什么要主从复制&#xff1f; 主从复制谁复制谁&#xff1f; 数据放在什么地方&#xff1f; 一、mysql支持的复制类型 1.1STATEMENT&#xff1a;基于语句的复制 1.2ROW&#xff1a;基于行的复制 1.3MIXED&#xff1a;混合类型的复制 二、主从复制的工作过程 三个重…
阅读更多...
HarmonyOS 应用开发之UIAbility组件与UI的数据同步

HarmonyOS 应用开发之UIAbility组件与UI的数据同步

基于当前的应用模型&#xff0c;可以通过以下几种方式来实现UIAbility组件与UI之间的数据同步。 使用EventHub进行数据通信&#xff1a;在基类Context中提供了EventHub对象&#xff0c;可以通过发布订阅方式来实现事件的传递。在事件传递前&#xff0c;订阅者需要先进行订阅&a…
阅读更多...
I/O模型的一些理解

I/O模型的一些理解

I/O模型的一些理解 一些基本的概念同步阻塞、同步非阻塞、异步阻塞、异步非阻塞总结概念 I/O模型一些例子 从源头解释从TCP发送数据的流程说起阻塞I/O | 非阻塞I/OI/O多路复用信号驱动I/O异步I/O再谈IO模型里面的同步异步 参考连接 参考链接 参考链接 一些基本的概念 阻塞(b…
阅读更多...
Postman传对象失败解决

Postman传对象失败解决

文章目录 情景复现解决方案总结 情景复现 postman中调用 debug发现pId传入失败 分析解释&#xff1a; 实体类中存在pId、uid和num字段 controller层将GoodsCar作为请求体传入 解决方案 当时觉得很奇怪&#xff0c;因为uid和num可以被接收&#xff0c;而pId和num的数据类型相…
阅读更多...
pyecharts操作三

pyecharts操作三

pyecharts操作三 pyecharts 是一个用于生成Echarts图表的Python库。Echarts是百度开源的一个数据可视化JS库&#xff0c;可以生成一些非常酷炫的图表。 环境安装 pip install pyecharts 检查版本 import pyecharts print(pyecharts.version) 2.0.3 GL关系图 import rando…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站