【c++ primer 笔记】第11章 关联容器

🎉作者简介:👓

      博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢
     
     
      c
     
     
      +
     
     
      +
     
     
      ,
     
     
      g
     
     
      o
     
     
      ,
     
     
      p
     
     
      y
     
     
      t
     
     
      h
     
     
      o
     
     
      n
     
     
      ,
     
     
      目前熟悉
     
     
      c
     
     
      +
     
     
      +
     
     
      ，
     
     
      g
     
     
      o
     
     
      语言，数据库，网络编程，了解分布式等相关内容
     
    
   
   
    \textcolor{orange}{博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容}
   
  
 博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容

📃

      个人主页：
     
    
   
   
    \textcolor{gray}{个人主页：}
   
  
 个人主页： 小呆鸟_coding

🔎

      支持
     
     
      :
     
    
   
   
    \textcolor{gray}{支持:}
   
  
 支持:
 
  
   
    
     
      如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦
     
    
   
   
    \textcolor{green}{如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦}
   
  
 如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦👍
 
  
   
    
     
      就是给予我最大的支持！
     
    
   
   
    \textcolor{green}{就是给予我最大的支持！}
   
  
 就是给予我最大的支持！🎁

💛本文摘要💛
本专栏主要是对c++ primer这本圣经的总结，以及每章的相关笔记。目前正在复习这本书。同时希望能够帮助大家一起，学完这本书。 本文主要讲解第11章 关联容器

文章目录

🌰关联容器

🔥11.0 概述

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

关联容器

支持高效的关键字查找和访问

关联容器包括map 和 set。

头文件定义

• map 和 multimap 在头文件 map 中，
• set 和 multiset 在头文件 set 中，
• 无序 map 和无序 set 分别在头文件 unordered_map 和 unordered_set 中。
  容器类型解释按关键字有序保存元素

  map
  

  关键数组：保存

  关键字-值
  

  对

  set
  

  关键字即值，即只保存关键字的容器

  multimap
  

  支持同一个键多次出现的

  map
  

multiset

支持同一个键多次出现的

set

无序集合

unordered_map

用哈希函数组织的

map

unordered_set

用哈希函数组织的

set

unordered_multimap

哈希组织的

map

，关键字可以重复出现

unordered_multiset

哈希组织的

set

，关键字可以重复出现

🔥11.1 使用关联容器

使用map

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

map<string,size_t> word_count;while(cin>>word)++word_count[word];for(constauto&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<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);

pair

的类型从

v1

和

v2

的类型推断出来。

p.first

返回

p

的名为

first

的数据成员。

p.second

返回

p

的名为

second

的数据成员。

p1 relop p2

运算关系符按字典序定义。

p1 == p2

必须两对元素两两相等

p1 != p2

同上
创建 pair 类型的返回值

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

pair<string,int>process(bool a){if(a)return{"lala",16};//列表初始化elsereturn pair<string,int>();//隐式构造返回值}'也可以使用make_pair'returnmake_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异常。

🎃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_thasher(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;

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