C++ 关联式容器核心解析：map 与 set 实战指南

1.1 find 方法对比

set<int> s;
s.insert(3); s.insert(2); s.insert(4); s.insert(5);
s.insert(1); s.insert(5); // 重复插入无效
s.insert(2); 

// 方式一：成员函数 find
auto pos = s.find(3);

// 方式二：算法库 find
auto pos2 = std::find(s.begin(), s.end(), 3);

性能差异： 显然方式一更优。set::find 利用红黑树结构，复杂度 O(logN)；而 std::find 是线性遍历，复杂度 O(N)。删除元素时建议配合成员函数迭代器使用。

1.2 lower_bound 与 upper_bound

set<int> myset;
for(int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 ... 90

auto itlow = myset.lower_bound(30); // 指向第一个 >= 30 的元素 (30)
auto itup = myset.upper_bound(65);  // 指向第一个 > 65 的元素 (70)
myset.erase(itlow, itup);           // 删除 [30, 70) 区间内的元素

这两个函数遵循左闭右开区间原则，常用于范围查询或批量删除。

2. multiset 容器

multiset 与 set 类似，区别在于允许元素重复。底层同样是红黑树。

2.1 count 与 equal_range

count 用于统计某个值出现的次数。对于 multiset，这非常实用。

multiset<int> ms = {1, 2, 3, 3, 4, 5};
int c = ms.count(3); // 结果为 2

equal_range 返回一个 pair，包含两个迭代器，分别指向等于给定值的第一个元素和最后一个元素的下一个位置。

auto result = ms.equal_range(3);
for(auto it = result.first; it != result.second; ++it) {
    cout << *it << " "; // 输出 3 3
}

3. map 容器

map 是最常用的关联容器之一，存储由键 key 和值 value 组合而成的元素。key 唯一且有序，value 与之关联。

3.1 多种插入方式

map<string, string> dict;

// 1. 普通对象插入
pair<string, string> kv1("insert", "插入");
dict.insert(kv1);

// 2. 匿名对象插入
dict.insert(pair<string, string>("sort", "排序"));

// 3. make_pair 插入（推荐，省去类型声明）
dict.insert(make_pair("string", "字符串"));

// 4. 初始化列表插入（C++11 起支持）
dict.insert({"string", "字符串"});

关于引用的疑问： 在 const pair<string, string>& kv2 = {"insert", "插入"}; 中，引用绑定到了临时对象。由于常量左值引用会延长临时对象生命周期，这里不会增加额外的拷贝开销，但直接传值通常更高效。

3.2 访问操作符

箭头运算符 ->

map<string, string>::iterator it = dict.begin();
while(it != dict.end()) {
    cout << it->first << ":" << it->second << endl;
    ++it;
}

map 内部重写了 -> 运算符，使其直接返回 first 的地址，代码更简洁。(*it).first 等价于 it->first。

下标运算符 []

map<string, int> m;
m["key"] = 10; // 如果 key 不存在，会自动创建并初始化为 0
int val = m["key"];

原理： operator[] 内部调用 insert。如果 key 已存在，返回现有 value 的引用；如果不存在，插入新节点并返回新 value 的引用。因此它既可以读也可以写，但要注意它会隐式插入数据。

3.3 实战：随机链表的复制

题目描述： 给定一个带有随机指针的链表，要求深拷贝该链表。

思路： 利用 map 建立原节点与新节点的映射关系。

1. 第一次遍历：创建所有新节点，存入 map<Node*, Node*>，Key 为原节点，Value 为新节点。
2. 第二次遍历：通过 map 查找原节点对应的随机指针指向的新节点，赋值给新节点的随机指针。

代码实现：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeCopyMap;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        Node* cur = head;

        // 第一次遍历：创建节点并建立映射
        while(cur) {
            Node* copynode = new Node(cur->val);
            if(copytail == nullptr) {
                copyhead = copytail = copynode;
            } else {
                copytail->next = copynode;
                copytail = copynode;
            }
            nodeCopyMap[cur] = copynode;
            cur = cur->next;
        }

        // 第二次遍历：设置 random 指针
        Node* copy = copyhead;
        cur = head;
        while(cur) {
            if(cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                copy->random = nodeCopyMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

为什么能通过 cur->random 找到 newnode->random？ 因为 nodeCopyMap 记录了 {原节点 A -> 新节点 A'} 的关系。当处理 A 时，cur->random 指向 C，我们通过 nodeCopyMap[C] 就能拿到 C'，从而正确连接 A' 的随机指针。

4. multimap 容器

multimap 与 map 的唯一区别是：key 可以重复。因此它不支持 operator[] 操作，因为无法确定返回哪个 value。其他接口与 map 基本一致。

在实际应用中，multiset 和 multimap 的使用频率低于 set 和 map，但在需要处理一对多关系时非常关键。