代码仓库shanchuann/CPP-Learninng

deque 与 list

在深入学习有序关联容器前，先明确 STL 顺序容器中 deque 与 list 的核心差异，便于后续区分顺序容器与关联容器的适用边界。两类容器均属于序列式容器，存储线性数据，但底层结构、迭代器稳定性、操作效率差异显著，具体对比如下：

迭代器与引用

std::deque 作为双端队列，底层由分段连续内存块组成，仅在容器两端插入或删除元素时，已存在的迭代器、引用和指针完全保持有效；但在容器中间位置执行插入、删除操作，会触发内存块调整，导致所有迭代器、引用、指针失效。而 std::list 是双向链表结构，无论在容器任意位置执行插入、删除操作，都仅需修改节点指针，不会移动元素，因此所有迭代器、引用、指针均保持有效，这是 list 最核心的优势。

扩展与收缩

std::deque 的扩容与缩容通过新增或删除独立内存块实现，无需整体迁移数据，效率优于连续存储的 vector ；仅当容器尺寸大幅增长时，才可能重新分配大块内存。 std::list 的扩容缩容仅需新增或删除单个链表节点，全程仅修改前后节点指针，操作耗时固定，效率极高，无内存重新分配的开销。

初始化与填充

std::deque 支持 assign 、 resize 等成员函数高效初始化，填充数据的效率略低于连续存储的 vector ，但远高于 list ； std::list 的初始化与填充需逐个创建链表节点，无法批量连续写入，效率低于 deque 和 vector ，更适合零散插入的场景。

选型核心结论：频繁在两端增删、需要兼顾随机访问与空间效率，选 deque ；频繁在任意位置增删、不关心随机访问，选 list 。

有序关联容器

C++标准模板库中的有序关联容器，是一类以键值关系为核心组织逻辑、底层依托**红黑树（平衡二叉树）**实现的容器类型，包含 map 、 multimap 、 set 、 multiset 四种标准实现。这类容器的核心共性是存储元素会按照预设的键值排序规则自动排列，遍历结果始终为有序序列，这一特征使其与 vector 、 list 、 deque 等顺序容器、 unordered_map 等无序关联容器形成明确区分。

红黑树的自平衡特性，让这类容器的元素查找、插入、删除操作均具备稳定的对数级时间复杂度O(logn)，即便数据规模扩大，操作效率也不会出现大幅衰减，尤其适合需要有序管理数据、频繁执行按键检索的开发场景。所有有序关联容器均属于双向迭代器范畴，不支持随机访问，迭代器仅能执行自增、自减操作，且除被修改节点外，其余迭代器、引用、指针在插入删除操作中均保持有效，这也是其区别于其他容器的重要特性。

std::pair 类模板

std::pair 是 C++标准库提供的基础类模板，是有序关联容器中键值对存储的核心载体， map 与 multimap 的每一个元素均以 std::pair 的形式存储，其中 first 成员对应键， second 成员对应值，无需开发者自定义结构体即可实现两个异构或同构数据的捆绑存储。该模板属于轻量级工具类，无额外内存开销，适配所有基础数据类型与自定义类型，是关联容器操作中不可或缺的基础组件。

std::pair 的完整模板原型为：template <class T1, class T2> struct pair;，其中 T1 对应 first 成员的类型， T2 对应 second 成员的类型，模板内部会自动定义 first_type 与 second_type 类型别名，分别映射 T1 和 T2 ，方便类型推导与泛型编程使用。其公有成员变量 first 与 second 可直接访问，无需借助成员函数，大幅简化数据读写流程； C++17 标准引入的结构化绑定特性，可直接将 pair 对象解构为两个独立变量，进一步简化多值返回与数据拆解的代码编写。

std::pair 的创建方式分为两类，一是直接调用构造函数，显式指定模板参数并初始化；二是通过 std::make_pair 函数模板创建，该函数可自动推导传入参数的类型，无需手动声明模板参数，适配泛型场景。标准库为 std::pair 重载了完整的关系运算符，包括==、!=、<、>、<=、>=，比较逻辑严格遵循字典序规则：先对比 first 成员，若 first 成员相等，再对比 second 成员，这一规则也是有序关联容器排序的核心依据之一。此外， std::pair 支持赋值操作与 swap 交换操作，可实现两个 pair 对象的内容互换，适配数据交换场景。

std::pair 简化源码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class _T1,class _T2>
struct pair
{
    typedef _T1 first_type;
    typedef _T2 second_type;
    // 默认构造
    pair(): first(_T1()), second(_T2()){}
    // 带参构造
    pair(const _T1 &_V1, const _T2 &_V2): first(_V1), second(_V2) {}
    // 公有成员变量
    _T1 first;
    _T2 second;
};
// 关系运算符重载
template<class _T1,class _T2> inline bool operator==(const pair<_T1,_T2>&_X,const pair<_T1,_T2>&_Y)
{ return(_X.first ==_Y.first && _X.second ==_Y.second); }
template<class _T1,class _T2> inline pair<_T1, _T2> make_pair(const _T1 &_X,const _T2 &_Y)
{ return (pair<_T1,_T2>(_X,_Y)); }

pair 基础使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <utility>
#include <string>
#include <iostream>
using namespace std;

int main()
{
    // 直接构造初始化
    std::pair<std::string, int> na1("yhping", 12);
    // make_pair自动推导类型初始化
    std::pair<std::string, int> na2 = std::make_pair("yhping", 23);

    // 直接访问成员变量
    cout << na1.first << endl;
    cout << na1.second << endl;

    // C++17结构化绑定
    auto [name, age] = na1;
    cout << name << endl;
    cout << age << endl;

    // pair比较操作
    cout << (na1 < na2) << endl;
    return 0;
}

map 关联容器

map 是实现一对一键值映射的有序关联容器，核心特性为键唯一、键不可修改、自动按键排序，每个键仅能对应一个值，杜绝重复键存储，适用于需要严格一一映射的业务场景。其完整模板原型为：template <class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key, T>>> class map;，其中 Key 为键类型， T 为值类型， Compare 为排序比较器（默认 less升序，可自定义 greater实现降序）， Allocator 为内存分配器，默认使用标准分配器。

map 容器的键类型必须满足可比较要求，即支持 Compare 指定的比较运算符，自定义类型需重载对应的比较运算符，否则无法完成排序与插入操作。容器底层红黑树会将键作为排序依据，插入元素时自动调整树结构维持平衡，遍历容器得到的序列始终符合预设排序规则，无需手动排序。 map 的迭代器为双向迭代器，且迭代器指向的元素类型为 pair<const Key, T>， const 修饰键的特性决定了无法通过迭代器直接修改键值，仅能修改值成员，强行修改键会破坏红黑树结构，导致程序出现未定义行为。

map 底层红黑树简化源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template<class _K,class _Ty,class _Pr=less<_K>>
class map
{
public:
    // 键值对类型，键为const不可修改
    typedef pair<const _K, _Ty> value_type;
    // 底层依托红黑树实现
    typedef _Tree<_K,value_type> _Imp;
protected:
    _Imp _Tr;
};
// 红黑树节点简化结构
template<class _K,class _Ty,class _Pr>
class _Tree
{
protected:
    enum _RedBlack {_Red,_Black};
    struct _Node;
    typedef struct _Node *_Nodeptr;
    struct _Node
    {
        _Nodeptr _Left, _Parent, _Right;
        _Ty _Value;
        _RedBlack _color;
    };
    _Nodeptr _Head;
    size_type _size;
};

初始化方式

map 支持多种初始化方式，覆盖不同开发场景：一是默认构造，创建空容器；二是列表初始化，直接传入键值对列表完成初始化；三是范围初始化，通过其他 map 容器或迭代器区间完成拷贝；四是拷贝构造与移动构造，实现容器的深拷贝或资源转移。

成员函数细分

  1. 容量与状态查询： empty()判断容器是否为空， size()返回当前元素个数， max_size()返回容器可容纳的最大元素数，均为常量时间复杂度 O(1)。
  2. 元素访问： at(const Key& key)会执行键存在性检查，若键不存在则抛出 std::out_of_range 异常，安全性更高； operator[](const Key& key)无异常检查，键不存在时会自动插入该键，值采用默认构造初始化，适合快速赋值，但需注意避免无意插入冗余元素。
  3. 元素插入： insert()支持插入 pair 对象、迭代器区间、列表初始化数据，返回值为 pair<iterator, bool>， bool 标识插入是否成功（键重复则失败）； emplace()为原位构造，直接在容器内部构造 pair 对象，避免临时对象拷贝，效率高于 insert ； insert_or_assign()为 C++17 新增接口，键存在则修改值，键不存在则插入，适配覆盖式插入场景。
  4. 元素删除： erase()包含三种重载，传入迭代器删除单个元素，返回下一个有效迭代器；传入键值删除所有匹配键的元素（ map 中仅一个），返回删除个数；传入迭代器区间删除范围元素，返回尾迭代器； clear()清空容器所有元素， size 置为 0 。
  5. 元素查找： find(const Key& key)返回匹配键的迭代器，无匹配则返回 end()； count(const Key& key)返回匹配键的元素个数（ map 中为 0 或 1 ）； contains(const Key& key)为 C++20 新增接口，直接返回 bool 值标识键是否存在，使用更便捷； lower_bound 、 upper_bound 、 equal_range 用于范围查找，适配区间检索场景。

std::map 迭代器使用注意事项

使用 map 迭代器时，需严格遵守以下规则，避免迭代器失效与未定义行为：

  1. 迭代器有效性：仅被删除节点的迭代器失效，其余节点迭代器、引用均保持有效；删除元素后，禁止使用失效迭代器。
  2. 常量迭代器限制： const_iterator 无法修改元素值，修改值需使用普通迭代器，且绝对禁止修改键。
  3. 遍历中删除元素：遍历过程中直接删除元素会导致当前迭代器失效，需将迭代器赋值为 erase()的返回值（下一个有效迭代器）。
  4. end()迭代器禁忌： end()指向尾后位置，无法解引用，遍历终止条件需严格判断迭代器是否等于 end()。
  5. 键修改规范：如需修改键，必须先删除原键元素，再插入新键元素，禁止直接通过迭代器修改键值。

map 实战代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

struct Student
{
    std::string s_id;
    std::string s_name;
    std::string s_sex;
    int s_age;
};

ostream &operator<<(ostream &out, const struct Student &s)
{
    out << "id:" << s.s_id << " name:" << s.s_name << " sex:" << s.s_sex << " age:" << s.s_age;
    return out;
}

typedef std::map<std::string, int> StudMap;

int main()
{
    std::vector<struct Student> svec = {
        {"2024001", "lzj", "man", 12},
        {"2024002", "yxj", "woman", 13},
        {"2024003", "zgs", "man", 11},
        {"2024004", "sjh", "man", 10},
        {"2024005", "wjy", "woman", 11},
        {"2024006", "zjf", "man", 13},
        {"2024008", "hm", "man", 17}
    };

    // 空map初始化，emplace原位插入
    std::map<std::string, int> simap;
    int n = svec.size();
    for (int i = 0; i < n; ++i)
    {
        simap.emplace(svec[i].s_id, i);
    }

    // 迭代器遍历有序元素
    for (auto &x : simap)
    {
        cout << "x.first:" << x.first << " x.second:" << x.second << endl;
        cout << svec[x.second] << endl;
    }

    // 测试at与[]访问差异
    try {
        // 键存在正常访问
        cout << simap.at("2024001") << endl;
        // 键不存在抛出异常
        // simap.at("2024999");
    } catch (const std::out_of_range& e) {
        cout << e.what() << endl;
    }
    // 键不存在，自动插入默认值
    simap["2024999"];
    cout << "map插入冗余键后size:" << simap.size() << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef std::map<int, std::string> ServerMap;

int main()
{
    ServerMap sermap = {
        {2000, "node1"},
        {23000, "node2"},
        {480000, "node3"},
        {980000, "node4"}
    };

    // lower_bound：首个不小于指定键的元素
    for (int i = 1998; i < 2002; ++i)
    {
        auto it = sermap.lower_bound(i);
        cout << "i:" << i << " ip:" << it->first << " node:" << it->second << endl;
    }

    // upper_bound：首个大于指定键的元素
    for (int i = 1998; i < 2002; ++i)
    {
        auto it = sermap.upper_bound(i);
        cout << "i:" << i << " ip:" << it->first << " node:" << it->second << endl;
    }

    // equal_range：返回匹配键的上下界迭代器对
    auto itpair = sermap.equal_range(2000);
    if (itpair.first != sermap.end()) {
        cout << "匹配元素：" << itpair.first->first << " " << itpair.first->second << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <cstdlib>
using namespace std;

int main()
{
    typedef std::map<std::string, int> wordMap;
    const char *filename = "tulun.txt";
    std::ifstream in(filename);
    if (!in)
    {
        fprintf(stderr, "could not open file %s\n", filename);
        exit(EXIT_FAILURE);
    }

    wordMap wordmap;
    std::string word;
    // 利用[]自动插入特性实现单词计数
    while (in >> word)
    {
        wordmap[word]++;
    }

    // 遍历输出有序单词及频次
    for (const auto& w : wordmap)
    {
        cout << w.first << ":" << w.second << endl;
    }

    return 0;
}

multimap 多重映像容器

multimap 是支持重复键存储的有序关联容器，底层同样基于红黑树实现，与 map 共享核心底层逻辑，核心区别在于 multimap 允许同一个键对应多个值，适用于一对多映射的业务场景。其完整模板原型为：template <class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key, T>>> class multimap;，模板参数含义与 map 完全一致，键类型同样需满足可比较要求，且键不可修改。

multimap 与 map 的特性差异可规整为以下几点，二者的操作逻辑与底层实现一脉相承，仅在重复键处理上存在区别：

  1. 键唯一性： map 强制键唯一，重复键插入失败； multimap 允许键重复，所有插入操作均成功。
  2. 元素访问接口： map 提供 at()与 operator[]，可直接通过键定位唯一值； multimap 无这两个接口，因重复键无法定位唯一值，仅能通过迭代器与查找接口遍历匹配元素。
  3. 插入返回值： map 的 insert 返回 pair<iterator, bool>，标识插入结果； multimap 的 insert 仅返回 iterator ，指向新插入元素，无布尔标识。
  4. 删除操作： map 删除指定键仅能删除一个元素； multimap 删除指定键会删除所有匹配键的元素，也可通过迭代器删除单个重复元素。

multimap 的成员函数与 map 高度重合，容量查询、迭代器操作、范围查找接口完全一致，其中equal_range是处理重复键的核心接口，可快速获取同一键对应的所有元素的迭代器区间，避免逐一遍历整个容器，大幅提升检索效率。 multimap 的插入支持 insert 、 emplace 、 emplace_hint 等方式， emplace_hint 可指定插入位置提示，利用红黑树特性优化插入效率，适合已知元素大致位置的场景。

multimap 实战代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef std::map<int, std::string> ISMap;
typedef std::multimap<int, std::string> ISMulMap;

int main()
{
    ISMap ismap;
    ISMulMap ismulmap;

    // map重复键插入失败
    auto it = ismap.insert(std::make_pair(23, "yhping"));
    cout << "map首次插入结果：" << it.second << " 值：" << it.first->second << endl;
    it = ismap.insert(std::make_pair(23, "tulun"));
    cout << "map重复插入结果：" << it.second << " 值：" << it.first->second << endl;

    // multimap重复键插入成功
    auto mit = ismulmap.insert(std::make_pair(23, "yhping"));
    cout << "multimap首次插入值：" << mit->second << endl;
    mit = ismulmap.insert(std::make_pair(23, "tulun"));
    cout << "multimap重复插入值：" << mit->second << endl;

    // 遍历multimap所有元素
    cout << "multimap全部元素：" << endl;
    for (const auto& elem : ismulmap) {
        cout << elem.first << " " << elem.second << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <map>
#include <string>
using namespace std;

typedef std::multimap<std::string, std::string> PhoneMap;

int main()
{
    // 列表初始化，同一姓名对应多个号码
    PhoneMap phonebooks = {
        {"hming", "15081003368"},
        {"hming", "18946033855"},
        {"hming", "16601261930"},
        {"tulun", "16535828685"},
        {"tulun", "11503043829"},
        {"yhping", "13983964254"},
        {"yhping", "18392344066"}
    };

    // 全量遍历
    for (const auto &px : phonebooks)
    {
        cout << "name:" << px.first << " phone:" << px.second << endl;
    }

    // 按姓名查询所有号码，equal_range定位区间
    std::string name;
    cout << "请输入查询姓名：" << endl;
    while (cin >> name && name != "end")
    {
        auto range = phonebooks.equal_range(name);
        if (range.first == phonebooks.end()) {
            cout << "未查询到该姓名信息" << endl;
            continue;
        }
        cout << "姓名：" << name << " 对应号码：";
        for (auto it = range.first; it != range.second; ++it)
        {
            cout << it->second << " ";
        }
        cout << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

struct DNSRecord
{
    std::string ipAddress;
    std::string type;
};

std::multimap<std::string, DNSRecord> dnsRecords;

// 插入DNS记录
void addDNSRecord(const std::string &domain, const DNSRecord &record)
{
    dnsRecords.emplace(domain, record);
}

// 查询域名对应所有IP
std::vector<DNSRecord> findDNS(const std::string &domain)
{
    std::vector<DNSRecord> results;
    auto range = dnsRecords.equal_range(domain);
    for (auto it = range.first; it != range.second; ++it)
    {
        results.push_back(it->second);
    }
    return results;
}

int main()
{
    addDNSRecord("baidu.com", {"192.168.23.1", "IPv4"});
    addDNSRecord("baidu.com", {"2002::c0a8:1701", "IPv6"});
    addDNSRecord("tulun.net", {"192.168.0.23", "IPv4"});
    addDNSRecord("tulun.net", {"2002::c0a8:17", "IPv4"});

    std::string domainToQuery = "baidu.com";
    std::cout << "域名" << domainToQuery << "的DNS记录：" << std::endl;
    auto records = findDNS(domainToQuery);
    for (const auto &record : records)
    {
        std::cout << "IP:" << record.ipAddress << ",类型:" << record.type << std::endl;
    }

    return 0;
}

set 关联容器

set 是专注于存储唯一有序元素的关联容器，底层同样基于红黑树实现，与 map 的核心区别在于 set 仅存储单一元素（元素本身即为键），无独立的键值对结构，元素兼具键与值的双重属性。其完整模板原型为：template <class T, class Compare = less<T>, class Allocator = allocator<T>> class set;，其中 T 为存储元素类型， Compare 为排序比较器， Allocator 为内存分配器，元素类型必须满足可比较要求，否则无法完成排序与插入。

set 容器的核心特性为元素唯一、自动排序、元素不可修改，其迭代器指向的元素为 const 类型，即便使用非 const 迭代器，也无法修改元素值，因为修改元素等同于修改键，会破坏红黑树的排序结构。若需要修改 set 中的元素，必须先通过 erase 删除原元素，再插入修改后的新元素，这是 set 操作的核心规范。 set 的迭代器为双向迭代器，支持正向与反向遍历，迭代器稳定性与 map 一致，插入删除操作仅影响当前节点迭代器。

std::set 迭代器使用注意事项

  1. 迭代器仅在指向元素被删除时失效，其余操作均不影响其他迭代器有效性；
  2. set 迭代器默认是常量迭代器，无法修改任何元素值，修改元素需先删后插；
  3. 遍历过程中删除元素，需借助临时容器存储待删元素，遍历结束后统一删除，或利用 erase 返回值更新迭代器；
  4. 禁止解引用 end()迭代器，禁止直接修改元素值破坏排序规则。

核心成员函数特性

set 的成员函数与 map 高度相似，无元素访问接口（因无独立值），核心函数聚焦于插入、删除、查找与容量查询。 insert 函数返回值为 pair<iterator, bool>，元素重复则插入失败， bool 值为 false ； emplace 实现原位构造，效率高于 insert ； find 函数查找指定元素，返回对应迭代器，无匹配则返回 end()； count 函数返回 0 或 1 ，用于判断元素是否存在； lower_bound 、 upper_bound 、 equal_range 同样支持范围查找，适配有序区间检索场景。

set 的初始化方式与 map 一致，支持默认构造、列表初始化、范围初始化、拷贝与移动构造，可直接通过数组、 vector 等容器的迭代器区间完成初始化，快速实现数据去重与排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{
    const int n = 20;
    std::vector<int> ivec;
    std::set<int> iset;
    ivec.reserve(n);
    srand(time(0));

    // 生成随机重复数据
    for (int i = 0; i < n; ++i)
    {
        ivec.push_back(rand() % 20);
    }

    cout << "原始vector无序重复数据：" << endl;
    for (int num : ivec)
    {
        cout << "\t" << num;
    }
    cout << endl << endl;

    // 范围插入，自动去重+排序
    iset.insert(ivec.begin(), ivec.end());
    cout << "set去重并升序排列后数据：" << endl;
    for (int num : iset)
    {
        cout << "\t" << num;
    }
    cout << endl;

    // 测试元素存在性
    int target = 10;
    if (iset.find(target) != iset.end()) {
        cout << "元素" << target << "存在于set中" << endl;
    } else {
        cout << "元素" << target << "不存在于set中" << endl;
    }

    return 0;
}

multiset 多重集合容器

multiset 是允许存储重复元素的有序关联容器，底层基于红黑树实现，与 set 共享底层逻辑，核心区别是 multiset 不限制元素唯一性，可存储多个相同元素，适用于需要有序管理重复数据的场景。其完整模板原型为：template <class T, class Compare = less<T>, class Allocator = allocator<T>> class multiset;，模板参数含义与 set 完全一致，元素类型需满足可比较要求，元素同样不可直接修改。

multiset 与 set 的核心差异集中在元素重复性与部分函数行为： multiset 的 insert 函数仅返回 iterator ，指向新插入元素，插入操作永远成功； count 函数可返回大于 1 的数值，代表指定元素的出现次数；删除指定元素时，传入迭代器仅删除单个元素，传入元素值则删除所有匹配值的元素，需根据业务场景选择合适的删除方式。

std::multiset 迭代器使用注意事项

核心规则与 set 完全一致，额外注意：删除单个重复元素必须传入迭代器，传入元素值会删除所有同值元素，避免误删数据；迭代器同样无法修改元素值，强行修改会导致编译失败，如需变更元素，遵循先删后插原则。

multiset 的迭代器特性、排序规则、迭代器稳定性与 set 完全一致，范围查找接口 equal_range 同样是处理重复元素的核心工具，可快速定位同一元素的所有实例区间，避免全容器遍历。其底层红黑树的自平衡逻辑，保证了即便存储大量重复元素，插入、删除、查找操作仍保持 O(logn)的稳定效率，适合成绩统计、频次记录等需要有序重复数据的场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <set>
#include <string>
using namespace std;

int main()
{
    // 存储学生成绩，允许重复分数
    std::multiset<int> scoreSet;
    // 插入重复成绩
    scoreSet.insert(85);
    scoreSet.insert(92);
    scoreSet.insert(78);
    scoreSet.insert(85);
    scoreSet.insert(92);
    scoreSet.insert(88);
    scoreSet.insert(78);

    // 遍历有序成绩序列
    cout << "学生成绩有序升序列表：" << endl;
    for (int score : scoreSet)
    {
        cout << score << " ";
    }
    cout << endl << endl;

    // 统计指定分数出现次数
    int target = 85;
    cout << "分数" << target << "出现的总次数：" << scoreSet.count(target) << endl;

    // 查找所有92分的成绩
    auto range = scoreSet.equal_range(92);
    cout << "所有92分成绩：";
    for (auto it = range.first; it != range.second; ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    // 删除单个85分成绩
    auto delIt = scoreSet.find(85);
    if (delIt != scoreSet.end()) {
        scoreSet.erase(delIt);
    }
    cout << "删除单个85分后，剩余85分次数：" << scoreSet.count(85) << endl;

    return 0;
}

有序关联容器对比无序关联容器

C++11 新增无序关联容器（ unordered_map 、 unordered_multimap 、 unordered_set 、 unordered_multiset ），底层基于哈希表实现，与有序关联容器的核心对比如下，便于开发中精准选型：

对比维度 有序关联容器（ map/set ） 无序关联容器（ unordered_map/set ）
底层实现 红黑树（平衡二叉树） 哈希表+链表/红黑树（解决冲突）
时间复杂度 查找/插入/删除：稳定 O(logn) 平均 O(1)，最坏 O(n)（哈希冲突）
元素顺序 按键自动有序，遍历结果有序 无序，存储顺序由哈希值决定
迭代器类型 双向迭代器 单向迭代器
键类型要求 支持<比较运算符 支持哈希函数+==比较
适用场景 需要有序遍历、范围查找、稳定效率 纯快速查找、不关心顺序、高并发查询

核心选型口诀：一对一映射选 map ，一对多映射选 multimap ；纯唯一元素去重选 set ，重复元素有序统计选 multiset ；需要有序+稳定效率选红黑树系列，纯极速查找选无序哈希系列。

  • std::map：唯一键+一对一映射+有序，适合字典、索引、键值唯一的配置管理；
  • std::multimap：重复键+一对多映射+有序，适合电话簿、 DNS 记录、多值关联场景；
  • std::set：唯一元素+有序+去重，适合权限校验、数据排重、有序集合操作；
  • std::multiset：重复元素+有序，适合成绩统计、频次计数、有序重复数据管理。

所有有序关联容器依托红黑树实现，牺牲部分极致速度换取稳定效率与有序性，是工程开发中兼顾可靠性与实用性的核心容器，尤其适合业务逻辑中需要有序管理、范围检索的场景，是 C++ STL 容器体系的核心组成部分。