【C++基础】系列博客为参考《C++ Primer中文版（第5版）》（C++11标准）一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.关联容器操作
除了表9.2中列出的类型，关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。
对于set类型，key_type和value_type是一样的；set中保存的值就是关键字。在一个map中，元素是关键字-值对。即，每个元素是一个pair对象，包含一个关键字和一个关联的值。由于我们不能改变一个元素的关键字，因此这些pair的关键字部分是const的：
1
2
3
4
5
set<string>::value_type v1;//v1是一个string
set<string>::key_type v2;//v2是一个string
map<string, int>::value_type v3;//v3是一个pair<const string, int>
map<string, int>::key_type v4;//v4是一个string
map<string, int>::mapped_type v5;//v5是一个int
只有map类型（unordered_map、unordered_multimap、multimap和map）才定义了mapped_type。
2.关联容器迭代器
当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。对map而言，value_type是一个pair类型，其first成员保存const的关键字，second成员保存值：
1
2
3
4
5
6
7
8
9
//获得指向word_count中一个元素的迭代器
auto map_it = word_count.begin();
//*map_it是指向一个pair<const string, size_t>对象的引用
cout << map_it->first;//打印此元素的关键字
cout << " " << map_it->second;//打印此元素的值
map_it->first = "new key";//错误：关键字是const的
*map_it = pair<string, size_t>("test", 1);//错误：关键字是const的
*map_it = pair<const string, size_t>("test", 1);//错误：关键字是const的
++map_it->second;//正确：我们可以通过迭代器改变元素
2.1.set的迭代器是const的
虽然set类型同时定义了iterator和const_iterator类型，但两种类型都只允许只读访问set中的元素。与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改：
1
2
3
4
5
6
7
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
set<int>::iterator set_it = iset.begin();
if (set_it != iset.end())
{
*set_it = 42;//错误：set中的关键字是只读的
cout << *set_it << endl;//正确：可以读关键字
}
2.2.遍历关联容器
1
2
3
4
5
6
7
8
9
//获得一个指向首元素的迭代器
auto map_it = word_count.cbegin();
//比较当前迭代器和尾后迭代器
while (map_it != word_count.cend())
{
//解引用迭代器，打印关键字-值对
cout << map_it->first << " occurs " << map_it->second << " times" << endl;
++map_it;//递增迭代器，移动到下一个元素
}
本程序的输出是按字典序排列的。当使用一个迭代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素。
1
2
3
4
5
6
7
map<string,int> m={ {"b",2},{"c",1},{"a",3} };
auto map_it = m.cbegin();
while(map_it != m.cend())
{
cout << map_it->first << " " << map_it->second << endl;
++map_it;
}
输出为：
1
2
3
a 3
b 2
c 1
map会根据关键字自动调整元素的排序。
2.3.关联容器和算法
我们通常不对关联容器使用泛型算法。关键字是const这一特性意味着不能将关联容器传递给修改或重排容器元素的算法，因为这类算法需要向元素写入值，而set类型中的元素是const的，map中的元素是pair，其第一个成员是const的。
关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速）查找，因此对其使用泛型搜索算法几乎总是个坏主意。例如，关联容器定义了一个名为find的成员，它通过一个给定的关键字直接获取元素。我们可以用泛型find算法来查找一个元素，但此算法会进行顺序搜索。使用关联容器定义的专用的find成员会比调用泛型find快得多。
在实际编程中，如果我们真要对一个关联容器使用算法，要么是将它当作一个源序列，要么当作一个目的位置。例如，可以用泛型copy算法将元素从一个关联容器拷贝到另一个序列。类似的，可以调用inserter将一个插入器绑定到一个关联容器。通过使用inserter，我们可以将关联容器当作一个目的位置来调用另一个算法。
3.添加元素
关联容器的insert成员向容器中添加一个元素或一个元素范围。由于map和set（以及对应的无序类型）包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响：
1
2
3
4
vector<int> ivec = {2,4,6,8,2,4,6,8};//ivec有8个元素
set<int> set2;//空集合
set2.insert(ivec.cbegin(), ivec.cend());//set2有4个元素
set2.insert({1,3,5,7,1,3,5,7});//set2现在有8个元素
insert有两个版本，分别接受一对迭代器，或是一个初始化器列表。
3.1.向map添加元素
对一个map进行insert操作时，必须记住元素类型是pair。
1
2
3
4
5
//向word_count插入word的4种方法
word_count.insert({word,1});
word_count.insert(make_pair(word,1));
word_count.insert(pair<string, size_t>(word,1));
word_count.insert(map<string, size_t>::value_type(word,1));
3.2.检测insert的返回值
insert（或emplace）返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，告诉我们插入操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。如果关键字已在容器中，则insert什么事情也不做，且返回值中的bool部分为false。如果关键字不存在，元素被插入容器中，且bool值为true。
1
2
3
4
5
6
7
map<string,int> m={ {"b",2},{"c",1},{"a",3} };
//ret1.first指向{"d",5}
//ret1.second为true
auto ret1 = m.insert({"d",5});
//ret2.first指向{"a",3}
//ret2.second为false
auto ret2 = m.insert({"a",5});
作为一个例子，我们用insert重写单词计数程序：
1
2
3
4
5
6
7
8
9
10
11
//统计每个单词在输入中出现次数的一种更烦琐的方法
map<string, size_t> word_count;//从string到size_t的空map
string word;
while(cin >> word)
{
//插入一个元素，关键字等于word，值为1；
//若word已在word_count中，insert什么也不做
auto ret = word_count.insert({word,1});
if(!ret.second) //word已在word_count中
++ret.first->second; //递增计数器
}
3.3.展开递增语句
在这个版本的单词计数程序中，递增计数器的语句很难理解。通过添加一些括号来反映出运算符的优先级，会使表达式更容易理解一些：
1
++((ret.first)->second);//等价的表达式
如果使用的是旧版本的编译器，或者是在新标准推出之前编写的代码，ret的声明和初始化可能复杂些：
1
pair<map<string, size_t>::iterator, bool> ret = word_count.insert(make_pair(word,1));
3.4.向multiset或multimap添加元素
1
2
3
4
5
multimap<string, string> authors;
//插入第一个元素，关键字为Barth,John
authors.insert({"Barth,John","Sot-Weed Factor"});
//正确：添加第二个元素，关键字也是Barth,John
authors.insert({"Barth,John","Lost in the Funhouse"});
对允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。这里无须返回一个bool值，因为insert总是向这类容器中加入一个新元素。
4.删除元素
关联容器定义了三个版本的erase，如表11.5所示。
5.map的下标操作
map和unordered_map容器提供了下标运算符和一个对应的at函数，如表11.6所示。set类型不支持下标，因为set中没有与关键字相关联的“值”。元素本身就是关键字，因此“获取与一个关键字相关联的值”的操作就没有意义了。我们不能对一个multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。
类似我们用过的其他下标运算符，map下标运算符接受一个索引（即，一个关键字），获取与此关键字相关联的值。但是，与其他下标运算符不同的是，如果关键字并不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化。
1
2
3
map<string, size_t> word_count; //empty map
//插入一个关键字为Anna的元素，关联值进行值初始化；然后将1赋予它
word_count["Anna"] = 1;
将会执行如下操作：
- 在word_count中搜索关键字为Anna的元素，未找到。
- 将一个新的关键字-值对插入到word_count中。关键字是一个const string，保存Anna。值进行值初始化，在本例中意味着值为0。
- 提取出新插入的元素，并将值1赋予它。
由于下标运算符可能插入一个新元素，我们只可以对非const的map使用下标操作。
对一个map使用下标操作，其行为与数组或vector上的下标操作很不相同：使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到map中。
5.1.使用下标操作的返回值
map的下标运算符与我们用过的其他下标运算符的另一个不同之处是其返回类型。通常情况下，解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但对map则不然：当对一个map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象。
与其他下标运算符相同的是，map的下标运算符返回一个左值。由于返回的是一个左值，所以我们既可以读也可以写元素：
1
2
3
cout << word_count["Anna"]; //用Anna作为下标提取元素；会打印出1
++word_count["Anna"]; //提取元素，将其增1
cout << word_count["Anna"]; //提取元素并打印它；会打印出2
6.访问元素
1
2
3
4
5
set<int> iset = {0,1,2,3,4,5,6,7,8,9};
iset.find(1); //返回一个迭代器，指向key==1的元素
iset.find(11); //返回一个迭代器，其值等于iset.end()
iset.count(1); //返回1
iset.count(11); //返回0
6.1.equal_range函数
此函数接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。
1
2
3
//pos保存迭代器对，表示与关键字匹配的元素范围
for(auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first)
cout << pos.first->second << endl;
