C++学习笔记十-关联容器

一    
    
    
    
、概述：关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素
    
    
    
    ，而顺序容器则通过元素在容器中的位置顺序存储和访问元素
    
    
    
    。

1.关联容器（Associative containers）支持通过键来高效地查找和读取元素     


     


     


     


。两个基本的关联容器类型是 map set 




 




 




 




。map 的元素以键－值（key-value）对的形式组织：键用作元素在 map 中的索引     


     


     


     


，而值则表示所存储和读取的数据

   

   

   

   。set 仅包含一个键 




 




 




 




，并有效地支持关于某个键是否存在的查询     

     

     

     

。

2.一般来说

   

   

   

   ，如果希望有效地存储不同值的集合     

     

     

     

，那么使用 set 容器比较合适  




  




  




  




，而 map 容器则更适用于需要存储（乃至修改）每个键所关联的值的情况  




  




  




  




。在做某种文本处理时


  


  


  


  ，可使用 set 保存要忽略的单词


  


  


  


  。而字典则是 map 的一种很好的应用：单词本身是键     
     
     
     
，而它的解释说明则是值     
     
     
     
。

3.关联容器类型：

map 关联数组：元素通过键来存储和读取

set 大小可变的集合   




   




   




   




，支持通过键实现的快速读取

multimap 支持同一个键多次出现的 map 类型

multiset 支持同一个键多次出现的 set 类型

二 


     


     


     


    、pair 类型：

1.pair 的创建和初始化：pair 包含两个数据值   




   




   




   




。与容器一样



 



 



 



 ，pair 也是一种模板类型



 



 



 



 。但又与之前介绍的容器不同                    ，在创建 pair 对象时    




    




    




    




，必须提供两个类型名：pair 对象所包含的两个数据成员各自对应的类型名字



















，这两个类型必相同                    。

pair<string, string> anon; // holds two strings pair<string, int> word_count; // holds a string and an int pair<string, vector<int> > line; // holds string and vector<int>

如果在创建 pair 对象时不提供初始化式                    ，则调用默认构造函数对其成员采用值初始化    




    




    




    




。于是     



     



     



     



，anon 是包含两空 string 类型成员的 pair 对象



















，line 则存储一个空的 string 类型对象和一个空的vector 类型对象



















。word_count 中的 int 成员获得 0 值
    
    
    
    ，而 string 成员则初始化为空 string 对象                    。

2.可在定义时为每个成员提供初始化式：

pair<string, string> author("James", "Joyce"); 3.pairs 对象的操作：

make_pair(v1, v2) 以 v1 和 v2 值创建一个新 pair 对象     


     


     


     


，其元素类型分别是 v1 和 v2 的类型

p1 < p2 两个 pair 对象之间的小于运算 




 




 




 




，其定义遵循字典次序：如果 p1.first < p2.first 或者 !(p2.first < p1.first) && p1.second < p2.second

   

   

   

   ，则返回 true

p1 == p2 如果两个 pair 对象的 first 和 second 成员依次相等     

     

     

     

，则这两个对象相等     



     



     



     



。该运算使用其元素的 == 操作符

p.first 返回 p 中名为 first 的（公有）数据成员

p.second 返回 p 的名为 second 的（公有）数据成员

三

 




 




 




 


、关联容器的公共操作：

1.三种构造函数：

C<T> c; // creates an empty container // c2 must be same type as c1 C<T> c1(c2); // copies elements from c2 into c1 // b and e are iterators denoting a sequence C<T> c(b, e); // copies elements from the sequence into c

2.begin   

   

   

   

、end  

     

     

     

   、rbegin 和 rend 操作



















。

3.对于 map 容器  




  




  




  




，value_type 并非元素的类型


  


  


  


  ，而是描述键及其关联值类型的 pair 类型
    
    
    
    。 4.支持swap 和赋值操作     


     


     


     


。但关联容器不提供 assign 函数 




 




 




 




。 5.支持clear 和 erase 操作     
     
     
     
，但关联容器的 erase 运算返回 void 类型

   

   

   

   。 6.resize 函数不能用于关联容器     

     

     

     

。 四


  




  




  




  

、map 类型容器：

map 是键－值对的集合  




  




  




  




。map 类型通常可理解为关联数组（associative array）：可使用键作为下标来获取一个值   




   




   




   




，正如内置数组类型一样


  


  


  


  。而关联的本质在于元素的值与某个特定的键相关联



 



 



 



 ，而并非通过元素在数组中的位置来获取     
     
     
     
。

１.map 的构造函数：

map<k, v> m; 创建一个名为 m 的空 map 对象                    ，其键和值的类型分别为 k 和 v

map<k, v> m(m2); 创建 m2 的副本 m    




    




    




    




，m 与 m2 必须有相同的键类型和值类型

map<k, v> m(b, e); 创建 map 类型的对象 m



















，存储迭代器 b 和 e 标记的范围内所有元素的副本   




   




   




   




。元素的类型必须能转换为 pair<const k, v>

２.键类型的约束：在使用关联容器时                    ，它的键不但有一个类型     



     



     



     



，而且还有一个相关的比较函数



 



 



 



 。默认情况下



















，标准库使用键类型定义的 < 操作符来实现键（key type）的比较                    。对于键类型
    
    
    
    ，唯一的约束就是必须支持 < 操作符     


     


     


     


，至于是否支持其他的关系或相等运算 




 




 




 




，则不作要求    




    




    




    




。

３．map 对象的元素是键－值对

   

   

   

   ，也即每个元素包含两个部分：键以及由键关联的值



















。map 迭代器返回 value_type 类型的值——包含 const key_type 和 mapped_type 类型成员的 pair 对象；下标操作符则返回一个 mapped_type 类型的值                    。

４．关联类型：在学习 map 的接口时     

     

     

     

，需谨记 value_type 是 pair 类型  




  




  




  




，它的值成员可以修改


  


  


  


  ，但键成员不能修改     



     



     



     



。

map<K, V>::key_type 在 map 容器中     
     
     
     
，用做索引的键的类型

map<K, V>::mapped_type 在 map 容器中   




   




   




   




，键所关联的值的类型

map<K, V>::value_type 一个 pair 类型



 



 



 



 ，它的 first 元素具有 const map<K, V>::key_type 类型                    ，而 second 元素则为 map<K, V>::mapped_type 类型

５.给 map 添加元素：可使用 insert 成员实现；或者    




    




    




    




，先用下标操作符获取元素



















，然后给获取的元素赋值



















。在这两种情况下                    ，一个给定的键只能对应于一个元素这一事实影响了这些操作的行为
    
    
    
    。map 对象键所关联的值采用值初始化：类类型的元素用默认构造函数初始化     



     



     



     



，而内置类型的元素初始化为 0     


     


     


     


。

６.map::insert 的使用：

A.插入单个元素的 insert 版本使用键－值 pair 类型的参数 




 




 




 




。类似地



















，对于参数为一对迭代器的版本
    
    
    
    ，迭代器必须指向键－值 pair 类型的元素

   

   

   

   。另一个差别则是：map 容器的接受单个值的 insert 版本的返回类型     

     

     

     

。使用下标给 map 容器添加新元素时     


     


     


     


，元素的值部分将采用值初始化  




  




  




  




。在添加新 map 元素时 




 




 




 




，使用 insert 成员可避免使用下标操作符所带来的副作用：不必要的初始化


  


  


  


  。

B.map 对象中一个给定键只对应一个元素     
     
     
     
。如果试图插入的元素所对应的键已在容器中

   

   

   

   ，则 insert 将不做任何操作   




   




   




   




。含有一个或一对迭代器形参的 insert 函数版本并不说明是否有或有多少个元素插入到容器中



 



 



 



 。

C.传递给 insert 的实参相当笨拙                    。可用两种方法简化：使用 make_pair:

word_count.insert(make_pair("Anna", 1));

Or use a typedef:

或使用 typedef

typedef map<string,int>::value_type valType; word_count.insert(valType("Anna", 1)); D.insert操作:

m.insert(e)

e 是一个用在 m 上的 value_type 类型的值    




    




    




    




。如果键（e.first）不在 m 中     

     

     

     

，则插入一个值为 e.second 的新元素；如果该键在 m 中已存在  




  




  




  




，则保持 m 不变



















。该函数返回一个 pair 类型对象


  


  


  


  ，包含指向键为 e.first 的元素的 map 迭代器     
     
     
     
，以及一个 bool 类型的对象   




   




   




   




，表示是否插入了该元素 m.insert(beg, end) beg 和 end 是标记元素范围的迭代器



 



 



 



 ，其中的元素必须为 m.value_type 类型的键－值对                    。对于该范围内的所有元素                    ，如果它的键在 m 中不存在    




    




    




    




，则将该键及其关联的值插入到 m     



     



     



     



。返回 void 类型 m.insert(iter, e) e 是一个用在 m 上的 value_type 类型的值



















。如果键（e.first）不在 m 中



















，则创建新元素                    ，并以迭代器 iter 为起点搜索新元素存储的位置
    
    
    
    。返回一个迭代器     



     



     



     



，指向 m 中具有给定键的元素

7.查找并读取 map 中的元素：

A.下标操作符给出了读取一个值的最简单方法



















，但是
    
    
    
    ，使用下标存在一个很危险的副作用：如果该键不在 map 容器中     


     


     


     


，那么下标操作会插入一个具有该键的新元素     


     


     


     


。

B.m.count(k), 返回 m 中 k 的出现次数,对于 map 对象 




 




 




 




，count 成员的返回值只能是 0 或 1 




 




 




 




。map 容器只允许一个键对应一个实例

   

   

   

   ，所以 count 可有效地表明一个键是否存在

   

   

   

   。

Ｃ．m.find(k)     

     

     

     

，如果 m 容器中存在按 k 索引的元素  




  




  




  




，则返回指向该元素的迭代器     

     

     

     

。如果元素不存在


  


  


  


  ，则返回 end 迭代器.

8.从map中删除元素：

A.m.erase(k),删除 m 中键为 k 的元素  




  




  




  




。返回 size_type 类型的值     
     
     
     
，表示删除的元素个数(要么是0   




   




   




   




，要么是1);

B.m.erase(p),从 m 中删除迭代器 p 所指向的元素


  


  


  


  。p 必须指向 m 中确实存在的元素



 



 



 



 ，而且不能等于 m.end()     
     
     
     
。返回 void

C.m.erase(b, e),从 m 中删除一段范围内的元素                    ，该范围由迭代器对 b 和 e 标记   




   




   




   




。b 和 e 必须标记 m 中的一段有效范围：即 b 和 e 都必须指向 m 中的元素或最后一个元素的下一个位置



 



 



 



 。而且    




    




    




    




，b 和 e 要么相等（此时删除的范围为空）



















，要么 b 所指向的元素必须出现在 e 所指向的元素之前                    。返回 void 类型

9.map 对象的迭代遍历:与其他容器一样                    ，map 同样提供 begin 和 end 运算     



     



     



     



，以生成用于遍历整个容器的迭代器    




    




    




    




。在使用迭代器遍历 map 容器时



















，迭代器指向的元素按键的升序排列



















。

五  


  


  


  


、set类型容器：set 容器只是单纯的键的集合                    。

1.set 不支持下标操作符
    
    
    
    ，而且没有定义 mapped_type 类型     



     



     



     



。在 set 容器中     


     


     


     


，value_type 不是 pair 类型 




 




 




 




，而是与 key_type 相同的类型



















。它们指的都是 set 中存储的元素类型
    
    
    
    。这一差别也体现了 set 存储的元素仅仅是键

   

   

   

   ，而没有所关联的值     


     


     


     


。与 map 一样     

     

     

     

，set 容器存储的键也必须唯一  




  




  




  




，而且不能修改 




 




 




 




。

2.set 容器的定义和使用：以一段范围的元素初始化 set 对象


  


  


  


  ，或在 set 对象中插入一组元素时     
     
     
     
，对于每个键   




   




   




   




，事实上都只添加了一个元素

   

   

   

   。

3.往set中添加元素：与 map 容器的操作一样                    ，带有一个键参数的 insert 版本返回 pair 类型对象    




    




    




    




，包含一个迭代器和一个 bool 值



















，迭代器指向拥有该键的元素                    ，而 bool 值表明是否添加了元素  




  




  




  




。使用迭代器对的 insert 版本返回 void 类型


  


  


  


  。

４.正如不能修改 map 中元素的键部分一样     



     



     



     



，set 中的键也为 const     
     
     
     
。在获得指向 set 中某元素的迭代器后



















，只能对其做读操作
    
    
    
    ，而不能做写操作：

六   
     
     
     
  、multimap 和 multiset 类型：multiset 和 multimap 类型则允许一个键对应多个实例   




   




   




   




。

1.multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同     


     


     


     


，只有一个例外：multimap 不支持下标运算



 



 



 



 。不能对 multimap 对象使用下标操作 




 




 




 




，因为在这类容器中

   

   

   

   ，某个键可能对应多个值                    。

2.元素的添加和删除：

Ａ．由于键不要求是唯一的     

     

     

     

，因此每次调用 insert 总会添加一个元素    




    




    




    




。例如  




  




  




  




，可如下定义一个 multimap 容器对象将作者映射到他们所写的书的书名上



















。这样的映射可为一个作者存储多个条目：