C++ STL 有序关联容器详解
在 C++ 中，如果需要快速查找一组数据中的唯一元素，或者统计某个键出现的次数，手写数组或列表往往代码冗长且效率低下。STL（标准模板库）中的关联容器——set、multiset、map 和 multimap，正是为解决这类问题而生的。
1. set 容器
常用接口说明
1.1 构造函数
最常用的构造方式有三种，分别支持迭代器区间、拷贝以及初始化列表：
void test01() {
vector<int> v({ 4,5,2,9,6,8,3,1,7,7,7,7 });
set<int> st1(v.begin(), v.end()); // 迭代器区间构造
set<int> st2(st1); // 拷贝构造
set<int> st3({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造
}
1.2 迭代器
begin() 和 end() 是最常用的迭代器接口，常用于遍历或作为区间构造的参数。由于 set 底层是平衡二叉搜索树（红黑树），begin() 返回的迭代器指向最小的元素。
void test02() {
set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 });
auto begin = st.begin(); // 返回第一个节点的迭代器
auto end = st.end(); // 返回最后一个节点后一个位置的迭代器
cout << *begin << endl;
cout << *(--end) << endl; // --end 找到最后一个有效节点
}
为了方便后续观察容器状态，我们可以封装一个简单的打印函数。
1.3 插入 insert
set 底层基于红黑树，插入数据遵循二叉搜索树规则，但不允许插入相同的值。insert 接口的返回值比较特殊，是一个 pair 对象：
first: 迭代器。如果插入成功，指向新节点；如果已存在，指向原节点。second: 布尔值。插入成功为true，失败为false。
void test03() {
set<int> st;
pair<set<int>::iterator, bool> p1, p2;
p1 = st.insert(5);
st.insert(3);
p2 = st.insert(5); // 插入已存在的值
cout << *(p1.first) << endl;
if (p2.second) cout << "原来不存在" << endl;
else cout << "原来存在" << endl;
}
1.4 删除 erase
删除操作同样返回后继迭代器，被删除节点的迭代器会失效。
void test04() {
set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 });
Print_container(st);
set<int>::iterator it = st.erase(st.begin()); // 删除第一个节点
cout << *it << endl;
}
1.5 查找 find
找到则返回节点迭代器，未找到返回 set::end()。
void test05() {
set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 });
auto it = st.find(5);
if(it != st.end()) {
cout << *it << endl;
}
}
1.6 统计 count
由于 set 不允许重复值，count 要么返回 1，要么返回 0。因此它也可以用来判断元素是否存在。
void test06() {
set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 });
cout << st.count(5) << endl; // 输出 1
cout << st.count(50) << endl; // 输出 0
}
1.7 区间查找 lower_bound / upper_bound
这两个接口非常强大，可以根据不存在的值来确定区间范围。
// 删除 [30, 50) 区间内的值
void test07() {
set<int> st1({ 20,10,50,30,10,90,70,40,80 });
Print_container(st1);
auto begin1 = st1.find(30);
auto end1 = st1.find(50);
while (begin1 != end1) {
begin1 = st1.erase(begin1);
}
Print_container(st1); // 结果：10 20 50 70 80 90
// 使用 lower_bound/upper_bound 删除 [30, 50]
set<int> st2({ 20,10,50,30,10,90,70,40,80 });
Print_container(st2);
auto begin2 = st2.lower_bound(30);
auto end2 = st2.upper_bound(50);
while (begin2 != end2) {
begin2 = st2.erase(begin2);
}
Print_container(st2); // 结果：10 20 70 80 90
}
2. multiset 容器
multiset 与 set 的主要区别在于支持插入相同的值。因此部分接口行为有所差异：
- 查找：
find返回中序遍历序列中的第一个匹配项。 - 删除：调用
erase(val)会一次性删除所有值为val的节点。 - 统计：
count可能返回大于 1 的值。
常用接口说明
2.1 插入
void test1() {
multiset<int> multi;
multi.insert(3);
multi.insert(2);
multi.insert(3);
multi.insert(3);
Print_container(multi);
}
2.2 查找
当存在多个相同值时，find 仅返回第一个。若需遍历所有相同值，可结合 equal_range 使用。
2.3 删除
与 set 类似，但针对值的删除会移除所有匹配项。
2.4 统计
void test4() {
multiset<int> multi;
multi.insert(3);
multi.insert(3);
multi.insert(3);
multi.insert(3);
Print_container(multi);
cout << multi.count(3); // 输出 4
}
2.5 equal_range
返回包含所有相等元素的迭代器区间。
3. map 容器
map 的常用接口逻辑与 set 基本一致，只是操作对象从单一键值变成了键值对（Key-Value）。查找、删除、统计及区间查找均基于键值完成。
常用接口说明
3.1 构造函数
支持默认构造、迭代器区间构造等。
3.2 插入 insert
map 插入时需要提供键值和映射值。利用 pair 可以方便地构造数据：
void test01() {
map<string, string> dict1;
pair<string, string> p("first", "第一");
dict1.insert(p);
dict1.insert(pair<string, string>("second", "第二"));
dict1.insert({ "third", "第三" });
dict1.insert(make_pair("forth", "第四"));
map<string, string> dict2 = {
{"left", "左边"},
{"right", "右边"},
{"insert", "插入"},
{"string", "字符串"}
};
Print_Container(dict1);
Print_Container(dict2);
}
注意：当插入新节点的键值已存在时，映射值不会更新。
3.3 operator[]
operator[] 功能强大，兼具查找、插入和修改映射值的能力。若键不存在则自动插入默认值，若存在则直接修改映射值。其返回值是映射值的引用。
void test_4() {
map<string, string> dict;
dict.insert({ "left", "左边" });
dict.insert(make_pair("right", "右边"));
dict["sort"]; // 查找 + 插入（默认空字符串）
dict["string"] = "字符串"; // 查找 + 修改
dict["left"] = "左边的"; // 查找 + 修改
auto it = dict["left"];
cout << it << endl;
}
常见场景：统计字符串中元素出现次数。将元素作为键，计数作为映射值，利用 operator[] 的特性即可轻松实现。
4. multimap 容器
multimap 几乎与 map 一样，区别在于支持插入相同键值的节点。
常用接口说明
4.1 插入
void Test01() {
multimap<string, string> mp;
mp.insert(make_pair("left", "左边"));
mp.insert(make_pair("left", "左边"));
mp.insert(make_pair("left", "左边"));
Print_Container(mp);
}
4.2 删除
void Test02() {
multimap<string, string> mp;
mp.insert(make_pair("left", "左边"));
mp.insert(make_pair("left", "左边"));
mp.insert(make_pair("left", "左边"));
mp.erase("left"); // 删除所有 key 为 left 的节点
Print_Container(mp);
}
掌握这些容器的特性，能让我们在处理复杂数据结构时更加得心应手，避免重复造轮子。