0


【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 概述

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

关联容器

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

关联容器包括mapset

头文件定义

  • map multimap 在头文件 map 中,
  • setmultiset 在头文件 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;
无论是有序容器还是无序容器,具有相同关键字的元素都是相邻存储的。
标签: c++ 开发语言

本文转载自: https://blog.csdn.net/weixin_45043334/article/details/126246260
版权归原作者 小呆鸟_coding 所有, 如有侵权,请联系我们删除。

“【c++ primer 笔记】第11章 关联容器”的评论:

还没有评论