关联容器

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。map中的元素是一些关键字-值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。set中每个元素只包含一个关键字，set支持高效的关键字查询操作–检查一个给定关键字是否存在set中。
简单来说，map可以理解为关键字-值对的集合，可以称为关联数组。而map可以理解为关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。
而在标准库中提供8个关联容器，这8个关联容器的不同主要体现在一下三个维度上：

1. 或者是一个map，或者是一个set
2. 或者要求不重复的关键字，或者允许出现重复的关键字
3. 按顺序保存元素，或者无序保存元素。

根据这三个特征定义出的8个关联容器如下所示：

按关键字有序保存元素（按照关键字升序排列）

1. map 关联数组，保存关键字-键对
2. set 关键字即值，即只保存关键字容器
3. multimap 关键字可重复出现的map
4. multiset 关键字可重复出现的set

无序集合

1. unordered_map 用哈希函数组织的map
2. unordered_set 用哈希函数组织的set
3. unordered_multimap 用哈希函数组织的map：关键字可以重复出现
4. unordered_multiset 用哈希函数组织的set：关键字可以重复出现

类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容易则定义在头文件unordered_map和unordered_set中。

关联容器的使用

使用map

一个经典的使用关联数组的例子就是单词计数程序

map<string,size_t> wordCount;
string word;
while(cin >> word)
    ++ wordCount[word];
for(const auto &w : wordCount)
cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << endl;

上述是一个比较经典的使用map的例子，类似顺序容器，关联容器也是模板。为了定义一个map，我们必须指定关键字和值的类型。

使用set

根据上述程序做一个扩展，忽略常见单词，如“the”、“and”、“or”等。这个时候我们可以用set来存储这些关键字。具体实现如下所示：

map<string,size_t> wordCount;
set<string> exculde = {"The","And","Or",
            "the","and","or"};
string word;
while(cin >> word)
    if(exculde.find(word) == exculde.end())
        ++ wordCount[word];

和map类似，set也是模板，所以为了定义一个set必须指定其元素类型。至于判定该元素是否在忽略字符串集合中，利用find调用之后返回的迭代器来判断，当set中存在这个元素时，find会返回指向这个位置的迭代器，否则，find会返回尾后迭代器。

关联容器概述

关联容器不支持顺序容器关于位置相关的操作，比如push_back、push_front。原因是关联容器中元素是根据关键字存储的，这些操作对于关联容器是没有意义的。关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。
并且关联容器迭代器都是双向的。

当初始化一个map时，必须提供关键字类型和值类型。我们将每个关键字-值包围在花括号里，如{key,value},一组键值对一起构成了map中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。

关键字类型的要求

对于有序容器–map、set、multimap、multiset，关键字类型必须定义元素比较的方法（这样才可以实现关键字有序）。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。
所提供的操作必须在关键字类型上定义一个严格弱序。如果两个关键字是等价的（即，任何一方都不“小于等于”另一个），那么容器将它们视为相等来处理。当用作 map的关键字时，只能有一个元素与这两个关键字相关联，而且可以使用这两个关键字其中之一来访问对应的值。
用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型是提供此操作的类型。
举例如下所示：

bool compareIsbn(const SalesData &lhs,const SalesData &rhs){

    return lhs.isbn() < rhs.isbn();
}

multiset<SalesData,decltype(compareIsbn)*> bookstore(compareIsbn);

pair 类型

pair类型定义在头文件utility中。一个pair保存两个数据成员。类似容器，pair是一个用来生成特定类型的模板。当创建一个pair时，我们必须提供两个类型名，pair的数据成员将具有对应的类型，不过两个类型不要求一样。

与其他标准库类型不同，pair的数据成员是public的。两个成员分别命名为 first和second。

关联容器操作

关联容器迭代器

一个map的value_type是一个pair类型，我们可以改变pair的值，但不能改变关键字成员的值。迭代器在使用时，不能更改关键字的值，因为其是const的。
set的迭代器是const的，迭代器只允许只读访问set中的元素。与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改。
通常我们不对关联容器使用泛型算法。关键字是const这一特性意味不能将关联容器传递给修改或重排容器元素的算法，因为这类算法需要向元素写入值，而set类型中的元素是const的，map中的元素是pair的，其第一个成员是const的。
对于关联容器我们一般进行的操作就是添加键值对或关键字，查询操作。当然，便利的操作是一种低效的查询方式，在关联容器中提供了一种查询方法find，这种专门为关联容器定义的find成员会比调用其他的方法效率高很多。

添加元素

set的insert存在两个版本，分别接受一对迭代器，或是一个初始化列表。
map的insert，必须 记住元素类型是pair。通常对于要插入的数据，并没有现成的pair对象。可以在insert的参数创建一个pair：

wordCount.insert({word,1});
wordCount.insert(make_pair(word,1));
wordCount.insert(pair<string,size_t>(word,1));
wordCount.insert(map<string,size_t>::value_type(word,1));

关于insert的返回值，返回值依赖于容器类型和参数，对于不包含重复关键字的容器，添加单一元素的insert和emplace版本会返回一个pair，告诉我们插入操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。若元素已经存在于容器中，则insert什么事情也不错，返回值中的bool部分为false。
下面举一个统计每个单词在输入中出现次数的例子：

map<string,size_t> wordCount;
string word;
while(cin >> word)
{
    auto ret = wordCount.insert({word,1});
    if(!ret.second)
        ++ ret.first->second;
}

上述例子中，ret的类型为pair<map<string,size_t>::iterator,bool> ret= wordCount.insert({word,1})
对于允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。这里无须返回一个bool值，因为每次insert总是向这类容器中写入一个新元素。

删除元素

关联容器定义了三个版本的erase，与顺序容器一样，我们可以通过传递给erase一个迭代器或一个迭代器对来删除一个元素或者一个元素范围。当指定元素被删除以后返回void。
而关联容器提供一个额外的删除操作，它可以接受一个key_type参数。此版本删除所有匹配给定关键字的元素，返回实际删除的元素的数量。
所以对于保存不重复关键字的容器，erase的返回值总是0或1。若返回值为0，则表明想要删除的元素并不在容器里。
对允许重复关键字的容器，删除元素的数量可能大于1；

map的下标操作

map和unordered_map容器提供了下标运算符和一个对应的at函数。set不支持下标操作，因为set中没有与关键字相关联的值。并且也不能对multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字想关联。
下标运算符，如果此关键字不在map中，会为它创建一个元素并插入到map中。
at函数，访问关键字对应的元素，并带有参数检查，若关键字不在关联容器中，会抛出一个out_of_range异常。
至于返回值，需要重点关注一下返回值的类型，当对map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象。

访问元素

关联容器提供多种查找一个指定元素的方法。如果我们只是关心一个特定元素是否包含在容器中，find是最好的选择。对于不允许重复关键字的容器，可能使用find还是count并没有什么区别，但对于允许重复关键字的容器，count还会做更多的工作：如果关键字在容器中，还会统计关键字出现的次数，而find不会做这个操作。
find会返回一个迭代器，指向关键字对应的元素，若关键字不在容器中，则返回尾后迭代器。
count会返回关键字等于关键字的元素的数量，对于不允许重复关键字的容器，返回值永远是0和1。
c.lower_bound(k)返回一个迭代器，指向第一个关键字不小于k的元素。
c.upper_bound(k)返回一个迭代器，指向第一个关键字大于k的元素。
c.equal_range(k)返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end();

对map和unordered_map类型，下标运算符提供了最简单的提取元素的方法。但是如我们所见，使用下标操作有一个非常严重的副作用：如果关键字在map中不存在，下标操作会插入一个具有给定关键字的元素。这种行为有时候会引来错误。所以当我们只是想知道一个给定关键字是否存在与map中，而不想改变map。这样就不能使用下标运算符来检查一个元素是否存在。
在multimap或multiset中查找元素，如果其中多个元素具有给定的关键字，则这些元素在容器中会相邻存储。
对于提取出这些相同的元素有三种思路，具体如下：

1. 利用count返回这个关键字对应的元素的数目，利用find函数返回关键字对应的第一个元素的迭代器。
2. 可以借用upper_bound和lower_bound的返回迭代器来确定相同元素的范围，如果返回相同的迭代器，则给定的关键字不在容器中。
3. 直接调用equal_range函数，返回一个迭代器pair，若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个关键字指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。即两个迭代器是相等的。

一个关于单词转换的map

在最后举一个应用之前所学的例子，具体程序功能如下所示：

给定一个string，将它转换为另一个string。程序的输入是两个文件。第一个保存的是一些规则，用来转换第二个文件中的文本。每条规则由两部分组成：一个可能出现在输入文件中的单词和一个用来替代它的词语。表达的含义是，每当第一个单词在输入中时，我们就将它替代为对应的短语。第二个输入文本包含要转换的文本。

具体实现代码如下：

#include <map>
#include <fstream>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;

map<string, string> bulidMap(ifstream &mapFile)
{
    map<string, string> transMap;
    string key;
    string value;
    while (mapFile >> key && getline(mapFile, value))
    {
        if (value.size() > 1)
        {
            transMap[key] = value.substr(1);
        }
        else
        {

        }
    }
    return transMap;
}

const string & transform(const string &s, const map<string, string> &m){

    auto mapIt = m.find(s);
    if (mapIt != m.cend())
        return mapIt->second;
    else
        return s;
}

void wordTransform(ifstream &mapfile, ifstream &input){

    auto transMap = bulidMap(mapfile);
    string text;
    while (getline(input, text))
    {
        istringstream strm(text);
        string word;
        bool firstWord = true;
        while (strm >> word)
        {
            if (firstWord)
            {
                firstWord = false;
            }
            else
            {
                cout << ' ';
            }
            cout << transform(word, transMap);
        }
        cout << endl;
    }
}

int main(){

    std::ifstream input("input.txt",std::ifstream::in);
    std::ifstream replace("replace.txt",std::ifstream::in);
    wordTransform(replace, input);

    return 0;
}

无序容器

在新标准中定义了4个无序容器，这些容器不是使用比较运算符来组织元素的，而是使用了一个哈希函数和关键字类型的==运算符。

管理桶

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。如果容器允许重复关键字，所有具有相同关键字的元素都会在同一个桶里。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

理想情况下，哈希函数将每个特定的映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的元素。

赏

谢谢你请我吃糖果

支付宝

微信