C++标准库学习（二）：关联容器

关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器类型是map和set。map的元素以键-值（key-value）对的形式组织：键用于元素在map中的索引，而值则表示所存储和读取的数据。set仅包含一个键，并有效地支持关于某个键是否存在的查询。map可理解为字典，set可理解为一类元素的集合。

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

一般来说，如果希望有效地存储不同值的集合，那么使用 set 容器比较合适，而 map 容器则更适用于需要存储（乃至修改）每个键所关联的值的情况。在做某种文本处理时，可使用 set 保存要忽略的单词。而字典则是 map 的一种很好的应用：单词本身是键，而它的解释说明则是值。

set 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。如果一个键必须对应多个实例，则需使用 multimap 或 multi set，这两种类型允许多个元素拥有相同的键。

---

1 pair类型

pair 包含两个数据值。在创建 pair 对象时，必须提供两个类型名：pair 对象所包含的两个数据成员各自对应的类型名字。如果在创建 pair 对象时不提供初始化式，则调用默认构造函数对其成员采用值初始化。也可在定义时为每个成员提供初始化式。

pair <string, int> word_count;
pair <string, string> author("James", "Joy");

pair 类型的使用相当繁琐，因此，如果需要定义多个相同的 pair 类型对象，可考虑利用 typedef 简化其声明：

typedef pair<string, string> Author; 
Author joyce("James", "Joyce");

与其他标准库类型不同，对于 pair 类，可以直接访问其数据成员：其成员都是仅有的，分别命名为 first 和 second。只需使用普通的点操作符（成员访问标志）即可访问其成员：

string firstBook; 
if (author.first == "James" && author.second == "Joyce") 
    firstBook = "Stephen Hero"; 

除了构造函数，标准库还定义了一个 make_pair 函数，由传递给它的两个实参生成一个新的 pair 对象。可如下使用该函数创建新的 pair 对象，并赋给已存在的 pair 对象：

pair<string, string> next_auth; 
string first, last; 
while (cin >> first >> last) { 
    next_auth = make_pair(first, last); 
} 

---

2 map类型

map 是键－值对的集合。map 类型通常可理解为关联数组（associative array）：可使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。在使用关联容器时，它的键不但有一个类型，而且还有一个相关的比较函数。默认情况下，标准库使用键类型定义的 < 操作符来实现键的比较。

2.1 map对象的定义

map的构造函数

map 对象的元素是键－值对，也即每个元素包含两个部分：键以及由键关联的值。map 的 value_type 就反映了这个事实。该类型比前面介绍的容器所使用的元素类型要复杂得多：value_type 是存储元素的键以及值的 pair 类型，而且键为 const。例如，word_count 数组的 value_type 为 pair<const string, int> 类型。

map <string,int> word_count;
word_count.insert( make_pair("James", "Joyce") );
map<string, int>::iterator map_it = word_count.begin(); 
 cout << map_it->first; 
 cout << " " << map_it->second;

2.2 给 map 添加元素

定义了 map 容器后，下一步工作就是在容器中添加键－值元素对。该项工作可使用 insert 成员实现；或者，先用下标操作符获取元素，然后给获取的元素赋值。在这两种情况下，一个给定的键只能对应于一个元素这一事实影响了这些操作的行为。

用下标操作符来获取该键所关联的值。如果该键已在容器中，则返回该键所关联的值。只有在所查找的键不存在时，map 容器才为该键创建一个新的元素，并将它插入到此 map 对象中。此时，所关联的值采用值初始化：类类型的元素用默认构造函数初始化，而内置类型的元素初始化为 0。

map<string, int> word_count; // empty map from string to int 
string word; 
while (cin >> word) 
    ++word_count[word]; 

使用下标给 map 容器添加新元素时，元素的值部分将采用值初始化。通常，我们会立即为其赋值，其实就是对同一个对象进行初始化并赋值。而插入元素的另一个方法是：直接使用 insert 成员，其语法更紧凑：

word_count.insert(map<string, int>::value_type("Anna", 1)); 
word_count.insert(make_pair("Anna", 1)); 

map 对象中一个给定键只对应一个元素。如果试图插入的元素所对应的键已在容器中，则 insert 将不做任何操作。但是，带有一个键－值 pair 形参的 insert 版本将返回一个值：包含一个迭代器和一个 bool 值的 pair 对象，其中迭代器指向 map 中具有相应键的元素，而 bool 值则表示是否插入了该元素。如果该键已在容器中，则其关联的值保持不变，返回的 bool 值为 true。在这两种情况下，迭代器都将指向具有给定键的元素。

map<string, int> word_count; 
string word; 
while (cin >> word) { 
    // inserts element with key equal to word and value 1; 
    // if word already in word_count, insert does nothing 
    pair<map<string, int>::iterator, bool> ret =  
         word_count.insert(make_pair(word, 1)); 
    if (!ret.second)          // word already in word_count 
        ++ret.first->second;  // increment counter 
} 

2.3 查找并读取 map 中的元素

不能使用下标来查找map中的某一元素是否存在，因为如果该键不在 map 容器中，那么下标操作会插入一个具有该键的新元素。map 容器提供了两个操作：count 和 find，用于检查某个键是否存在而不会插入该键。

对于 map 对象，count 成员的返回值只能是 0 或 1。map 容器只允许一个键对应一个实例，所以 count 可有效地表明一个键是否存在。find 操作返回指向元素的迭代器，如果元素不存在，则返回 end 迭代器。

int occurs = 0;
map <string, int>::iterator it = word_count.find("foobar");
if(it != wor_count.end() )
    occurs = it->second;

2.4 从 map 对象中删除元素

从 map 对象中删除元素

if (word_count.erase(removal_word)) 
    cout << "ok: " << removal_word << " removed\n"; 
else cout << "oops: " << removal_word << " not found!\n"; 

2.5 map 对象的迭代遍历

与其他容器一样，map 同样提供 begin 和 end 运算，以生成用于遍历整个容器的迭代器。例如，可如下将 map 容器 word_count 的内容输出：

map<string, int>::const_iterator it = word_count.begin();
while(it != word_count.end()){
    cout<< it->first <<" occurs "
            << it->second << " times " <<endl;
    ++it;
}

---

3 set类型

map 容器是键－值对的集合，好比以人名为键的地址和电话号码。相反地，set 容器只是单纯的键的集合。例如，某公司可能定义了一个名为 bad_checks 的 set 容器，用于记录曾经给本公司发空头支票的客户。当只想知道一个值是否存在时，使用 set 容器是最适合的。例如，在接收一张支票前，该公司可能想查询 bad_checks 对象，看看该客户的名字是否存在。

set 容器支持大部分的 map 操作，包括上面描述的构造函数、 insert 操作、 count 和 find 操作、 erase 操作等。但是， 不支持下标操作符，而且没有定义 mapped_type 类型。在 set 容器中，value_type 不是 pair 类型，而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。这一差别也体现了 set 存储的元素仅仅是键，而没有所关联的值。与 map 一样，set 容器存储的键也必须唯一，而且不能修改。

vector<int> ivec;
for( vector<int>::size_type i = 0; i !=10; ++i){
    ivec.push_back(i);
    ivec.push_back(i);
}
set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl;      // prints 20 
cout << iset.size() << endl;      // prints 10 

set<string> set1;
set1.insert("the");

set<int> iset2;
iset2. insert( ivec.begin(), ivec.end() );     // iset2 has 10 elements

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 

set<int>::iterator set_it = isec.find(1);
cout<< *set_it <<endl;

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

4 multimap 和 multiset 类型

map 和 set 容器中，一个键只能对应一个实例。而 multiset 和 multimap 类型则允许一个键对应多个实例。例如，在电话簿中，每个人可能有单独的电话号码列表。在作者的文章集中，每位作者可能有单独的文章标题列表。multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义：分别是 map 和 set 头文件。

multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同，只有一个例外：multimap 不支持下标运算。不能对 multimap 对象使用下标操作，因为在这类容器中，某个键可能对应多个值。为了顺应一个键可以对应多个值这一性质，map 和 multimap，或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 时，对于某个键，必须做好处理多个值的准备，而非只有单一的值。

由于键不要求是唯一的，因此每次调用 insert 总会添加一个元素。

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

关联容器 map 和 set 的元素是按顺序存储的， multimap 和 multset 也一样。因此，在 multimap 和 multiset 容器中，如果某个键对应多个实例，则这些实例在容器中将相邻存放。 在 multimap 和 multiset 中查找元素有三种策略，而且三种策略都基于一个事实——在 multimap 中，同一个键所关联的元素必然相邻存放。

• 使用 find 和 count 操作

• lower_bound 和 upper_bound
• enual_range 函数

返回迭代器的关联容器操作

equal_range 函数返回存储一对迭代器的 pair 对象。如果该值存在，则 pair 对象中的第一个迭代器指向该键关联的第一个实例，第二个迭代器指向该键关联的最后一个实例的下一位置。如果找不到匹配的元素，则 pair 对象中的两个迭代器都将指向此键应该插入的位置。

pair<authors_it, authors_it> pos = authors.equal_range(search_item); 
while (pos.first != pos.second) { 
    cout << pos.first->second << endl; 
    ++pos.first; 
}