【C++】—— set 与 multiset

【C++】—— map 与 set

1 序列式容器和关联式容器
2 set 系列的使用
- 2.1 set 和 multiset 参考文档
- 2.2 set 类的介绍
- 2.3 set 的迭代器和构造
- 2.4 set的增删查
- - 2.4.1 insert
  - 2.4.2 find 与 erase
  - 2.4.3 count
- 2.5 lower_bound 与 upper_bound
- 2.6 multiset 与 set 的差异
- - 2.6.1 不再去重
  - 2.6.2 find 返回中序的第一个
  - 2.6.3 erase 删除所有的 x
  - 2.6.4 count 个数

1 序列式容器和关联式容器

前面我们已经接触过 STL 中的部分容器如：string、vector、list、deque、array等，这些容器统称为序列式容器，因为他们是逻辑结构为线性序列的数据结构（物理结构不一定为线性），两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，它依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有 map / set 系列和 unordered_map / unordered_set 系列

本文讲解的 $ma p$ 和 $se t$ 底层是红黑树，红黑树是一颗平衡二叉搜索树。 $se t$ 是 $k ey$ 搜索场景的结构， $ma p$ 是 $k ey$ / $v a l u e$ 搜索场景的结构

2 set 系列的使用

2.1 set 和 multiset 参考文档

https://legacy.cplusplus.com/reference/set/

2.2 set 类的介绍

set 的声明如下：

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

• $se t$ 的声明如上，T 就是 $se t$ 底层关键字的类型

• $se t$ 默认要求 T 支持小于比较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数

• $se t$ 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。

• ⼀般情况下，我们都不需要传后两个模版参数。

• $se t$ 底层是用红黑树实现，增删查效率是 O(logN)，迭代器遍历是⾛的搜索树的中序，所以是有序的。

• 前面部分我们已经学习了 $v ec t or$ / $l i s t$ 等容器的使用，STL 容器接口设计，高度相似，所以这里我们就不再⼀个接口⼀个接口的介绍，而是直接带着大家看文档，挑比较重要的接口进行介绍。

这里库中的模板参数用的是 T，个人认为这里设计的不够好，既然是搜索，那用 Key 更好，我们可以将其当成是 Key，虽然库中没用这个名字。

2.3 set 的迭代器和构造

$se t$ 的迭代器是一个双向迭代器：

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

$se t$ 主要构造方式如下：

无参构造

explicit set(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

迭代器区间构造

template <class InputIterator>
set(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

拷贝构造

set(const set& x);
set(const set& x, const allocator_type& alloc);

列表构造

set(initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

2.4 set的增删查

首先要注意的是： $se t$ 是不支持改的，因为 $se t$ 属于关联式容器，对齐进行数据修改会破坏它的存储结构

2.4.1 insert

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator, bool> insert(const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

这里 $v a l u e$ _ $t y p e$ 就是 T，即 Key；此外 $k ey$ _ $t y p e$ 也是 T。这里这么设计是为了和后面的 $ma p$ 保持一致

返回值 pair<iterator, bool> 这里还不需要用到它，暂不解释，在后面的 $ma p$ 部分会详细介绍。

举个栗子：

int main()
{// 去重+升序排序set<int> s;// 去重+降序排序（给⼀个⼤于的仿函数）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);set<int>::iterator it = s.begin();while (it != s.end()){// error C3892: “it”: 不能给常量赋值// *it = 1;cout << *it << " ";++it;}cout << endl;。return 0;
}

运行结果：

可以看到， $se t$ 是不允许两个相同的值进行插入的，即 $se t$ 有去重功能。并且 $se t$ 是不允许修改的，*it = 1 进行修改会报错。
默认 $se t$ 走的是升序，如果想走降序，可以传递一个大于的仿函数。迭代器的底层走的是一个中序遍历

$se t$ 支持列表插入

int main()
{set<int> s;s.insert({ 2,8,3,9,2 });for (auto e : s){cout << e << " ";} cout << endl;return 0;
}

$se t$ 除了支持整型，其他任意类型都是可以的（如果该类型不支持比较，需自己传递仿函数），我们以 $s t r in g$ 为例

int main()
{// void insert(initializer_list<value_type> il);// 构造出临时对象再拷贝构造，优化成直接构造set<string> strset = { "sort", "insert", "add" };// 遍历string⽐较ascll码⼤⼩顺序遍历的for (auto& e : strset){cout << e << " ";} return 0;
}

2.4.2 find 与 erase

const_iterator find(const value_type& val) const;
iterator       find(const value_type& val);

$f in d$ 返回的是对应位置的迭代器，如果没找到就返回 end()

迭代器删除

iterator  erase(const_iterator position);

Key删除

size_type erase(const value_type& val);

$s i ze$ _ $t y p e$ 是一个无符号整型，即 $u n s i g n e d$ $in t$ ，返回的是删除元素的个数。
如果删除成功，表示删除了一个值，返回 1；删除失败，表示没有删除值，返回 0

为什么这里不用 $b oo l$ 呢？这里是为了兼容 $m u lt i se t$ 。
$m u lt i se t$ 中允许相同数插入的，可能 $er a se$ 多个相同的值，这时就不能用 $b oo l$ 了

迭代器区间删除

iterator  erase(const_iterator first, const_iterator last);

栗子：

int main()
{set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";} cout << endl;// 删除最⼩值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);if (num == 0){cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";}cout << endl;// 直接查找在利⽤迭代器删除xcin >> x;auto pos = s.find(x);if (pos != s.end()){s.erase(pos);}else{cout << x << "不存在！" << endl;}for (auto e : s){cout << e << " ";} cout << endl;return 0;
}

$se t$ 进行删除同样会导致迭代器失效

i )

此时删除的是叶子结点 1，删除后迭代器中的指针为野指针，迭代器失效。

ii )

删除 6 节点。它要与 5 或 7 节点进行交换，删除进行删除。虽然此时迭代器中的指针并不是野指针，但它原来的意义已经改变了，我们也认为是迭代器失效。

而且从我们的角度，我们不知道这个节点是直接删除还是替代法删除。

$p s$ ：对二叉搜索树的删除有不理解的小伙伴可移步至：【C++】—— 二叉搜索树

2.4.3 count

$co u n t$ 的功能是返回 $v a l u e$ _ $t y p e$ 在容器中的个数

size_type count (const value_type& val) const;

$co u n t$ 是给 $m u lt i s t$ 设计的，因为对 $se t$ 而言 $co u n t$ 要么返回 1 要么返回 0，并没有什么意义。但对于 $m u lt i se t$ 就不一样， $m u lt i se t$ 是允许多个相同值存在的

我们可以用 $co u n t$ 来判断一个 $Key$ 在不在，在的话返回的是 1，不在返回 0。
而且用 $co u n t$ 来判断往往比 $f in d$ 更方便，因为 $f in d$ 返回的是迭代器，迭代器 != end() 才是找到了

int main()
{set<int> s = { 4,2,7,2,8,5,9 };// 利⽤count间接实现快速查找int x;cin >> x;if (s.count(x)){cout << x << "在！" << endl;} else{cout << x << "不存在！" << endl;} return 0;
}

2.5 lower_bound 与 upper_bound

// 返回⼤于等于val位置的迭代器
iterator lower_bound(const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound(const value_type& val) const;

$l o w er$ _ $b o u n d$ 与 $u pp er$ _ $b o u n d$ 是为了方便查找一段区间
我们曾经说过，在 STL 里面，只要是迭代器区间必须是左闭右开，这时就可以用到 $l o w er$ _ $b o u n d$ 与 $u pp er$ _ $b o u n d$

举个栗子：


int main()
{std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";}cout << endl; 实现查找到的[itlow,itup)包含[30, 60]区间 返回 >= 30（这里即返回30）//auto itlow = myset.lower_bound(30); 返回 > 60（这里即返回70）//auto itup = myset.upper_bound(60);// 实现查找到的[itlow,itup)包含[25, 55]区间//对应别人来说，并不知道容器里面是否有 25 和 55，但是查找这段区间的方法与查找30-60的方法一样的// 返回 >= 25（这里即返回30）auto itlow = myset.lower_bound(25);// 返回 > 55（这里即返回60）auto itup = myset.upper_bound(55);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";}cout << endl;return 0;
}

2.6 multiset 与 set 的差异

$m u lt i se t$ 和 $se t$ 的使用基本完全类似，主要区别点在于 $m u lt i se t$ 支持值冗余，那么 $in ser t$ / $f in d$ / $co u n t$ / $er a se$ 都围绕着支持值冗余有所差异，具体参看下面的样例代码理解。

2.6.1 不再去重

相比 $se t$ 不同的是， $m u lt i se t$ 是排序，但是不去重

int main()
{multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;return 0;
}

2.6.2 find 返回中序的第一个

相比 $se t$ 不同的是， $x$ 可能会存在多个， $f in d$ 查找中序遍历的第一个

int main()
{multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;} cout << endl;return 0;
}

简单讲一下他是怎么找到中序的第一个的。
查找依然是 O(logN) 算法的查找，并不是通过中序的方式遍历一遍，这样的话二叉搜索树就失去其意义。
中序的查找规则是：左子树 -> 根 -> 右子树。
假设要找的值是 5 ：如果找到了一个 5 ，就再往其左子树找，因为中序第一个 5 一定是在左树；直到找到了某一个 5 ，并且其左子树没有 5 ，表面当前 5 就是中序的第一个 5。

为什么这里要找中序的第一个呢？因为找中序的第一个 x，就可以用迭代器不断++，就可以找到所有的 x

2.6.3 erase 删除所有的 x

相比 $se t$ 不同的是， $er a se$ 给值时会删除所有的 x

int main()
{multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };for (auto e : s){cout << e << " ";} cout << endl;int x;cin >> x;s.erase(x);for (auto e : s){cout << e << " ";} cout << endl;return 0;
}

2.6.4 count 个数

相比 $se t$ 不同的是， $co u n t$ 会返回 $x$ 的实际个数

int main()
{multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };for (auto e : s){cout << e << " ";}cout << endl;int x;cin >> x;cout << s.count(x) << endl;return 0;
}