C++STL剖析（六）—— set和multiset的概念和使用

🌟 前言

在 STL 中主要有两种类型的容器：序列式容器 和 关联式容器：

• 序列式容器里面存储的是元素本身，其底层为线性序列的数据结构。比如：vector，list，deque，forward_list 等。
• 关联式容器里面存储的是 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。比如：set，map，unordered_set，unordered_map 等。

但是有一点需要注意，STL 当中的 stack，queue 和 priority_queue 属于容器适配器。

stack 和 queue 默认使用的基础容器是 deque，而 priority_queue 使用的基础容器是 vector。

🍑 树型结构和哈希结构

根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器：树型结构 和 哈希结构：

其中，树型结构容器中的元素是一个有序的序列，而哈希结构容器中的元素是一个无序的序列。

🍑 键值对

键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表 键值，value 表示与 key 对应的信息。

比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL 中关于键值对的定义方式如下：

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}
};

1. set的介绍和使用

set 的介绍：

• set 是按照一定顺序存储元素的容器。
• 在 set 中，元素的 value 也标识它（value 就是 key，类型为 T)，并且每个 value 必须是唯一的。set 中的元素不能在容器中修改（元素总是 const 类型），但是可以从容器中插入或删除它们。
• 在内部，set 中的元素总是按照其内部比较对象（类型为Compare）所指示的特定严格弱排序准则进行排序。
• set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但 set 容器允许根据顺序对子集进行直接迭代。
• set 在底层是用二叉搜索树（红黑树）实现的。

注意：

• 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 <key, value>，set 中只放 value，但在底层实际存放的是由 <value, value>构成的键值对。
• set 中插入元素时，只需要插入 value 即可，不需要构造键值对。
• set 中的元素不可以重复（因此可以使用 set 进行去重）。
• 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
• set 中的元素默认按照小于来比较
• set 中查找某个元素，时间复杂度为：$logN$
• set中的元素不允许修改，因为 set 在底层是用二叉查找树来实现的，若是对二叉查找树当中某个结点的值进行了修改，那么这棵树将不再是二叉查找树。

🍑 set的模板参数列表

如下图所示：

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

🍑 set的构造

这里主要有 3 种方式：

（1）无参构造一个空容器

set<int> s1; // 构造一个int类型的空容器

（2）拷贝构造某类型容器

set<int> s2(s1); // 拷贝构造int类型s1容器的复制品

（3）使用迭代器区间进行初始化构造

vector<int> v1 = { 1,2,3,4,5 };
set<int> s3(v1.begin(), v1.end()); // 构造vector对象某段区间的复制品

🍑 set的使用

set 的成员函数主要分为：迭代器，容量操作，修改操作。

需要注意的是，对于 set 而言，它的普通迭代器和 const 迭代器都不支持修改。

我这里只列举几个常用的，其它的可以看文档学习。

🍅 insert

在 set 中插入元素 val，实际插入的是 <val, val> 构成的键值对

• 如果插入成功，返回 <val在set中的位置, true>
• 如果插入失败，说明 val 在 set 中已经存在，返回 <val在set中的位置, false>

代码示例

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);// 遍历for (auto e : s){cout << e << " ";}
}

可以看到当插入重复元素时，set 的去掉了的，并且还进行了升序的排序

🍅 find

在容器中搜索查找 val 元素，如果找到，则返回一个迭代器，否则返回 set::end 的迭代器。

代码示例

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);auto pos = s.find(5);if (pos != s.end()){cout << "找到了" << endl;}
}

运行结果

🍅 erase

删除 set 中的元素，这里有 3 种删除方式。

（1）从 set 容器中删除单个元素（搭配 find 使用）

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos = s.find(5);if (pos != s.end()){s.erase(pos); // 删除元素5cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}// 遍历for (auto e : s){cout << e << " ";}
}

可以看到元素 5 已经被删除了

（2）从 set 容器中删除单个元素（直接传要删除的元素）

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);s.erase(5);// 遍历for (auto e : s){cout << e << " ";}
}

可以看到 5 已经被删除

那么它和第 1 种的区别是什么呢？

• erase(x)：如果 x 存在就删除；如果不存在，不做任何改变
• erase(pos)：如果 x 存在就删除；如果不存在，此时 pos 位置指向 set::end 的迭代器，那么程序运行就会报错。

其实这种方式本质上可以理解为 erase 去调用了迭代器和 find。

（3）从 set 容器中删除一组元素（传的是迭代器区间 [first,last)）

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos = s.find(5);if (pos != s.end()){s.erase(pos, s.end()); // 从5开始所有的元素全部删除cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}// 遍历for (auto e : s){cout << e << " ";}
}

可以看到从 5 开始所有的元素都已经被删除

🍅 swap

交换 set 容器中的元素

代码示例

void testset()
{set<int> s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);set<int> s2;s2.insert(6);s2.insert(3);s2.insert(8);s2.insert(7);s1.swap(s2);cout << "s1:";// 遍历for (auto e1 : s1){cout << e1 << " ";}cout << "s2:";// 遍历for (auto e2 : s2){cout << e2 << " ";}
}

可以看到 s1 和 s2 的元素已经被交换了

🍅 empty

判断 set 容器是否为空，空返回 true，非空返回 false。

代码示例

void testset()
{set<int> s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);set<int> s2;cout << s1.empty() << endl; // s1容器不为空,输出0cout << s2.empty() << endl; // s2容器为空,输出1
}

运行结果

🍅 size

返回 set 中有效元素的个数

代码示例

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 打印元素个数cout << s.size() << endl;
}

运行结果

🍅 count

返回 set 中值为 x 的元素的个数。

代码示例

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 元素3的个数cout << s.count(3) << endl;// 元素7的个数cout << s.count(10) << endl;
}

可以看到 3 出现了一次，10 不存在

这个接口对于 set 容器其实没有太大用处，因为 set 当中的每个 value 都是唯一的。

🍅 lower_bound

返回一个指向容器中第一个元素的迭代器，该迭代器不被认为在val之前（它是等于或在val之后）

其实就是，返回大于等于 val 位置的迭代器。

代码示例一

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回3位置的迭代器auto lowIt = s.lower_bound(3);cout << *lowIt << endl;// 如果6不存在就返回比6大的位置的迭代器lowIt = s.lower_bound(6);cout << *lowIt << endl;
}

运行结果

代码示例二

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除大于等于4的所有值auto lowIt = s.lower_bound(4);s.erase(lowIt, s.end());// 遍历for (auto e : s){cout << e << " ";}
}

可以看到大于等于 4 的所有值都被删除了

🍅 upper_bound

返回指向容器中第一个元素的迭代器，该元素被认为是 val 之后的元素。

也就是说，不管 val 存在还是不存在，都返回比 val 大的那个值。

代码示例

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回大于3位置的迭代器auto lowIt = s.upper_bound(3);cout << *lowIt << endl;// 如果6不存在就返回比6大的位置的迭代器lowIt = s.upper_bound(6);cout << *lowIt << endl;
}

运行结果

其实 lower_bound 和 upper_bound 可以搭配使用，删除元素中间的一段区间。

void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(6);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除 [3, 7] 这段区间中的所有数auto leftIt = s.lower_bound(3); // 返回3位置的迭代器auto rightIt = s.upper_bound(7); // 返回8位置的迭代器s.erase(leftIt, rightIt);// 遍历for (auto e : s){cout << e << " ";}
}

注意，erase 删除的迭代器区间是左闭右开，也就是说 rightIt 是 8 位置的迭代器，但是 erase 只会删除到 7。

[3, 8) ⇒ [3, 7]

2. multiset的介绍和使用

multiset 的介绍：

• multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。
• 在 multiset 中，元素的 value 也会识别它（因为 multiset 中本身存储的就是 <value, value> 组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T)，multiset 元素的值不能在容器中进行修改（因为元素总是 const 的)，但可以从容器中插入或删除。
• 在内部，multiset 中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。
• multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列。
• multiset 底层结构为二叉搜索树(红黑树)。

注意：

• multiset 中再底层中存储的是 <value, value> 的键值对
• mtltiset 的插入接口中只需要插入即可
• 与 set 的区别是，multiset 中的元素可以重复，set 是中 value 是唯一的
• 使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列
• multiset 中的元素不能修改
• 在 multiset 中找某个元素，时间复杂度为$O(logN)$
• multiset 的作用：可以对元素进行排序

multiset的模板参数列表如下：

🍑 multiset的使用

当我们插入多个元素时，multiset 允许键值冗余，也就说 multiset 容器当中存储的元素是可以重复的。

代码示例

void testmultiset()
{multiset<int> ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(1);ms.insert(3);ms.insert(3);// 遍历for (auto e : ms){cout << e << " ";}
}

可以看到是存在多个相同元素的。

另外，它和 set 容器所提供的成员函数的接口都是基本一致的，所以就不全部列举了，只列举几个稍微有点小差别的函数接口。

🍅 find

在容器中搜索 val 元素，如果找到，则返回中序位置的第一个迭代器，否则返回 multiset::end 的迭代器。

代码示例

void testmultiset()
{multiset<int> ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(5);ms.insert(6);ms.insert(5);ms.insert(3);ms.insert(3);for (auto e : ms){cout << e << " ";}cout << endl;auto pos = ms.find(5); // 多个5的话,返回中序第一个5// 打印pos位置后面的所有元素while (pos != ms.end()){cout << *pos << " ";++pos;}
}

可以看到确实是从第一个 5 开始打印的

🍅 erase

从容器中删除单个元素，直接传要删除的话，erase 是的返回值是 size_type

它会把容器中所有的 val 全部删除，并且返回删除的 val 的个数。

代码示例

void testmultiset()
{multiset<int> ms;ms.insert(4);ms.insert(5);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(5);ms.insert(6);ms.insert(5);ms.insert(3);ms.insert(3);// 删除容器中所有的5,并返回5的个数cout << ms.erase(5) << endl;for (auto e : ms){cout << e << " ";}
}

可以看到元素 5 已经被删除了，并且元素个数是 4。

🍅 count

在容器中搜索等同于 val 的元素，并返回匹配的个数。

代码示例

void testmultiset()
{multiset<int> ms;ms.insert(4);ms.insert(3);ms.insert(2);ms.insert(2);ms.insert(5);ms.insert(7);ms.insert(1);ms.insert(3);ms.insert(6);ms.insert(5);ms.insert(3);// 统计3的个数cout << ms.count(3) << endl;// 遍历for (auto e : ms){cout << e << " ";}
}

运行结果

3. 两个数组的交集

题目描述

解题思路

对于求并集、交集、差集，其实有一种特定的方法，如下图所示：

代码实现

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 去掉num1当中重复的元素并排序set<int> s1;for (auto e1 : nums1){s1.insert(e1);}// 去掉num2当中重复的元素并排序set<int> s2;for (auto e2 : nums2){s2.insert(e2);}vector<int> ret; // 存放交集auto it1 = s1.begin(); // 指向s1的起始位置auto it2 = s2.begin(); // 指向s2的起始位置while (it1 != s1.end() && it2 != s2.end()) // 当s1和s2都没有遍历完时{if (*it1 < *it2) {it1++;}else if (*it2 < *it1){it2++;}else // 当it1和it2指向的元素相等时,就是交集{ret.push_back(*it1); // 把元素尾插到ret中,然后同时向后挪动it1++;it2++;}}return ret; // 返回交集}
};