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 对象中插入一组元素时，对于每个键，事实上都只添加了一个元素。

?

1 2 3 4 5 6 7 8 9 10

// define a vector with 20 elements, holding two copies of each number from 0 to 9 vector<int> ivec; for (vector<int>::size_type i = 0; i != 10; ++i) { ivec.push_back(i); ivec.push_back(i); // duplicate copies of each number } // 对于vector中的重复元素，只插入一个。 set<int> iset(ivec.begin(), ivec.end()); cout << ivec.size() << endl; // prints 20 cout << iset.size() << endl; // prints 10</int></int></int>

3.往set中添加元素：与 map 容器的操作一样，带有一个键参数的 insert 版本返回 pair 类型对象，包含一个迭代器和一个 bool 值，迭代器指向拥有该键的元素，而 bool 值表明是否添加了元素。使用迭代器对的 insert 版本返回 void 类型。

?

1 2 3 4

iset.find(1) // returns iterator that refers to the element with key == 1 iset.find(11) // returns iterator == iset.end() iset.count(1) // returns 1 iset.count(11) // returns 0

?

1

４.正如不能修改 map 中元素的键部分一样，set 中的键也为 const。在获得指向 set 中某元素的迭代器后，只能对其做读操作，而不能做写操作：

?

1 2 3 4

// set_it refers to the element with key == 1 set<int>::iterator set_it = iset.find(1); *set_it = 11; // error: keys in a set are read-only cout << *set_it << endl; // ok: can read the key</int>

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

1.multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同，只有一个例外：multimap 不支持下标运算。不能对 multimap 对象使用下标操作，因为在这类容器中，某个键可能对应多个值。

2.元素的添加和删除：

Ａ．由于键不要求是唯一的，因此每次调用 insert 总会添加一个元素。例如，可如下定义一个 multimap 容器对象将作者映射到他们所写的书的书名上。这样的映射可为一个作者存储多个条目：

?

1 2 3 4 5 6 7 8 9

// adds first element with key Barth authors.insert(make_pair( string("Barth, John"), string("Sot-Weed Factor"))); // ok: adds second element with key Barth authors.insert(make_pair( string("Barth, John"), string("Lost in the Funhouse")));

?

1

?

1	Ｂ．<strong>带有一个键参数的 <tt>erase</tt> 版本将删除拥有该键的所有元素，并返回删除元素的个数。</strong>而带有一个或一对迭代器参数的版本只删除指定的元素，并返回 <tt>void</tt> 类型：

?

1

?

1	3.在 <tt>multimap</tt> 和 <tt>multiset</tt> 中查找元素:<strong>在 <tt>multimap</tt> 和 <tt>multiset</tt> 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。</strong>