C++ 关联容器实战：Set、Map 与键值对详解

关联式容器概述

在 C++ STL 中，vector、list、deque 等属于序列式容器，底层是线性结构，存储的是元素本身。而关联式容器虽然也是用来存储数据，但它的核心在于**<key, value>结构的键值对**。这使得它在数据检索上比序列式容器效率更高，典型的如 set、map、unordered_set、unordered_map 等。

需要区分的是，stack、queue 和 priority_queue 属于容器适配器，它们默认的基础容器分别是 deque、vector 等，并不直接归类为关联式容器。

树形结构与哈希结构

根据应用场景不同，STL 实现了两种主要结构的关联式容器：

关联式容器	容器结构	底层实现
set, map, multiset, multimap	树型结构	平衡搜索树 (红黑树)
unordered_set, unordered_map...	哈希结构	哈希表

树型结构中的元素是有序的，适合需要遍历有序数据的场景；哈希结构则是无序的，追求极致的查找速度。

键值对基础

键值对（Key-Value Pair）表示具有一一对应关系的结构，通常包含两个成员变量：key 代表索引或标识，value 表示与 key 对应的具体信息。这是关联式容器的核心存储单元。

Set 与 Multiset

Set 的使用

set 是按照特定次序存储元素的容器。在 set 中，元素的 value 同时也作为 key 存在，且每个 value 必须是唯一的。这意味着 set 中的元素不能在容器中修改（元素总是 const），但可以从容器中插入或删除。

内部而言，set 的元素总是按照比较对象（类型比较）指示的严格弱排序准则进行排序。由于底层基于二叉搜索树（通常是红黑树）实现，通过 key 访问单个元素的速度通常比 unordered_set 慢，但它允许根据顺序对子集进行直接迭代。

构造方式

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

void testSetConstructor() {
    // 构造空的 set
    set<int> s1;
    
    // 迭代器区间构造，会自动去重并排序
    vector<int> v1 = { 1,2,3,4,5,5,6,7,7 };
    set<int> s2(v1.begin(), v1.end());
    
    // 拷贝构造
    set<int> s3(s2);
    
    for(auto & element : s2) cout << element << " ";
    cout << endl;
    for (auto& element : s3) cout << element << " ";
    cout << endl;
}

迭代器与容量

set 支持正向和反向迭代器。容量操作包括 size() 获取元素个数，empty() 判断是否为空。

void testSetCapacity() {
    vector<int> v1 = { 1,8,9,7,5,6,4,3,2 };
    set<int> s1(v1.begin(), v1.end());
    
    cout << "Size: " << s1.size() << endl;
    cout << "Empty: " << s1.empty() << endl;
}

修改与删除

set 不支持修改现有元素，因为它是有序的，修改 key 会破坏树的平衡。我们只能通过 insert 插入新元素，或通过 erase 删除元素。

void testSetModification() {
    set<int> s1;
    s1.insert(1); s1.insert(2); s1.insert(3);
    s1.insert(5); s1.insert(6); s1.insert(7);
    s1.insert(25);
    
    for (auto& element : s1) cout << element << " ";
    cout << endl;
    
    // 使用 find 定位后删除
    set<int>::iterator Position = s1.find(2);
    if(Position != s1.end()) s1.erase(Position);
    
    // 直接通过 key 删除，返回删除的元素个数
    size_t count = s1.erase(3);
    cout << "Deleted count: " << count << endl;
    
    // count 方法用于检查元素是否存在
    cout << "25 exists: " << s1.count(25) << endl;
}

范围操作

lower_bound 和 upper_bound 提供了强大的范围查询能力。lower_bound(key) 返回第一个大于等于 key 的迭代器，upper_bound(key) 返回第一个大于 key 的迭代器。结合这两个函数，可以轻松实现闭区间或半开区间的删除。

void testSetRangeOps() {
    set<int> s1;
    for(int i=0; i<10; ++i) s1.insert(i * 10);
    
    // 获取 [25, 80) 范围内的迭代器
    auto itlow = s1.lower_bound(25);
    auto itup = s1.upper_bound(70);
    
    // 删除该范围内的所有元素
    s1.erase(itlow, itup);
    
    for (auto& element : s1) cout << element << " ";
    cout << endl;
}

Multiset

multiset 与 set 类似，也是按特定顺序存储元素，但允许元素重复。底层同样是红黑树。

void testMultiSet() {
    multiset<int> s1;
    s1.insert(1); s1.insert(1); s1.insert(3);
    s1.insert(2); s1.insert(5);
    
    for (auto& element : s1) cout << element << " ";
    // 输出结果：1 1 2 3 5
}

注意：multiset 的元素同样不能被修改，只能插入或删除。

Map 与 Multimap

Map 的使用

map 是关联容器，按照特定的次序（通常按 key 比较）存储由键值 key 和值 value 组合而成的元素。在 map 内部，key 与 value 绑定在一起，类型为 pair<const Key, T>。

关键点：

1. Key 唯一性：map 中的 key 是唯一的，且不能修改。
2. 有序性：遍历时可以得到一个有序的序列。
3. 下标访问：支持 operator[]，如果 key 不存在，会自动创建默认 value 并插入。
4. 底层实现：平衡二叉搜索树（红黑树）。

迭代器与访问

map 的迭代器指向 pair<const Key, T> 类型的元素。可以通过 .first 访问 key，.second 访问 value。

void testMapIterator() {
    map<string, string> m1;
    m1.insert({"Begin", "开始"});
    m1.insert(make_pair("End", "结束"));
    
    map<string, string>::iterator it = m1.begin();
    while (it != m1.end()) {
        cout << it->first << ": " << it->second << endl;
        ++it;
    }
}

元素访问与修改

在使用 operator[] 时需注意：如果 key 不存在，它会先插入一个默认构造的 value，然后返回引用。如果需要安全地访问而不想触发插入，应使用 at() 方法，当 key 不存在时会抛出异常。

void testMapAccess() {
    map<string, string> dict;
    dict["string"] = "字符串";
    
    // operator[] 若 key 不存在会插入默认值
    string val = dict["right"];
    
    // at() 若 key 不存在会抛异常
    try {
        string safeVal = dict.at("left");
    } catch (...) {
        cout << "Key not found via at()" << endl;
    }
}

删除元素可以使用 erase(key) 或 erase(iterator)。

void testMapModify() {
    map<string, string> Dictionary;
    Dictionary.insert({"apple","苹果"});
    Dictionary.insert({"banana", "香蕉"});
    Dictionary.insert({"watermelon", "西瓜"});
    
    // 删除指定 key
    Dictionary.erase("lemon"); // 如果 lemon 不存在，count 为 0，不会报错
    Dictionary.erase("watermelon");
    
    for (auto& Kv : Dictionary) 
        cout << Kv.first << ": " << Kv.second << endl;
}

Multimap

multimap 与 map 的唯一区别在于：key 是可以重复的。它常用于统计词频等场景。

void testMultiMap() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果" };
    multimap<int, string> SortMap;
    map<string, int> CountMap;
    
    // 先统计频率
    for (auto& element : arr) CountMap[element]++;
    
    // 再按频率排序存入 multimap
    for (auto& kv : CountMap) 
        SortMap.insert({kv.second, kv.first});
    
    for (auto& kv : SortMap) 
        cout << kv.first << ": " << kv.second << endl;
}

注意：multimap 没有重载 operator[]，因为 key 不唯一，无法确定返回哪个 value。