一.序列式容器和关联式容器

在开始今天的内容之前，我们先讲一下这两个结构：

1.什么是序列式容器？

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

2.什么是关联式容器？

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

---

二.键值对 --- pair

这种结构通常用来表示一种一一对应的映射关系。在它的内部，一般只包含两个重要的成员变量：key（键值）和 value（数值/信息）。其中，key 是用于索引的唯一标识，而 value 则是与这个标识所对应的具体内容。

举个例子，我们现在要设计一个英汉互译词典。在这个词典中，每一个英文单词都对应着一个唯一的中文释义；反过来，每个中文翻译也对应着一个英文单词。这两者之间存在着明确的一一映射关系。也就是说，只要给出一个英文单词（key），我们就可以依据这个结构，在词典中精准地找出与之匹配的中文含义（value）。

图片中我们可以看到,std::pair是 C++ 标准库中定义在 <utility> 头文件里的一个类模板（准确来说是结构体模板），作用就是将两个可能属于不同类型的数据放在一起，从而且成一个单一的对象。在pair内部只有两个公有成员变量：first 和 second，分别用来存储第一个值和第二个值。与此同时，它还提供了两个类型别名：first_type 对应第一个参数的类型 T1，second_type 对应第二个参数的类型 T2。

使用 pair 时，需要在模板参数列表中显式指定两个元素的类型。

从图中我们可以看到：std::make_pair 同样定义在 <utility> 头文件中，但它是一个函数模板。它的功能是构造并返回一个 pair 对象，其中 first 被设置为传入的第一个参数 x，second 被设置为传入的第二个参数 y。

make_pair 的优势在于类型自动推导，编译器会根据传入的实际参数自动推断出 pair<T1, T2> 的模板类型。它的内部实现本质上就是调用了 pair<T1, T2>(x, y) 的构造函数并返回该对象。

此外，make_pair 还支持隐式类型转换，从一个包含不同类型元素的 pair 对象构造另一个 pair 对象，只要相应的类型之间可以隐式转换。

先用代码对比一下如下：

#include <iostream>
#include <utility>      
#include <string>
using namespace std;

int main()
{
    
    //使用 pair--显式写 <int, string>
    pair<int, string> p1(1, "apple");        
    pair<int, string> p2(2, "banana");
    pair<int, string> p3;
    p3.first = 3;
    p3.second = "cherry";

    cout << p1.first << ":" << p1.second << endl;   // 1:apple
    cout << p2.first << ":" << p2.second << endl;   // 2:banana
    cout << p3.first << ":" << p3.second << endl;   // 3:cherry

   
    // 方式二：使用 make_pair-->自动推导为 pair<int, const char*>
    auto p4 = make_pair(4, "date");         
    auto p5 = make_pair(5, string("elder"));

    cout << p4.first << ":" << p4.second << endl;   // 4:date
    cout << p5.first << ":" << p5.second << endl;   // 5:elder
   

    return 0;
}

代码中的：string("elder")  用一个 C 风格字符串构造一个 string 对象（类型是 string）。

---

接着我们讲一下键值对：

SGI-STL 中关于键值对的定义：map 中存放的元素是一个个的键值对（也就是我们说的 pair 对象）。

详细简介：

// map 中存的就是这个结构体，key 和 value 被封装在一起
template <class K, class V>      // K = Key（键的类型），V = Value（值的类型）
struct KeyValuePair             
{
    // 让外部可以通过 KeyValuePair<int, string>::KeyType 拿到 int
    // 通过 KeyValuePair<int, string>::ValueType 拿到 string
    typedef K KeyType;     // 键的类型
    typedef V ValueType;   // 值的类型

    //成员变量 
    K key;     // 相当于 map 中的 key（键）
    V value;   // 相当于 map 中的 value（值）

    // 默认构造函数
    // 不传参数时，key 和 value 各自调用自己的默认构造函数初始化
    // 比如：KeyValuePair<int, string>()--> key = 0, value = ""
    KeyValuePair()
        : key(K())      // K() 是 K 类型的默认值（int 为 0）
        , value(V())    // V() 是 V 类型的默认值（string 为 ""）
    {}

    // 带参构造函数
    // 传入 k 和 v，分别初始化 key 和 value
    // 举个例子KeyValuePair<int, string>(1, "苹果") --> key = 1, value = "苹果"
    KeyValuePair(const K& k, const V& v)
        : key(k)        // 用 k 初始化 key
        , value(v)      // 用 v 初始化 value
    {}
};

构造一个 pair 对象（键值对）

// 写法一：直接构造
std::pair<int, int> p(10, 20);

// 写法二：make_pair 构造
std::pair<int, int> p = std::make_pair(10, 20);

法一：调用 pair 的构造函数，显式指定类型；

法二：调用 make_pair 函数模板，编译器根据参数 10,20 自动推导类型为 int,int（隐式类型转换）。

---

三.树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。

这四种容器的共同点是：使用平衡搜索树（即红黑树）作为其底层结构，容器中的元素是一个有序的序列。

1.set（集合）

set - C++ Reference

• set的声明如下，T就是set底层关键字的类型
• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数
• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。
• ⼀般情况下，我们都不需要传后两个模版参数。
• set底层是⽤红⿊树实现，增删查效率是 O(logN) ，迭代器遍历是⾛的搜索树的中序，所以是有序的。
• 前⾯部分我们已经学习了vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似，所以这⾥我们就不再⼀个接口一个接⼝的介绍，⽽是直接带着⼤家看⽂档，挑比较重要的接⼝进⾏介绍。

大致内容如下：

• set 是按照一定次序存储元素的容器。
• 在 set 中，元素的 value 也标识它（value 就是 key，类型为 T），并且每个 value 必须是唯一的。set 中的元素不能在容器中修改（元素总是 const），但是可以从容器中插入或删除它们。
• 在内部，set 中的元素总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序。
• set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代。
• set 在底层是用二叉搜索树（红黑树）实现的

2.set 的使用

a. set的模板参数列表

template < class T,                    // 模板参数1：元素类型
           class Compare = less<T>,    // 模板参数2：比较方式（默认升序）
           class Alloc = allocator<T>  // 模板参数3：内存分配器（默认）
> class set;

参数说明

1.T —— 元素类型

set 中存放元素的类型，实际在底层存储的是键值对 <value, value>，即键和值都是 T 类型。

2.Compare —— 比较规则

set 中元素默认按照 小于（<） 来比较，就是升序排列。

• 内置类型：一般情况下不需要传递该参数，使用默认的 less<T> 即可

• 自定义类型：无法直接比较时，需要用户显式传递比较规则，通常使用函数指针或仿函数（函数对象） 来传递

3.Alloc —— 空间配置器

set 中元素空间的管理方式，使用 STL 提供的空间配置器（allocator） 来管理内存的分配与释放，一般使用默认即可。

---

b. set的构造

// empty (1) ⽆参默认构造
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
// copy (3) 拷⻉构造
set (const set& x);
// 补充：
//initializer list (5) initializer 列表构造
set (initializer_list<value_type> il,
const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
//il	花括号初始化列表
//作用：用花括号列表初始化集合，自动去重并排序。

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main()
{
    // 1. 默认构造（空 set）
    set<int> s1;
    s1.insert(5);
    s1.insert(2);
    s1.insert(8);
    s1.insert(2);  // 重复插入无效

    cout << "s1: ";
    for (int x : s1) cout << x << " ";
    cout << endl;

    // 2. 迭代器区间构造
    vector<int> v = { 10, 30, 20, 50, 40 };
    set<int> s2(v.begin(), v.end());

    cout << "s2: ";
    for (int x : s2) cout << x << " ";
    cout << endl;

    // 也可以用数组构造
    int arr[] = { 9, 5, 7, 3, 1 };
    set<int> s3(arr, arr + 5);

    cout << "s3: ";
    for (int x : s3) cout << x << " ";
    cout << endl;

    // 3. 拷贝构造
    set<int> s4(s2);  // 拷贝 s2

    cout << "s4: ";
    for (int x : s4) cout << x << " ";
    cout << endl;

    //  4. initializer_list 构造 
    set<int> s5 = { 5, 2, 8, 1, 3 };  // 自动排序去重

    cout << "s5: ";
    for (int x : s5) cout << x << " ";
    cout << endl;

    // 5. 降序 set（指定 greater）
    set<int, greater<int>> s6 = { 1, 2, 3, 4, 5 };

    cout << "s6(降序): ";
    for (int x : s6) cout << x << " ";
    cout << endl;

    //  6. 自定义类型需要传比较器
    struct Student
    {
        int id;
        string name;
    };

    struct CmpStudent
    {
        bool operator()(const Student& a, const Student& b) const
        {
            return a.id < b.id;  // 按学号升序
        }
    };

    // 用 initializer_list 构造自定义类型 set
    set<Student, CmpStudent> students = {
        {1002, "李四"},
        {1001, "张三"},
        {1004, "赵六"},
        {1003, "王五"}
    };

    cout << "学生(按学号): ";
    for (const auto& s : students)
    {
        cout << s.id << ":" << s.name << " ";
    }
    cout << endl;

    return 0;
}

---

c. set 的迭代器

set的⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

代码如下：

#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int> s = { 1, 2, 3, 4, 5 };

    //  正向迭代器
    cout << "正向遍历: ";
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    // 反向迭代器 
    cout << "反向遍历: ";
    for (set<int>::reverse_iterator rit = s.rbegin(); rit != s.rend(); ++rit)
    {
        cout << *rit << " ";
    }
    cout << endl;

    // C++11 范围 for（底层用的也是迭代器)
    cout << "范围for遍历: ";
    for (int x : s)
    {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

---

d. set 的容量

代码如下：

#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int> s1;

    // empty()：判断是否为空 
    cout << "s1是否为空:"  << s1.empty() << endl;  

    s1.insert(10);
    s1.insert(20);
    s1.insert(30);

    cout << "s1是否为空: " << s1.empty() << endl;  

    // size()：返回元素个数
    cout << "s1中元素个数: " << s1.size() << endl;  

    s1.insert(10);  // 重复插入，无效
    cout << "插入重复元素后个数: " << s1.size() << endl;  

    s1.insert(40);
    cout << "插入40后个数: " << s1.size() << endl;  

    // 空 set 的 size
    set<int> s2;
    cout << "s2是否为空: " << s2.empty() << endl; 
    cout << "s2中元素个数: " << s2.size() << endl;
    return 0;
}

---

e. set 修改操作

set 基础操作：

代码如下：

#include<iostream>
#include<set>
using namespace std;

int main()
{
    //  1. 初始化并遍历 
    set<int> s = { 4, 2, 7, 2, 8, 5, 9 };  // 重复的2会被去重
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;   // 输出：2 4 5 7 8 9（自动升序）

    //2. 删除最小值（迭代器删除） 
    s.erase(s.begin());   // begin()指向最小元素2
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;   // 输出：4 5 7 8 9

    // 3. 按值删除（erase(key)）
    int x;
    cin >> x;
    int num = s.erase(x);   // 返回删除的个数（0或1）
    if (num == 0)
    {
        cout << x << "不存在！" << endl;
    }
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    // 4. 查找后删除（find + erase）
    cin >> x;
    auto pos = s.find(x);   // set自带的查找，O(logN)
    if (pos != s.end())
    {
        s.erase(pos);       // 迭代器删除
    }
    else
    {
        cout << x << "不存在！" << endl;
    }
    for (auto e : s)
    {
        cout << e << " ";
    }
    cout << endl;

    // 5. 两种查找方式对比
    auto pos1 = find(s.begin(), s.end(), x);   // 算法库的find，O(N)
    auto pos2 = s.find(x);                     // set自带的find，O(logN)  

    // 6. 用 count 判断存在
    cin >> x;
    if (s.count(x))      // count返回0或1（set中元素唯一）
    {
        cout << x << "在！" << endl;
    }
    else
    {
        cout << x << "不存在！" << endl;
    }

    return 0;
}

---

lower_bound / upper_bound 区间操作

#include<iostream>
#include<set>
using namespace std;

int main()
{
    std::set<int> myset;

    //1. 插入数据
    for (int i = 1; i < 10; i++)
        myset.insert(i * 10);   // 10 20 30 40 50 60 70 80 90

    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;   // 10 20 30 40 50 60 70 80 90

    // 2. lower_bound / upper_bound 区间删除 
    //删除 [30, 60] 区间内的所有元素

    auto itlow = myset.lower_bound(30);   // 返回第一个 >= 30 的迭代器 ---> 指向30
    auto itup = myset.upper_bound(60);    // 返回第一个 > 60 的迭代器 --> 指向70

    // 删除 [itlow, itup) 区间，即 30, 40, 50, 60
    myset.erase(itlow, itup);

    for (auto e : myset)
    {
        cout << e << " ";
    }
    cout << endl;   // 10 20 70 80 90

    return 0;
}

---

f. set 的使用举例

void test_set()
{
    // 用数组构造set（自动去重 + 排序）
    int nums[] = { 2, 6, 4, 8, 10, 3, 6, 5 };
    set<int> s(nums, nums + sizeof(nums)/sizeof(nums));
    // 6只存一份，自动排序
    cout << s.size() << endl;  // 输出：7（去重后个数）

    s.insert(6);  // 6已存在，插入无效

    cout << s.size() << endl;  // 还是7

    // 正向遍历set --> 升序输出（无重复）
    for (auto& e : s)
        cout << e << " ";
    cout << endl;
    // 输出：2 3 4 5 6 8 10

    // 反向遍历set → 降序输出
    for (auto it = s.rbegin(); it != s.rend(); ++it)
        cout << *it << " ";
    cout << endl;
    // 输出：10 8 6 5 4 3 2

    // 两种查找方式对比

    // 方式一：算法库的find（暴力遍历 O(N)）
    // auto it = find(s.begin(), s.end(), 4);

    // 方式二：set自带的find（红黑树查找 O(logN)）
    auto it = s.find(4);

    if (it != s.end())
    {
        s.erase(it);  // 方式一：迭代器删除
    }
    s.erase(6);       // 方式二：按值删除

    // count判断元素是否存在
    cout << s.count(3) << endl;  // 输出：1（3存在）
    cout << s.count(9) << endl;  // 输出：0（9不存在）
}

注意：set 容器中不允许存在重复元素（即数据冗余）。使用 set 的迭代器遍历容器中的元素，会得到一个有序序列（默认升序）。因此，当一组数据通过 set 存储后，便自动完成了 排序 + 去重 的操作效果。

set总结

• 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，而set只放value，但在底层实际存放的是由<value, value>构成的键值对。
• set中插入元素时，只需要插入value即可，不需要构造键值对。
• set中的元素不可以重复，因此可以利用set进行数据去重。
• 使用set的迭代器遍历set中的元素，可以得到一个有序序列，默认情况下为升序。
• set中的元素默认按照小于来比较，即升序排列。如果需要降序，可以指定greater<T>作为第二个模板参数。
• set中查找某个元素的时间复杂度为O(logN)，增删查改操作都是O(logN)。
• set中的元素不允许修改。因为set底层采用红黑树实现，元素值的变化会破坏树的排序规则，导致整个结构失效。所以set的迭代器实际上是一个常量迭代器，只能读取不能写入。
• set的底层使用红黑树来实现，这棵树是一棵平衡搜索树，保证了操作的高效性。

---

3.map（映射）

map - C++ Reference

大致翻译：

• map 是关联容器，它按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素。
• 在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair: typedef pair<const key, T> value_type;
• 在内部，map 中的元素总是按照键值 key 进行比较排序的。
• map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代（即对 map 中的元素进行迭代时，可以得到一个有序的序列）。
• map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value。
• map 通常被实现为二叉搜索树更准确的说：平衡二叉搜索树（又叫做红黑树）。
   

---

4.map的使用

template < class Key,                          // 参数1：键的类型
           class T,                            // 参数2：值的类型
           class Compare = less<Key>,          // 参数3：比较规则（默认升序）
           class Alloc = allocator<pair<const Key, T>>  // 参数4：空间配置器
> class map;

a.参数解释：

1.key：键值对中 key 的类型。在 map 中，key 是唯一的，不能重复，且不能被修改（因为 key 被修饰为 const）。

2.T：键值对中 value 的类型。value 与 key 一一对应，允许被修改。

3.Compare：比较器的类型。map 中的元素按照 key 的大小进行排序，缺省情况下按照小于（<） 来比较，即升序。

• 内置类型（如 int、double、string 等）：支持默认比较，该参数一般不需要传递

• 自定义类型（如结构体、类对象）：无法直接比较，需要用户显式传递比较规则，通常使用函数指针或仿函数（函数对象） 来实现

比较方式：

• 小于（<）升序：使用 less<T>（默认）

• 大于（>）降序：定义 map 时模板参数中需显式指定 greater<T>

// 升序（默认）
map<int, string> m1;
// 降序
map<int, string, greater<int>> m2;

4.Alloc：空间配置器，用于管理底层内存的分配与释放。一般使用 STL 提供的默认空间配置器即可，除非用户有特殊需求（如内存池定制），否则不需要传递该参数。

---

b. map的构造

// 1. 无参默认构造
// 创建一个空的 map，按 key 升序排列
explicit map(const key_compare& comp = key_compare(),
             const allocator_type& alloc = allocator_type());

• comp：const key_compare&    key_compare()    比较器对象，默认 less<Key>（升序）
• alloc：const allocator_type&    allocator_type()    空间配置器，管理内存分配

作用：创建一个空的 map 对象。explicit 关键字禁止隐式类型转换。

map<int, string> m1;                    // 空 map，默认升序
map<int, string, greater<int>> m2;      // 空 map，指定降序

---

// 2. 迭代器区间构造
// 用 [first, last) 区间内的元素构造 map
template <class InputIterator>
map(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

• first：区间起始迭代器
• last：区间结束迭代器（不包含）
• comp：比较器，默认升序
• alloc ：空间配置器，默认

作用：用已有容器或数组的一段区间构造 map。区间元素必须是 pair<Key, T> 类型。

vector<pair<int, string>> v = {{1,"A"}, {2,"B"}};
map<int, string> m(v.begin(), v.end());

pair<int, string> arr[] = {{1,"A"}, {2,"B"}};
map<int, string> m2(arr, arr + 2);

---

// 3. 拷贝构造
// 用已有 map 拷贝构造一个新 map
map(const map& x);

x：另一个同类型的 map 对象
作用：深拷贝已有 map，两个对象完全独立。

map<int, string> m1 = {{1,"A"}, {2,"B"}};
map<int, string> m2(m1);   // m2 是 m1 的副本

---

// 4. initializer_list 构造（C++11）
// 用花括号列表直接初始化 map
map(initializer_list<value_type> il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

• il：初始化列表，格式 { {key1,val1}, {key2,val2}, ... }
• comp：比较器，默认升序
• alloc：空间配置器，默认

作用：用花括号列表直接初始化 map，最常用的构造方式。

map<int, string> m = {{1,"A"}, {3,"C"}, {2,"B"}};   // 自动按 key 排序

---

#define _CRT_SECURE_NO_WARNINGS 1
#include <map>
#include<iostream>
#include<string>
using namespace std;

int main()
{
    // 1. 无参默认构造 
    // 创建一个空的 map，默认按 key 升序排列
    map<int, string> m1;
    m1[1] = "苹果";
    m1[3] = "香蕉";
    m1[2] = "橘子";
    cout << "m1: ";
    for (auto& kv : m1)
        cout << kv.first << ":" << kv.second << " ";  
    cout << endl;

    //2. 迭代器区间构造
    // 用已有容器的一段区间构造 map
    map<int, string> temp;
    temp[1] = "A";
    temp[2] = "B";
    temp[3] = "C";
    map<int, string> m2(temp.begin(), temp.end());
    cout << "m2: ";
    for (auto& kv : m2)
        cout << kv.first << ":" << kv.second << " ";  
    cout << endl;

    // 也可以用数组构造（需要构造 pair 数组）
    pair<int, string> arr[] = {
        {1, "甲"},
        {3, "丙"},
        {2, "乙"}
    };
    map<int, string> m3(arr, arr + 3);
    cout << "m3: ";
    for (auto& kv : m3)
        cout << kv.first << ":" << kv.second << " "; 
    cout << endl;

    // 3. 拷贝构造
    // 用已有的 map 拷贝一份
    map<int, string> m4(m3);
    cout << "m4: ";
    for (auto& kv : m4)
        cout << kv.first << ":" << kv.second << " ";
    cout << endl;

    // 4. initializer_list 构造（C++11）
    // 用花括号列表直接初始化
    map<int, string> m5 = {
        {3, "三"},
        {1, "一"},
        {2, "二"}
    };
    cout << "m5: ";
    for (auto& kv : m5)
        cout << kv.first << ":" << kv.second << " ";  
    cout << endl;

    //  5. 指定降序（传入比较器）
    map<int, string, greater<int>> m6 = {
        {3, "三"},
        {1, "一"},
        {2, "二"}
    };
    cout << "m6(降序): ";
    for (auto& kv : m6)
        cout << kv.first << ":" << kv.second << " ";  
    cout << endl;

    //  6. 自定义类型作为 key
    struct Student
    {
        int id;
        string name;
    };

    struct CmpStudent
    {
        bool operator()(const Student& a, const Student& b) const
        {
            return a.id < b.id;
        }
    };

    map<Student, int, CmpStudent> m7 = {
        {{1001, "张三"}, 90},
        {{1003, "王五"}, 85},
        {{1002, "李四"}, 88}
    };
    cout << "m7(自定义排序): ";
    for (auto& kv : m7)
    {
        cout << kv.first.id << ":" << kv.first.name
            << "-->" << kv.second << "分 ";
    }
    cout << endl;

    return 0;
}

---

c.map的迭代器

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    map<int, string> m = { {1, "张三"}, {2, "李四"}, {3, "王五"}, {4, "赵六"} };

    //正向迭代器 begin() / end() 
    cout << "正向遍历（升序）: ";
    for (map<int, string>::iterator it = m.begin(); it != m.end(); ++it)
    {
        cout << it->first << ":" << it->second << " ";
    }
    cout << endl;

    // 反向迭代器 rbegin() / rend()
    cout << "反向遍历（降序）: ";
    for (map<int, string>::reverse_iterator rit = m.rbegin(); rit != m.rend(); ++rit)
    {
        cout << rit->first << ":" << rit->second << " ";
    }
    cout << endl;

    return 0;
}

---

d. map的容量与元素访问

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    map<int, string> m;

    // =empty()：判断是否为空
    cout << "刚创建时是否为空: " << m.empty() << endl; 

    m[1] = "张三";
    m[2] = "李四";
    m[3] = "王五";

    cout << "插入元素后是否为空: " << m.empty() << endl;  

    //  size()：返回元素个数
    cout << "当前元素个数: " << m.size() << endl; 

    m[4] = "赵六";
    cout << "插入赵六后个数: " << m.size() << endl; 

    m[2] = "李四2";  // 修改已有元素，个数不变
    cout << "修改key=2后个数: " << m.size() << endl;  

    //operator[]：访问/修改value 
    cout << "\n====== operator[] 使用 ======" << endl;

    // 1. 读取已有元素
    cout << "m[1] = " << m[1] << endl;   
    cout << "m[3] = " << m[3] << endl;    

    // 2. 修改已有元素
    m[1] = "张三修改版";
    cout << "修改后 m[1] = " << m[1] << endl;  

    // 3. 插入新元素（key不存在时自动插入）
    m[5] = "孙七";  // key=5 不存在，自动插入
    cout << "插入key=5后: ";
    for (auto& kv : m)
        cout << kv.first << ":" << kv.second << " ";
    cout << endl;

    // 4. operator[] 访问不存在的key-->会插入默认值
    cout << "访问不存在的key=10: " << m[10] << endl; 
    cout << "访问后元素个数: " << m.size() << endl;    

    return 0;
}

---

那如果当 key 不在 map 中时，通过 operator 获取对应 value 时会发生什么问题？

注意：在元素访问时，有一个与 operator[] 类似的操作 at() 函数（该函数不常用），都是通过 key 找到与其对应的 value 然后返回其引用。

两者的区别在于：

当 key 不存在时，operator[] 会用默认 value 与 key 构造键值对然后插入，并返回该默认 value 的引用；

而 at() 函数会直接抛出异常（out_of_range），不会插入新元素。

---

e. map中元素的修改

#include <string>
#include <map>
#include <iostream>
using namespace std;
 
void TestMap()
{
    map<string, string> m;
 
    // 向map中插入元素的方式：
    // 将键值对<"cat","猫咪">插入map中，用pair直接来构造键值对
    m.insert(pair<string, string>("cat", "猫咪"));
 
    // 将键值对<"dog","狗狗">插入map中，用make_pair函数来构造键值对
    m.insert(make_pair("dog", "狗狗"));
 
    // 借用operator[]向map中插入元素
    /*
    operator[]的原理是：
    用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
    如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
    如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
    operator[]函数最后将insert返回值键值对中的value返回
    */
 
    // 将<"bird", "">插入map中，插入成功，返回value的引用，将"小鸟"赋值给该引用结果
    m["bird"] = "小鸟";
 
    // key不存在时抛异常
    // m.at("fish") = "鱼儿";
    cout << "当前元素个数：" << m.size() << endl;
 
    // 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
    cout << "遍历map元素：" << endl;
    for (auto& e : m)
        cout << e.first << "--->" << e.second << endl;
    cout << endl;
 
    // map中的键值对key一定是唯一的，如果key存在将插入失败
    auto ret = m.insert(make_pair("cat", "猫猫"));
    if (ret.second)
        cout << "<cat, 猫猫>不在map中，已经插入" << endl;
    else
        cout << "键值为cat的元素已经存在：" << ret.first->first << "--->" << ret.first->second << "，插入失败" << endl;
 
    // 删除key为"bird"的元素
    m.erase("bird");
 
    if (1 == m.count("bird"))
        cout << "bird还在" << endl;
    else
        cout << "bird已被删除" << endl;
}
 
int main()
{
    TestMap();
    return 0;
}

---

operator[] 函数介绍：

map::operator= - C++ Reference

前面学习的 vector 容器里面的 vector::operator[] 是传入元素下标，返回对该元素的引用。而 map 中的 operator[] 访问元素函数，和其它容器有挺大区别的，已经不是传统的数组下标访问了。

map 的 operator[] 底层实际上调用的是 insert() 函数

map::operator[] 工作原理说明

map 容器中的 map::operator[] 接收一个键值 key，通过该 key 在 map 中查找并判断该元素是否存在：

• 如果 key 存在：说明 insert 插入失败，insert 函数返回的 pair 对象中会带出指向该元素的迭代器。通过这个迭代器，可以获取该元素 key 对应的映射值 value，然后函数返回该 value 的引用。

• 如果 key 不存在：说明 insert 插入成功，此时会插入一个新元素 <key, value()>，然后函数返回其对应映射值 value 的引用。

注意：插入新元素时，value() 是一个缺省值，它是调用 value 类型的默认构造函数构造出来的一个匿名对象。例如，如果 value 是 string 类型，就会调用 string 的默认构造函数，生成一个空字符串。

operator[] 总结

使用 map::operator[] 传入一个键值 key，它的行为如下：

• 如果 key 在 map 中，直接返回该 key 对应映射值 value 的引用。

• 如果 key 不在 map 中，会自动插入一个新元素 <key, value()>，然后返回该 key 对应映射值 value 的引用。

拿到函数返回的映射值 value 引用后，我们可以直接对其进行读取或修改操作。

map<string, string> dict;
 
// 这里的意思是：先插入 pair("apple", "")，再修改 "apple" 对应的 value 值为 "苹果"
dict["apple"] = "苹果";
 
// 等价于：
dict["apple"];           // 第一次访问 key 不存在 --> 插入 pair("apple", "")
dict["apple"] = "苹果";  // key 这是时候就已存在 --> 修改其 value 为 "苹果"

---

map::at() 与 operator[] 的对比

类似的成员函数 map::at() 在元素存在时和 map::operator[] 具有相同的行为，区别在于，当元素不存在时 map::at() 会抛出异常（std::out_of_range），而 operator[] 则会插入新元素。

operator[] 能读能写还能凭空造元素，at() 只负责查，查不到就报错。

---

insert函数介绍

map::insert - C++ Reference

功能说明：

向 map 中插入键值对（pair 对象）时，insert 会先通过该元素的 key 查找并判断是否存在于 map 中：

• 如果 key 已经存在，插入失败，返回一个 pair 对象：<指向该元素的迭代器, false>。

• 如果 key 不存在，插入成功，返回一个 pair 对象：<指向新插入元素的迭代器, true>。

这里的 bool 值表示插入是否成功。

---

举例：实现英汉字典

下面实现一个简单的英汉字典，通过英文单词查找对应的中文含义。

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
    // 定义字典
    map<string, string> dict;

    // 向字典中插入单词的两种方式 

    // 方式一：直接构造 pair 匿名对象（写法略繁琐）
    dict.insert(pair<string, string>("sort", "排序"));

    // 方式二：用 make_pair 构造 pair 对象（更简洁，推荐）
    dict.insert(make_pair("left", "左边"));
    dict.insert(make_pair("tree", "树"));

    //遍历字典输出所有单词 

    // 正确写法：通过迭代器遍历
    for (auto it = dict.begin(); it != dict.end(); ++it)
    {
        // it 指向一个键值对，通过 -> 访问 first 和 second
        cout << it->first << " : " << it->second << endl;
    }

    return 0;
}

遍历 map 的注意事项

用迭代器遍历 map 元素时，写法上和其他容器有些不同。下面这种写法是错误的：

//  错误写法
for (auto it = dict.begin(); it != dict.end(); ++it)
{
    cout << *it << endl; 
}

原因：it 是当前元素的迭代器，解引用 *it 得到的是一个 pair<const string, string> 对象（键值对），而 map 中没有对 pair 类型重载流插入运算符 <<，编译器不知道该如何输出这个键值对，所以会报错。

正确写法：通过 it->first 获取键，it->second 获取值，分别输出即可。

//  正确写法
for (auto it = dict.begin(); it != dict.end(); ++it)
{
    cout << it->first << " : " << it->second << endl;
}

或者使用更简洁的范围 for：

//  也可以用范围 for
for (auto& kv : dict)
{
    cout << kv.first << " : " << kv.second << endl;
}

---

迭代器遍历map元素的两种方式：

// 迭代器遍历map
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{  
    /* 1、迭代器是像指针一样的类型
    * 对当前元素的迭代器it解引用(*it)可以得到当前节点中存储的数据：即pair对象(键值对)，然后用'.'再去访问pair对象中的kv值
    * 这里调用的是it.operator*() 解引用运算符重载函数，返回值为：pair对象的引用
    */
    cout << (*it).first << ", " << (*it).second << endl;
 
    /* 2、迭代器箭头->，返回当前迭代器指向j的地址(指针)：pair<string, int>*，实际上是调用的operator->()函数
    * 该指针再使用'->'就可以取到(pair对象)里面的kv值，即first和second
	* 代码为：it->->first，但可读性太差，编译器进行了特殊处理，省略掉了一个箭头，保持了程序的可读性
    */
    // 一般结构体的指针才会使用'->'来访问成员，所以当迭代器管理的节点中的数据是结构体的时候，就可以用'->'
    cout << it->first << ", " << it->second << endl; // 常用这种写法
    it++;
}

---

举例：统计单词出现的次数

法一，定义 map，遍历 str，向 map 中插入元素（键值对）：

string fruits[] = { "apple", "apple", "banana", "apple", "orange", "banana", "apple", "orange" };
 
// 定义map，用于统计每种水果出现的次数
map<string, int> fruitCount;
 
// 遍历数组，统计每个单词出现的次数
for (auto& e : fruits)  // 传引用，避免string深拷贝
{
    // 先查找当前水果是否已经在map中
    auto ret = fruitCount.find(e);
    if (ret == fruitCount.end())  // 没找到，说明第一次出现
    {
        fruitCount.insert(make_pair(e, 1));  // 插入<水果名, 1>
    }
    else  // 找到了，说明之前出现过
    {
        ret->second++;  // 对应水果的出现次数+1
    }
}
 
// 遍历map，打印每种水果及其出现次数
for (auto& e : fruitCount)
{
    cout << e.first << " : " << e.second << "次" << endl;
}

这个说法法，先查找当前单词是否在 map 中，如果不在，则插入，但是在插入函数内又会查找一次，找到插入的位置，有点冗余。

---

法二：插入元素时，insert 本来就有查找功能：

void test_map()
{
    string fruits[] = { "apple", "apple", "banana", "apple", "orange", "banana", "apple", "orange" };
    
    // 定义map，统计每种水果出现次数
    map<string, int> count_map;
 
    // 遍历数组
    for (auto& e : fruits)
    {
        // 尝试插入<水果, 1>，返回值是一个pair对象
        auto ret = count_map.insert(make_pair(e, 1));
        // insert返回值类型：pair<map<string, int>::iterator, bool>
        // 其中：iterator 指向该key对应的元素，bool 表示插入是否成功
 
        // 插入失败，说明该水果已存在
        // 此时返回的pair对象为：<指向该元素的迭代器, false>
        if (ret.second == false)
        {
            // 通过迭代器将其出现次数 +1
            (ret.first)->second++;
        }
    }
 
    // 遍历map，输出每种水果及其出现次数
    for (auto& e : count_map)
    {
        cout << e.first << " : " << e.second << "次" << endl;
    }
}

---

法三：

使用 map::operator[] 时，传入键值 key，它会自动判断：

• 如果 key 存在，直接返回对应 value 的引用

• 如果 key 不存在，插入新元素 <key, value()>（value() 为默认值），再返回其引用

这样一来，无论是新插入还是已存在，我们拿到的都是该键对应 value 的引用，可以直接对其进行操作。基于这个特性，统计水果出现次数的代码可以大幅简化：

string words[] = { "apple", "apple", "banana", "apple", "orange", "banana", "apple", "orange" };

// 定义map，用于统计单词出现次数
map<string, int> wordCount;

// 使用 operator[] 统计
// 原理：key存在则返回value引用，不存在则插入<key, 0>再返回引用
for (auto& e : words)
{
    wordCount[e]++;   // 无论是否存在，直接将对应次数加1
}

// 遍历map，打印 <单词, 出现次数>
for (auto& e : wordCount)
{
    cout << e.first << " : " << e.second << "次" << endl;
}

---

map 总结

• map 中的元素是键值对（pair 结构体），由 key 和 value 两部分组成

• key 在 map 中是唯一的，并且不能被修改（只能修改 key 对应的映射值 value）

• 元素默认按照 key 的小于（<） 关系进行排序，即升序

• 使用迭代器遍历 map 时，可以得到一个有序序列（按 key 升序）

• map 的底层采用平衡搜索树（红黑树） 实现，查找效率较高，时间复杂度为 O(logN)

• 支持 operator[] 操作符，底层通过查找 + 插入实现：传入 key，即可找到并返回对应的 value 引用

---

5.multiset

multiset - C++ Reference

multiset 介绍

• multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。
   
• multiset 中，元素的 value 也会识别它（因为 multiset 中本身存储的就是 <value, value> 组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T），multiset 元素的值不能在容器中进行修改（因为元素总是 const 的），但可以从容器中插入或删除。
• 在内部，multiset 中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。
• multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列。
• multiset 底层结构为二叉搜索树（红黑树）。

---

注意事项

• multiset 在底层存储的是 <value, value> 键值对，value 既是键也是值

• 插入时只需传入 value 即可，不需要构造键值对

• 与 set 的区别：multiset 中的元素可以重复，而 set 中的元素是唯一的

• 使用迭代器遍历 multiset 可以得到有序序列（默认升序）

• multiset 中的元素不能被修改（迭代器为常量迭代器）

• 查找某个元素的时间复杂度为 O(logN)

• multiset 的主要作用：对元素进行排序（允许重复元素）

---

6.multiset的使用

这里给大家只简单演示 set 与 multiset 的不同，其他接口接口与 set 相同，可以参考前面我讲的set。

#include <set>
 
void TestMultiset()
{
    int nums[] = { 5, 2, 3, 7, 5, 8, 5, 9, 5, 6 };
    // multiset 在底层实际存储的是 <int, int> 的键值对
    multiset<int> ms(nums, nums + sizeof(nums)/sizeof(nums[0]));
 
    for (auto& e : ms)
        cout << e << " ";
    cout << endl;
    // 输出：2 3 5 5 5 5 6 7 8 9
 
    cout << ms.count(5) << endl;  // 运行结果：4（5出现了4次）
    cout << ms.count(3) << endl;  // 运行结果：1（3出现了1次）
 
    return 0;
}

---

7.multimap

大致内容：

• Multimaps 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对<key, value>，其中多个键值对之间的 key 是可以重复的。
• 在 multimap 中，通常按照 key 排序和唯一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对：typedef pair<const Key, T> value_type;
• 在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。
• multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。
• multimap 在底层用二叉搜索树（红黑树）来实现。
   

强调：multimap 和 map 的唯一不同就是：map 中的 key 是唯一的，而 multimap 中的 key 是可以重复的。

---

8.multimap的使用

multimap 和 map 的用法基本一致，核心区别在于：multimap 中的 key 是可以重复的。其他方面和 map 类似：

1.元素默认按照 key 的小于（<） 关系进行排序

2.底层同样采用红黑树实现

3.使用迭代器遍历可以得到有序序列

和 map 一样，使用时需要包含头文件 #include <map>。

---

问题补充：为什么 multimap 没有 operator[]？

multimap 中没有重载 operator[] 操作符。

原因在于：operator[] 是通过 key 来查找并返回对应的 value，但 multimap 中同一个 key 可能对应多个 value，此时无法确定返回哪一个，所以该操作没有实际意义。

因此，multimap 只提供了通过迭代器访问元素的方式，如 find()、lower_bound()、upper_bound()、equal_range() 等函数。

---

代码如下：

#include <iostream>
#include <map>
using namespace std;

int main()
{
    // 一个学生可以选修多门课程
    multimap<string, string> courses;

    // 插入数据（key允许重复）
    courses.insert(make_pair("张三", "语文"));
    courses.insert(make_pair("李四", "数学"));
    courses.insert(make_pair("张三", "英语"));
    courses.insert(make_pair("张三", "数学"));
    courses.insert(make_pair("李四", "语文"));

    // 遍历输出（按key升序）
    cout << "所有选课记录: " << endl;
    for (auto& e : courses)
    {
        cout << e.first << " : " << e.second << endl;
    }

    // 统计"张三"选了几门课
    cout << "张三选了 " << courses.count("张三") << " 门课" << endl;

    // 查找"张三"的所有课程
    auto range = courses.equal_range("张三");
    cout << "张三的课程: ";
    for (auto it = range.first; it != range.second; ++it)
    {
        cout << it->second << " ";
    }
    cout << endl;

    return 0;
}