set和map

补充：序列容器和关联容器

序列容器与关联容器对比表

对比维度 序列容器（Sequence Containers） 关联容器（Associative Containers）
核心特性 以插入顺序存储元素，元素的位置由插入时机和方式决定，不自动排序 以键（Key） 为核心组织元素，元素按键的预设规则（默认升序）自动排序，位置与插入顺序无关
底层数据结构 - vector：动态数组（连续内存）
- list：双向链表（非连续内存）
- deque：双端队列（分段连续内存）
- array：固定大小数组（连续内存）		 - set/multiset：红黑树（平衡二叉搜索树）
- map/multimap：红黑树（键值对映射）
- unordered_*：哈希表（链地址法解决冲突）
元素访问方式 1. 下标访问（vector/array/deque，支持[]和at()）
2. 迭代器访问（所有序列容器）
3. 前端/后端访问（front()/back()，除array外）		 1. 键访问（map/unordered_map支持[]和at()，通过键找值）
2. 迭代器访问（按排序/哈希桶顺序遍历）
3. 不可通过下标直接访问位置（无“位置”概念）
插入/删除效率 - vector：尾部插入/删除O(1)，中间/头部插入/删除O(n)（需移动元素）
- list：任意位置插入/删除O(1)（只需修改指针）
- deque：两端插入/删除O(1)，中间O(n)		 - 有序关联容器（set/map）：插入/删除O(log n)（红黑树旋转维护平衡）
- 无序关联容器（unordered_*）：平均O(1)，最坏O(n)（哈希冲突严重时）
查找效率 - 按值查找：O(n)（需遍历所有元素，vector可通过find()算法实现）
- 按位置查找：O(1)（vector/array/deque的下标访问）		 - 按键查找：
- 有序关联容器：O(log n)（红黑树二分查找）
- 无序关联容器：平均O(1)，最坏O(n)
- 按值查找（set除外）：需遍历，效率低
元素唯一性 允许重复元素，无自动去重机制（需手动通过unique()等算法处理） - set/map：键唯一，插入重复键会失败（返回pair标记）
- multiset/multimap：键可重复，允许插入多个相同键的元素
内存占用 - vector：可能存在内存冗余（预分配空间，capacity()> size()）
- list：每个元素需额外存储前后指针，内存开销大
- array：无冗余，固定大小		 - 有序关联容器：红黑树节点需存储键、值、颜色、父子指针，内存开销较大
- 无序关联容器：哈希表需维护桶数组和链表节点，且存在负载因子冗余
适用场景 1. 需要按插入顺序访问元素（如日志记录）
2. 需要频繁随机访问元素（如数组计算，选vector）
3. 需要频繁在中间插入/删除（如链表操作，选list）		 1. 需要按键快速查找/插入/删除（如字典、缓存，选unordered_map）
2. 需要按键排序的场景（如排行榜、有序映射，选map）
3. 需要存储唯一值集合（如去重，选set）
典型容器示例 vector、list、deque、array、forward_list（单向链表） set、multiset、map、multimap、unordered_set、unordered_multiset、unordered_map、unordered_multimap

一.set（集合）

set包含在头文件中

1.set的概念

set的中文翻译是集合的意思，没错就是高中数学中的那个集合
集合是按照特定顺序存储唯一元素的容器。
set包含在头文件<set>中

  1. 元素特性：

    • 元素的值即其自身的键（T类型）
    • 每个值必须唯一，不允许重复
    • 元素值在容器中无法修改（始终为常量），但支持插入和删除操作

  2. 内部排序：

    • 元素始终按照内部比较对象（Compare类型）的特定严格弱排序标准进行排序
    • 排序规则在容器定义时确定

  3. 性能对比：

    • 与unordered_set相比，通过key访问元素的速度较慢
    • 优势在于支持根据元素顺序直接迭代访问子集

  4. 实现方式：

    • 通常基于二叉搜索树实现（标准中未强制规定，但实际实现多采用红黑树等平衡二叉搜索树）

2.set的构造和迭代器

// set容器的类模板定义
template < 
    class T,                  // 元素类型，既是键类型也是值类型（key_type = value_type = T）
    class Compare = less<T>,  // 比较器类型，默认使用less<T>（小于比较），用于元素排序
    class Alloc = allocator<T>// 分配器类型，默认使用标准分配器，用于内存管理
> class set;

// (1) 无参默认构造函数
// 功能：创建一个空的set容器
// 参数：
//   - comp：比较器对象，用于指定排序规则，默认使用Compare类型的默认构造对象
//   - alloc：分配器对象，用于内存分配，默认使用Alloc类型的默认构造对象
explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

// (2) 迭代器区间构造函数（模板函数）
// 功能：通过迭代器区间[first, last)中的元素创建set容器
// 参数：
//   - first/last：输入迭代器，指定元素来源的区间（左闭右开）
//   - comp：比较器对象，同(1)
//   - alloc：分配器对象，同(1)
template <class InputIterator>
set (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& = allocator_type());
 
// (3) 拷贝构造函数
// 功能：通过拷贝另一个set容器x创建新的set容器
// 参数：x - 被拷贝的set容器
set (const set& x);

// (5) 初始化列表构造函数
// 功能：通过初始化列表il中的元素创建set容器
// 参数：
//   - il：initializer_list类型的元素列表
//   - comp：比较器对象，同(1)
//   - alloc：分配器对象，同(1)
set (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
 
// 迭代器特性说明：
// set的迭代器是双向迭代器，且指向的元素是常量（value_type为const T）
// 即无法通过迭代器修改容器中的元素值
iterator -> a bidirectional iterator to const value_type

// 正向迭代器相关函数
iterator begin();  // 返回指向容器第一个元素的迭代器
iterator end();    // 返回指向容器尾后位置（最后一个元素的下一个位置）的迭代器

// 反向迭代器相关函数
reverse_iterator rbegin();  // 返回指向容器最后一个元素的反向迭代器
reverse_iterator rend();    // 返回指向容器首前位置（第一个元素的前一个位置）的反向迭代器

3.set的增删查

为什么set不能修改元素呢？
set 不能修改元素，主要因为：

  1. 它是有序容器，元素值决定排序位置，修改会破坏内部有序性
  2. 底层通常是红黑树，值的改变会导致整个树结构失效
  3. 迭代器被设计为常量类型，从接口上禁止修改

如需更新元素，需先删除旧元素，再插入新元素。

3.1 set关于增删查的接口

// 成员类型定义
key_type    -> 第一个模板参数(T)，即键的类型
value_type  -> 第一个模板参数(T)，即元素的值类型（set中键和值类型相同）


// 插入操作

// 单个元素插入
// 功能：向容器中插入元素val
// 返回值：pair对象，其中iterator指向插入的元素（或已存在的相同元素），bool表示是否插入成功
// 说明：如果val已存在，插入失败，返回已存在元素的迭代器和false
pair<iterator, bool> insert(const value_type& val);

// 初始化列表插入
// 功能：插入初始化列表il中的所有元素
// 说明：对于列表中已存在于容器的元素，不会重复插入
void insert(initializer_list<value_type> il);

// 迭代器区间插入
// 功能：插入[first, last)区间内的所有元素
// 说明：区间中已存在于容器的元素，不会重复插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);


// 查找操作

// 查找元素
// 功能：查找值为val的元素
// 返回值：若找到，返回指向该元素的迭代器；否则返回end()
iterator find(const value_type& val);

// 计数元素
// 功能：统计值为val的元素个数
// 返回值：计数结果（set中只能是0或1，因为元素唯一）
size_type count(const value_type& val) const;


// 删除操作

// 按位置删除
// 功能：删除迭代器position指向的元素
// 返回值：指向被删除元素下一个位置的迭代器
iterator erase(const_iterator position);

// 按值删除
// 功能：删除值为val的元素
// 返回值：删除的元素个数（set中只能是0或1）
size_type erase(const value_type& val);

// 按区间删除
// 功能：删除[first, last)区间内的所有元素
// 返回值：指向被删除区间最后一个元素下一个位置的迭代器
iterator erase(const_iterator first, const_iterator last);


// 边界操作

// 下界查找
// 功能：查找第一个大于等于val的元素
// 返回值：指向该元素的迭代器
iterator lower_bound(const value_type& val) const;

// 上界查找
// 功能：查找第一个大于val的元素
// 返回值：指向该元素的迭代器
iterator upper_bound(const value_type& val) const;

3.2测试代码

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


void set_test()
{
    // 创建一个包含重复元素的vector
    vector<int> v = { 1,5,4,3,7,9,8,2,6,8,2,6 };

    // 用vector的元素初始化set（自动去重并排序）
    set<int> s(v.begin(), v.end());

    // 插入元素0
    s.insert(0);

    // 遍历输出set中的元素（此时应为0,1,2,3,4,5,6,7,8,9）
    for (auto e : s) cout << e << " ";
    cout << endl;

    // 查找元素7
    auto it = s.find(7);
    // 输出迭代器类型信息（不同编译器可能显示不同）
    cout << typeid(it).name() << endl;
    // 输出找到的元素值
    cout << *it << endl;

    // 删除元素2和0
    s.erase(2);
    s.erase(0);

    // 再次遍历输出（此时应为1,3,4,5,6,7,8,9）
    for (auto e : s) cout << e << " ";
    cout << endl;

    // 使用 lower_bound 查找第一个大于等于5的元素
    // 此时集合中元素为1,3,4,5,6,7,8,9，预期结果为5
    auto lowerIt = s.lower_bound(5);
    if (lowerIt != s.end()) {  // 检查迭代器是否有效（未指向末尾）
        cout << "lower_bound(5) found: " << *lowerIt << endl;
    }
    else {
        cout << "lower_bound(5) not found" << endl;
    }

    // 使用 upper_bound 查找第一个大于6的元素
    // 此时集合中元素为1,3,4,5,6,7,8,9，预期结果为7
    auto upperIt = s.upper_bound(6);
    if (upperIt != s.end()) {  // 检查迭代器是否有效
        cout << "upper_bound(6) found: " << *upperIt << endl;
    }
    else {
        cout << "upper_bound(6) not found" << endl;
    }
}

int main() {
    set_test();  // 调用测试函数
    return 0;
}

二.multiset(多重集合)

1.multiset介绍

multiset包含在头文件<set>中

#include <iostream>
#include <set>
#include <iomanip>  // 用于格式化输出
using namespace std;

int main()
{
    // multiset特性1：排序但不去重（与set的核心区别）
    multiset<int> ms = {4, 2, 7, 2, 4, 8, 4, 5, 4, 9};
    
    // 输出初始集合（已排序但保留重复元素）
    cout << "初始multiset元素（排序但不去重）: ";
    for (auto val : ms) {
        cout << val << " ";
    }
    cout << "\n----------------------------------------\n";
    
    // 提示用户输入要查找的值
    int x;
    cout << "请输入要查找的整数: ";
    cin >> x;
    
    // multiset特性2：find()返回第一个匹配元素的迭代器（中序遍历的第一个）
    auto pos = ms.find(x);
    if (pos != ms.end()) {
        cout << "找到的所有值为" << x << "的元素: ";
        // 遍历所有相同元素（利用有序特性）
        while (pos != ms.end() && *pos == x) {
            cout << *pos << " ";
            ++pos;
        }
        cout << endl;
        
        // multiset特性3：count()返回元素的实际出现次数（set中只能是0或1）
        cout << "值为" << x << "的元素出现次数: " << ms.count(x) << endl;
        
        // multiset特性4：erase(值)会删除所有匹配元素（set中最多删除1个）
        size_t erased = ms.erase(x);
        cout << "成功删除" << erased << "个值为" << x << "的元素\n";
        
        // 输出删除后的集合
        cout << "删除后剩余元素: ";
        for (auto val : ms) {
            cout << val << " ";
        }
        cout << endl;
    } else {
        cout << "集合中不存在值为" << x << "的元素" << endl;
    }
    
    return 0;
}

2.multiset与set对比

对比维度 set multiset
元素唯一性 元素值唯一，不允许重复 元素值可重复，支持冗余存储
insert() 返回值 返回 pair<iterator, bool>，bool 表示是否插入成功 只返回新插入元素的迭代器（始终插入成功）
find() 行为 返回唯一匹配元素的迭代器（若存在） 返回第一个匹配元素的迭代器（中序遍历首个）
count() 结果 只返回 0 或 1（存在/不存在） 返回元素实际出现的次数
erase(值) 行为 删除最多 1 个匹配元素，返回 0 或 1 删除所有匹配元素，返回删除的总个数
适用场景 需要存储唯一值集合（如去重、字典键） 需要存储可重复值的有序集合（如统计频次、多重映射）
底层实现 通常基于红黑树（平衡二叉搜索树） 同 set，基于红黑树
排序特性 元素按比较规则自动排序 同 set，元素按比较规则自动排序
元素修改限制 元素不可直接修改（需先删后插） 同 set，元素不可直接修改

三.map（映射表）

1.map介绍

  1. 模板参数说明

    • Key：map 底层关键字（key）的类型，是元素排序和查找的核心依据
    • T：map 底层值（value）的类型，即与关键字关联的数据类型
    • Compare = less<Key>：键的比较器类型，默认用 less<Key>（按 key 升序）；若 Key 不支持默认小于比较，或需自定义排序规则（如降序），可自行实现仿函数传入
    • Alloc = allocator<pair<const Key,T>>：内存分配器类型，负责为 map 存储的键值对（pair<const Key,T>）分配内存；一般无需手动指定，使用默认分配器即可

  2. 底层实现与效率

    • 底层基于红黑树（平衡二叉搜索树）实现，保证树结构的平衡
    • 增、删、查、改操作的时间复杂度均为 O(logN)（N 为元素个数），效率稳定

  3. 迭代器与排序特性

    • 迭代器遍历遵循红黑树的中序遍历规则
    • 遍历结果会按 Key 的比较规则（默认升序）有序排列，即输出序列是按 key 有序的

  4. 参数使用原则

    • 大多数场景下，只需指定前两个模板参数（Key 和 T）
    • 后两个参数（Compare 和 Alloc）仅在特殊需求时使用（如自定义排序、特殊内存管理），默认值可满足常规需求
// map容器的类模板定义
template < 
    class Key,                     // 键（key）的类型，用于元素的查找和排序
    class T,                       // 值（value）的类型，与键关联的数据
    class Compare = less<Key>,     // 键的比较器类型，默认使用less<Key>（小于比较）
                                   // 用于指定键的排序规则，若Key不支持小于比较，需自定义仿函数
    class Alloc = allocator<pair<const Key, T>>  // 分配器类型，默认使用标准分配器
                                                 // 负责管理键值对（pair<const Key, T>）的内存分配
> class map;

/* 补充说明：
1. 模板参数使用：一般情况下无需指定后两个参数（Compare和Alloc），使用默认值即可
2. 键值对特性：每个元素是一个pair<const Key, T>，键（Key）不可修改，值（T）可以修改
*/

2.pair类型介绍

2.1 pair的概念

pair 是 C++ 标准库中的一个模板结构体，主要作用是将两个不同类型的数据组合成一个单一的复合对象，用于表示成对出现且存在关联的数据。

具体用途包括：

  1. 作为 map/unordered_map 的元素类型：存储键值对（key-value），first 成员表示键，second 成员表示值
  2. 函数返回多个值：当需要返回两个相关结果时（如查找结果+状态），可通过 pair 封装
  3. 存储关联性数据：例如坐标（x,y）、区间（start,end）等成对出现的数据
  4. 作为容器元素：可在 vector、list 等容器中存储 pair，形成键值对列表

pair 的优势在于无需自定义结构体就能便捷地处理成对数据，且支持比较运算（按 first 成员优先比较，再比较 second 成员），非常适合需要组合两个数据的场景。

// map中存储的键值对类型定义：first为const Key（不可修改的键），second为T（可修改的值）
typedef pair<const Key, T> value_type;

// pair结构体模板：用于存储两个不同类型的数据（键值对）
template <class T1, class T2>
struct pair 
{
    typedef T1 first_type;   // 第一个元素的类型（通常为键类型）
    typedef T2 second_type;  // 第二个元素的类型（通常为值类型）

    T1 first;  // 第一个元素（在map中为const Key，作为键）
    T2 second; // 第二个元素（在map中为T，作为值）
 
    // 1. 默认构造函数：使用类型的默认构造函数初始化成员
    pair() : first(T1()), second(T2())
    {}
 
    // 2. 带参构造函数：用a初始化first，用b初始化second
    pair(const T1& a, const T2& b) : first(a), second(b)
    {}
 
    // 3. 模板拷贝构造函数：从其他类型的pair复制构造
    // 支持不同但可转换的类型（如pair<int, double>构造pair<long, float>）
    template<class U, class V> 
    pair(const pair<U, V>& pr) : first(pr.first), second(pr.second)
    {}
};

// 辅助函数：便捷创建pair对象（自动推导类型，无需显式指定模板参数）
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{
    return pair<T1, T2>(x, y);  // 返回用x和y初始化的pair对象
}

2.2 pair类代码关键说明：

  1. map与pair的关系：
    map的每个节点数据是pair<const Key, T>类型，其中first是不可修改的键（保证map排序的稳定性），second是可修改的值。

  2. pair的核心作用：
    封装两个关联的数据（键和值），作为map的基本存储单元，实现"键-值"映射关系。

  3. make_pair的优势：
    自动推导参数类型，简化pair对象的创建。例如：
    make_pair(1, "hello") 等价于 pair<int, const char*>(1, "hello")，但写法更简洁。

  4. 构造函数的灵活性：
    支持默认初始化、指定值初始化和跨类型拷贝构造，适应不同场景下的对象创建需求。

3. map的构造

// map容器的构造函数与迭代器接口

// (1) 无参默认构造函数
// 功能：创建一个空的map容器
// 参数：
//   - comp：键的比较器对象，用于指定排序规则（默认使用less<Key>）
//   - alloc：内存分配器对象（默认使用标准分配器）
explicit map (const key_compare& comp = key_compare(),
            const allocator_type& alloc = allocator_type());

// (2) 迭代器区间构造函数（模板函数）
// 功能：通过迭代器区间[first, last)中的键值对创建map容器
// 参数：
//   - first/last：输入迭代器，指向键值对序列的区间（左闭右开）
//   - comp/alloc：同(1)
template <class InputIterator>
map (InputIterator first, InputIterator last,
   const key_compare& comp = key_compare(),
   const allocator_type& = allocator_type());

// (3) 拷贝构造函数
// 功能：通过拷贝另一个map容器x创建新的map
// 参数：x - 被拷贝的map容器
map (const map& x);

// (4) 初始化列表构造函数
// 功能：通过初始化列表il中的键值对创建map容器
// 参数：
//   - il：initializer_list<value_type>类型的键值对列表
//   - comp/alloc：同(1)
map (initializer_list<value_type> il,
   const key_compare& comp = key_compare(),
   const allocator_type& alloc = allocator_type());


// 迭代器特性说明：
// map的迭代器是双向迭代器，指向的元素为value_type（即pair<const Key, T>）
// 注意：通过迭代器只能修改second（值），不能修改first（键），否则会破坏底层红黑树结构
iterator -> a bidirectional iterator to const value_type


// 正向迭代器
iterator begin();  // 返回指向容器第一个键值对的迭代器（按key升序的第一个元素）
iterator end();    // 返回指向容器尾后位置的迭代器（最后一个元素的下一个位置）

// 反向迭代器
reverse_iterator rbegin();  // 返回指向容器最后一个键值对的反向迭代器
reverse_iterator rend();    // 返回指向容器首前位置的反向迭代器


/* 补充说明：
1. 遍历特性：由于底层是红黑树（二叉搜索树），迭代器遍历采用中序遍历，默认按key的升序排列
2. 范围for支持：因支持迭代器，可直接使用范围for循环遍历所有键值对
3. 修改限制：key（first）不可修改，value（second）可修改，保证底层树结构的有序性
*/

4.map的增删查

// map的成员类型定义
key_type       -> 第一个模板参数(Key)，即键的类型
mapped_type    -> 第二个模板参数(T)，即与键关联的值的类型
value_type     -> pair<const key_type, mapped_type>，即键值对类型（键不可修改，值可修改）


// 插入操作

// 单个键值对插入
// 功能：向map中插入键值对val
// 返回值：pair<pair对象，其中iterator指向插入的键值对（或已存在的同键键值对），bool表示是否插入成功
// 说明：若key已存在（无论value是否相同），插入失败
pair<iterator, bool> insert(const value_type& val);

// 初始化列表插入
// 功能：插入初始化列表il中的所有键值对
// 说明：对于列表中已存在于map的key，对应的键值对不会重复插入
void insert(initializer_list<value_type> il);

// 迭代器区间插入
// 功能：插入[first, last)区间内的所有键值对
// 说明：区间中已存在于map的key，对应的键值对不会重复插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);


// 查找操作

// 按key查找
// 功能：查找键为k的键值对
// 返回值：若找到，返回指向该键值对的迭代器；否则返回end()
// 扩展：通过迭代器可访问value（如it->second）并修改
iterator find(const key_type& k);

// 按key计数
// 功能：统计键为k的键值对个数
// 返回值：计数结果（map中只能是0或1，因为key唯一）
size_type count(const key_type& k) const;


// 删除操作

// 按位置删除
// 功能：删除迭代器position指向的键值对
// 返回值：指向被删除元素下一个位置的迭代器
iterator erase(const_iterator position);

// 按key删除
// 功能：删除键为k的键值对
// 返回值：删除的键值对个数（map中只能是0或1）
size_type erase(const key_type& k);

// 按区间删除
// 功能：删除[first, last)区间内的所有键值对
// 返回值：指向被删除区间最后一个元素下一个位置的迭代器
iterator erase(const_iterator first, const_iterator last);


// 边界操作

// 下界查找（非const版本）
// 功能：查找第一个键大于等于k的键值对
// 返回值：指向该键值对的迭代器
iterator lower_bound(const key_type& k);

// 下界查找（const版本）
// 功能：同非const版本，但返回const迭代器（不可通过迭代器修改value）
const_iterator lower_bound(const key_type& k) const;

与set核心差异说明：

  • 与set的主要区别：map插入的是键值对（pair），而set插入的是单一值；通过find找到迭代器后，map可修改对应的值（it->second），而set不能修改元素。
  • key唯一性：map中key唯一，插入已存在的key会失败，这一点与set的元素唯一性一致。
  • 操作特性：查找、删除操作均通过key进行，与set的接口使用方式类似，但map额外提供了对value的访问和修改能力。

5.map的数据修改

5.1 map关于修改的源代码

// 成员类型定义
key_type       -> 第一个模板参数(Key)，即键的类型
mapped_type    -> 第二个模板参数(T)，即与键关联的值的类型
value_type     -> pair<const key_type, mapped_type>，即键值对类型（键为const不可修改）


// 查找操作
// 功能：查找键为k的元素
// 返回值：指向该元素的迭代器；若未找到，返回end()
// 说明：通过迭代器可修改对应的值（it->second）
iterator find(const key_type& k);


// 插入操作
// 功能：插入键值对val（类型为value_type）
// 返回值：pair<iterator, bool>对象
//   - first：指向键对应的迭代器（无论插入成功与否）
//   - second：插入成功为true，失败（键已存在）为false
pair<iterator, bool> insert(const value_type& val);


// 下标访问操作符
// 功能：访问或修改键k对应的值，不存在则插入新键值对
// 返回值：键k对应的值的引用（mapped_type&）
mapped_type& operator[] (const key_type& k);


// operator[]的内部实现逻辑
mapped_type& operator[] (const key_type& k)
{
    // 尝试插入键值对(k, 默认构造的mapped_type对象)
    // 若k已存在，insert返回已有元素的迭代器和false
    // 若k不存在，insert插入新元素并返回新元素的迭代器和true
    pair<iterator, bool> ret = insert({k, mapped_type()});
    
    // 获取指向键k对应元素的迭代器
    iterator it = ret.first;
    
    // 返回该元素的值的引用（可用于修改）
    return it->second;
}

  1. map的修改限制

    • 支持修改 mapped_type 数据（即键值对中的值）
    • 不允许修改 key_type 数据（即键），因为键是底层红黑树排序的依据，修改会破坏树的结构和有序性

  2. 通过迭代器修改值

    • 迭代器遍历过程中，或通过 find() 找到目标键对应的迭代器后，可通过 it->second 修改对应的值
    • 示例：auto it = map.find(key); if (it != map.end()) it->second = new_value;

  3. operator[] 的多功能性

    • 修改功能：若键已存在，map[key] 返回对应值的引用，可直接赋值修改（如 map["name"] = "new"）
    • 插入功能：若键不存在，会自动插入一个新键值对（键为指定值，值为默认构造的 mapped_type 对象）
    • 查找功能：通过 map[key] 可直接访问键对应的值（不存在则触发插入）

  4. 类型命名说明

    • mapped_type：typedef 为模板参数 T，即日常所说的“值”（可修改）
    • value_type：红黑树节点存储的实际类型，为 pair<const key_type, mapped_type>（键为 const，不可修改）
    • 日常使用中，通常将 mapped_type 称为“值”，与直观理解一致

    5.2 insert实现的具体过程

    在这里插入图片描述
    首先，我们可以把 map 的 operator[] 想象成一个“智能储物柜”的操作：

步骤拆解（对应图中流程）

  1. 调用 insert 尝试存东西：
    你用 map[key] 时，相当于告诉 map：“我要存/取 key 对应的东西”。map 内部先执行 insert(make_pair(key, mapped_type())) —— 尝试插入一个键是 key、值是**默认构造的 mapped_type（比如 int 就是 0，string 就是空字符串）**的键值对。

    • 如果 key 之前不存在，就真的插入这个新键值对；
    • 如果 key 已经存在，插入失败，但能找到已有的键值对。

  2. 拿到 insert 返回的“结果包”：
    insert 返回一个 pair<iterator, bool>（图里的 pair<iterator, bool>），这个“结果包”里：

    • first 是一个迭代器（相当于“指向储物柜格子的指针”），指向 key 对应的键值对；
    • second 是 bool（标记插入是否成功，成功为 true，已存在为 false）。

  3. 通过迭代器找到具体格子：
    取“结果包”里的 first（迭代器），解引用它（* 操作），就能拿到 key 对应的键值对 pair<key_type, mapped_type>（图里的 pair<key_type, mapped_type>）。

  4. 取出/修改“值”：
    键值对里的 second 就是我们要的“值”（mapped_type 类型），所以最终返回 second 的引用 —— 这样你就能直接读、写这个“值”了（比如 map["age"] = 20 就是修改，int a = map["age"] 就是读取）。

总结
map[key] 干了两件事：

  • 若 key 不存在，自动插入一个带默认值的键值对，再返回这个默认值的引用（你可以后续修改它）；
  • 若 key 已存在，直接找到已有键值对，返回对应值的引用（供你读或改）。

就像储物柜：第一次存新钥匙，会给你开个新格子放默认物品；下次用同一把钥匙，直接打开已有格子让你取/换物品。

6.map的使用

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    // 创建一个map，键为string类型，值为int类型（姓名->年龄）
    map<string, int> people;

    // 1. 插入元素
    // 方法1：使用insert插入pair
    people.insert(make_pair("Alice", 25));
    people.insert(pair<string, int>("Bob", 30));
    
    // 方法2：使用operator[]插入（更简洁）
    people["Charlie"] = 35;
    people["David"] = 40;

    // 2. 遍历元素（按key自动排序）
    cout << "所有人员信息：" << endl;
    for (const auto& pair : people) {
        // first是key，second是value
        cout << pair.first << " 的年龄是 " << pair.second << endl;
    }
    cout << endl;

    // 3. 查找元素
    string name = "Bob";
    auto it = people.find(name);
    if (it != people.end()) {
        cout << name << " 找到了，年龄是 " << it->second << endl;
    } else {
        cout << name << " 未找到" << endl;
    }
    cout << endl;

    // 4. 修改元素
    // 方法1：通过迭代器修改
    it = people.find("Alice");
    if (it != people.end()) {
        it->second = 26;  // Alice年龄加1
        cout << "修改后，Alice 的年龄是 " << it->second << endl;
    }
    
    // 方法2：通过operator[]修改
    people["Bob"] = 31;  // Bob年龄加1
    cout << "修改后，Bob 的年龄是 " << people["Bob"] << endl;
    cout << endl;

    // 5. 删除元素
    // 方法1：按key删除
    size_t erased = people.erase("David");
    if (erased) {
        cout << "David 已被删除" << endl;
    }
    
    // 方法2：按迭代器删除
    it = people.find("Charlie");
    if (it != people.end()) {
        people.erase(it);
        cout << "Charlie 已被删除" << endl;
    }
    cout << endl;

    // 6. 查看修改后的结果
    cout << "剩余人员信息：" << endl;
    for (const auto& pair : people) {
        cout << pair.first << " 的年龄是 " << pair.second << endl;
    }

    return 0;
}

代码说明：

  1. 创建map：std::map<std::string, int> people 定义了一个键为字符串（姓名）、值为整数（年龄）的map
  2. 插入元素：
    • 使用insert配合make_pair或pair构造函数
    • 使用operator[]更简洁（如people["Charlie"] = 35）
  3. 遍历元素：利用范围for循环，通过pair.first访问键，pair.second访问值
  4. 查找元素：find方法返回迭代器，找到时指向对应键值对，未找到时等于end()
  5. 修改元素：
    • 通过迭代器的second成员修改（it->second = 26）
    • 直接使用operator[]修改（people["Bob"] = 31）
  6. 删除元素：可以按键删除，也可以按迭代器删除

四.multimap(多重映射)

map和multimap对比

对比维度 map multimap
定义与头文件 头文件<map>，是一种关联式容器，存储键值对（key - value），基于红黑树实现，提供快速查找功能 头文件<map>，同样是关联式容器，存储键值对，底层基于红黑树，用于处理键值对关系
键的唯一性 键（key）必须唯一，不允许重复的键存在，否则插入操作会失败 键可以重复，允许多个值与同一个键关联
插入操作 insert() 插入键值对时，若键已存在，插入操作失败，返回一个pair<iterator, bool>，bool值为false ，表示插入未成功 insert() 无论键是否重复，都能成功插入键值对
查找操作 使用find() 方法，若找到对应键，返回指向该键值对的迭代器；若未找到，返回end()迭代器。因为键唯一，count() 方法返回值只能是0或1 find() 方法返回第一个匹配键的迭代器；count() 方法返回键出现的次数
删除操作 erase(key) 方法删除指定键的键值对，若键存在，返回1，否则返回0；erase(position) 删除指定位置的键值对 erase(key) 方法删除所有匹配键的键值对，返回删除的元素个数；erase(position) 同样用于删除指定位置的键值对
修改操作 不支持直接修改键值，因为修改键会破坏红黑树的有序结构。但可以通过迭代器修改值（it->second = new_value）；也能使用operator[] 来访问和修改值（前提是键存在） 不支持直接修改键值。由于键可重复，不能像map 一样使用operator[] 操作符
使用场景 适用于需要确保键唯一，实现一对一映射关系的场景，如学生学号与成绩的映射 适用于一个键对应多个值的场景，比如一个单词对应多个释义
性能特点 插入、删除、查找操作的平均时间复杂度都是 O ( log ⁡ n ) O(\log n) O(logn)，n 为容器中元素的个数，由于键唯一，在查找和插入时会有键是否重复的判断 插入、删除、查找操作的平均时间复杂度同样是 O ( log ⁡ n ) O(\log n) O(logn) ，但因为键可重复，在插入和删除所有匹配键的元素时，可能会涉及多个节点的操作
迭代器遍历 迭代器遍历按键的升序（默认情况，可自定义比较规则）顺序进行 迭代器遍历也按键的升序（默认情况，可自定义比较规则）顺序进行
# c++ # 开发语言 # 学习
Logo
AI大模型技术社区

分享最新、最前沿的AI大模型技术，吸纳国内前几批AI大模型开发者

更多推荐

cover

全能播 LiveOmni：东南亚跨境电商 AI 直播系统的技术落地与实操优化

avatar AI大模型技术社区
cover

Mendix Workflow你可能不知道的 5 个卓越功能

avatar AI大模型技术社区
cover

为什么你的自动化总失败？2026年配置秘籍

avatar AI大模型技术社区