详解C++ STL set 容器
详解C++ STL set 容器
本篇随笔简单介绍一下\(C++STL\)中\(set\)容器的使用方法及常见使用技巧。
set容器的概念和性质
\(set\)在英文中的意义是:集合。\(set\)容器也的确“人如其名”,实现了这个集合的功用。
高中数学必修一集合那章(高一以下的小伙伴不用慌,不讲数学只讲概念),关于集合的性质,给出了三个概念:无序性、互异性、确定性。
那么,\(set\)容器的功用就是维护一个集合,其中的元素满足互异性。
我们可以将其理解为一个数组。这个数组的元素是两两不同的。
这个两两不同是指,如果这个\(set\)容器中已经包含了一个元素\(i\),那么无论我们后续再往里假如多少个\(i\),这个\(set\)中还是只有一个元素\(i\),而不会出现一堆\(i\)的情况。这就为我们提供了很多方便。
但是,需要额外说明的是,刚刚说集合是有无序性的,但是\(set\)中的元素是默认排好序(按升序排列)的。(稍微说一句,\(set\)容器自动有序和快速添加、删除的性质是由其内部实现:红黑树(平衡树的一种)。这个东西过于高深我不会,所以不予过多介绍,有兴趣的小伙伴可以自行浏览相关内容。)
set容器的声明
\(set\)容器的声明和大部分\(C++STL\)容器一样,都是:容器名<变量类型> 名称的结构。前提需要开#include
#include<set>
set<int> s;
set<char> s;
set<pair<int,int> > s;
set<node> s;
struct node{...};
set容器的使用
其实,\(C++STL\)容器的使用方式都是差不多的。我们完全可以举一反三地去类比。与\(bitset\)重定义了许多奇形怪状新的函数之外,其他都是大致相同的。所以笔者在此不再做幼稚的介绍,大家都是竞赛狗,应该都能自己看明白。
s.empty();
\(empty()\)函数返回当前集合是否为空,是返回1,否则返回0.
s.size();
\(size()\)函数返回当前集合的元素个数。
s.clear();
\(clear()\)函数清空当前集合。
s.begin(),s.end();
\(begin()\)函数和\(end()\)函数返回集合的首尾迭代器。注意是迭代器。我们可以把迭代器理解为数组的下标。但其实迭代器是一种指针。这里需要注意的是,由于计算机区间“前闭后开”的结构,\(begin()\)函数返回的指针指向的的确是集合的第一个元素。但\(end()\)返回的指针却指向了集合最后一个元素后面一个元素。
s.insert(k);
\(insert(k)\)函数表示向集合中加入元素\(k\)。
s.erase(k);
\(erase(k)\)函数表示删除集合中元素\(k\)。这也反映了\(set\)容器的强大之处,指哪打哪,说删谁就删谁,完全省略了遍历、查找、复制、还原等繁琐操作。更不用像链表那种数据结构那么毒瘤。直接一个函数,用\(O(logn)\)的复杂度解决问题。
s.find(k);
\(find(k)\)函数返回集合中指向元素\(k\)的迭代器。如果不存在这个元素,就返回\(s.end()\),这个性质可以用来判断集合中有没有这个元素。
其他好用的函数
下面介绍一些不是很常用,但是很好用的\(set\)容器的内置函数
s.lower_bound(),s.upper_bound();
熟悉\(algorithm\)库和二分、离散化的小伙伴会对这两个函数比较熟悉。其实这两个函数比较常用。但是对于\(set\)集合来讲就不是很常用。其中\(lower\_bound\)返回集合中第一个大于等于关键字的元素。\(upper\_bound\)返回集合中第一个严格大于关键字的元素。
s.equal_range();
这个东西是真的不常用...可能是我太菜了。
这个东西返回一个\(pair\)(内置二元组),分别表示第一个大于等于关键字的元素,第一个严格大于关键字的元素,也就是把前面的两个函数和在一起。如果有一个元素找不到的话,就会返回\(s.end()\)。
相关文章
- 【c++STL——第十讲】bit set系列 (常用知识点总结)
- C++模板之函数模板实例化和具体化
- C++之构造函数、参数列表、析构函数
- c/c++常见试题
- C++必知必会(1)
- [c++菜鸟]《Accelerate C++》习题解答
- [c++菜鸟]《Accelerate C++》读书笔记
- c++ set与unordered set的区别
- C++同步项目——结构化程序设计之全部任务
- c++ set用法详解
- C++中的野指针问题
- qt C++中指针自动释放内存及程序中的内存操作、管理
- 开源免费的C/C++网络库(c/c++ sockets library)补充
- C++中防止STL中迭代器失效——map/set等关联容器——vector/list/deque等序列容器—如何防止迭代器失效—即erase()的使用
- 《Visual C++ 开发从入门到精通》——1.3 利用Visual C++ 6.0编写C++程序
- OpenCV使用pthread实现多线程加速处理图像(C++)
- 基于C++实现(控制台)应用递推法完成经典型算法的应用【100010505】
- Ubuntu下更改Vim配置文件打造C/C++风格
- 理清gcc、libc、libstdc++的关系(libstdc++是gcc搞的,libc++是llvm搞的,他们都是C++标准库的实现)
- C++基类与派生类的转换
- C++ boost thread学习(一)
- 149、【动态规划】leetcode ——343. 整数拆分(C++版本)
- 堆(stack) 之 c 和 c++模板实现(空类默认成员函数 初谈引用 内联函数)