🌰关联容器

🔥11.0 概述

• 关联容器中的元素按关键字来保存和访问
• 顺序容器中的元素按他们在容器中的位置来保存和访问
• 关联容器与顺序容器许多行为相同，但是有着根本不同，不同之处反应关键字作用

关联容器支持高效的关键字查找和访问
关联容器包括map 和 set。

头文件定义

• map 和 multimap 在头文件 map 中，
• set 和 multiset 在头文件 set 中，
• 无序 map 和无序 set 分别在头文件 unordered_map 和 unordered_set 中。

🔥11.1 使用关联容器

使用map

• map一般用来保存关键字和值的映射，例如关键字是姓名，值是电话，爱好等。
• map 可以使用范围 for 循环,得到的结果是pair

map<string, size_t> word_count;
while(cin>>word)
    ++word_count[word];
for(const auto &w : word_count)
    {
        cout << w.first << w.second
    }

使用set

• set通常用来判断一个值是否存在
• set 可以使用范围 for 循环

map<string, size_t> word_count;
set<string> exclude = {"the","a","hello"};
while(cin>>word)
    if(exclude.find(word) == exclude.end())
         ++word_count[word];

🔥11.2 关联容器概述

• 所有的有序、无序关联容器都支持下面这些普通容器的公共操作。
• 关联容器不支持顺序容器的位置相关的操作，例如push_front,push_back等关联容器中的元素是根据关键字存储的。
• 关联容器的迭代器都是双向的。

'类型别名'
iterator
const_iterator
value_type //容器元素类型。定义方式： vector<int>::value_type
reference //元素类型的引用。定义方式： vector<int>::reference
const_reference //元素的 const 左值类型

'构造函数'-'三种通用的构造函数：同类拷贝、迭代器范围初始化、列表初始化'
C c1;                          // 默认构造函数，构造空容器。
C c1 (c2);                    // 拷贝构造函数，容器类型与元素类型必须都相同
C c1 (c2.begin(), c2.end());  // 要求两种元素类型可以转换即可。
C c1 {a, b, c, ...};          // 使用初始化列表，容器的大小与初始化列表一样大
        // 只有顺序容器的构造函数可以接受大小参数，关联容器不行。

'赋值与swap'
c1 = c2;
c1 = {a,b,c,....}
a.swap(b);
swap(a,b);//两种 swap 等价

'大小'
c.size();
c.max_size();//c 可以保存的最大元素数目，是整个内存层面的容量，不是已分配内存。不同于 caplity, caplity 只能用于 vector，queue，string
c.empty();

'添加/删除元素（不适用于array）'
c.insert(args); //将 args 中的元素拷贝进 c，args 是一个迭代器或迭代器范围
c.emplace(inits);//使用 inits 构造 c 中的一个元素
c.erase(args);//删除指定的元素，args 是一个迭代器或迭代器范围
c.clear();

'关系运算符'
==; !=; <; <=; >; >=  //所有容器都支持相等和不等运算符。无序关联容易不支持大于小于运算符。

'获取迭代器'
c.begin(); c.end(); 
c.cbegin(); c.cend(); //返回 const_iterator

'反向容器的额外成员'
reverse_iterator //逆序迭代器，这是一个和 iterator 不同的类型
const_reverse_iterator 
c.rbegin();c.rend();
c.crbegin();c.crend();

关联容器特有操作

'类型别名'
key_type //关键字类型
mapped_type //每个关联的类型，只适用于 map
value_type //对于 set，与 key_type 相同，对于 map，为 pair<const key_type,mapped_type>

🎃11.2.1 定义关联容器

• 需要指定元素类型。
• 关联容器的初始化可以使用直接初始化（使用小括号）、列表初始化（使用花括号）、拷贝初始化（使用等号）。
• 使用迭代器范围进行直接初始化时，如果迭代器范围中有重复关键字，生成的 set 和 map 会自动去除重复的元素。

值初始化

• 除了三种构造函数外，关联容器可以进行值初始化。初始化器必须能转换为容器中元素的类型。

map<string, int> word_count = {{"a", 1}, {"b", 2}};
set<string> exclude = {"the", "a"};

注意：初始化map时需要将每个关键字-值包围在花括号中{key-value}

初始化 multiset 和 multimap

• 一个map和set中的关键字必须是唯一的，但是对于multiset和multmap可以有多个相同的关键字。
• 使用迭代器范围进行直接初始化时，无论有没有重复关键字，都会生成包含所有元素的 multiset 和 multimap。

🎃11.2.2 关键字类型要求

• 对于有序容器，关键字类型必须定义元素比较的方法。默认是<。

有序容器关键字类型

• 对于有序容器，关键字类型必须定义元素比较的方法。默认是<。
• 可以使用如 vector 等容器的迭代器来作为有序容器的关键字。
• 重载了 < 运算符的类可以直接用作关键字。

• 可以向算法提供一个自己定义的比较操作，操作必须在关键字类型上定义一个严格弱序

  • 两个关键字不能同时”小于等于“对方。
  • A < B, B < C则A必须小于C（传递性）
  • 如果两个关键字互不”小于等于“对方，那么两个就是等价的。容器将它们看做相等。

注意：当俩个关键字是等价的，容器会将这俩个看做相等，当用作map的关键字时，只能有一个元素与这俩个关键字关联，我们可以用俩着中的任意一个来访问

使用关键字类型的比较函数

• 当自己定义了比较操作，必须在定义关联容器时指出来
• 自定义的操作类型（函数指针类型）应在尖括号中紧跟元素类型给出。并将函数名作为参数传递给构造函数。
• 比较函数应该返回 bool 值，两个参数的类型应该都是容器的关键字类型。当第一个参数小于第二个参数时返回真。

'比较函数的定义方式'
bool comp(const Sales_data &lhs, const Sales_data &rhs)
{
    return lhs.isbn() < rhs.isbn();
}
'定义容器对象'
multiset<Sales_data,decltype(comp)*> bookstore(comp);

注意:当使用 decltype 获取函数指针时要加上 * 运算符。

🎃11.2.3 pair类型

• 在utility头文件中定义。
• 一个pair保存两个数据成员，两个类型不要求一样。

pair 定义

• pair的默认构造函数对数据成员进行值初始化，因此 string，vector 等类型会默认为空，int 会默认为 0。

'直接定义'
pair<string, int> p;//默认初始化
pair<string, int> p(str, i);
pair<string, int> p{"lala", 16};
pair<string, int> p = {"lala", 16};

'使用 make_pair'
auto p = make_pari(v1, v2);//pair 的类型根据 v1 和 v2 的类型推断。

创建 pair 类型的返回值

• 如果一个函数返回一个 pair，可以对返回值进行列表初始化或隐式构造返回值

pair<string,int> process(bool a){
    if(a) 
        return {"lala",16};//列表初始化
    else 
        return pair<string,int>();//隐式构造返回值
}

'也可以使用make_pair'
return make_pair(v.back, v.back.size());

🔥11.3 关联容器操作

• 关联容器还有特殊的类型别名

'类型别名'
key_type //关键字类型
mapped_type //每个关联的类型，只适用于 map
value_type //对于 set，与 key_type 相同，对于 map，为 pair<const key_type,mapped_type>

注意

• set 的 key_type 类型不是常量，pair 的 first 成员也不是常量，只有 map 的 value_type 中的 first 成员是常量。
• 由于不能改变一个元素的关键字，因此这些pair的关键字部分是const的

🎃11.3.1 关联容器迭代器

• 解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。
• 对于map来说value_type是一个pair类型，first成员保存const的关键字，second成员保存值

注意：一个map的value_type是一个pair,可以改变pair的值，但不能改变关键字成员的值

set的迭代器是const

• set 的关键值与 map 的关键值一样，都是不能改变的。
• 可以用 set 的迭代器读取元素值，但不能修改。

遍历关联容器

• map 和 set都支持 begin 和 end 操作
• 遍历关联容器：使用begin和end，遍历map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

关联容器和算法

• 一般不对关联容器使用泛型算法，因为cosnt这一特性意味着不能将关联容器传递给修改或重排容器元素的算法。
• 当对关联容器使用泛型算法时，一般要么把它作为源序列，要么把它作为目的序列。比如从关联容器拷贝元素，向关联容器插入元素等。
• 要是用关联容器所特有的find算法

🎃11.3.2 添加元素

• 由于map和set（以及对应的无序类型）包含不重复的关键字，因此往容器中插入一个存在的元素对容器没有影响

像map中添加元素

• 关联容器添加元素一般使用 insert 成员，可以添加一个元素也可以添加一个元素范围，或者初始化列表。

map<string, int> m;
'四种方法'
m.insert({word, 1});                    //最简单的方法，直接使用花括号
m.insert(make_pair(word, 1));
m.insert(pair<string, int>(word, 1));   //pair 类型直接定义
m.insert(map<string, int>::value_type(word, 1));

使用 emplace 添加元素

s.emplace(args);//args用来构造一个元素，其他和 s.insert(10) 相同
s.emplace(iter, args);//除了 args 其他和 s.insert(iter, 10) 相同

检查insert的返回值

• insert 返回值依赖于容器的类型和参数
• 对于不重复的map和set，添加的单一元素的 insert 和 emplace 都返回一个 pair，pair 内是具有给定关键字的元素的迭代器和一个 bool 值
• 对于不重复的map和set，添加多个元素都返回 void在向 map 或 set 添加元素时，检测 insert 的返回值可以很有用，要灵活使用。

while(cin>>word){
    auto ret = word_count.insert({word,1});
    if(ret.second = false)
        ++ret.first->second;
}

'解释'
ret : 保存insert返回的值，是一个pair
ret.first : 是pair的第一个成员，是一个map迭代器，指向具有给定关键字的元素
ret.first-> : 解引用此迭代器,提取map中的元素，元素也是一个pair
ret.first->second : map中元素的值部分
++ret.first->second : 递增

'替换'
pair<map<string,size_t>::iterator, bool> ret = word_count.insert({word,1});

向 multiset 或 multimap 添加元素

• 在 multiset 或 multimap 上调用 insert 总会插入元素。
• 插入单个元素的 insert 返回一个指向新元素的迭代器。

🎃11.3.3 删除元素

• 关联容器定义了三个版本的erase，其中俩个与顺序容器相似的版本（通过传递迭代器或一个迭代器对来删除一个元素或一个元素范围，返回void）

  • 与顺序容器相似版本：注意顺序容器会返回删除元素后一个元素的迭代器，而这里的 erase 返回 void
  • 额外版本：输入参数为关键字（key_value 注意不是关键字的迭代器），返回删除的元素数量，对于非重复关键字的容器，返回值总是 1 或 0。

'与顺序容器相似版本的 erase'
s.erase(iter);           // 删除一个元素，返回 void
s.erase(iter1, iter2)    // 删除一个范围，返回 void
'额外版本'
auto cnt = s.erase("lala");//删除一个关键字，返回该关键字对应的元素的数量

删除关联容器的最后一个元素

m.erase(--m.end());   // 正确！m 的迭代器支持自增与自减
m.erase(m.rbegin());  // 错误！

遍历容器删除元素

'map'
map<int, int> m;
for(auto iter = m.begin(); iter != m.end(); ){
    if(iter->second == 0)
        m.erase(iter++); //这是循环map删除指定元素的唯一方式。利用了 i++ 的原理
    else
        iter++;    
}
'vector'
vector<int> v;
for(auto iter = v.begin(); iter != v.end(); ){
    if(*iter == 0)
        iter = v.erase(iter);//vecotr 的 erase 操作返回所删除元素之后的迭代器
    else
        iter++;    
}

🎃11.3.4 map的下标操作

• map 和 unordered_map 都支持下标操作和对应的 at 函数。
• set 类型则不支持下标。multimap 和 unordered_multimap 不支持下标操作。
• 如果关键字不再 map 中，会创建一个元素并插入到 map 中，关联值将进行值初始化。

注意：

1. 因为关联值是值初始化，所以在单词计数程序中，可以直接 map[word]++ ，不必特意插入元素。
2. map 的下标操作只能返回非常量引用（不同于顺序容器的下标操作），如果 map 本身是常量，则无法使用下标访问元素，这时要用 at() 函数。

c[k]    返回关键字为k的元素；如果k不在c中，添加一个关键字为k的元素，对其值初始化。
c.at(k)    访问关键字为k的元素，带参数检查；若k不存在在c中，抛出一个out_of_range异常。

使用下标操作的返回值

• 与vector和string不同，map下标运算符返回的类型与解引用map迭代器得到的类型不同
• 解引用一个map迭代器会得到一个value_type对象,对map进行下标操作得到一个mapped_type对象

🎃11.3.5 访问与查找元素

访问元素

• map 可以通过下标或 at() 函数访问元素。
• set 只能通过迭代器来访问元素。

'基本的访问操作'
c[k];
c.at(k);

访问 map/set 的最后一个元素：m.rbegin() 或 --m.end()。

查找元素

• 关联容器查找一个指定元素的方法有多种。一般 find 是最佳选择。
• 对于不允许重复关键字的容器，find 和 count 差别不大，对于允许重复关键字的容器，count 会统计有多少个元素有相同的关键字。

'查找操作'
c.find(k);//返回一个迭代器，指向关键字为 k 的元素，如果 k 不在容器中，返回尾后迭代器。
c.count(k);//返回关键字等于 k 的元素数量。
c.lower_bound(k);//返回一个迭代器，指向第一个关键字不小于 k 的元素。
c.upper_bound(k);//返回一个迭代器，指向第一个关键字大于 k 的元素。
c.equal_range(k);//返回一个迭代器 pair，表示关键字等于 k 的元素范围。若干 k 不存在，pair 的两个成员相等，指向可以安全插入 k 的位置

注意

• lower_bound和upper_bound不适用于无序容器。
• 下标和at操作只适用于非const的map和unordered_map。

检查元素是否存在

• 检查元素是否存在用 find 或 count。

if(word_count.find("lala") == word_count.end())
if(word_count.count("lala") == 0)

在 multimap 或 multiset 中查找元素

• 在不允许重复关键字的关联容器查找一个元素简单，要在 multimap 或 multiset 中查找所有具有给定关键字的元素比较麻烦。
• 如果一个mutimap或mutiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储

三种方法：

1. 使用 find 和 count 配合，找到第一个关键字为 k 的元素和所有关键字为 k 的元素数目，遍历完成。
2. 使用 lower_bound 和 upper_bound 配合。注意当关键字 k 不存在时，这两个函数返回相同的迭代器，可能是尾后迭代器也可能不是。
3. 使用 equal_range。最直接的方法

string a("hello world");
auto sum = authors.count(a);   //此作者一共有几本书
suto iter = authors.find(a);  //此作者第一本书
while (sum)
    cout << iter->second << endl;
    ++iter;
    -- sum;

for(auto bg = authors.lower_bound(a), ed = authors.upper_bound(a); bg != ed; ++bg)
    cout << beg->second << endl;

for(auto pos = authors.equal_range(a); pos.first != pos.second; ++pos.first)
    cout << pos.first->second;

🔥11.4 无序容器

• 有序容器使用比较运算符来组织元素；无序容器使用哈希函数和关键字类型的==运算符。
• 无序容器用于关键字类型不好排序的情况。
• 无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。

使用无序容器

• 无序容器也有 find，insert，迭代器等操作。
• 在大多数情况下，可以用无序容器替换对应的有序容器，反之亦然。但是注意无序容器中元素未按顺序存储。

管理桶

• 无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。
• 无序容器使用哈希函数将元素映射到桶，并将具有一个特定哈希值的所有元素保存在相同的桶中。如果容器允许重复关键字，那所有具有相同关键字的元素也都在同一个桶中。不同关键字的元素也可能映射到相同的桶。
• 对于相同的参数，哈希函数总是产生相同的结果。
• 当一个桶中保存了多个元素，需要顺序搜索这些元素来查找想要的那个。计算一个元素的哈希值和在桶中搜索通常都很快。

'桶接口'
c.bucket_count();      //返回正在使用的桶的数目
c.max_bucket_count();  //返回容器能容纳的最多的桶的数量
c.bucket_size(n);      //返回第 n 个桶中有多少个元素
c.bucket(k);           //返回关键字为 k 的元素所在的桶

'桶迭代'
local_iterator         //类型别名，可以用来访问桶中元素的迭代器类型
const_local_iterator   //类型别名，桶迭代器的常量版本
c.begin(n), c.end(n)  //返回桶 n 的首元素迭代器和尾后迭代器
c.cbegin(n),c.cend(n) 

'哈希策略'
c.load_factor();      //返回每个桶的平均元素数量，类型为 float
c.max_load_factor();  //返回 c 试图维护的平均桶大小，类型为 float。c 会在需要时添加新的桶，始终保持 load_factor <= max_loat_factor
c.rehash(n);          //重组存储，使得 bucket_count >= n 且 bucket_count > size / max_load_factor
c.reserve(n);         //重组存储，使得 c 可以保存 n 个元素而不必 rehash。

无序容器对关键字的要求

• 默认情况下，无序容器使用 == 运算符比较关键字，使用用一个 hash<key_type> （hash 模板）类型的对象来生成每个元素的哈希值。
• 标准库为内置类型（包括指针）和 string、智能指针等都定义了 hash，因此内置类型，string 和智能指针类型都能直接用来作为无序容器的关键字。
• 对于自定义的类类型，不能直接用来作为无序容器的关键字，因为他们不能直接使用 hash 模板，除非提供自己的 hash 模板版本。

'定义自己的 hash 模板版本'
size_t hasher(const Sales_data &sd){
    return hash<string>() (sd.isbn());//这里采用了标准库的 hash 类型对象来计算 isbn 成员的哈希值，作为整个 Sale_data 对象的哈希值。
}
'重载比较函数（这里是相等）'
bool eq(const Sales_data &lhs, const Sales_data &rhs){
    return lhs.isbn() == rhs.isbn();
}
'定义 unordered_multiset'
unordered_multiset< Sales_data, decltype(hasher)*, decltype(eq)* > sals;

无论是有序容器还是无序容器，具有相同关键字的元素都是相邻存储的。