C++ STL 容器详解：map 与 set 原理及实战

4. Insert 和迭代器遍历使用样例

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

int main() {
    // 去重 + 升序排序
    set<int> s1;
    // 去重 + 排降序 (传一个大于的仿函数)
    set<int, greater<int>> s2;
    
    s2.insert(1); s2.insert(4); s2.insert(-2); s2.insert(100);
    
    // 使用迭代器遍历
    for (auto it = s2.begin(); it != s2.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 使用范围 for 打印
    for (const auto& e : s2) {
        cout << e << " ";
    }
    cout << endl;
    
    // 支持插入一段 initializer_list 列表值，已经存在的值插入失败
    s2.insert({2, 3, 4, 5});
    
    // set 里面存入 string 类型的值
    set<string> strset = {"sort", "animal", "list", "young"};
    for (const auto& e : strset) {
        cout << e << " ";
    }
    return 0;
}

5. Find 和 Erase 使用样例

erase 删除成功就返回 1，删除失败就返回 0。

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

int main() {
    set<int> s = {1, 4, 0, 34, 12, 56};
    
    // 1. 利用迭代器进行删除，删除最小值
    s.erase(s.begin());
    
    // 2. 直接输入 x，删除 x
    int x = 0;
    cin >> x;
    int num = s.erase(x);
    if (num == 0) {
        cout << x << "不存在!" << endl;
    }
    
    // 3. 先查找再利用迭代器去删除
    int y = 0;
    cin >> y;
    auto pos = s.find(y);
    if (pos != s.end()) {
        s.erase(pos);
    } else {
        cout << "不存在！" << endl;
    }
    
    // 利用 count 间接实现快速查找
    cin >> x;
    if (s.count(x)) {
        cout << x << "在！" << endl;
    } else {
        cout << x << "不存在！" << endl;
    }
    return 0;
}

Lower_bound + Upper_bound

这两个接口常用于查找区间。lower_bound 返回 >= val 的第一个位置，upper_bound 返回 > val 的第一个位置。两者结合可以处理 [left, right) 区间的操作。

6. Multiset 和 Set 的差异

multiset 和 set 的使用基本完全类似，主要区别在于 multiset 支持值冗余（不去重）。

• insert/find/count/erase 都围绕着支持值冗余有所差异。
• find 返回中序里面的第一个匹配项。
• count 会返回 x 的实际个数。
• erase(val) 会删除所有的 x。

五、Map

1. Map 简介

map 是关联容器，按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素。

• key 用于排序和唯一标识元素。
• value 存储与此键值 key 关联的内容。
• 内部通过 value_type 绑定在一起，typedef pair<const key, T> value_type。
• 通常被实现为二叉搜索树（更准确的说：平衡二叉搜索树/红黑树）。

2. 掌握 Pair 与 Make_pair

Pair：C++ 标准库中的模板类，允许将两个不同类型的数据组合在一起。

template <class T1, class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    // ... 构造函数省略
};

Make_pair：用于简化 std::pair 对象的创建，可以自动推导出 pair 的类型，无需显式指定模板参数类型。

3. Map 对象多种插入场景

int main() {
    map<string, string> dict;
    
    // 1. 使用匿名对象
    dict.insert(pair<string, string>("left", "左边"));
    
    // 2. 使用 make_pair，省略类型的书写
    dict.insert(make_pair("right", "右边"));
    
    // 3. 隐式类型转化
    dict.insert({"string", "字符串"});
    
    // 4. 初始化列表
    map<string,string> dic2 = {
        {"string", "字符串"},
        {"left", "左边"},
        {"right", "右边"}
    };
    return 0;
}

关于以上两种 map 初始化的方式，推荐使用初始化列表写法。同时需要注意的是 dict.insert({ "string", "字符串" }); 这里不是列表初始化 initializelist，而是调用 pair 构造函数，强制类型转化为 pair 类型插入数据。

4. 将数据存在结构体

map 中的元素类型是 pair。key 是不能随意修改的，可能会破坏搜索树结构，但 key 所对应的内容 value 是支持修改的。

auto it = dict.begin();
while (it != dict.end()) {
    // 不能修改 it->first (key)
    // 可以修改 it->second (value)
    it->second += "y";
    ++it;
}

5. Map 相关接口使用

构造

map 支持正向和反向迭代遍历，遍历默认按 key 的升序顺序。支持修改 value 数据，不支持修改 key 数据。

增删查

• insert: 插入 pair 键值对数据，如果 key 已存在则插入失败。
• find: 返回 k 所在的迭代器，不仅可以确认 key 在不在，还找到 key 映射的 value。
• erase: 删除迭代器位置的值或删除 k。

构造遍历及增删查使用样例

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

int main() {
    // 初始化
    map<string, string> dict = {
        {"left","左边"},{"right","右边"},{"list","列表"},{"animal","动物"}
    };
    
    // 范围 for，为什么这里使用引用？避免拷贝开销
    for (const auto& e : dict) {
        cout << e.first << ":" << e.second << endl;
    }
    
    // 结构化绑定，将 dict 里面的值分别赋值给 k 和 v，C++17 才开始支持的
    for (const auto& [k,v] : dict) {
        cout << k << ":" << v << endl;
    }
    
    // 经典的 key/value 场景，通过一个值去找另一个值
    string str;
    while (cin >> str) {
        auto ret = dict.find(str);
        if (ret != dict.end()) {
            cout << "->" << ret->second << endl;
        } else {
            cout << "不存在！请重新输入" << endl;
        }
    }
    return 0;
}

Map 的数据修改 + operator[] 功能

operator[] 的底层是用 insert 实现的。它不仅仅支持修改，还支持插入数据和查找数据，所以它是一个多功能复合接口。

Insert 返回值说明：

1. 如果 key 已经在 map 中，插入失败，返回 pair<iterator, bool>，second 为 false。
2. 如果 key 不在 map 中，插入成功，返回 pair<iterator, bool>，second 为 true。

无论插入成功还是失败，返回 pair 对象的 first 都会指向 key 所在的迭代器。正是因为这一点，insert 可以用来实现 operator[]。

// operator[] 的内部实现逻辑示意
mapped_type& operator[](const key_type& k) {
    // 1. 如果 k 不在 map 中，insert 会插入 k 和 mapped_type 默认值
    // 2. 如果 k 在 map 中，insert 会插入失败，但是返回 iterator 指向 key 结点
    pair<iterator, bool> ret = insert({k, mapped_type()});
    iterator it = ret.first;
    return it->second;
}

应用示例：统计水果出现的次数

int main() {
    string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉"};
    map<string, int> countMap;
    
    // 方法一：利用 [] 插入 + 修改功能，巧妙实现统计
    for (const auto& str : arr) {
        // [] 先查找水果在不在 map 中
        // 1. 不在，说明水果第一次出现，则插入 {水果，0}，同时返回次数的引用，++一下就变成 1 次了
        // 2. 在，则返回水果对应的次数++
        countMap[str]++;
    }
    
    for (const auto& e : countMap) {
        cout << e.first << ":" << e.second << endl;
    }
    return 0;
}

Erase 注意事项

这里使用 insert 不会出现迭代器失效的问题，而 erase 可能会出现迭代器失效的问题，需要特别注意删除后的迭代器更新。

六、Multimap

1. Multimap 和 Map 的差异

multimap 和 map 的使用基本完全类似，主要区别点在于 multimap 支持关键值 key 冗余。

• find 时，如果有多个 key，返回中序第一个。
• multimap 不支持 operator[]，因为支持 key 冗余，operator[] 就只能支持插入了，不能支持修改（无法确定修改哪一个 value）。

2. Multimap 使用事项

• Multimaps 是关联式容器，按照特定的顺序，存储由 key 和 value 映射成的键值对。<key,value>，其中多个键值对之间的 key 是可以重复的。
• 底层用二叉搜索树 (红黑树) 来实现。
• 使用时与 map 包含的头文件相同。

七、总结

map 和 set 是基于红黑树的高效数据结构，适用于需要有序性和快速查找的场景。set 保证唯一性，map 保证 Key 唯一性并关联 Value。在实际开发中，利用 operator[] 的特性可以简化代码逻辑，但要注意其底层可能涉及插入操作的性能开销。对于需要保留重复 Key 的场景，应选择 multimap 或 multiset。