C++ STL 有序关联容器详解：set、map 及其变体用法

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);
}

掌握这些容器的特性，能让我们在处理复杂数据结构时更加得心应手，避免重复造轮子。