【C++】set 容器的使用

上文链接

• 【C++】二叉搜索树

一、序列式容器和关联式容器

STL 中的部分容器如 vector、list、deque 等，这些容器统称为序列式容器，因为它们是逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，依旧是序列式容器。顺序容器中的元素是按它们在容器中的存储位置来顺序保存和访问的。

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

本章节讲解的 set 底层是红黑树，红黑树是一棵平衡二叉搜索树。set 是 key 搜索场景的结构， map 则是 key/value 搜索场景的结构。

---

二、set 容器

1. 参考文档

• set 和 multiset 的使用

---

2. set 介绍

set 的声明如下，T 就是 set 底层关键字的类型。

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

set 底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。一般情况下，我们都不需要传后两个模版参数。

set 底层是用红黑树实现，增删查效率是 $O(\log N)$，迭代器遍历是按照中序遍历的顺序走的，所以是有序的。

---

3. set 构造函数与迭代器

注：下面是 set 类中一些类型的原型。

Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)

(1) 无参默认构造

// empty 无参默认构造 
explicit set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

// 示例
set<int> s1;

---

(2) 迭代器区间构造

// range 迭代器区间构造 
template <class InputIterator>
set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());

// 示例
vector<int> v = { 1, 2, 3 };
set<int> s2(v.begin(), v.end());for (auto e : s2) cout << e << " ";

// 输出
1 2 3

---

(3) 列表构造

// initializer list 列表构造 
set (initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());

// 示例
set<int> s3 = { 1, 2, 3 };

---

(4) 拷贝构造

set (const set& x);

// 示例
set<int> s3 = { 2, 1, 3 };
set<int> s4(s3);for (auto e : s2) cout << e << " ";

// 输出
1 2 3

---

(5) 迭代器

// 迭代器是一个双向迭代器 
iterator -> a bidirectional iterator to const value_type// 正向迭代器 
iterator begin();
iterator end();// 反向迭代器 
reverse_iterator rbegin();
reverse_iterator rend();

#include<iostream>
#include<set>using namespace std;int main()
{set<int> s1 = { 4, 6, 2, 5, 7, 3 };for (auto it = s1.begin(); it != s1.end(); it++){cout << (*it) << " ";}return 0;
}

// 输出
2 3 4 5 6 7 

---

4. set 的增删查

(1) insert 插入数据

• 单个数据插入，如果已经存在则不会插入。一般可以根据 set 不允许插入重复数据的特性对一组数据进行去重。

pair<iterator,bool> insert (const value_type& val);

// 示例
set<int> s1;
s1.insert(5);
s1.insert(8);
s1.insert(7);
s1.insert(5);for (auto e : s1) cout << e << " ";

// 输出
5 7 8

---

• 列表插入，已经在容器中存在的值不会插入。

void insert (initializer_list<value_type> il);

// 示例
set<int> s2 = { 1, 2, 3 };
s2.insert({ 3, 5, 4 });for (auto e : s2) cout << e << " ";

// 输出
1 2 3 4 5

---

• 迭代器区间插入，已经在容器中存在的值不会插入。

template <class InputIterator>
void insert (InputIterator first, InputIterator last);

// 示例
vector<int> v = { 1, 2, 3 };
set<int> s3 = { 3, 8, 4 };s3.insert(v.begin(), v.end());for (auto e : s3) cout << e << " ";

// 输出
1 2 3 4 8

---

(2) erase 删除数据

• 删除一个迭代器位置对应的值，返回被删除元素之后的一个元素对应的迭代器。

iterator erase (const_iterator position);

// 示例
set<int> s1 = { 5, 3, 8, 7, 2 };for (auto e : s1) cout << e << " ";
cout << endl;// 删除最小值
s1.erase(s1.begin());for (auto e : s1) cout << e << " ";

// 输出
2 3 5 7 8
3 5 7 8

---

• 删除 val，val 不存在返回 0，存在返回 1。

size_type erase (const value_type& val);

// 示例
set<int> s2 = { 5, 3, 8, 7, 2 };int x;
cin >> x;int num = s2.erase(x);
if (num)
{cout << "删除成功: ";for (auto e : s2) cout << e << " ";cout << endl;
}
else
{cout << x << "不存在: ";for (auto e : s2) cout << e << " ";cout << endl;
}

// 输入1
7
// 输出1
删除成功: 2 3 5 8// 输入2
1
// 输出2
1不存在: 2 3 5 7 8

---

• 删除一段迭代器区间的值，返回被删除元素之后的一个元素对应的迭代器。

iterator erase (const_iterator first, const_iterator last);

// 示例
set<int> s3 = { 5, 7, 3, 8, 4 };for (auto e : s3) cout << e << " ";
cout << endl;s3.erase(++s3.begin(), --s3.end());for (auto e : s3) cout << e << " ";

// 输出
3 4 5 7 8
3 8

---

(3) find 与 count 查找数据

• **find：查找 val，返回 val 所在的迭代器，没有找到返回 end()。 **

算法库中也有一个 find 函数，但是在 set 中的 find 查找的效率是 $O(\log N)$，而算法库中的效率则是 $O(N)$。

iterator find (const value_type& val);

// 示例
set<int> s1 = { 4, 8, 7, 5, 9 };int x;
cin >> x;auto pos = s1.find(x);
if (pos != s1.end()) pos = s1.erase(pos);
else cout << x << "不存在！" << endl;for (auto e : s1) cout << e << " ";

// 输入1
7
// 输出1
4 5 8 9// 输入2
1
// 输出2
1不存在！
4 5 7 8 9

---

• count：查找 val，返回 val 的个数。

size_type count (const value_type& val) const;

// 示例
set<int> s2 = { 4, 8, 7, 5, 9 };int x;
cin >> x;if (s2.count(x)) cout << "存在" << endl;
else cout << "不存在" << endl;

// 输入1
2
// 输出1
不存在// 输入2
8
// 输出2
存在

---

(4) lower_bound 与 upper_bound

• lower_bound：返回大于等于 val 位置的迭代器。
• upper_bound：返回大于 val 位置的迭代器。

iterator lower_bound (const value_type& val) const;
iterator upper_bound (const value_type& val) const;

// 示例
set<int> s;
for (int i = 1; i < 10; i++)s.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : s) cout << e << " ";
cout << endl;// 实现查找在 [30, 65] 区间内的元素并删除// 返回 >= 30 的第一个元素对应的迭代器
auto itlow = s.lower_bound(30);
// 返回 > 65 的第一个元素对应的迭代器
auto itup = s.upper_bound(65);
// 删除这段区间的值 
s.erase(itlow, itup);for (auto e : s) cout << e << " ";
cout << endl;

// 输出
10 20 70 80 90

---

三、multiset 与 set 的区别

multiset 和 set 的使用基本一样，主要区别点在于 multiset 支持数据的重复。

在 set 中，insert 数据时如果遇到重复的数据则会插入失败，但是在 multiset 中则会继续插入，可以重复。erase 删除数据时如果指定了某一个元素 x，那么在 multiset 中会将所有的 x 全部删除，并返回删除的个数。这也是为什么在 set 中 erase 的返回值不设计成 bool 类型而是返回 0 或者 1 的原因。

下文链接

• 【C++】map 容器的使用