C++ set

1. 背景

关联式容器

STL 中的部分容器,比如: vector list deque 、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别? 关联式容器 也是用来存储数据的,与序列式容器不同的是,其 里面存储的是 <key, value> 结构的 键值对,在数据检索时比序列式容器效率更高

键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 key value key
表键值, value 表示与 key 对应的信息 。比如:现在要建立一个英汉互译的字典,那该字典中必然
有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应
该单词,在词典中就可以找到与其对应的中文含义。

树形结构的关联式容器

根据应用场景的不同, STL 总共实现了两种不同结构的管理式容器:树型结构与哈希结构。 树型结 构的关联式容器主要有四种:map set multimap multiset 。这四种容器的共同点是:使用平衡搜索树( 即红黑树)作为其底层结果,容器中的元素是一个有序的序列。

2.set的介绍

1. set 是按照一定次序存储元素的容器
2. set 中,元素的 value 也标识它 (value 就是 key ,类型为 T) ,并且每个 value 必须是唯一的。set中的元素不能在容器中修改 ( 元素总是 const) ,但是可以从容器中插入或删除它们。
3. 在内部, set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。
4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢,但它们允许根据顺序对子集进行直接迭代。
5. set 在底层是用二叉搜索树 ( 红黑树 ) 实现的。
注意:
1. map/multimap 不同, map/multimap 中存储的是真正的键值对 <key, value> set 中只放value,但在底层实际存放的是由 <value, value> 构成的键值对。
2. set 中的元素不可以重复 ( 因此可以使用 set 进行去重 )
3. 使用 set 的迭代器遍历 set中的元素,可以得到有序序列,set 中的元素默认按照小于来比较

3. set的使用

1. set的模板参数列表

T: set 中存放元素的类型,实际在底层存储 <value, value> 的键值对。
Compare set 中元素默认按照小于来比较
Alloc set 中元素空间的管理方式,使用 STL 提供的空间配置器管理

2. set的构造

函数声明功能介绍
set (const Compare& comp = Compare(), const Allocator&
= Allocator() );
构造空的set
set (InputIterator first, InputIterator last, const
Compare& comp = Compare(), const Allocator& =
Allocator() );
[first, last)
间中的元素构造
set
set ( const set<Key,Compare,Allocator>& x);
set 的拷贝构造

3. set的迭代器

函数声明功能介绍
iterator begin()返回set中起始位置元素的迭代器
iterator end()返回set中最后一个元素后面的迭代器
const_iterator cbegin() const返回set中起始位置元素的const迭代器
const_iterator cend() const返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin()返回set第一个元素的反向迭代器,即end
reverse_iterator rend()
返回set最后一个元素下一个位置的反向迭代器,即rbegin
const_reverse_iterator
crbegin() const
返回set第一个元素的反向const迭代器,即cend
const_reverse_iterator
crend() const
返回 set 最后一个元素下一个位置的反向 const 代器,即 crbegin

4. set的容量

函数声明功能介绍
bool empty ( ) const检测set是否为空,空返回true,否则返回true
size_type size() const返回set中有效元素的个数

5. set修改操作

函数声明
功能介绍
pair<iterator,bool> insert ( const value_type& x )
set 中插入元素 x ,实际插入的是 <x, x> 构成的 键值对,如果插入成功,返回 < 该元素在 set 中的 位置, true>, 如果插入失败,说明 x set 中已经 存在,返回 <x set 中的位置, false>

void erase ( iterator

position )

删除setposition位置上的元素
size_type erase ( const
key_type& x )
删除 set 中值为 x 的元素,返回删除的元素的个数
void erase ( iterator first,
iterator last )
删除set[first, last)区间中的元素
void swap (
set<Key,Compare,Allocator>& st );
交换set中的元素
void clear ( )
set 中的元素清空
iterator find ( const key_type& x ) const
返回set中值为x的元素的位置
size_type count ( const
key_type& x ) const
返回 set 中值为 x 的元素的个数

4.set的模拟实现

首先我们要使用红黑树进行封装set即可,如下是RBTree.cpp的文件,有关红黑树的详细介绍,可以点击了解C++ 红黑树。

#include <iostream>
#include <vector>
using namespace std;
namespace rbtree
{enum Color{RED,BLACK,};//当我们需要存储键值对,那么T就是pair<K, V>//当我们只存储key值,那么T就是Ktemplate <class T>struct RBTreeNode{//构造函数RBTreeNode(T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}//成员变量RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;//节点数据Color _col;//颜色};//实现迭代器template<class T, class Ref, class Ptr>struct RBTreeIterator{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;Node* _node;//构造函数RBTreeIterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}bool operator==(const Self& s)const{return _node == s._node;}bool operator!=(const Self& s)const{return _node != s._node;}//前置++Self& operator++(){//如果右子树不为空,说明该树未取完,要取右子树的最左结点if (_node->_right){Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}//右子树为空,说明该树已经取完,要回到cur为左孩子的parentelse{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}//后置++Self operator++(int){Self old = new Self(_node);//如果右子树不为空,说明该树未取完,要取右子树的最左结点if (_node->_right){Node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}//右子树为空,说明该树已经取完,要回到cur为左孩子的parentelse{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_right == cur){cur = parent;parent = cur->_parent;}_node = parent;}return old;}//前置--Self& operator--(){Self old = new Self(_node);//如果左子树不为空,说明该树未取完,要取左子树的最右结点if (_node->_left){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}//左子树为空,说明该树已经取完,要回到cur为右孩子的parentelse{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return old;}//后置--Self operator--(int){//如果左子树不为空,说明该树未取完,要取左子树的最右结点if (_node->_left){Node* right = _node->_left;while (right->_right){right = right->_right;}_node = right;}//左子树为空,说明该树已经取完,要回到cur为右孩子的parentelse{Node* cur = _node, * parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}};//前面的K用于传入key的类型,后面的T用于传入红黑树存储的数据类型。keyOfT仿函数,取出T对象中的key,用于比较template<class K, class T, class KeyOfT>class RBTree{typedef typename RBTreeNode<T> Node;typedef typename RBTreeIterator<T, T&, T*> iterator;public://构造函数RBTree():_root(nullptr){} //析构函数~RBTree(){Destroy(_root);_root = nullptr;}iterator begin(){Node* left = _root;while (left->_left){left = left->_left;}return iterator(left);}iterator end(){return iterator(nullptr);}pair<iterator, bool> Insert(const T& data){KeyOfT kot; if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}//找位置插入Node* cur = _root, * parent = _root;while (cur){if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);cur->_parent = parent;if (kot(data) < kot(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}Node* ret = cur;//检查颜色(当连续出现两个红色时需要调整)while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;//如果uncle存在且为红,则将parent和uncle变黑,grandparent变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上检查cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑else{//将grandparent右旋,grandparent变为红,parent变为黑if (cur == parent->_left){RotateR(grandparent);grandparent->_col = RED;parent->_col = BLACK;}//将parent左旋,grandparent右旋,将cur变为黑,grandparent变为红else{RotateL(parent);RotateR(grandparent);grandparent->_col =  RED;cur->_col = BLACK;}//此时最上面的结点为黑,可以直接结束break;}}else{Node* uncle = grandparent->_left;//如果uncle存在且为红,则将parent和uncle变黑,grandparent变红if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//继续向上检查cur = grandparent;parent = cur->_parent;}//uncle不存在或者为黑else{//将grandparent左旋,grandparent变为红,parent变为黑if (cur == parent->_right){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}//将parent右旋,grandparent左旋,将cur变为黑,grandparent变为红else{RotateR(parent);RotateL(grandparent);grandparent->_col = RED;cur->_col = BLACK;}break;}}}//把根节点变为黑_root->_col = BLACK;return make_pair(iterator(ret), true);}bool _IsRBTree(Node* root, int count, int blacknum){if (root == nullptr){if (count != blacknum){return false;}return true;}if (root->_col == BLACK){count++;}return _IsRBTree(root->_left, count, blacknum) &&_IsRBTree(root->_right, count, blacknum);}bool IsRBTree(){if (_root->_col == RED){return false;}int blacknum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){blacknum++;}cur = cur->_left;}return _IsRBTree(_root, 0, blacknum);}void _InOrder(Node* root){KeyOfT kot;if (root == nullptr){return;}_InOrder(root->_left);cout << kot(root->_data) << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}private:void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* grandparent = parent->_parent;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;}else{if (grandparent->_left == parent)grandparent->_left = subR;elsegrandparent->_right = subR;}subR->_parent = grandparent;}//右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* grandparent = parent->_parent;parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;}else{if (grandparent->_left == parent)grandparent->_left = subL;elsegrandparent->_right = subL;}subL->_parent = grandparent;}//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);}//右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = parent->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);}Node* _root;};
};

set.cpp文件如下

#include "RBTree.cpp"
namespace lbk
{template<class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename rbtree::RBTreeIterator<K, K&, K*> iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator, bool> insert(const K& key){return _t.Insert(key);}void InOrder(){_t.InOrder();}private://前面的K用于传入key的类型,后面的T用于传入红黑树存储的数据类型。//红黑树中存储的值不可以改变,应加上constrbtree::RBTree<K, const K, SetKeyOfT> _t;};
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

了解高防 IP

一、高防 IP 的基本概念 高防 IP 是指拥有强大防御能力的 IP 地址。它主要通过将攻击流量引流到高防机房进行清洗和过滤&#xff0c;再将正常的流量回注到源站&#xff0c;从而保障源站服务器的稳定运行。 二、高防 IP 的工作原理 当用户的服务器遭受 DDoS 攻击时&#xff0…

医疗器械上市欧美,需要什么样的网络安全相关申报文件?

医疗器械在欧美上市时&#xff0c;需要提交的网络安全相关申报文件主要包括以下几个方面&#xff0c;这些要求基于欧美地区的法律法规和监管机构的指导文件。 一、美国FDA要求 1. 网络安全管理计划 内容&#xff1a;制造商需要提交一份网络安全管理计划&#xff0c;该计划应包含…

基于OSS前端直传的分片上传以及断点续传

一、大文件分片上传 原型 大文件如果直接上传的话由于nginx的限制会导致响应500报错&#xff0c;或者响应时间过长导致响应超时 并且大文件上传有如下缺点 上传时间长: 对于大文件&#xff0c;直接上传可能需要较长时间&#xff0c;特别是在网络速度较慢或不稳定的情况下。这…

亚信安慧AntDB亮相PostgreSQL中国技术大会,获“数据库最佳应用奖”并分享数据库应用实践

7月12日&#xff0c;第13届PostgreSQL中国技术大会在杭州顺利举办&#xff0c;亚信安慧AntDB数据库荣获“数据库最佳应用奖”。大会上&#xff0c;亚信安慧AntDB数据库同事带来《基于AntDB的CRM系统全域数据库替换实践》和《亚信安慧AntDB数据库运维之路》两场精彩演讲&#xf…

STM32H7的LPUART基础和唤醒示例

STM32H7的LPUART基础知识 硬件框图低功耗的高级特性低功耗串口的时钟以及波特率低功耗串口发送时序低功耗串口支持的唤醒方式 LPUART 的全称是 Low power universal synchronous asynchronous receiver transmitter&#xff0c;中文意思是低功耗通用异步收发器&#xff0c;简称…

PHP多功能投票系统源码小程序

&#x1f389;决策不再难&#xff01;「多功能投票小程序」一键搞定所有选择困难症✨ &#x1f914;选择困难&#xff1f;「多功能投票小程序」来救场&#xff01; 每次聚会、团队讨论还是日常小决策&#xff0c;是不是总有那么几个瞬间让你陷入“选哪个好呢&#xff1f;”的…

数驭未来,景联文科技构建高质大模型数据库

国内应用层面的需求推动AI产业的加速发展。根据IDC数据预测&#xff0c;预计2026年中国人工智能软件及应用市场规模会达到211亿美元。 数据、算法、算力是AI发展的驱动力&#xff0c;其中数据是AI发展的基石&#xff0c;中国的数据规模增长速度预期将领跑全球。 2024年《政府工…

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十五章 Pinctrl和GPIO子系统实验

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…

基于opencv的答题卡识别

文章目录 一、背景需求二、处理步骤图片预处理检测到答题卡轮廓透视变换找每个圆圈的轮廓轮廓排序判断是否答题正确 一、背景需求 传统的手动评分方法耗时且容易出错&#xff0c;自动化评分可以可以显著提高评分过程的速度和准确性、减少人工成本。 答题卡图片处理效果如下&am…

dockerfile部署wordpress

1.将容器直接提交成镜像 [rootlocalhost ~]# docker commit 8ecc7f6b9c12 nginx:1.1 sha256:9a2bb94ba6d8d952527df616febf3fbc8f842b3b9e28b7011b50c743cd7b233b [rootlocalhost ~]# docker images REPOSITORY TAG IMAGE ID CREATED SIZE nginx …

javafx的ListView代入项目的使用

目录 1. 创建一个可观察的列表&#xff0c;用于存储ListView中的数据,这里的User是包装了用户的相关信息。 2.通过本人id获取friendid&#xff0c;及好友的id&#xff0c;然后用集合接送&#xff0c;更方便直观一点。 3.用for遍历集合&#xff0c;逐个添加。 4.渲染器&…

【我的养猪日记】区块链游戏

剧情介绍 年少无知留给了故乡&#xff0c;谦卑有礼送给了远方&#xff0c;有工作的地方没家&#xff0c;有家的地方没工作&#xff0c;他乡留不下灵魂&#xff0c;故乡安不了肉身&#xff0c;从此便有了漂泊。在外漂泊数年的你每天过着&#xff0c;挤不完的公交地铁、交不完的房…

面试场景题系列--(2)短 URL 生成器设计:百亿短 URL 怎样做到无冲突?--xunznux

文章目录 面试场景题&#xff1a;短 URL 生成器设计&#xff1a;百亿短 URL 怎样做到无冲突&#xff1f;1. 需求分析2. 短链接生成算法2.1 自增法2.2 散列函数法2.3 预生成法 3. 部署模型3.1 其他部署方案 4. 设计4.1 重定向响应码4.2 短 URL 预生成文件及预加载4.3 用户自定义…

EtherNet/IP转Profinet协议网关(经典配置案例)

怎么样才能把EtherNet/IP和Profinet网络连接起来呢?这几天有几个朋友问到了这个问题&#xff0c;作者在这里统一为大家详细说明一下。其实有一个设备可以很轻松地解决这个问题&#xff0c;名为JM-PN-EIP&#xff0c;下面是详细介绍。 一&#xff0c;设备主要功能 1、捷米特J…

AnyMP4 Data Recovery for Mac v1.5.8免激活版:高效数据恢复新选择

AnyMP4 Data Recovery for Mac是一款专为Mac用户设计的高效数据恢复软件&#xff0c;凭借其强大的功能和简洁的操作界面&#xff0c;为用户提供了快速、安全的数据恢复体验。 该软件支持恢复多种文件类型&#xff0c;包括照片、视频、音频、文档等&#xff0c;无论是常见的图片…

前端学习7——自学习梳理

​​​​​​jQuery 教程 | 菜鸟教程jQuery 教程 jQuery 是一个 JavaScript 库。 jQuery 极大地简化了 JavaScript 编程。 jQuery 很容易学习。 本章节的每一篇都包含了在线实例 通过本站的在线编辑器&#xff0c;你可以在线运行修改后的代码&#xff0c;并查看运行结果。 实例…

【Python正则表达式】:文本解析与模式匹配

文章目录 1.正则表达式2. re模块3.修饰符3.元字符3-1 字符匹配元字符3-2 重复次数限定元字符3-3 字符集合匹配元字符3-4 分组元字符3-5 边界匹配元字符3-6 字符类别匹配元字符 4.技巧4-1 贪婪与非贪婪 5.案例 1.正则表达式 正则表达式面向什么样的问题&#xff1f; 1、判断一个…

uniapp引入自定义图标

目录 一、选择图标&#xff0c;加入购物车 二、下载到本地 三、导入项目 四、修改字体引用路径 五、开始使用 这里以扩展iconfont图标为例 官网&#xff1a;iconfont-阿里巴巴矢量图标库 一、选择图标&#xff0c;加入购物车 二、下载到本地 直接点击下载素材&#xff0…

2019数字经济公测大赛-VMware逃逸

文章目录 环境搭建漏洞点exp 环境搭建 ubuntu :18.04.01vmware: VMware-Workstation-Full-15.5.0-14665864.x86_64.bundle 这里环境搭不成功。。patch过后就报错&#xff0c;不知道咋搞 发现可能是IDA加载后的patch似乎不行对原来的patch可能有影响&#xff0c;重新下了patch&…

【Kettle实现神通(数据库)MPP增量、全量数据ETL,同步任务Linux运行(通用)】

1、背景介绍 具体Kettle操作步骤不做过多介绍&#xff0c;主要技术方案说明&#xff0c;Kettle8.2版本放在底部链接提取&#xff0c;本次采用Kettle实现源端&#xff1a;神通数据通用库、目标端&#xff1a;神通MPP增量数据同步&#xff0c;并在服务器端运行Job。 2、windows…