关联容器
- [x] 关联容器中的元素是按关键字来保存和访问的
- [x] 顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的
- 关联容器支持高效的关键字查找和访问
- 两个主要的关联容器是
map和set
- [x] map中的元素是一些关键字---值(key---value)对:关键字起到索引的作用，值则表示与索引相关联的数据
- [x] set中每个元素只包含一个关键字set支持高效的关键字查询操作----检查一个给帝国关键字是否在set中
- 标准库提供8个关联容器，这8个容器的不同主要体现在三个维度上
- [x] 或者是一个set，或者是一个map
- [x] 或者要求不重复的关键字，或者允许重复关键字
- [x] 按顺序保存元素，或无序保存
- 允许重复关键字的容器名字中都包含单词
multi,不保持关键字按顺序存储的容器的名字都以单词unordered开头
- 无序容器使用哈希函数来组织元素
关联容器使用
- [x] set的find函数会返回一个迭代器，如果给定关键字在set中，迭代器指向该关键字，否则，find返回尾后迭代器
关联容器概述
- 关联容器(有序的和无序的)都支持普通容器操作
- 关联容器不支持顺序容器的位置相关操作，例如push_front或push_back
- [x] 原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义
- [x] 关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作
定义关联容器
- 定义一个map时，必须指明关键字类型又指明值类型
- 定义一个set时，只需指明关键字类型，因为set中没有值
- 对关联容器初始化
map<string,size_t> word_count; //空容器
set<string> exclude = {"the","but"}; //set列表初始化
map<string,string> authors = {{"joyce","james"},{"asu","thdko"}}
关键字类型的要求
- 对于有序容器----
map multimap set multiset，关键字类型必须定义元素比较的方法
pair
关联容器操作
- 在一个map对象中，元素是关键字--值对，即，每个元素是一个pair对象
关联容器迭代器
- 当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用，对map而言，value_type就是一个pair类型，其first成员保存const关键字，second成员保存值
- 必须记住，一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值
- set的迭代器是const的
- 遍历关联容器
auto map_it = word.cbegin();
while(map_it != word.cend()){
string s1 = map_it.first;
string s2 = map_it.second;
++map_it;
}
- [x] 关键字是const这一特性意味着不能将关联容器传递给修改或重排容器元素的算法
添加元素
- 关联容器的insert成员向容器中添加一个元素或一个元素范围
- [x] 由于map和set包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响
vector<int> ivec = {2,4,6,8,2,4,6,8}; //ivec有8个元素
set<int> set2; //空集合
set2.insert(ivec.cbegin(),ivec.cend()); //set2有4个元素
set2.insert({1,3,5,7,1,3,5,7})； //set2有8个元素
- insert有两个版本，分别接受一对迭代器，或是一个初始化列表
- 向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<string,size_t>(word,1));
- 对于不包含重复关键字的容器(map\set)insert(或emplace)返回一个pair对象，pair对象的first成员是一个迭代器，second成员是一个bool值，指出元素插入成功还是失败
- 对于包含重复关键字的容器insert(或emplace)返回指向新元素的迭代器，这里无需返回一个bool值，因为insert总是向这类容器加入一个新元素
map的下标操作
- map和unprdered_map容器提供了下标运算符和一个对应的at函数，set类型不支持下标
- 通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的，但map不然:当对一个map进行下标操作时，会获得一个，mapped_type对象，但当解引用一个map迭代器时，会得到一个value_type对象
访问元素
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); //返回一个迭代器，指向key == 1的元素
iset.find(11); //返回一个迭代器，其值等物iset.end()
iset.find(1); //返回1
iset.find(11); //返回0
- 在允许重复关键字的容器中，可能有很多元素具有给定的关键字，则这些元素在容器中会相邻存储
string search_item("Alain de Botton"); //要查找的作者
auto entries = authors.count(serach_item); //元素的数量
auto iter = authors.find(search_item); //此作者的第一本书
while(entries){
cout<<iter->second<<endl; //打印每个题目
++iter; //前进到下一本书
--entries; //记录已经打印了多少本书
}
- 当我们遍历一个multimap或multiset时，保证可以得到序列中所有具有给定关键字的元素
- 使用lower_bound和upper_bound来解决上述问题
- [x] 如果关键字在容器中，lower_bound返回的迭代器指向第一个具有给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配给定的关键字的元素之后的位置
- [x] 如果元素不在multimap中，则lower_bound和upper_bound会返回相等的迭代器——指向一个不影响排序的关键字插入位置
- [x] 使用lower_bound和upper_bound会得到一个迭代器范围，表示所有具有该关键字的元素的范围
- [x] lower_bound返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向，如果关键字不再容器中，则lower_bound会返回关键字的第一个安全插入点————不影响容器中元素顺序的插入位置
//authors和serach_item的定义与前述一致
//beg和end表示对应此作者的元素的范围
for(auto beg = authors.lower_bound(search_item)),end = authors.upper_bound(search_item) ; beg != end ; ++beg)
{
cout<<iter->second<<endl;
}
- 如果lower_bound和upper_bound返回相同的迭代器，则给定关键字不在容器中
- equal_range函数
- [x] 此函数返回一个迭代器pair，若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置，若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置
//authors和serach_item的定义与前述一致
//pos保存迭代器对
for(auto pos = authors.equal_range(search_item) ; pos.first != pos.second ; ++pos.first)
{
cout<<iter->second<<endl;
}
无序容器
- [x] unordered_map
- [x] unordered_set
- [x] unordered_multimap
- [x] unordered_multiset
管理桶
- 无序容器在存储上组织为一组桶，每个桶保存零个或多个元素，无序容器使用一个哈希函数将元素映射到桶，为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶，容器将具有一个特定的哈希值的所有元素都保存在相同的桶中，如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中
- 无序容器的性能依赖于哈希函数的质量和桶的数量何额大小
- 对于相同的参数，哈希函数必须总是产生相同的结果，理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是将不同关键字的元素映射到相同的桶也是允许的
- 当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想找的那个元素
- 计算一个元素的哈希值和在桶中查找元素通常都是很快的操作，但如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量的比较操作
- 无序函数提供了一组管理桶的函数，这些成员函数允许我们查询容器的状态以及在必要的时候强制容器进行重组
无序容器对关键字类型的要求
- 标准库为内置类型(包括指针)提供了
hash模板，还为一些标准库类型，包括string和只能指针类型定义了hash，所以我们可以直接定义关键字是内置类型(包括指针类型)、string或是只能指针类型的无序容器
- 我们不能直接帝国一关键字类型为自定义类型的无序容器，与容器不同，不能直接使用哈希模板，必须提供我们自己的hash模板版本
Summary
- 关联容器支持通过关键字高效查找和提取元素，对关键字的使用将关联容器和顺序容器区分开来，顺序容器中是通过位置访问元素的
- 标准库定义了八个关联容器，每个容器
- [x] 是一个map或是一个set，map保存关键字---值对，set只保存关键字
- [x] 要求关键字唯一或不要求
- [x] 保持关键字有序或不保证有序
- 有序容器使用比较函数来比较关键字，从而将元素按顺序排序，默认情况下，比较操作时采用关键字类型的<运算符
- 无序容器使用关键字类型的==运算符和一个hash<key_type>类型的对象来组织元素
- 允许重复关键字的容器的名字中都包含mult
- 使用哈希技术的容器的名字都以unordered开头
