C++ STL 有序关联容器：set、multiset、map 与 multimap 详解

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;     // 输出最大值
}

为了方便观察容器内容，后续示例中我们将直接使用循环打印，不再依赖外部辅助函数。

插入 insert

set 不允许插入重复值。insert 的返回值是一个 pair<iterator, bool> 对象：

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

删除 erase

erase 支持通过迭代器或键值删除。通过迭代器删除时，函数会返回该节点后一个节点的迭代器，原迭代器失效。

void test04() {
    set<int> st({4, 5, 2, 9, 6, 8, 3, 1, 7, 7, 7, 7});
    set<int>::iterator it = st.erase(st.begin()); // 删除第一个节点
    cout << *it << endl;                          // 访问下一个节点
}

查找 find

找到则返回迭代器，未找到返回 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;
    }
}

统计 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
}

区间查找 lower_bound/upper_bound

这两个函数可用于确定区间范围，常用于批量删除。

void test07() {
    set<int> st1({20, 10, 50, 30, 10, 90, 70, 40, 80});
    // 删除 [30, 50)
    auto begin1 = st1.find(30);
    auto end1 = st1.find(50);
    while (begin1 != end1) {
        begin1 = st1.erase(begin1);
    }
    for (const auto& val : st1) cout << val << " "; // 10 20 50 70 80 90
    cout << endl;

    // 删除 [30, 50]
    set<int> st2({20, 10, 50, 30, 10, 90, 70, 40, 80});
    auto begin2 = st2.lower_bound(30);
    auto end2 = st2.upper_bound(50);
    while (begin2 != end2) {
        begin2 = st2.erase(begin2);
    }
    for (const auto& val : st2) cout << val << " "; // 10 20 70 80 90
    cout << endl;
}

multiset 容器

multiset 与 set 类似，但允许插入相同的值。因此部分接口行为有所不同：

• 插入：直接插入，不检查重复。
• 查找 find：返回中序遍历序列中的第一个匹配项。
• 删除 erase：若通过键值删除，会一次性删除所有具有相同值的节点；若通过迭代器删除，仅删除当前迭代器指向的节点。
• 统计 count：返回匹配到的元素总个数，可能大于 1。
• equal_range：返回包含所有相同值元素的迭代器区间。

void test1() {
    multiset<int> multi;
    multi.insert(3);
    multi.insert(2);
    multi.insert(3);
    multi.insert(3);
    for (const auto& val : multi) cout << val << " "; // 2 3 3 3
    cout << endl;
}

void test4() {
    multiset<int> multi;
    multi.insert(3);
    multi.insert(3);
    multi.insert(3);
    multi.insert(3);
    cout << multi.count(3); // 输出 4
}

map 容器

map 存储键值对（Key-Value），按键排序。其查找、删除、统计等操作逻辑与 set 一致，只是针对的是 Key。

构造函数

map<string, string> dict1;
map<string, string> dict2 = { {"left", "左边"}, {"right", "右边"} };

插入 insert

可以使用 pair 对象或初始化列表插入。注意，如果 Key 已存在，映射值不会更新。

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", "第四"));
    
    for (const auto& kv : dict1) {
        cout << kv.first << ": " << kv.second << endl;
    }
}

operator[]

operator[] 功能强大，兼具查找、插入和修改功能。如果 Key 不存在，会自动插入默认构造的值；如果存在，则修改映射值。返回值为映射值的引用。

void test_4() {
    map<string, string> dict;
    dict["sort"] = "排序";      // 查找 + 插入 + 修改
    dict["string"] = "字符串";  // 查找 + 修改
    
    auto it = dict["left"];     // 若 left 不存在，会插入空字符串并返回引用
    cout << it << endl;
}

常见场景是利用 operator[] 统计字符串中元素的出现次数：将元素作为 Key，计数作为 Value。

multimap 容器

multimap 允许插入相同 Key 的节点。除了 Key 可重复外，其他接口行为与 map 基本一致。

void Test01() {
    multimap<string, string> mp;
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    mp.insert(make_pair("left", "左边"));
    for (const auto& kv : mp) {
        cout << kv.first << ": " << kv.second << endl;
    }
}

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" 的节点
}

参考文档：

• set
• multiset
• map
• multimap