C++ 关联容器：set、map 和键值对实战笔记

这里能看出，哪怕源 vector 里有重复元素，set 也会在构造时顺手去重，只留下唯一值。

迭代器和容量操作

set 支持正向和反向迭代器。底层是红黑树，遍历时天然按顺序输出。

void TestIterator() {
    vector<int> v1 = { 1,2,3,4,5,5,6,7,7 };
    set<int> s1(v1.begin(), v1.end());
    
    // 正向迭代
    set<int>::iterator it = s1.begin();
    while(it != s1.end()) {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    
    // 反向迭代
    set<int>::reverse_iterator rit = s1.rbegin();
    while (rit != s1.rend()) {
        cout << *rit << " ";
        rit++;
    }
    cout << endl;
}

void TestCapacity() {
    vector<int> v1 = { 1,8,9,7,5,6,4,3,2 };
    set<int> s1(v1.begin(), v1.end());
    cout << s1.size() << endl;      // 输出元素个数
    cout << s1.empty() << endl;     // 判断是否为空
}

插入、删除和查找

set 不能改元素本身，但可以靠 insert 和 erase 管理内容。find 返回迭代器，配合 erase 删除指定元素挺顺手，尤其是需要先判断是否存在的时候。

void TestModification() {
    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;
    
    // 通过迭代器删除
    set<int>::iterator Position = s1.find(2);
    if(Position != s1.end()) s1.erase(Position);
    
    // 直接通过 key 删除，返回删除的元素个数
    size_t count = s1.erase(3);
    cout << "删除的元素个数:" << count << endl;
    
    // 统计特定 key 的数量
    cout << "25 的数量:" << s1.count(25) << endl;
}

lower_bound 和 upper_bound 也很有用，做范围查询时比你自己遍历省得多。比如想拿到 [25, 80) 之间的元素，再统一处理或者删除，这种场景用有序容器就很舒服。

Multiset 的区别

multiset 和 set 的接口很像，底层也一样是红黑树，差别只有一个：它允许重复元素。也就是说，插入时不用担心重复值被吞掉。

void TestMultiSet() {
    multiset<int> s1;
    s1.insert(1); s1.insert(1); s1.insert(3);
    s1.insert(2); s1.insert(5); s1.insert(7);
    
    for (auto& element : s1) cout << element << " ";
    // 输出结果会包含重复的 1
}

Map 与 Multimap

Map 的特点

map 也是关联容器，按 key 的顺序存储键值对。key 负责排序和唯一标识，value 负责保存实际内容。底层同样是红黑树。

map 支持下标访问符 []。写法很顺手：把 key 放进去，就能拿到对应的 value。要注意的是，如果 key 不存在，operator[] 会先插入这个 key，再把 value 默认初始化。这个行为在做字典类映射时很好用，但在只读场景里也容易多出一些你没打算创建的数据。

迭代器和元素访问

map 的迭代器指向 pair<const Key, T>，所以 key 用 .first，value 用 .second。

void TestMapIterator() {
    map<string, string> m1;
    // 多种插入方式
    m1.insert({"Begin", "开始"});
    m1.insert(make_pair("End", "结束"));
    m1.insert({"Top", "顶部"});
    
    map<string, string>::iterator it = m1.begin();
    while (it != m1.end()) {
        cout << (*it).first << ":" << it->second << endl;
        ++it;
    }
}

容量和修改

map 的 count 可以用来判断 key 是否存在。at() 也能访问 value，但它和 operator[] 的差别很明显：key 不存在时，at() 直接抛异常，不会替你插入新元素。

void TestModify() {
    map<string, string> Dictionary;
    Dictionary.insert({"apple","苹果"});
    Dictionary.insert({"banana", "香蕉"});
    Dictionary.insert({"watermelon", "西瓜"});
    
    // 删除元素
    Dictionary.erase("lemon"); // 若 lemon 不存在则无影响
    Dictionary.erase("watermelon");
    
    for (auto& Kv : Dictionary) 
        cout << Kv.first << ":" << Kv.second << endl;
}

Multimap 的使用

multimap 和 map 的区别不复杂：map 的 key 唯一，multimap 的 key 可以重复。也正因为这样，multimap 没有重载 operator[]，否则连'该返回哪一个 value'都说不清。

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;
}

这段代码的思路很常见：先用 map 统计频率，再用 multimap 按频率做排序输出。写法不算花哨，但在处理词频、排名这类问题时，够直接，也够稳。