第11章关联容器

关联容器支持高效的关键字查找和访问操作。2个主要的关联容器（associative-container）类型是map和set。

map中的元素是一些键值对（key-value）：关键字起索引作用，值表示与索引相关联的数据。
set中每个元素只包含一个关键字，支持高效的关键字查询操作：检查一个给定关键字是否在set中。

标准库提供了8个关联容器，它们之间的不同体现在三个方面：

是map还是set类型。
是否允许保存重复的关键字。
是否按顺序保存元素。

允许重复保存关键字的容器名字都包含单词multi；无序保存元素的容器名字都以单词unordered开头。

有序容器：

类型	特性
`map`	保存键值对的关联数组
`set`	只保存关键字的容器
`multimap`	关键字可重复出现的`map`
`multiset`	关键字可重复出现的`set`

无序容器：

类型	特性
`unordered_map`	用哈希函数管理的`map`
`unordered_set`	用哈希函数管理的`set`
`unordered_multimap`	关键字可重复出现的`unordered_map`
`unordered_multiset`	关键字可重复出现的`unordered_set`

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

使用关联容器（Using an Associative Container）

map类型通常被称为关联数组（associative array）。

从map中提取一个元素时，会得到一个pair类型的对象。pair是一个模板类型，保存两个名为first和second的公有数据成员。map所使用的pair用first成员保存关键字，用second成员保存对应的值。

// count the number of times each word occurs in the input
map<string, size_t> word_count;     // empty map from string to size_t
string word;
while (cin >> word)
    ++word_count[word];     // fetch and increment the counter for word
for (const auto &w : word_count)    // for each element in the map
    // print the results
    cout << w.first << " occurs " << w.second
        << ((w.second > 1) ? " times" : " time") << endl;

set类型的find成员返回一个迭代器。如果给定关键字在set中，则迭代器指向该关键字，否则返回的是尾后迭代器。

关联容器概述（Overview of the Associative Containers）

定义关联容器（Defining an Associative Container）

定义map时，必须指定关键字类型和值类型；定义set时，只需指定关键字类型。

初始化map时，提供的每个键值对用花括号{}包围。

map<string, size_t> word_count;   // empty
// list initialization
set<string> exclude = { "the", "but", "and" };
// three elements; authors maps last name to first
map<string, string> authors =
{
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {"Dickens", "Charles"}
};

map和set中的关键字必须唯一，multimap和multiset没有此限制。

关键字类型的要求（Requirements on Key Type）

对于有序容器——map、multimap、set和multiset，关键字类型必须定义元素比较的方法。默认情况下，标准库使用关键字类型的<运算符来进行比较操作。

用来组织容器元素的操作的类型也是该容器类型的一部分。如果需要使用自定义的比较操作，则必须在定义关联容器类型时提供此操作的类型。操作类型在尖括号中紧跟着元素类型给出。

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

// bookstore can have several transactions with the same ISBN
// elements in bookstore will be in ISBN order
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

`pair`类型（The `pair` Type）

pair定义在头文件utility中。一个pair可以保存两个数据成员，分别命名为first和second。

pair<string, string> anon;        // holds two strings
pair<string, size_t> word_count;  // holds a string and an size_t
pair<string, vector<int>> line;   // holds string and vector<int>

pair的默认构造函数对数据成员进行值初始化。

在C++11中，如果函数需要返回pair，可以对返回值进行列表初始化。早期C++版本中必须显式构造返回值。

pair<string, int> process(vector<string> &v)
{
    // process v
    if (!v.empty())
        // list initialize
        return { v.back(), v.back().size() };
    else
        // explicitly constructed return value
        return pair<string, int>();
}

关联容器操作（Operations on Associative Containers）

关联容器定义了类型别名来表示容器关键字和值的类型。

类型	含义
`key_type`	容器的关键字类型
`mapped_type`	`map`的值类型
`value_type`	对于`set`，与`key_type`相同对于`map`，为`pair<const key_type, mapped_type>`

对于set类型，key_type和value_type是一样的。set中保存的值就是关键字。对于map类型，元素是键值对。即每个元素是一个pair对象，包含一个关键字和一个关联的值。由于元素关键字不能改变，因此pair的关键字部分是const的。另外，只有map类型（unordered_map、unordered_multimap、multimap、map）才定义了mapped_type。

set<string>::value_type v1;        // v1 is a string
set<string>::key_type v2;          // v2 is a string
map<string, int>::value_type v3;   // v3 is a pair<const string, int>
map<string, int>::key_type v4;     // v4 is a string
map<string, int>::mapped_type v5;  // v5 is an int

关联容器迭代器（Associative Container Iterators）

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

// get an iterator to an element in word_count
auto map_it = word_count.begin();
// *map_it is a reference to a pair<const string, size_t> object
cout << map_it->first;          // prints the key for this element
cout << " " << map_it->second;  // prints the value of the element
map_it->first = "new key";      // error: key is const
++map_it->second;               // ok: we can change the value through an iterator

虽然set同时定义了iterator和const_iterator类型，但两种迭代器都只允许只读访问set中的元素。类似map，set中的关键字也是const的。

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;       // error: keys in a set are read-only
    cout << *set_it << endl;    // ok: can read the key
}

map和set都支持begin和end操作。使用迭代器遍历map、multimap、set或multiset时，迭代器按关键字升序遍历元素。

通常不对关联容器使用泛型算法。

添加元素（Adding Elements）

使用insert成员可以向关联容器中添加元素。向map和set中添加已存在的元素对容器没有影响。

通常情况下，对于想要添加到map中的数据，并没有现成的pair对象。可以直接在insert的参数列表中创建pair。

// four ways to add word to word_count
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));

insert或emplace的返回值依赖于容器类型和参数：

对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，表示操作是否成功。pair的first成员是一个迭代器，指向具有给定关键字的元素；second成员是一个bool值。如果关键字已在容器中，则insert直接返回，bool值为false。如果关键字不存在，元素会被添加至容器中，bool值为true。
对于允许包含重复关键字的容器，添加单一元素的insert和emplace版本返回指向新元素的迭代器。

删除元素（Erasing Elements）

与顺序容器不同，关联容器提供了一个额外的erase操作。它接受一个key_type参数，删除所有匹配给定关键字的元素（如果存在），返回实际删除的元素数量。对于不包含重复关键字的容器，erase的返回值总是1或0。若返回值为0，则表示想要删除的元素并不在容器中。

`map`的下标操作（Subscripting a `map`）

操作	含义
`c[k]`	返回关键字为`k`的元素；若`k`不存在，则向`c`中添加并进行值初始化
`c.at(k)`	返回关键字为`k`的元素；若`k`不存在，则抛出`out_of_range`异常

map下标运算符接受一个关键字，获取与此关键字相关联的值。如果关键字不在容器中，下标运算符会向容器中添加该关键字，并值初始化关联值。

由于下标运算符可能向容器中添加元素，所以只能对非const的map使用下标操作。

对map进行下标操作时，返回的是mapped_type类型的对象；解引用map迭代器时，返回的是value_type类型的对象。

访问元素（Accessing Elements）

操作	含义
`c.find(k)`	返回指向第一个关键字为`k`的元素的迭代器或尾后迭代器
`c.count(k)`	返回关键字为`k`的元素的数量
`c.lower_bound(k)`	返回指向第一个关键字不小于`k`的元素的迭代器
`c.upper_bound(k)`	返回指向第一个关键字大于`k`的元素的迭代器
`c.equal_range(k)`	返回一个迭代器`pair`，表示关键字为`k`的元素范围

如果multimap或multiset中有多个元素具有相同关键字，则这些元素在容器中会相邻存储。

multimap<string, string> authors;
// adds the first element with the key Barth, John
authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: adds the second element with the key Barth, John
authors.insert({"Barth, John", "Lost in the Funhouse"});

string search_item("Alain de Botton");      // author we'll look for
auto entries = authors.count(search_item);  // number of elements
auto iter = authors.find(search_item);      // first entry for this author
// loop through the number of entries there are for this author
while(entries)
{
    cout << iter->second << endl;   // print each title
    ++iter;      // advance to the next title
    --entries;   // keep track of how many we've printed
}

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

// definitions of authors and search_item as above
// beg and end denote the range of elements for this author
for (auto beg = authors.lower_bound(search_item),
        end = authors.upper_bound(search_item);
    beg != end; ++beg)
    cout << beg->second << endl;    // print each title

lower_bound和upper_bound有可能返回尾后迭代器。如果查找的元素具有容器中最大的关键字，则upper_bound返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则lower_bound也返回尾后迭代器。

equal_range操作接受一个关键字，返回一个迭代器pair。若关键字存在，则第一个迭代器指向第一个匹配关键字的元素，第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在，则两个迭代器都指向一个不影响排序的关键字插入位置。

// definitions of authors and search_item as above
// pos holds iterators that denote the range of elements for this key
for (auto pos = authors.equal_range(search_item);
        pos.first != pos.second; ++pos.first)
    cout << pos.first->second << endl;  // print each title

无序容器（The Unordered Containers）

新标准库定义了4个无序关联容器（unordered associative container），这些容器使用哈希函数（hash function）和关键字类型的==运算符组织元素。

无序容器和对应的有序容器通常可以相互替换。但是由于元素未按顺序存储，使用无序容器的程序输出一般会与有序容器的版本不同。

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

默认情况下，无序容器使用关键字类型的==运算符比较元素，还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内置类型和一些标准库类型提供了hash模板。因此可以直接定义关键字是这些类型的无序容器，而不能直接定义关键字类型为自定义类类型的无序容器，必须先提供对应的hash模板版本。

第11章 关联容器