c++对象池：C笔记关联容器
c++对象池：C笔记关联容器unordered_setstring word; map<string size_t> word_count; set<string> exclude_articles = {"a" "an" "the" "A" "An" "The"}; // 需要剔除的冠词 while (cin >> word) if (exclude_articles.find(word) == exclude_articles.end()) // 只统计不在 set 中的单词 // find(key) 返回一个迭代器，若 key 在 set 中，则返回指向 key 的迭代器，否则返回尾后迭代器 word_count[word]; 1 2 3 4 5 6 7 multisetunordered_mapunordered_multimapset
关联容器概述
- 顺序容器中的元素按其在容器中的顺序保存和访问，而关联容器中的元素则按关键字保存和访问
关联容器类型
map
- key - value 映射的集合，关键字不允许重复，且有序排列
- #include <map>
- 使用例子：
string word; map<string size_t> word_count; // 一个从字符串到计数的空 map // 要定义一个 map，必须同时提供 key 和 value 的类型 while (cin >> word) word_count[word]; // 通过下标运算符将 word 的计数器加 1 // 如果 key 不在当前 map 中，下标运算符会创建一个新映射 for (const auto wc : word_count) // wc 的实际类型为 pair cout << wc.first << " occurs " << wc.second << ((wc.second > 1) ? "times" : "time") << endl; // wc.first 指向当前映射 wc 中的 key，wc.second 指向当前映射 wc 中的 value 1 2 3 4 5 6 7 8 9 10
multimap
- key - value 映射的集合，关键字允许重复，且有序排列
- #include <map>
unordered_map
- key - value 映射的集合，关键字不允许重复，无序排列
- #include <unordered_map>
unordered_multimap
- #include <unordered_map>
- key - value 映射的集合，关键字允许重复，无序排列
set
- key 的集合，关键字不允许重复，且有序排列
- #include <set>
- 使用例子：
string word; map<string size_t> word_count; set<string> exclude_articles = {"a" "an" "the" "A" "An" "The"}; // 需要剔除的冠词 while (cin >> word) if (exclude_articles.find(word) == exclude_articles.end()) // 只统计不在 set 中的单词 // find(key) 返回一个迭代器，若 key 在 set 中，则返回指向 key 的迭代器，否则返回尾后迭代器 word_count[word]; 1 2 3 4 5 6 7
multiset
- key 的集合，关键字允许重复，且有序排列
- #include <set>
unordered_set
- key 的集合，关键字不允许重复，无序排列
- #include <unordered_set>
unordered_multiset
- key 的集合，关键字允许重复，无序排列
- #include <unordered_set>
关键字类型
- 对于有序容器，关键字类型必须定义了元素之间比较的方法
使用自定义的关键字比较操作
- 为了使用自定义的操作，必须在定义关联容器时同时提供关键字类型和比较操作的类型 —— 一种函数指针类型，指向自定义的比较函数
bool compare(const string & str1 const string & str2) { return str1.size() < str2.size(); } set<string> exclude1 = {"a" "an" "the" "A" "An" "The"}; set<string decltype(compare)*> exclude2(compare) = exclude1; 1 2 3 4 5 6
pair 类型
- #include <utility>
- 一个 pair 包含两个 public 的数据成员，分别命名为 first 和 second
- map 的每个元素都是一个 pair
关联容器操作
类型别名
- key_type：关键字类型
- mapped_type：map 中值的类型
- value_type：对于 set，与 key_type 相同；对于 map，为 pair<const key_type mapped_type>
迭代器
- 解引用一个迭代器返回一个 value_type 类型的引用
- map 和 set 的关键字都是 const 的，不允许修改，因此迭代器也是 const_iterator 类型
- map 中的 value 可以修改
auto map_it = word_count.begin(); // map_it 的类型为 &pair<const string size_t> cout << map_it->first << " " << map_it->second; map_it->first = "new key"; // ERROR! map_it->second; 1 2 3 4
添加元素：insert()
向 map 或 set 添加元素
- 必须以 pair 的形式向 map 添加元素：
word_count.insert({word 1}); word_count.insert(make_pair(word 1)); word_count.insert(pair<string size_t>(word 1)); word_count.insert(map<string size_t>::value_type(word 1)); 1 2 3 4
- 对于不包含重复元素的关联容器，insert() 返回一个 pair。pair 的 first 成员是指向具有给定关键字的元素，second 是一个 bool 值，指出元素是插入成功还是已经存在于容器中。如果元素已经存在于容器中，second 为 false，否则为 true
向 multimap 或 multiset 添加元素
multimap<string string> player; player.insert({"LeBron James" "Cleveland Cavaliers"}); player.insert({"LeBron James" "Miami Heat"}); player.insert({"LeBron James" "Los Angeles Lakers"}); player.insert({"Dwayne Wade" "Cleveland Cavaliers"}); player.insert({"Dwayne Wade" "Miami Heat"}); player.insert({"Dwayne Wade" "Chicago Bulls"}); 1 2 3 4 5 6 7
- 对于允许重复关键字的容器，insert() 操作总是成功，并返回一个指向新元素的迭代器
删除元素：erase()
- erase(key)：删除所有关键字为 key 的元素，返回被删除元素的个数
- erase(iter)：删除迭代器 iter 指向的元素，iter 不能指向尾后元素；返回指向所删除元素之后的元素的迭代器
- erase(begin end)：删除迭代器范围内的元素，返回 end
访问元素
map 和 unordered_map 的下标 [] 和 at()：通过 key 获得 value
- 下标运算符不支持 multimap 和 unordered_multimap
- 如果关键字不存在，则会创建一个元素并插入到 map 中，并对 value 值初始化
- 由于下标运算符可能插入新元素，因此只能对非 const 的 map 使用下标
- 对于 at(key)，若 key 不存在，则抛出 out_of_range 异常
- map 的下标返回 mapped_type 类型的对象（即值），且是一个左值
在关联容器中查找元素
- find(key)：返回一个迭代器，指向第一个关键字为 key 的元素；若不存在，则返回尾后迭代器
- count(key)：返回关键字为 key 的元素数量
- lower_bound(key)：返回一个迭代器，指向第一个关键字不小于 key 的元素
- upper_bound(key)：返回一个迭代器，指向第一个关键字大于 key 的元素
- equal_range(key)：返回一个迭代器 pair，第一个迭代器指向第一个关键字为 key 的元素，第二个迭代器指向最后一个关键字为 key 的元素之后的位置；若未找到，则两个迭代器都指向 end()
