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

4.1.1.2. set 的迭代器

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

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

int main() {
    TestIterator();
}

4.1.1.3. set 的容量

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

void Test_Capacity() {
    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;
}

int main() {
    Test_Capacity();
}

4.1.1.4. set 的修改

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

void Test_Modification() {
    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 与 erase 函数
    set<int>::iterator Position = s1.find(2);
    s1.erase(Position);
    Position = s1.find(3);
    size_t count = s1.erase(3);
    cout <<"删除的元素个数:>" << count << endl;
    for (auto& element : s1) cout << element << " ";
    cout << endl;
    cout <<"25 的数量:>" << s1.count(25) << endl;
}

int main() {
    Test_Modification();
}

4.1.1.5. set 的其他操作

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

void Test_Operation() {
    set<int> s1;
    s1.insert(1);
    s1.insert(2);
    s1.insert(3);
    s1.insert(5);
    s1.insert(6);
    s1.insert(7);
    s1.insert(25);
    set<int>::iterator it = s1.find(5);
    for (auto& element : s1) cout << element << " ";
    cout << endl;
    if (s1.end() != it) {
        cout << *it << endl;
        s1.erase(it);
    } else cout << "找不到" << endl;
    for(auto & element : s1) cout << element << " ";
    cout << endl;
    for (size_t i = 1; i < 10; i++) {
        s1.insert(i * 10);
    }
    for (auto element : s1) cout << element << " ";
    cout << endl;
    // 获取的是闭区域
    set<int>::iterator itlow = s1.lower_bound(25);
    // 获取的是比 70 大的值，但是小于 80
    set<int>::iterator itup = s1.upper_bound(70);
    //[25,80)
    s1.erase(itlow, itup);
    for (auto& element : s1) cout << element << " ";
    cout << endl;
}

int main() {
    Test_Operation();
}

4.2. multiset

1. multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. 在 multiset 中，元素的 value 也会识别它 (因为 multiset 本身存储的是<value,value>组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T)。multiset 的元素的值不能在容器中进行修改 (因为元素总是 const 的),但可以从容器中插入或者删除。
3. 在内部，multiset 中的元素总是按照内部比较规则 (类型比较) 所指示的特定严格弱排序准则进行排序。
4. multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. multiset 底层结构为红黑树。

PS:

1. multiset 中在底层中存储的是<value,value>的键值对。
2. multiset 的插入接口中只需要插入即可。
3. 与 set 的区别是，multiset 的元素可以重复，set 中 value 是唯一的。
4. multiset 中的元素不能被修改。

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

void Test_MultiSet() {
    // key 模型搜索，排序 + 不去重 + 允许数据冗余
    multiset<int> s1;
    s1.insert(1);
    s1.insert(1);
    s1.insert(3);
    s1.insert(2);
    s1.insert(5);
    s1.insert(7);
    s1.insert(9);
    s1.insert(15);
    s1.insert(35);
    for (auto& element : s1) cout << element << " ";
}

int main() {
    Test_MultiSet();
}

4.3. Map And MultiMap

1. map 是关联容器，它按照特定的次序 (按照 key 来比较) 存储由键值 key 和值 value 组合而成的元素。
2. 在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为pair:typedef pair<const key,T>value_type;
3. 在内部，map 中的元素总是按照键值 key 进行比较排序的。
4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代 (即对 map 中的元素进行迭代时，可以得到一个有序的序列)。
5. map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value。
6. map 通常被实现为二叉搜索树 (更准确的说：平衡二叉搜索树 (红黑树)).

4.3.1. map 的使用

key: 键值对中 key 的类型 T: 键值对中 value 的类型 Compare: 比较器的类型，map 中的元素是按照 key 来比较的，缺省情况下按照小于来比较，一般情况下 (内置类型元素) 该参数不需要传递，如果无法比较时 (自定义类型),需要用户自己显式传递比较规则 (一般情况下按照函数指针或者仿函数来传递). Alloc: 通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器. 注意：在使用 map 时，需要包含头文件。

4.3.1.1. map 的迭代器

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

void Test_MapIterator() {
    map<string, string>m1;
    pair<string, string>Kv1("Begin", "开始");
    m1.insert(Kv1);
    m1.insert(pair<string, string>("End", "结束"));
    m1.insert(make_pair("Top", "顶部"));
    // 多参数构造函数支持隐式类型转换
    m1.insert({ "Bottom","底部" });
    map<string, string>::iterator it = m1.begin();
    while (it != m1.end()) {
        cout << (*it).first << ":" << it->second << endl;
        ++it;
    }
}

int main() {
    Test_MapIterator();
    return 0;
}

4.3.1.2. map 的容量与元素访问

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

void The_Pricinple() {
    map<string, string> dict;
    dict.insert({ "string","字符串" });
    // 插入 (一般不这么用)
    dict["right"];
    // 插入 + 修改
    dict["left"] = "左边";
    // 返回 (返回的是 Value 的引用)
    cout << dict["string"] << endl;
    dict["right"] = "右边";
    string str;
    while (cin >> str) {
        if (dict.count(str)) {
            cout << "在字典里面" << endl;
        } else {
            cout << "不在字典里面" << endl;
        }
    }
}

int main() {
    The_Pricinple();
    return 0;
}

注意: 在元素访问时，有一个与 operator[] 类似的操作 at()(该函数不常用) 函数，都是通过 key 找到与 key 对应的 value 然后返回其引用，不同的是:当 key 不存在时，operator[] 用默认 value 与 key 构造键值对然后插入，返回该默认 value，at() 函数直接抛异常.

4.3.1.3. map 中元素的修改

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

void Test_Modify() {
    map<string, string> Dictionary;
    Dictionary.insert({ "apple","苹果" });
    Dictionary.insert(pair<string, string>("banana", "香蕉"));
    Dictionary.insert({"watermelon", "西瓜"});
    Dictionary.insert({ "orange", "橙子" });
    Dictionary.insert({ "lemon", "柠檬" });
    for (auto& Kv : Dictionary) cout << Kv.first << ":>" << Kv.second << endl;
    cout << "----------------------------" << endl;
    Dictionary.erase("lemon");
    Dictionary.erase("watermelon");
    for (auto& Kv : Dictionary) cout << Kv.first << ":>" << Kv.second << endl;
}

int main() {
    Test_Modify();
    return 0;
}

4.3.2. Map 的总结

• map 中的元素总是键值对。
• map 中的 key 是唯一的，并且不能修改。
• 默认按照小于的方式对 Key 进行比较。
• map 中的元素如果用迭代器去进行遍历，可以得到一个有序的序列。
• map 的底层为红黑树，查找效率比较高。
• 支持 [] 操作符，operator[] 中实际进行插入查找。

4.3.3. Multimap

1. Multimap 是关联式容器，它按特定的顺序，存储由 Key 和 value 映射成的键值对<key,value>,其中多个键值对之间的 key是可以重复的。
2. 在 multimap 中，通过按照 key 排序和唯一地标识元素，而映射的 value 存储与 key 关联的内容，key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对:typedef pair<const Key, T> value_type;
3. 在内部，multimap 的元素总是通过其内部比较对象，按照指定的特定严格弱排序对 key 进行排序

注意：multimap 和 map 的唯一不同就是：map 中的 key 是唯一的，而 multimap 中 key 是可以重复的。

4.3.3.1. Multimap 的使用

1. multimap 中的key 是可以重复的。
2. multimap 中的元素默认将 key 按照小于来比较。
3. multimap 中没有重载 operator[] 操作.
4. 使用时与 map 包含的头文件相同。

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

void Test_MultiMap() {
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
    multimap<int, string> SortMap;
    map<string, int> CountMap;
    // 插入
    for (auto& element : arr) CountMap[element]++;
    // 插入
    for (auto& kv : CountMap) SortMap.insert({ kv.second,kv.first });
    // 默认按照 key 值排序
    for (auto& kv : SortMap) cout << kv.first << ":" << kv.second << endl;
    cout << endl;
}

int main() {
    Test_MultiMap();
    return 0;
}