C++ STL 有序关联容器：set、multiset、map 与 multimap 详解 | 极客日志

C++算法

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

C++ STL 有序关联容器包含 set、multiset、map 和 multimap 四种类型，底层基于红黑树实现，支持高效查找、插入和删除。set 存储唯一键，multiset 允许重复；map 存储键值对，multimap 允许重复键。本文详解各容器的构造函数、迭代器操作及常用接口差异，重点讲解 insert 返回值含义、erase 迭代器失效规则以及 operator[] 在 map 中的特殊用法。

SqlMaster发布于 2026/3/240 浏览

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

C++ STL 有序关联容器详解

在 C++ 开发中，当需要快速查找唯一元素或统计键值出现次数时，使用数组或列表手动实现往往代码冗长且效率低下。STL（标准模板库）中的关联容器——set、multiset、map 和 multimap，正是为解决这类问题而生的。它们底层通常基于红黑树实现，提供高效的插入、删除和查找操作。

set 容器

set 存储唯一的键值，自动排序。其常用接口如下：

构造函数

最常用的构造方式包括迭代器区间构造、拷贝构造和初始化列表构造：

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}); // 初始化列表构造
}

迭代器

返回指向最小元素的迭代器，指向最后一个元素的后一个位置。由于底层是平衡二叉搜索树，遍历时天然有序。

begin()

end()

set

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

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

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;                          // 访问下一个节点
}

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

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
}

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

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<string, string> dict1;
map<string, string> dict2 = { {"left", "左边"}, {"right", "右边"} };

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

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

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