• 1. 使用关联容器

• 2. 关联容器概述

  • 2.1 定义关联容器
  • 2.2 关键字类型的要求
  • 2.3 pair类型

• 3. 关联容器操作

  • 3.1 关联容器迭代器
  • 3.2 添加元素
  • 3.3 删除元素
  • 3.4 map的下标操作
  • 3.5 访问元素
  • 3.6 一个单词转换的map

• 4. 无序容器

关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保存和访问的。与之相对，顺序容器中的元素是按他们在容器中的位置来顺序保存和访问的。

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。map中的元素是一些关键字-值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。set中每个元素只包含一个关键字；set支持高效的关键字查询操作——检查一个给定关键字是否在set中。

#1. 使用关联容器

map是关键字-值对的集合。map类型通常被称为关联数组。关联数组与“正常”数组类似，不同之处在于其下标不必是整数。我们通过一个关键字而不是位置来查找值。

与之相对，set就是关键字的简单集合。当只是想知道一个值是否存在时，set是最有用的。

使用map

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

void demo_map() {
    //统计每个单词在输入中出现的次数
    map<string, size_t> word_count;
    string word;
    while (cin >> word && word != "exit")
    {
        ++word_count[word]; //提取word的计数器并将其加1
    }
    for (const auto &w : word_count)
    {
        //打印结果
        cout << w.first << " occurs " << w.second
            << ((w.second > 1) ? " times" : " time") << endl;
    }
}

类似顺序容器，关联容器也是模板。为了定义一个map，我们必须指定关键字和值的类型。此例中，while循环每次从标准输入中读取一个单词。它使用每个单词对word_count进行下标操作。如果word还在map中，下标运算符会创建一个新元素，其关键字为word，值为0。不管元素是否是新创建的，我们将其值加1。

使用set

上一个示例程序的一个合理扩展是：忽略常见单词，如“the”、“and”、“or”等。我们可以使用set保存想忽略的单词，只对不在集合中的单词统计出现次数：

void demo_set() {
    //统计输入中每个单词出现的次数
    map<string, size_t> word_count; //string到size_t的空map
    set<string> exclude = { "The","But","And","Or","An","A",
                            "the","but","and","or","an","a" };
    string word;
    while (cin >> word)
    {
        //只统计不在exclude中的单词
        if (exclude.find(word) == exclude.end()) {
            ++word_count[word]; //获取并递增word的计数器
        }
    }
}

与其他容器类似，set也是模板。为了定义一个set，必须指定其元素类型，本例中是string。与顺序容器类似，可以对一个关联容器的元素进行列表初始化。

此程序与前一个程序的重要不同是，在统计每个单词出现的次数之前，我们检查单词是否在忽略集合中，这是在if语句中完成的：

//只统计不在exclude中的单词
if (exclude.find(word) == exclude.end()) {
    ++word_count[word]; //获取并递增word的计数器
}

find调用返回一个迭代器。如果给定关键字在set中，迭代器指向该关键字。否则，find返回尾后迭代器。在此程序中，仅当word不在exclude中时我们才更新word的计数器。

#2. 关联容器概述

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

2.1 定义关联容器

定义一个map时，必须既指明关键字类型又指明值类型；而定义一个set时，只需指明关键字类型，因为set中没有值。每个关联容器都定义一个默认构造函数，它创建一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。在新标准下，我们可以对关联容器进行值初始化：

map<string,size_t> word_count; //空容器
//列表初始化
set<string> exclude = {"the","but","and","or","an","a",
                        "The","But","And","Or","An","A"};
//三个元素；authors将姓映射为名
map<string,string> authors = {
    {"Joyce","James"},
    {"Austen","Jane"},
    {"Dickens","Charles"}
};

与以往一样，初始化器必须能转换为容器中元素的类型。对于set，元素类型就是关键字类型。

当初始化一个map时，必须提供关键字类型和值类型。我们将每个关键字-值对包围在花括号中：

{key,value}

来指出它们一起构成了map中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。

初始化multimap或multiset

一个map或set中关键字必须是唯一的，即，对于一个给定的关键字，只能有一个元素的关键字等于它。容器multimap和multiset没有此限制，它们都允许多个元素具有相同的关键字。

下面的例子展示了具有唯一关键字的容器和允许重复关键字的容器之间的却别。

void demo_multiset() {
    //定义一个有20个元素的vector，保存0到9每个整数的两个拷贝
    vector<int> ivec;
    for (vector<int>::size_type i = 0; i != 10; ++i) {
        ivec.push_back(i);
        ivec.push_back(i); //每个数重复保存一次
    }
    //iset包含来自ivec的不重复的元素;miset包含所有20个元素
    set<int> iset(ivec.cbegin(), ivec.cend());
    multiset<int> miset(ivec.cbegin(),ivec.cend());

    cout << ivec.size() << endl;
    cout << iset.size() << endl;
    cout << miset.size() << endl;
}

即使我们用整个ivec容器来初始化iset，它也只含有10个元素：对应ivec中每个不同的元素。

2.2 关键字类型的要求

对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。

有序容器的关键字类型

可以向一个算法提供我们自己定义的比较操作，与之类似，也可以提供自己定义的操作来代替关键字上的<运算符。所提供的操作必须在关键字类型上定义一个严格弱序。可以将严格弱序看作“小于等于”，虽然实际定义的操作可能是一个复杂的函数。无论我们怎样定义比较函数，它必须具备如下基本性质：

• 两个关键字不能同时“小于等于”对方；如果k1“小于等于”k2，那么k2绝对不能“小于等于”k1。
• 如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。
• 如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。

如果两个关键字是等价的，那么容器将它们视作相等来处理。当用作map的关键字时，只能有一个元素与这两个关键字关联，我们可以用两者中任意一个来访问对应的值。

2.3 pair类型

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

pair<string,string> anon; //保存两个string
pair<string,size_t> word_count; //保存一个string和一个size_t
pair<string,vector<int>> line; //保存string和vector<int>

pair的默认构造函数对数据成员进行值初始化。因此，anon是一个包含两个空string的pair，line保存一个空string和一个空vector。

创建pair对象的函数

想象有一个函数需要返回一个pair。在新标准下，我们可以对返回值进行列表初始化。

pair<string, size_t> process(vector<string> &v) {
    if (!v.empty()){
        return {v.back(),v.back().size()};
    }else {
        return pair<string, size_t>();
    }
}

若v不为空，我们返回一个由v中最后一个string及其大小组成的pair。否则，隐式构造一个空pair，并返回它。

#3. 关联容器操作

对于set类型，key_type和value_type是一样的；set中保存的值就是关键字。在一个map中，元素是关键字-值对。即，每个元素是一个pair对象，包含一个关键字和一个关联的值。由于我们不能改变一个元素的关键字，因此这些pair的关键字部分是const的：

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<string,int>::key_type。

3.1 关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。对map而言，value_type是一个pair类型，其first成员保存const的关键字，second成员保存值：

//获得指向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->second; //正确：我们可以通过迭代器改变元素

set的迭代器是const的

虽然set类型同时定义了iterator和const_iterator类型，但两种类型都只允许只读访问set中的元素。与不能改变一个map元素的关键字一样，一个set中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改：

set<int> iset = { 1,2,3,4,5,6,7,8 };
set<int>::iterator set_it = iset.begin();
while (set_it != iset.end()) {
    *set_it = 42;//错误：set中的关键字是只读的
    cout << *set_it << endl;
}

3.2 添加元素

关联容器的insert成员向容器中添加一个元素或一个元素范围。map和set（以及对应的无序类型）包含不重复的关键字，因此，插入一个已存在的元素对容器没有任何影响：

vector<int> ivec = {2,4,6,8,2,4,6,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有两个版本，分别接受一对迭代器，或是一个初始化器列表，这两个版本的行为类似对应的构造函数——对于一个给定的关键字，只有一个带此关键字的元素才被插入到容器中。

向map添加元素

对一个map进行insert操作时，必须记住元素类型是pair。通常，对于想要插入的数据，并没有一个现成的pair对象。可以在insert的参数列表中创建一个pair：

//向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));

如我们所见，在新标准下，创建一个pair最简单的方法是在参数列表中使用花括号初始化。也可以调用make_pair或显示构造pair。

检测insert的返回值

insert（或emplace）返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，告诉我们插入操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。如果关键字已在容器中，则insert什么事情也不做，且返回值中的bool部分为false。如果关键字不存在，元素被插入容器中，且bool值为true。

作为一个例子，我们用insert重写单词计数程序：

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 删除元素

关联容器定义了三个版本的erase，与顺序容器一样，我们可以通过传递给erase一个迭代器或一个迭代器对来删除一个元素或者一个元素范围。这两个版本的erase与对应的顺序容器的操作非常类似：指定的元素被删除，函数返回void。

关联容器提供一个额外的erase操作，接受一个key_type参数。此版本删除所有匹配给定关键字的元素（如果存在的话），返回实际删除的元素的数量。我们可以用此版本在打印结果之前从word_count中删除一个特定的单词：

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

对于保存不重复关键字的容器，erase的返回值总是0或1。若返回值为0，则表明想要删除的元素并不在容器中，对允许重复关键字的容器，删除元素的数量肯能大于1。

3.4 map的下标操作

map和unordered_map容器提供了下标运算符和一个对应的at函数。

类似我们用过的其他下标运算符，map下标运算符接受一个索引（即，一个关键字），获取与此关键字相关联的值。但是，与其他下标运算符不同的是，如果关键字并不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化。

例如，如果我们编写如下代码：

map<string, size_t> word_count;
//插入一个关键字为Anna的元素，关联值进行值初始化；然后将1赋予它
word_count["Anna"] = 1;

将会执行如下操作：

• 在word_count中搜索关键字为Anna的元素，未找到。
• 将一个新的关键字-值对插入到word_count中。关键字是一个const string，保存Anna。值进行值初始化，在本例中意味着值为0。
• 提取出新插入的元素，并将值1赋予它。

由于下标运算符可能插入一个新元素，我们只可以对非const的map进行下标操作。

==对一个map使用下标操作，其行为与数组或vector上的下标操作很不相同：使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到map中。==

使用下标操作的返回值

map的下标运算符与我们用过的其他下标运算符的另一个不同之处是其返回类型。通常情况下，解引用一个迭代器所返回的类型与下标运算符的类型是一样的。但对map则不然：当对一个map进行下标操作时，会获得一个mapped_type对象；但当解引用一个map迭代器时，会得到一个value_type对象。

与其他下标运算符相同的是，map的下标运算符返回一个左值。由于返回的是一个左值，所以我们既可以读也可以写元素：

cout << word_count["Anna"]; //用Anna作为下标提取元素；会打印1
++word_count["Anna"]; //提取元素，将其增1
cout << word_count["Anna"]; //提取元素并打印它；会打印出2

3.5 访问元素

关联容器提供多种查找一个指定元素的方法。

对map使用find代替下标操作

下标操作有一个严重的副作用：如果关键字还未在map中，下标操作会插入一个具有给定关键字的元素。这种行为是否正确完全依赖于我们的预期是什么。例如，单词计数程序依赖于这样一个特性：使用一个不存在的关键字作为下标，会插入一个新元素，其关键字为给定关键字，其值为0。也就是说，下标操作的行为符合我们的预期。

但有时，我们只想知道一个给定关键字是否在map中，而不想改变map。这样就不能使用下标运算符来检查一个元素是否存在，因为关键字不存在的话，下标运算符会插入一个新元素。在这种情况下，应该使用find：

if(word_count.find("foobar") == word_count.end()) {
    cout << "foobar is not in the map" << endl;
}

在multimap和multiset中查找元素

对于允许重复关键字的容器来说，在容器中可能有很多元素具有给定的关键字。如果一个multimap或multiset中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。

例如，给定一个从作者到著作题目的映射，我们可能想打印一个特定作者的所有著作。可以用三种不同的方法来解决这个问题。最直观的方法是使用find和count：

string search_item("Alain de Botton"); //要查找的作者
auto entries = authors.count(search_item); //元素的数量
auto iter = authors.find(search_item); //容器中的第一个此类元素
while(entries) {
    cout << iter->second << endl;
    ++iter; //前进到下一个元素的位置
    --entries; //记录打印的元素的数量
}

首先调用count确定此作者共有多少本著作，并调用find获得一个迭代器，指向第一个关键字为此作者的元素。for循环的迭代次数依赖于count的返回值。特别是，如果count返回0，则循环一次也不执行。

==但我们遍历一个multimap或multiset时，保证可以得到序列中的所有具有给定关键字的元素。==

一种不同的， 面向迭代器的解决方案

我们还可以用lower_bound和upper_bound来解决此问题。这两个操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound返回的迭代器将指向第一个具有给定关键字的元素，而upper_bound返回的迭代器则指向最后一个匹配给定关键字的元素之后的位置。如果元素不在multimap中，则lower_bound和upper_bound会返回相等的迭代器——指向一个不影响排序的关键字插入位置。因此，用相同的关键字调用lower_bound和upper_bound会得到一个迭代器范围，表示所有具有该关键字的元素的范围。

当然，这两个操作返回的迭代器可能是容器的尾后迭代器。如果我们查找的元素具有容器中的最大的关键字，则此关键字的upper_bound返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则lower_bound返回的也是尾后迭代器。

==lower_bound返回的迭代器可能指向一个具有给定关键字的元素，但也可能不指向。如果关键字不在容器中，则lower_bound会返回关键字的第一个安全插入点——不影响容器中元素顺序的插入位置。==

使用这两个操作，我们可以重写前面的程序：

for(auto beg = authors.lower_bound(search_item),
    end = authors.upper_bound(search_item);beg != end; ++beg) {
    cout << beg->second <<endl;
}

此程序与count和find版本完成相同的工作，但更直接。

==如果lower_bound和upper_bound返回的相同的迭代器，则给定的关键字不在容器中。==

equal_range函数

解决此问题的最后一种方法是三种方法中最直接的：不必再调用upper_bound和lower_bound，直接调用equal_range即可。此函数接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素之后的位置。若未找到匹配元素，则两个迭代器都指向关键字可以插入的位置。

//authors和search_item的定义，与前面的程序一样
//pos保存迭代器对，表示与关键字匹配的元素范围
for(auto pos = authors.equal_range(search_item); 
    pos.first != pos.second;
    ++pos.first) {
    cout << pos.first->second <<endl;
}

#4. 无序容器

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

==如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。==

使用无序容器

除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作（find、insert等）。这意味着我们曾用于map和set的操作也能用于unordered_map和unordered_set。类似的，无序容器也有允许重复关键字的版本。

因此，通常可以用一个无序容器替换对应的有序容器，反之亦然。但是，由于元素未按顺序存储，一个使用无序容器的程序的输出（通常）会与使用有序容器的版本不同。

例如，可以用unordered_map重写最初的单词计数程序：

//统计出现次数，但单词不会按字典序排列
unordered_map<string,size_t> word_count;
string word;
while(cin >> word) {
    ++word_count[word]; //提取并递增word的计数器
}
for(const auto &w : word_count) { //对map中的每个元素
    cout << w.first << " occurs " << w.second
        << ((w.second > 1) ? " times" : " time") << endl;
}

管理桶

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

无序容器对关键字类型的要求

默认情况下，无序容器使用关键字类型的==运算符来比较元素，它们还使用hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型（包括指针）提供了hash模板。因此，我们可以直接定义关键字是内置类型（包括指针类型）、string还是智能指针类型的无序容器。

但是，我们不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的hash模板版本。

我们不适用默认的hash，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作。例如：为了将Sales_data用作关键字，我们需提供函数来替代==运算符和哈希值计算函数。我们从定义这些函数开始：

size_t haser(const Sales_data &sd) {
    return hash<string>() (sd.isbn());
}
bool eqOp(const Sales_data &lhs,const Sales_data &rhs) {
    return lsh.isbn() == rhs.isbn();
}

我们的hasher函数使用一个标准库hash类型对象来计算ISBN成员的哈希值，该hash类型建立在string类型之上。类似的，eqOp函数通过比较ISBN来比较两个Sales_data。

我们使用这些函数来定义一个unordered_multiset

using SD_multiset = unordered_multiset<Sales_data,decltype<hasher>*,decltype(eqOp)*>;
//参数是桶大小、哈希函数指针和相等性判断运算符指针
SD_multiset bookstore(42,hasher,eqOp);