第11章 关联容器

关联容器支持高效的关键字查找和访问。两个主要的关联容器(associative-container)类型是map和set。标准库提供了8个关联容器,这8个容器间的不同体现在
三个维度上:每个容器(1)或是一个set,或是一个map;(2)或者要求不重复关键字,或者允许重复关键字;(3)按顺序保存元素,或无序保存。无序容器使用哈希函数来组织元素。表11.1

11.1 使用关联容器

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

  1. 使用map:一个经典的使用关联数组的例子是单词计数程序

    类似顺序容器,关联容器也是模板。上述while循环每次从标准输入读取一个单词。它使用每个单词对word_count进行下标操作。如果word还未在map中,下标运算符会创建一个新元素,其关键字为word,值为0。不管元素是否新创建的,我们将其值加1。
  2. 使用set:上一个示例程序的一个合理扩展是:忽略常见单词如“the”、”and”等。我们可以使用set保存想忽略的单词。
11.2 关联容器概述

关联容器都支持9.2节中介绍的普通容器操作。关联容器不支持顺序容器的位置相关操作,例如push_front或push_back。原因是关联容器中元素是根据关键字存储的,这些操作对关联容器没有意义。

  • 每个关联容器都定义了一个默认构造函数,它创建了一个指定类型的空容器。我们也可以将关联容器初始化为另一个同类型容器的拷贝,或是从一个值范围来初始化关联容器,只要这些值可以转化为容器所需类型就可以。在新标准下,我们也可以对关联容器进行值初始化:
  • 初始化multimapmultiset
    一个map或set中的关键字必须是唯一的,容器multimap和multiset没有此限制,它们允许多个元素具有相同的关键字。
  • 关键字类型的要求
    关联容器对其关键字类型有一些限制。对于有序容器,关键字类型必须定义元素比较的方法默认情况下,标准库使用关键字类型<运算符来比较两个关键字
    使用关键字类型的比较函数:用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作,必须在定义关联容器类型时提供此操作的类型。例如,我们不能直接定义一个Sales_data的multiset,因为Sales_data没有<运算符。因此需要定义一个compareIsbn:

    为了使用自己定义的操作,在定义multiset时我们必须提供两个类型:关键字类型Sales_data,以及比较操作类型——应该是一种函数指针类型,可以指向compareIsbn。

    此处,我们使用decltype来指出自定义操作的类型。记住,当用decltype来获得一个函数指针类型时,必须加上一个*来指出我们要使用一个给定函数类型的指针;用compareIsbn来初始化bookstore对象,这表示当我们想bookstore添加元素时,通过调用compareIsbn来为这些元素排序。
  • pair类型
    在介绍关联容器之前,我们需要了解名为pair的标准库类型,它定义在头文件utility中。类似容器,pair是一个用来生成特定类的模板,与其他标准库类型不同,pair的数据成员是public的。两个成员分别命名为firstsecond,我们用普通的成员访问符号来访问它们。表11.2
  • 创建pair对象的函数
    在新标准下,我们可以对返回值进行列表初始化:

    在较早的C++版本中,不允许用花括号包围初始化器来返回pair这种类型的对象,必须显式构造返回值:
11.3 关联容器操作

除了表9.2中列出的类型,关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。表11.3

  • 关联容器迭代器
    当解引用一个关联容器的迭代器时,我们会得到一个类型为容器的value_type的值的引用。对map而言,value_type是一个pair类型,其first成员保存const的关键字,second成员保存值
    NOTE:必须记住,一个map的value_type是一个pair,我们可以改变pair的值,但不能改变关键字成员的值。
  • set的迭代器是const的
    虽然set类型同时定义了iterator和const_iterator类型,但两种类型都只允许只读访问set中的元素。与不能改变一个map元素的关键字一样,一个set中的关键字也是const的。
  • 遍历关联容器:当使用一个迭代器遍历一个map、multimap、set或multiset时,迭代器按关键字升序遍历元素。
  • 关联容器和算法
    我们通常不对关联容器使用泛型算法。关键字是const这一特性意味着不能将关联容器传递给修改或重排元素的算法,因为这类算法需要向元素写入值,而set类型中的元素是const的,map中的元素是pair,其第一个成员是const的。
    关联容器可用于只读取元素的算法。但是,很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行(快速)查找,因此对其使用泛型搜索算法几乎总是个坏主意。
  • 添加元素
    关联容器的insert成员,向容器中添加一个元素或一个元素范围。由于map和set包含不重复的关键字,因此插入一个已存在的元素对容器没有任何影响:

    insert有两个版本,分别接受一对迭代器,或是一个初始化器列表,这两个版本的行为类似对应的构造函数。
  • 向map添加元素
    对一个map进行insert操作时,必须记住元素类型是pair。通常,对于想要插入的数据,并没有一个现成的pair对象。可以在insert的参数列表中创建一个pair:

    如我们所见,在新标准下,创建一个pair最简单的方法是在参数列表中使用花括号初始化表11.4
  • 检测insert返回值
    insert(或emplace)返回的值依赖于容器类型和参数。对于不包含重复关键字的容器,添加单一元素的insert和emplace版本返回一个pair,告诉我们插入操作是否成功。pair的first成员是一个迭代器,指向具有给定关键字的元素;second成员是一个bool值,指出元素是插入成功还是已经存在于容器中
  • 删除元素:
    关联容器定义了三个版本的erase,与顺序容器一样,我们可以通过传递给erase一个迭代器或一个迭代器对来删除一个元素或一个元素范围;关联容器还提供一个额外的erase操作,它接受一个key_type参数表11.5
  • map的下标操作
    map和unordered_map容器提供了一个下标运算和一个对应的at函数,如表11.6所示。set类型不支持下标,因为set中没有与关键字相关联的值。表11.6与其他下标运算符不同的是,如果关键字并不在map中,会为它创建一个元素并插入到map中,关联值将进行初始化
    NOTE:对一个map使用下标操作,其行为与数组或vector上的下标操作很不相同:使用一个不在容器中的关键字作为下标,会添加一个具有此关键字的元素到map中。
  • 使用下标操作的返回值
    通常情况下,解引用一个迭代器所返回的类型与下标运算符返回的类型是一样的。但对map则不然:当对一个map进行下标操作时,会获得一个mapped_type对象;但当解引用一个map迭代器时,会得到一个value_type对象。与其他下标运算符相同的是,map的下标运算符返回一个左值。由于返回的是一个左值,所以我们既可以读也可以写元素:

    NOTE:与vector与string不同,map的下标运算符返回的类型与解引用map迭代器得到的类型不同。
  • 访问元素
    如果我们所关心的只不过是一个特定元素是否在容器中,可能find是最佳选择。对于不允许重复关键字的容器,可能使用find还是count没什么区别。

    表11.7
  • 对map使用find代替下标操作
    使用下标操作有一个严重的副作用:如果关键字还未在map中,下标操作会插入一个具有给定关键字的元素。但有时,我们只是想知道一个给定关键字是否在map中,而不想改变map。这种情况下,应该使用find:
  • 在multimap或multiset中查找元素:最直观的方法是使用find和count
11.4 无序容器(P394)

新标准定义了4个无序关联容器(unordered associative container)。这些容器不是使用比较运算符来组织元素,而是使用一个哈希函数(hash function)和关键字类型的==运算符
TIP:如果关键字类型固有就是无序的,或者性能测试发现问题可以用哈希技术解决,就可以使用无序容器。

  • 管理桶:无序容器在存储上组织为一组桶,每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素,容器首先计算元素的哈希值,它指出应该搜索哪个桶。容器将具有一个特定哈希值的所有元素都保存在相同的桶中。

发表评论

电子邮件地址不会被公开。 必填项已用*标注