关联容器和顺序容器的区别：关联容器中的元素 是按照关键字?来保存和访问的。
关联容器支持 通过关键字 来高效地查找和读取元素，基本的关联容器类型是?map和set。
关联容器类型：
| 按关键字有序保存元素： | |
| map | 关联数组：保存关键字-值对 |
| set | 关键字即值，即只保存关键字的容器 |
| multimap | 支持同一个键多次出现的map |
| multiset | 支持同一个键多次出现的set |
| 无序集合： | |
| unordered_map | 用哈希函数组织的map |
| unordered_set | 用哈希函数组织的set |
| unordered_multimap | 哈希组织的map，关键字可以重复出现 |
| unordered_multiset | 哈希组织的set，关键字可以重复出现 |
这8个容器间的不同体现在三个维度上：
- 或者是一个set，或者是一个map。
- 或者要求不重复的关键字，或者允许重复关键字。
- 或者按顺序保存元素，或无序保存元素。
11.1 使用关联容器
- map：是关键字-值对的集合。（map中的元素是一个 pair类型的对象）
- set：是关键字的简单集合。
int?main()?{
????//?统计数组中?单词出现的次数（map）:
????map<string,?size_t>?word_counts;
????vector<string>?words?=?{?"aa","bb","cc","cc"?,"bb","cc"?};
????for?(auto?w?:?words)?{
????????++word_counts[w];?????????//?w为"键"，word_counts[w]为"值"。若map中存在这样的单词w?就将键对应的"值"+1;?若不存在w，则将w作为"键"插入map(其对应的"值"初始为0)，再将"值"+1
????}
????for?(auto?counts?:?word_counts)?{
????????cout?<<?counts.first?<<?":?有?"?<<?counts.second?<<?"?个"?<<?endl;????????//?输出:?"aa"有1个，"bb"有2个，"cc"有3个
????}???????????????????????????????????????????????????????????????????????? ????//?counts为map中的元素(pair类型对象):?couts.first为"键"、count.second为"值"
???????
????//?检查数组中?是否有重复的单词（set）:
????set<string>?include;
????vector<string>?words1?=?{?"aa","bb","aa","cc"?,"bb"?};
????
????for?(auto?w?:?words1)?{
????????if?(include.find(w)?==?include.end())?{?????? ?//?include.find(w)查找set中是否存在w。如果返回的迭代器为end，说明set中不存在w，则将w插入set;?如果返回迭代器不为end，说明set中已经存在w，因此重复
????????????include.insert(w);
????????}
????????else?{
????????????cout?<<?w?<<?"?重复出现!"?<<?endl;???????? //?输出:?"aa"重复出现，"bb"重复出现
????????}
????}
}?????11.2 关联容器概述
(1) 定义关联容器：
- 定义一个map时，必须 既指明关键字类型 又指明值类型。（如：map<string, int> word_counts = { {"aa", 1}, {"bb", 2} };）
- 定义一个set时，只需指明关键字类型。（如：set<string> include = { "aa", "bb" };）
注：我们也可以将关联容器初始化为 另一个同类型容器的拷贝，或是从一个值范围 来初始化关联容器，只要这些值可以转化为 容器所需类型就可以。
(2) 关键字类型的要求：
对于有序容器，关键字类型必须定义 元素比较的方法。（默认情况下，标准库使用 关键字类型的<运算符 来比较两个关键字）
bool?compare_len(const?string&?str1,?const?string&?str2)?{????????//?单词按?短到长的顺序?排序
????return?str1.size()?<?str2.size();
}
int?main()?{
????vector<string>?words?=?{?"aaaa","bb","d","ccc","d"?};
????//?默认情况下，标准库使用?关键字类型的<运算符?来比较两个关键字:
????multiset<string>?multi_set1(words.begin(),?words.end());
????for?(auto?w?:?multi_set1)?{
????????cout?<<?w?<<?"?";????????????? //?输出:?{"aaaa","bb","ccc","d","d"}?（默认情况下，用string类型的"<运算符"?来比较两个关键字）
????}
????//?显式地传递一个比较函数?来比较两个关键字:
????multiset<string,?decltype(compare_len)*>?multi_set2(compare_len);????????//?decltype用于compare_len函数，返回函数类型而非函数指针类型，因此加上*?来指出我们需要一个函数类型的指针
????for?(auto?w?:?words)?{???????????????????????????????????????????????????//?把函数作为一个值使用时，该函数自动地转换成指针。（使用?compare_len?和?&compare_len?是一样的）
????????multi_set2.insert(w);
????}
????for?(auto?w?:?multi_set2)?{?
????????cout?<<?w?<<?"?";?????????????//?输出:?{"d","d","bb","ccc","aaaa"}?（显式地用?自定义的"compare_len函数"?来比较两个关键字）
????}
}?(3) pair类型：
- pair的数据成员是public的，在utility头文件中定义。
- 一个pair保存两个数据成员。（first 和 second）
pair的操作：
| pair<T1, T2> p； | p是一个pair，两个类型分别是T1和T2的成员 都进行了值初始化。 |
| pair<T1, T2> p(v1, v2)； | first和second分别用 v1和v2进行初始化。 |
| pair<T1, T2>p = {v1, v2}； | 等价于p(v1, v2)。 |
| make_pair(v1, v2)； | 返回一个 用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来。 |
| p.first | 返回p的 名为first的数据成员。 |
| p.second | 返回p的 名为second的数据成员。 |
| p1 relop p2 | 关系运算符(<,>,<=,>=) 按字典序定义。关系运算 利用元素的relop运算符来实现。 |
| p1 == p2 | 当first和second成员 分别相等时，两个pair相等。 |
| p1 != p2 | 同上。 |
int?main()?{
????pair<string,?int>?pa1{?"aaa",1?};
????auto?pa2?=?std::make_pair("bbb",?2);
????cout?<<?pa1.first?<<?"?出现"?<<?pa1.second?<<?"次";?????????//?输出:?"aaa"?出现1次
????cout?<<?pa2.first?<<?"?出现"?<<?pa2.second?<<?"次";?????????//?输出:?"bbb"?出现2次
}?11.3 关联容器操作
关联容器额外的类型别名：
| key_type | 此容器类型的 关键字类型。 |
| mapped_type | 每个关键字关联的类型 ("值"的类型)，只适用于map。 |
| value_type | 对于map，是pair<const key_type, mapped_type>类型； 对于set，和key_type相同。 |
(1) 关联容器迭代器：
- 解引用一个关联容器迭代器时，会得到一个类型为 容器的value_type的值 的引用。
- map的关键字是const的。
- set的迭代器是const的。
- 使用begin和end，遍历map、multimap、set、multiset时，迭代器按关键字升序遍历元素。（因为这些是有序容器）
int?main()?{
????vector<string>?words{?"bb","aa","dd","cc"?,"aa"?};
????set<string>?set(words.begin(),?words.end());
????map<string,?int>?map;
????for?(auto?w?:?words)?{
????????++map[w];
????}
????
????//?map的关键字是const的，set的迭代器是const的（只可读不可写）:
????auto?map_iter?=?map.begin();
????auto?set_iter?=?set.begin();
????cout?<<?"map——键:?"?<<?map_iter->first?<<?"??值:?"?<<?map_iter->second?<<?endl;????????//?输出:?map——键:?"aa"??值:?2
????cout?<<?"set——键:?"?<<?*set_iter?<<?endl;??????????????????????????????????????????????//?输出:?set——键:?"aa"
????map_iter->first?=?"bb";????????//?错误:?map的关键字是const的
????*set_iter?=?"bb";??????????????//?错误:?set的迭代器是const的
????
????//?遍历关联容器:
????for?(auto?map_iter?=?map.begin();?map_iter?!=?map.end();?++map_iter)?{
????????cout?<<?"map——键:?"?<<?map_iter->first?<<?"??值:?"?<<?map_iter->second?<<?endl;
????}
????for?(auto?set_iter?=?set.begin();?set_iter?!=?set.end();?++set_iter)?{
????????cout?<<?"set——键:?"?<<?*set_iter?<<?endl;
????}
}?(2) 添加元素：
关联容器insert操作：
| c.insert(v) | v是value_type类型的对象；args用来构造一个元素。?函数返回一个pair，包含一个迭代器，指向具有指定关键字的元素，以及一个 指示插入是否成功的bool值。 对于map和set，只插入关键字不在c中的元素。对于multimap和multiset 则总会插入给定元素，并返回一个 指向新元素的迭代器。 |
| c.emplace(args) | |
| c.insert(b, e) | b和e是迭代器，表示一个c::value_type类型值的范围；il是这种值的花括号列表。?函数返回void。? 对于map和set，只插入关键字不在c中的元素。对于multimap和multiset 则总会插入给定元素，并返回一个 指向新元素的迭代器。 |
| c.insert(il) | |
| c.insert(p, v) | 类似insert(v)或c.emplace(args)，但将迭代器p作为一个提示，指出从哪里开始搜索 新元素应该存储的位置。返回一个迭代器，指向具有给定关键字的元素。 |
| c.emplace(p, args) |
int main() {
map<string, int> word_count;
multimap<string, string> authors;
// 向map插入元素的 4种方法:
word_count.insert({ "aa",1 });
word_count.insert(std::make_pair("aa", 1));
word_count.insert(pair<string, int>("aa", 1));
word_count.insert(map<string, int>::value_type("aa", 1));
// 检测insert的返回值:
auto ret1 = word_count.insert({ "aa",1 }); // ret1和ret2 都为pair类型 （first为 map<string,int>::iterator类型，second为 bool类型）
auto ret2 = word_count.insert({ "bb",1 });
cout << ret1.first->first << " 出现" << ret1.first->second << " 次" << endl; // 输出: "aa" 出现1 次
cout << (ret1.second ? "插入成功" : "关键字已存在，插入失败") << endl; // 输出: "关键字已存在，插入失败"
cout << ret2.first->first << " 出现" << ret2.first->second << " 次" << endl; // 输出: "bb" 出现1 次
cout << (ret2.second ? "插入成功" : "关键字已存在，插入失败") << endl; // 输出: "插入成功"
// 向multimap添加元素:
auto ret3 = authors.insert({ "Bob","book1" }); // ret3和ret4 都为multimap<string,int>::iterator类型
auto ret4 = authors.insert({ "Bob","book2" });
for (auto pa : authors) { // 输出: "Bob——book1","Bob——book2"（允许重复关键字存在）
cout << pa.first << "——" << pa.second << endl;
}
}(3) 删除元素：
从关联容器中删除元素：
| c.erase(k) | 从c中删除每个 关键字为k的元素。返回一个size_type值，指出删除的元素的数量。 |
| c.erase(p) | 从c中删除 迭代器p指定的元素。p必须指向c中一个真实元素，不能等于c.end()。返回一个指向p之后元素的迭代器，若p指向c中的尾元素，则返回c.end()。 |
| c.erase(b, e) | 删除迭代器对b和e所表示范围中的元素。返回e。 |
int?main()?{
????map<string,?int> _map{?{"aaa",1},{"aaa",1?}?};
????multimap<string,?int> multi_map{?{"aaa",1},{"aaa",1?}?};
????cout?<<?_map.erase("aaa")?<<?endl;???????????????//?输出:?1?（删掉关键字为"aaa"的元素，返回删除的元素个数1，因为map是?保存不重复关键字的容器）
????cout?<<?multi_map.erase("aaa")?<<?endl;??????????//?输出:?2?（删掉关键字为"aaa"的元素，返回删除的元素个数2，因为multimap是?可以保存重复关键字的容器?）
}?????
(4) map的下标操作：
map和unordered_map的下标操作：
| c[k] | ?返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，并对其值初始化。 |
| c.at(k) | 访问关键字为k的元素，带参数检查；若k不存在c中，则抛出一个out_of_range异常。 |
- set类型不支持下标，因为set中没有与关键字相关联的“值”。
- 不能对 multimap或unordered_multimap 进行下标操作，因为这些容器中 可能有多个值与一个关键字相关联。
- 下标和at操作只适用于 非const的map和unordered_map。
- map下标运算符[ ]接受一个索引(即一个关键字)，获取与此关键字 相关联的值。但是，与其他下标运算符不同的是，如果关键字不存在map中，则会为它创建一个元素 并插入到map中，关联值 将进行值初始化。
int?main()?{
????map<string,?int> _map;
????int?n?=?_map["aaa"];??????????//?n=0?（因为"aaa"并不存在于_map中，因此为之创建一个元素，并插入到_map中，关联值?进行值初始化为0）
}???(5) 查找元素：
在一个关联容器中查找元素的操作：
| c.find(k) | 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器。 |
| c.count(k) | 返回关键字等于k的元素 的数量。对于不允许重复关键字的容器，返回值永远是0或1。 |
| c.lower_bound(k) | 返回一个迭代器，指向第一个关键字 不小于k的元素。 |
| c.upper_bound(k) | 返回一个迭代器，指向第一个关键字 大于k的元素。 |
| c.equal_range(k) | 返回一个迭代器pair，表示关键字等于k的元素 的范围。若k不存在，pair的两个成员均等于c.end()。 |
- lower_bound和upper_bound不适用于 无序容器。
int?main()?{
????//?在map中使用find来查找元素:
????map<string,?int>?_map{?{"aaa",1}?,{"bbb",1},{"ccc",1}?};
????auto?iter1?=?_map.find("bbb");???????????????????????????????????????//?iter1为?map<string,int>::iterator类型?（指向第一个关键字为"bbb"的元素?的迭代器）
????cout?<<?iter1->first?<<?"?——?"?<<?iter1->second?<<?endl;???????????? //?输出:?"bbb?——?1"
????//?在multimap中查找元素：
????multimap<string,?string>?multi_map{?{"Bob","book1"},{"Bob","book2"},{"Alice","book1"},{"Alice","book2"},{"Tom","book1"}?};
????//?(方法1)
????auto?iter2?=?multi_map.find("Alice");????????????????????????????????//?指向第一个关键字为"Alice"的元素?的迭代器
????auto?counts?=?multi_map.count("Alice");??????????????????????????????//?关键字为"Alice"的元素的数量
????while?(counts)?{
????????cout?<<?iter2->first?<<?"?——?"?<<?iter2->second?<<?endl;???????? //?输出:?"Alice?——?book"，"Alice?——?book2"
????????++iter2;
????????--counts;
????}
????//?(方法2)
????auto?beg?=?multi_map.lower_bound("Alice");???????????????????????????//?指向第一个关键字为"Alice"的元素?的迭代器
????auto?end?=?multi_map.upper_bound("Alice");???????????????????????????//?指向最后一个关键字为"Alice"的元素?之后的迭代器
????while?(beg?!=?end)?{
????????cout?<<?beg->first?<<?"?——?"?<<?beg->second?<<?endl;?????????????//?输出:?"Alice?——?book"，"Alice?——?book2"
????????++beg;
????}
????//?(方法3)
????auto?pos?=?multi_map.equal_range("Alice");?????????????????????????? ?//?pos为一个pair?（first和second为?标识关键字等于k的元素的范围?的迭代器）
????
????while?(pos.first?!=?pos.second)?{???????????????????????????
????????cout?<<?pos.first->first?<<?"?——?"?<<?pos.first->second?<<?endl;??????? ?//?输出:?"Alice?——?book"，"Alice?——?book2"
????????++pos.first;
????}
}?????11.4 无序容器
- 有序容器使用?比较运算符?来组织元素；无序容器使用?哈希函数和关键字类型的==运算符。
- 无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数?将元素映射到桶。
无序容器管理操作：
| 桶接口： | |
| c.bucket_count() | 正在使用的桶的数目。 |
| c.max_bucket_count() | 容器能容纳的最多的 桶的数目。 |
| c.bucket_size(n)? | 第n个桶中 有多少个元素。 |
| c.bucket(k) | 关键字为k的元素 在哪个桶中。 |
| 桶迭代： | |
| local_iterator | 可以用来访问 桶中元素的迭代器类型。 |
| const_local_iterator | 同上，const版本。 |
| c.begin(n)，c.end(n) | 桶n的 首元素迭代器和尾后迭代器。 |
| c.cbegin(n)，c.cend(n) | 同上，const版本。 |
| 哈希策略： | |
| c.load_factor() | 每个桶的平均元素数量，返回float值。 |
| c.max_load_factor() | c试图维护的 平均桶大小，返回float值。c会在需要时添加新的桶，以使得 load_factor<=max_load_factor。 |
| c.rehash(n) | 重组存储，使得 bucket_count>=n，且 bucket_count>size/max_load_factor。 |
| c.reverse(n) | 重组存储，使得c可以保存n个元素 且不必rehash。 |
无序容器对关键字类型的要求：
默认情况下，无序容器使用?关键字类型的==运算符?来比较元素，它们还使用一个?hash<key_ type>类型的对象?来生成每个元素的?哈希值。
标准库为内置类型(包括指针) 提供了hash模板。还为一些标准库类型(包括string和的智能指针类型) 定义了hash。
因此，我们可以直接定义 关键字是内置类型(包括指针类型)、string还是智能指针类型 的无序容器。
注：但是，我们不能直接定义?关键字类型为自定义类类型?的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的 hash模板版本。
class?Demo{
public:
????Demo(const?string&?s?=?"")?:str(s)?{}
????string?str;
};
size_t?hasher(const?Demo&?de)?{???????????????????????//?自定义哈希函数?
????return?std::hash<string>()(de.str);???????????????//?根据标准库为string?设置的hash模板，来生成hash<string>类型的对象，从而生成每个元素的哈希值
}
bool?eqOp(const?Demo&?de1,?const?Demo&?de2)?{?????????//?自定义比较相等函数
????return?de1.str.size()?==?de2.str.size();??????????//?如果Demo类型的元素的?成员对象str的长度相等?则元素相等
}
int?main()?{
????Demo?d1("aaa");
????Demo?d2("bbb");
????Demo?d3("ccc");
????Demo?d4("aaa");
????unordered_set<Demo>?words1{?{Demo("aaa")},?{?Demo("bbb")},?{?Demo("bbb")}};????????????????????//?错误:?标准库没有为?Demo类型定义?"==运算符"和哈希函数?（Demo是自定义类类型）
????unordered_multiset<Demo,?decltype(hasher)*,?decltype(eqOp)*>?words2{?10,hasher,?eqOp?};????????//?正确?（参数分别为:?桶的大小，哈希函数指针，相等性判断运算符指针）
????words2.insert(d1);???????????????????
????words2.insert(d2);
????words2.insert(d3);
????words2.insert(d4);
????auto?ret1?=?words2.bucket(d1);
????auto?ret2?=?words2.bucket(d2);
????auto?ret3?=?words2.bucket(d3);
????auto?ret4?=?words2.bucket(d4);
????cout?<<?"d1在第?"?<<?ret1?<<?"?个桶中"?<<?endl;????????//?输出:?d1在第?2?个桶中
????cout?<<?"d2在第?"?<<?ret2?<<?"?个桶中"?<<?endl;????????//?输出:?d2在第?5?个桶中
????cout?<<?"d3在第?"?<<?ret3?<<?"?个桶中"?<<?endl;????????//?输出:?d3在第?0?个桶中
????cout?<<?"d4在第?"?<<?ret4?<<?"?个桶中"?<<?endl;????????//?输出:?d4在第?2?个桶中
}????????注：如果我们的类定义了 ==运算符，则可以只重载哈希函数。
