【C++】set和multiset（关联式容器、键值对，set和multiset的基本特性、主要用途及常用操作）
目录
00.引言
关联式容器
键值对
树形结构的关联式容器
01.set容器
基本特性
主要用途
常用操作
02.multiset容器
基本特征
主要用途
常用操作
00.引言
关联式容器
在之前的文章中，我们介绍过STL中的部分容器，比如：vector、list、deque等等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。
关联式容器也是用于存储数据的，但与序列式容器不同的是，其里面存储的是<key,value>结构的键值对，在数据检索时比序列式容器效率更高。
键值对
键值对是一种数据结构，用于存储和表示关联数据。在这个结构中，每个数据项由两个部分组成：
-
键（Key）：
- 键是唯一的标识符，用于访问和引用对应的值。每个键在同一个集合中必须是唯一的，以确保能够正确检索到对应的值。
- 键通常是字符串、整数或其他类型的数据。
-
值（Value）：
- 值是与键相关联的数据项，包含实际的信息或数据。
- 值可以是任意类型的数据，甚至可以是复杂的数据结构（如数组、对象等）。
SGI-STL 中，键值对通常由 std::pair 来表示，其中 first 代表键，second 代表值。定义如下：
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
};
树形结构的关联式容器
STL总共实现了两种不同的关联式容器：树形结构与哈希结构。树形结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（即红黑树）作为其底层结果，因此插入、删除和查找操作的时间复杂度都是 O(log n），且容器中的元素是一个有序的序列。下面依次介绍每一个容器。
01.set容器
set容器中，存储的是键（key），而没有单独的值。这是因为 set 是一种集合数据结构，它用于存储唯一的元素，并且这些元素可以被看作是唯一的“键”。set 中的每一个元素都是集合中的唯一成员，因此不需要显式的键值对结构。
基本特性
1.唯一性：set 中的每个元素都是唯一的，不允许重复。
2.有序性：set 中的元素默认时按照升序排列的（基于 < 运算符），但可以通过自定义比较函数来改变排列规则
3.动态大小：set 的大小是动态的，可以随时插入和删除元素。
主要用途
1.去重存储：当需要存储一组不重复的元素时，set 是理想的选择，它可以自动去除重复的元素，不需要手动检查。
#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {1, 2, 3, 2, 4, 3, 5};
for (const auto& elem : mySet) {
std::cout << elem << " ";
}
return 0;
}
2.自动排序：set中的元素会默认按照升序进行排序存储，因此可以实现自动排序的效果。
3.高效查找：使用平衡二叉树作为底层数据结构，使得其查找、插入、删除的时间复杂度都为O(log n)，因此在需要频繁查找的情况下，set 也是一种高效的选择。
常用操作
1.创建
set<int> s; // 创建一个空的 set
set<int> s1 = {1, 2, 3, 4}; // 初始化一个 set2.插入元素
s.insert(5); // 插入一个元素
s.insert({6, 7, 8}); // 插入多个元素3.删除元素：
s.erase(5); // 删除一个元素
s.erase(s.begin()); // 删除迭代器指向的元素
s.erase(s.begin(), s.end()); // 删除某个范围内的元素4.查找元素：
auto it = s.find(5); // 查找元素，返回迭代器
if (it != s.end()) {
cout << "Element found: " << *it << endl;
} else {
cout << "Element not found" << endl;
}5.检查元素是否存在
if (s.count(5) > 0) {
cout << "Element exists" << endl;
} else {
cout << "Element does not exist" << endl;
}6.遍历
for (const auto& elem : s) {
cout << elem << " ";
}
cout << endl;
// 使用迭代器遍历
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " ";
}
cout << endl;7.获取大小
cout << "Size of set: " << s.size() << endl;02.multiset容器
multiset 也是C++标准库的一个关联容器，类似于 set，但它允许存储重复的元素，其内部通常使用红黑树实现，因此插入、删除、查找操作的时间复杂度都是O(log n)。
基本特征
1.允许重复元素：set 中的元素是唯一的，而 multiset 允许相同的元素多次出现。
2.自动排序：multiset 默认按照升序存储元素（基于 < 运算符）。与 set 一样，排序是通过红黑树等平衡二叉搜索树实现的。
3.高效查找：使用平衡二叉树作为底层数据结构，使得其查找、插入、删除的时间复杂度都为O(log n)
4.查找与计数：提供了 count 函数，可以用来返回某个元素出现的次数。支持使用 find、lower_bound 和 upper_bound 等函数查找特定元素的位置。
主要用途
1.统计频率：当你有一组数据并且希望记录每个元素的出现次数时，multiset 是很好的选择。通过 count 函数可以方便地获取某个元素的频次。
2.自动排序与重复数据：如果需要在处理数据时保持元素的有序性并且允许重复，那么 multiset 就比 set 更适合。
3.频繁的插入和删除
常用操作
1.插入元素
multiset 可以像 set 一样插入元素，但允许相同的元素多次插入：
#include <iostream>
#include <set>
int main() {
std::multiset<int> ms;
ms.insert(5);
ms.insert(3);
ms.insert(5); // 插入重复元素
ms.insert(1);
// 输出 multiset 中的元素
for (const auto& elem : ms) {
std::cout << elem << " ";
}
return 0;
}
2.计数元素
count 函数可以返回某个元素在 multiset 中出现的次数：
int count_5 = ms.count(5); // 结果为 2，表示 5 出现了两次
3.删除元素
erase 函数可以删除指定的元素，但会删除所有相同的元素。如果只想删除一个相同的元素，可以使用 erase(iterator)通过迭代器索引删除的方式：
ms.erase(5); // 删除 multiset 中所有的 54.查找元素
find 函数用于查找某个元素在 multiset 中的位置，返回的是一个迭代器：
auto it = ms.find(3);
if (it != ms.end()) {
std::cout << "找到了元素 3" << std::endl;
}
5.范围操作
multiset 支持范围操作，允许查找元素的范围。例如，equal_range 可以返回一个范围，表示某个元素在 multiset 中的所有位置：
auto range = ms.equal_range(5);
for (auto it = range.first; it != range.second; ++it) {
std::cout << *it << " "; // 输出所有等于 5 的元素
}
以上就是set和multiset的相关知识总结，欢迎在评论区留言，觉得这篇博客对你有帮助的，可以点赞收藏关注支持一波~😉