关联容器概述

一、前言

关联容器分为有序关联容器和无序关联容器，有序关联容器按关键字有序保存元素，底层数据结构为红黑树；无序关联容器底层数据结构是hashtable，因此是无序的。

关联容器

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

虽然关联容器的很多行为与顺序容器相同，但其不同之处反映了关键字的作用。

关联容器支持高效的关键字查找和访问。两个主要的关联容器类型是map和set。map中的元素是一些关键字-值对：关键字起到索引的作用，值则表示与索引相关联的数据。set中每个元素包含一个关键字；set支持高效的关键字查询操作——检查一个给定关键字是否在set中。例如，在某些文本处理过程中，可以用一个set来保存想要忽略的单词。字典则是一个很好的使用map的例子：可以将单词作为关键字，将单词释义作为值。

标准库提供8个关联容器，如下表所示。这8个容器间的不同体现在三个维度上：每个容器 （1）或者是一个set，或者是一个map；（2）或者要求不重复的关键字，或者允许重复关键字；（3）按顺序保存元素，或无序保存。允许重复关键字的容器的名字中都包含单词multi；不保存关键字按顺序存储的容器的名字都以单词unordered开头。因此一个unordered_multi_set是一个允许重复关键字，元素无序保存的集合，而一个set则是一个要求不重复关键字，有序存储的集合。无序容器使用哈希函数来组织元素。

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

关联容器类型

按关键字有序保存元素
map 　　　　　　　　关联数组：保存关键字-值对
set　　　　　　　　　关键字即值，即只保存关键字的容器
multimap　　　　　　关键字可重复出现的map
multiset　　　　　　   关键字可重复出现的set
无序容器
unordered_map　　　用哈希函数组织的map
unordered_set　　　　用哈希函数组织的set
unordered_multimap　　哈希组织的map；关键字可以重复出现
unordered_multiset　　  哈希组织的set；关键字可以重复出现

关联容器概述

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

除了顺序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作和类型别名。此外，无序容器还提供了一些用来调整哈希性能的操作。

关联容器的迭代器都是双向的（可读写，多遍扫描，可递增递减）。

定义关联容器

当定义一个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> autors={ {"Joyce","James"},
　　　　　　　　　　　　  {"Austen","Jane"},
　　　　　　　　　　　　  {"Dickens","Charles"}};

与以往一样，初始化器必须能转换为容器中元素的类型。对于set，元素类型就是关键字类型。
当初始化一个map时，必须提供关键字类型和值类型，我们将每个关键字-值对包围在花括号中：

　{key,value}

来指出它们一起构成了map中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。因此，anthors将姓映射到名，初始化它包括三个元素。

初始化multimap或multiset

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

关键字类型的要求

关联容器对其关键字类型有一些限制。对于无序容器中关键字的要求，我们后面介绍。对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型，在映射类型中，关键字类型是元素的第一部分的类型。因此，word_count的关键字类型是string。类似的，exclude的关键字类型也是string。

有序容器的关键字类型

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

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

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

使用关键字的比较函数

用来组织一个容器中元素的操作的类型也是容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟这元素类型给出。

在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。

例如，我们不能直接定义一个Sales_data的multiset，因为Sales_data没有<运算符。但是，可以用定义的compareIsbn函数来定义一个multiset。此函数在Sales_data对象的ISBN成员上定义了一个严格弱序。函数compareIsbn应该像下面这样定义

bool compareIsbn(const Sales_data &lhs,const Sales_data &rhs)
{
　　return lhs.isbn()<rhs.isbn();
}

为了使用自己定义的操作，在定义multiset时我们必须提供两个类型。关键字类型Sales_data，以及比较操作类型——应该是一种函数指针类型，可以指向compareIsbn。当定义此容器类型的对象时，需要提供想要使用的操作的指针。在本例中，我们提供一个指向compareIsbn的指针：

//bookstore中多条记录可以有相同的ISBN
//bookstore中的元素以ISBN的顺序进行排序
multiset<Sales_data,decltype(compareIsbn)*> bookstore(compareIsbn);

此处，我们使用decltype来指出自定义操作的类型。记住，当用decltype来获得一个函数指针类型时，必须加上一个*来指出我们要使用一个给定函数类型的指针。用compareIsbn来初始化bookstore对象，这表示当我们向bookstore添加元素时，通过compareIsbn来为这些元素排序。即，bookstore中的元素将按它们的ISBN成员的值排序。可以用compareIsbn代替&compareIsbn作为构造函数的参数，因为当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针。当然，使用&compareIsbn的效果也是一样的。

pair类型

在介绍关联容器操作之前，我们需要了解名为pair的标准库类型，它定义在头文件utility中。

一个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。word_count中的size_t 成员值为0，而string成员被初始化为空vector。

我们也可以为每个成员提供初始化器：

pair<string,string> author{"James","Joyce"};

这条语句创建了一个名为author的pair，两个成员被初始化为”James”和”Joyce”。

与其他标准库类型不同，pair的数据成员是public的。两个成员分别命名为first和second。我们用普通的成员访问符号来访问它们，例如

cout<<w.first<<" occurs "<<w.second<<endl;

此处，w 是指向某个元素的引用。map的元素是pair。在这条语句中，我们首先打印关键字——元素的first成员，接着打印计数器——second成员。标准库只定义了有限的几个pair操作，下表列出了这些操作：

pair上的操作

pair<T1,T2> p; 　　p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化
pair<T1,T2> p(v1,v2)　　p是一个成员类型为T1和T2的pair；first和second成员分别用v1和v2进行初始化
pair<T1,T2> p={v1,v2};　　等价于p(v1,v2)
make_pair(v1,v2)　　返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型推断出来
p.first　　 返回p的名为first的（公有）数据成员
p.second　　返回p的名为second的（公有）数据成员
p1 relop p2　　　　　　　　　　　　　   关系运算符（<、>、<=、>=）按字典序定义；例如，当p1.first<p2.first或!(p2.first<p1.first)&&p1.second<p2.second成立时，p1<p2为true。关系运算符利用元素的<运算符来实现
p1==p2　当first和second成员分别相等时，两个pair相等。相等性判断利用元素的==运算符实现
p1!=p2

创建pair对象的函数

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

pair<string,int>
process(vector<string> &v)
{
    //处理v
    if(!v.empty())
        return {v.back(),v.back().size()); // 列表初始化
    else
        return pair<string,int>();  //隐式构造返回值
}

在较早的C++版本中，不允许用花括号包围的初始化器来返回pair这种类型的对象，必须显示构造返回值：

if(!v.empty())
　　return pair<string,int>(v.back(),v.back().size());

我们还可以用make_pair来生成pair对象，pair的两个类型来自于make_pair的参数：

if(!v.empty())
　　return make_pair(v.back(),v.back().size());

无序容器

新标准定义了4个无序关联容器。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。在关键字类型的元素没有明显有序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。

虽然理论上哈希技术能获得更好的平均性能，但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作。因此，使用无序容器通常更为简单。

使用无序容器

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

管理桶

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

对于相同的参数，哈希函数必须总是产生相同的结果。理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量比较操作。

无序容器提供了一组管理桶的函数。如表所示。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

无序容器管理操作

桶接口
c.bucket_count()　　　　　　　　正在使用的桶的数目
c.max_bucket_count() 　　　　　 容器能容纳的最多的桶的数量
c.bucket_size(n)　　　　　　　　  第n个桶中有多少元素
c.bucket(k)　　　　　　　　　　  关键字为k的元素在哪个桶中
桶迭代
local_iterator 　　　　　　　　　可以用来访问桶中元素的迭代器类型
const_local_iterator　　　　　　 桶迭代器的const版本
c.begin(n),c.end(n)　　　　　　   桶n的首元素迭代器和尾后迭代器
c.cbegin(n),c.cend(n)　　　　       返回const_local_iterator
哈希策略
c.load_factor()　　　　　　　　　每个桶的平均元素数量，返回float值
c.max_load_factor()　　　　　　 c试图维护的平均桶大小，返回float值，c会在需要时添加新的桶，以使得load_factor<=max_load_factor
c.rehash(n)　　　　　　　　　　重组存储，使得bucket_count>=n且bucket_count>size/max_load_factor
c.reserve(n)　　　　　　　　　　重组存储，使得c可以保存n个元素且不必rehash

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

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

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

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

size_t hasher(const Sales_data &sd)
{
　　return hash<string>()(sd.isbn());
}

bool eqOp(const Sales_data &lhs,const Sales_data &rhs)
{
　　return lhs.isbn()==rhs.isbn();
}

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

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

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

为了简化bookstore的定义，首先为unordered_multiset定义了一个类型别名，此集合的哈希和相等性判断操作与hasher和eqOp函数有着相同的类型。通过使用这种类型，在定义bookstore时可以将我们希望它使用的函数的指针传递给它。

如果我们的类定义了==运算符，则可以只重载哈希函数：

//使用FooHash生成哈希值；Foo必须有==运算符
unordered_set<Foo,decltype(FooHash)*> fooset(10,FooHash);

示例

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
    unordered_map<string,int> word_count;
    word_count["to"] = 10;
    word_count["be"] = 20;
    auto iter = word_count.find("be");   //查找关键字为"be"的元素是否在unordered_map中，返回一个迭代器
    cout<<iter->first<<endl;
    cout<<iter->second<<endl;
    auto bucket = word_count.bucket("to");  //关键字为"to"的元素在那个桶上
    cout<<bucket<<endl;
    auto beg = word_count.begin(bucket);   //桶n的首元素迭代器，pair<string,int>类型
    cout<<beg->first<<endl;
    cout<<beg->second<<endl;
    return 0;
}