跳转至

第十一章 关联容器

关联容器与顺序容器有着根本的不同：

  • 关联容器中的元素是按关键字来保存和访问的。

  • 顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

关联容器支持高效的关键字查找和访问，有两个主要的关联容器：

  • map，其元素是一些关键字-值对，关键字起到索引作用，值则表示与之相关的数据。

  • set，每个元素只包含一个关键字。

使用关联容器

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

set就是关键字的简单集合。

具体使用案例见书本p375。

关联容器概述

关联容器（有序的和无序的）都支持9.2节（第294页）中介绍的普通容器操作。关联容器不支持顺序容器的位置相关的操作，例如push_front。

除了与顺序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作（见p388）和类型别名（见p381）。

关联容器的迭代器都是双向的。

定义关联容器

map<string, size_t> word_count; // 空容器
set<string> exclude = {"the", "but", "and"}; // 列表初始化

// 三个元素；authors将姓映射为名
map<string, string> authors = {
    {"Joyce", "James"},
    {"Austen", "Jane"},
    {"Dickens", "Charles"}
};

初始化multimap或multiset

一个map或set中的关键字必须是唯一的，即，对于一个给定的关键字，只能有一个元素的关键字等于它。

multimap和multiset没有此限制，它们都允许多个元素具有相同的关键字（这些元素会相邻存储）。

关键字类型的要求

对于有序容器，关键字类型必须定义元素比较的方法，默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。

使用关键字类型的比较函数

用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型（比如一个函数指针类型）。

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

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

pair类型

pair类型定义在头文件utility中。

一个pair保存两个数据成员，pair是一个用来生成特定类型的模板。

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

pair的默认构造函数对数据成员进行值初始化。也可以为每个成员提供初始化器：

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

pair的数据成员是public的，两个成员分别是first，second。

创建pair对象的函数

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

关联容器操作

除了表9.2(第295页)中列出的类型，关联容器还定义了这些类型：

  • key_type, 此容器类型的关键字类型

  • mapped_type, 每个关键字关联的类型，只适用于map

  • value_type, 对于set，与key_type相同，对于map, 为pair<const key_type, mapped_type>

关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的value_type的值的引用。对map而言，value_type是一个pair类型。

Note

必须记住，一个map的value_type是一个pair，我们可以改变pair的值，但不能改变关键字成员的值。

set的迭代器是const的

与不能改名map元素的关键字一样，一个set中的关键字也是const的。可以用一个set迭代器来读取元素的值，但不能修改。

遍历关联容器

map和set类型都支持begin和end操作，我们可以利用这些函数获取迭代器，然后用迭代器来遍历容器。

auto map_it = word_count.cbegin();
while (map_it != word_count.cend()) {
    // ...
    ++map_it; // 递增迭代器，移动到下一个元素
}

Note

当使用一个迭代器遍历一个map、multimap、set或multiset时，迭代器按关键字升序遍历元素。

关联容器和算法

我们通常不对关联容器使用泛型算法。更多讨论见书本p383。

添加元素

关联容器的insert成员向容器中添加一个元素或一个元素范围。由于map和set包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响。

向map添加元素

对一个map进行insert操作时，必须记住元素类型是pair。

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

向multiset或multimap添加元素

由于一个multi容器中的关键字不必唯一，在这些类型上调用insert总会插入一个元素：

multimap<string, string> authors;
// 插入第一个元素
authors.insert({"Barth, John", "Sot-Weed Factor"});
// 正确，添加第二个元素
authors.insert({"Barth, John"}, "Lost in the Funhouse");

对允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。

删除元素

关联容器定义了三个版本的erase：

  • 与顺序容器一样，传递给erase一个迭代器或一个迭代器范围来删除一个元素或一个元素范围。

  • 接受一个key_type参数，删除所有匹配给定关键字的元素（如果存在的话），返回实际删除的元素的数量。

对于保存不重复关键字的容器，erase的返回值总是0或1。

map的下标操作

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

set类型不支持下标操作，不能对一个multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

map下标运算符接受一个索引获取与此关键字相关联的值，如果关键字不在map中，会为它创建一个元素并插入到map中，关联值将进行值初始化。

使用下标操作的返回值

当对一个map进行下标操作时，会获得一个mapped_type对象。

当解引用一个map迭代器时，会得到一个value_type对象。

Note

与vector与string不同，map的下标运算符返回的类型与解引用map迭代器得到的类型不同。

访问元素

如果我们关心的只不过是一个特定元素是否已在容器中，使用find比较好。

对于不允许重复关键字的容器，可能使用find还是count没什么区别。

对于允许重复关键字的容器，count会统计有多少个元素有相同的关键字。

无序容器

无序容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。

在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。