img

关联容器

关联容器支持高效的关键字查找和访问操作。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成员保存对应的值。

1
2
3
4
5
6
7
8
9
// 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时，提供的每个键值对用花括号{}包围。

1
2
3
4
5
6
7
8
9
10
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没有此限制。

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

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

1
2
3
4
5
6
7
8
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);

这段代码定义了一个比较函数 compareIsbn，然后创建了一个 multiset 容器，用于存储 Sales_data 类型的对象。让我逐步解释：

  1. bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs)： 这是一个自定义的比较函数，用于比较两个 Sales_data 对象的 ISBN。lhs 和 rhs 是要比较的两个对象的引用。函数返回 true 表示 lhs 的 ISBN 小于 rhs 的 ISBN，否则返回 false。

  2. multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);： 这行代码创建了一个 multiset 容器，名为 bookstore，用于存储 Sales_data 类型的对象。multiset 是一个有序容器，它可以包含重复的元素，并且元素会按照指定的比较函数进行排序。

    • <Sales_data, decltype(compareIsbn)*> 指定了容器中存储的元素类型为 Sales_data，并且指定了比较函数的类型为 decltype(compareIsbn)*，即指向 compareIsbn 函数的指针。

    • bookstore(compareIsbn) 创建了 bookstore 容器，并将 compareIsbn 函数作为参数传递给容器的构造函数，用于指定元素的排序规则。由于 multiset 容器要求指定一个比较函数来决定元素的顺序，因此需要将 compareIsbn 函数的地址传递给容器，以便容器内部能够调用该函数来进行元素的比较和排序。

因此，bookstore 是一个按照 compareIsbn 函数指定的排序规则进行排序的 multiset 容器，可以存储多个具有相同 ISBN 的 Sales_data 对象，并且这些对象将按照 ISBN 的顺序进行排列。

pair类型（The pair Type）

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

1
2
3
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++版本中必须显式构造返回值。

1
2
3
4
5
6
7
8
9
10
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。

1
2
3
4
5
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成员保存值。

1
2
3
4
5
6
7
// 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的。

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;       // 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。

1
2
3
4
5
// 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中有多个元素具有相同关键字，则这些元素在容器中会相邻存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}

这段代码的目的是从 multimap 容器 authors 中查找特定作者的所有作品，并打印它们的标题。让我逐步解释：

  1. 定义了一个 multimap 容器 authors：

    1
    multimap<string, string> authors;

    这行代码创建了一个 multimap 容器，用于存储作者名和作品名的键值对。每个键（作者名）可以对应多个值（作品名）。

  2. 向容器中插入元素：

    1
    2
    authors.insert({"Barth, John", "Sot-Weed Factor"});
    authors.insert({"Barth, John", "Lost in the Funhouse"});

    这两行代码分别向 authors 容器中插入了两个具有相同键（"Barth, John"）的元素。因为 multimap 允许多个元素具有相同的键，所以这两个作品都会被插入。

  3. 定义要搜索的作者：

    1
    string search_item("Alain de Botton");

    这行代码定义了要搜索的作者名称。在这个示例中，搜索的作者并不存在于 authors 容器中。

  4. 查找元素：

    1
    2
    auto entries = authors.count(search_item);  // number of elements
    auto iter = authors.find(search_item);      // first entry for this author
    • authors.count(search_item) 返回与搜索项匹配的元素数量。在这里，因为搜索项并不存在于容器中，所以 entries 被初始化为0。
    • authors.find(search_item) 返回与搜索项匹配的第一个元素的迭代器。在这里，由于搜索项并不存在于容器中，iter 被初始化为指向容器末尾的迭代器（即 authors.end()）。

  5. 输出作者作品：

    1
    2
    3
    4
    5
    6
    while(entries)
    {
        cout << iter->second << endl;   // print each title
        ++iter;      // advance to the next title
        --entries;   // keep track of how many we've printed
    }

    这是一个循环，它的条件是 entries 不为0。但是，由于搜索项并不存在于容器中，所以循环体不会执行。因此，没有任何输出。

综上所述，这段代码的作用是试图从 multimap 容器 authors 中查找指定作者的作品，并打印它们的标题。但由于搜索项并不存在于容器中，所以不会有任何输出。

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

1
2
3
4
5
6
// 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。若关键字存在，则第一个迭代器指向第一个匹配关键字的元素，第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在，则两个迭代器都指向一个不影响排序的关键字插入位置。

1
2
3
4
5
// 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

这段代码使用了 equal_range 函数来查找 multimap 容器中指定键的所有元素，并将它们的位置存储在迭代器对 pos 中。然后，通过循环遍历该范围，并输出每个匹配键的对应值。让我逐步解释：

  1. auto pos = authors.equal_range(search_item);： 这行代码调用了 equal_range 函数，该函数会返回一个表示指定键在容器中的范围的迭代器对。authors 是一个 multimap 容器，search_item 是要查找的键值。pos 是一个自动类型的变量，用于存储返回的迭代器对。

  2. pos.first != pos.second： 这是一个循环条件，它检查迭代器对 pos 所表示的范围是否为空。如果范围不为空，则说明在容器中找到了与 search_item 匹配的元素。

  3. ++pos.first： 在循环的每次迭代中，迭代器 pos.first 会向前移动，以便遍历匹配键的所有元素。

  4. cout << pos.first->second << endl;： 这行代码输出了匹配键的对应值。由于 multimap 容器可以包含多个具有相同键的元素，因此 pos.first 是一个迭代器，它指向范围内的当前元素。pos.first->second 访问了该元素的值部分，即容器中存储的第二个数据成员（假设作者与书名关联），并将其输出到标准输出流中。

通过这种方式，该循环会逐个输出与指定键匹配的所有元素的对应值，直到范围中的所有元素都被遍历完毕。

无序容器（The Unordered Containers）

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

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

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

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