第9章 顺序容器

一个容器就是一些特定类型对象的集合。顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值,而是与元素加
入容器时的位置相对应。

9.1 顺序容器概述

表9.1列出了标准库中的顺序容器,所有顺序容器都提供了快速顺序访问元素的能力。表9.1 顺序容器类型

除了固定大小的array外,其他容器都提供高效、灵活的内存管理。容器保存元素的策略对容器操作的效率有着固有的,有时是重大的影响。

  1. 例如,vector和string将元素保存在连续的内存空间中。由于元素是连续存储的,由元素的下标来计算其地址是非常快速的。但是在这两种容器的中间位置添加或删除元素就非常耗时:在一次插入或删除操作后,需要移动插入/删除位置之后的多有元素,来保持连续存储。
  2. list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价,这两个容器不支持元素的随机访问:为了访问一个元素我们只能遍历整个容器。
  3. deque是一个更为复杂的数据结构。与string和vector类似,deque支持快速的随机访问。在deque的中间位置添加或删除元素的代价(可能)很高。但是,在deque的两端添加或删除元素都是很快的,与list和forward_list添加删除元素的速度相当。
  4. forward_list和array是新C++标准增加的类型。与内置数组相比,array是一种更安全、更容易使用的数组类型。与内置数组类似,array对象的大小是固定的,因此,array不支持添加和删除元素以及改变容器大小的操作。forward_list没有size操作。
9.2 容器库概览

容器类型上的操作形成一种层次:

  1. 某些操作是所有容器类型都提供的(参见表9.2)
  2. 另外一些操作仅针对顺序容器、关联容器、或无序容器。
  3. 还有一些操作只适用于一小部分容器。

表9.2容器操作表9.2

  • 迭代器:与容器一样,迭代器有着公共的接口:如果一个迭代器提供某个操作,那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。表3.6列出了容器迭代器支持的所有操作,其中有一个例外不符合公共结构特点——forward_list迭代器不支持递减运算符(–)。
  • begin和end成员:begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。以c开头的版本则返回const迭代器。以c开头的版本是C++新标准引入的用以支持auto以begin和end函数结合使用。(当不需要写访问时,应使用cbegin和cend)。
  • 容器定义和初始化:每个容器类型都定义了一个默认构造函数。除array之外,其他容器的默认构造函数都会创建一个指定类型的空容器,且都可以接受指定容器大小和元素初始值的参数。

表9.3 容器定义和初始化

  • 列表初始化:在新标准中,我们可以对一个容器进行列表初始化:
  • 与顺序容器大小相关的构造函数:除了与关联容器相同的构造函数外,顺序容器(array除外)还提供另一个构造函数,它接受一个容器大小和一个元素初始值。

    NOTE:只有顺去容器的构造函数才接受大小参数,关联容器并不支持
  • 标准库array具有固定大小:与内置数组一样,标准库array的大小也是类型的一部分。当定义一个array时,除了指定元素类型外,还要指定容器大小:

    由于大小是array类型的一部分,array不支持普通的容器构造函数。array大小固定的特性也影响了它所定义的构造函数的行为。与其他容器不容,一个默认构造函数的array是非空的:它包含了与其大小一样多的元素。这些元素都被默认初始化,就像一个内置数组中的元素那样。
  • 值得注意的是,虽然我们不能对内置数组类型进行拷贝或对象赋值操作,但array并无此限制:
  • 赋值和swap:与内置数组不同,标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型;由于右边运算对象的大小可能与左边运算对象的大小不同,因此array类型不支持assign。
  • 容器大小操作:除了一个例外,每个容器类型都有三个与大小相关的操作。成员函数size返回容器中元素的数目;empty当size为0时返回布尔值true,否则返回false;max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值。forward_list支持max_size和empty,但不支持size,原因将在下一节解释。
9.3 顺序容器操作

顺序容器和关联容器的不同之处在于两者组织元素的方式。这些不同之处直接关系到了元素如何存储、访问、添加以及删除。下面介绍顺序容器所特有的操作。

  • 向顺序容器中添加元素:除array外,所有标准容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。表9.5 向顺序容器添加元素

在一个vector或string的尾部之外的任何位置,或是一个deque的首尾之外的任何位置添加元素,都需要移动元素。而且,向一个vector或string添加元素可能引起整个对象存储空间的重新分配。

  • 使用push_back:除了array和forward_list之外,每个顺去容器(包括string类型)都支持push_back。

关键概念:容器元素是拷贝:当我们用一个对象来初始化容器时,或将一个对象插入到容器中时,实际上放入到容器中的是对象值的一个拷贝,而不是对象本身。就像我们将一个对象传递给非引用参数一样,容器中的元素与提供值的对象之间没有任何关联。随后对容器中的元素的任何改变都不会影响到原始对象,反之亦然。

  • 使用push_front:list、forward_list、deque容器支持名为push_front的类似操作。

    注意,deque想vector一样提供了随机访问元素的能力,但它提供了vector不支持的push_front。
  • 在容器中的特定位置添加元素:insert成员提供了更一般的添加功能它允许我们在容器中任意位置插入0个或多个元素。vector、deque、list、和string都支持insert成员。forward_list提供了特殊版本的insert成员,后面介绍。
  • 由于迭代器可能指向容器尾部之后不存在的元素的位置,而且在容器开始位置插入元素是很有用的功能,所以insert函数将元素插入到迭代器所指定的位置之前。
  • 虽然某些容器不支持push_front操作,但它们对于insert操作并无类似的限制(插入开始位置)。因此我们可以将元素插入到容器的开始位置,而不必担心容器是否支持push_front:

    WARNING:将元素插入到vector、deque和string中的任何位置都是合法的。然而,这样做可能很耗时。
  • 插入范围内元素:除了第一个迭代器参数之外,insert函数还可以接受更多的参数,这与容器构造函数类似。其中一个版本接受一个元素数目和一个值,它将指定数量的元素添加到指定位置之前,这些元素都按给定值初始化。

    在新标准下,接受元素个数或范围的insert版本返回指向第一个新加入的元素的迭代器。(在旧版本的标准库中,这些操作返回void)
  • 使用insert的返回值:通过使用insert的返回值,可以在容器中一个特定位置反复插入元素:

    NOTE:理解这个循环是如何工作的非常重要,特别是理解这个循环为什么等价于调用push_front尤为重要。
  • 使用emplace操作:新标准引入了三个新成员——emplace_front、emplace和emplace_back,这些操作构造而不是拷贝元素。
  1. 这些操作分别对应push_front、insert和push_back。
  2. 当调用push或insert成员函数时,我们将元素类型的对象传递给它们,这些对象被拷贝到容器中。
  3. 当我们调用一个emplace成员函数时,则是将参数传递给元素类型的构造函数,emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

    NOTE:emplace函数在容器中直接构造元素。传递给emplace函数的参数必须与元素类型的构造函数相匹配。
  • 访问元素:表9.6列出了我们可以用来在顺序容器中访问元素的操作。如果容器中没有元素,访问操作的结果是为定义的。包括array在内的每个顺序容器都有一个front成员函数,而除forward_list之外的所有顺序容器都有一个back成员函数。这两个操作分别返回首元素和尾元素的引用表9.6
  • 访问成员函数返回的是引用:在容器中访问元素的成员函数(即frong、back、下标和at)返回的都是引用。如果容器是一个const对象,则返回值是const引用。如果容器不是const的,则返回值是普通引用,我们可以用来改变元素的值:
  • 下标操作和安全的随机访问:提供快速随机访问的容器(string、vector、deque和array)也都提供下标运算符。给定下标必须“在范围内”,保证下标有效是程序员的责任,使用越界的下标是一种严重的程序设计错误,而且编译器并不检查这种错误。如果我们希望确保下标是合法的,可以使用at成员函数。at成员函数类似下标运算符,但如果下标越界,at会抛出一个out_of_range异常:
  • 删除元素:与添加元素的多种方法类似,(非array)容器也有多种删除元素的方式:表9.7
  • pop_front和pop_back成员函数:pop_front和pop_back成员函数分别删除首元素和尾元素。与vector和string不支持push_front一样,这些类型也不支持pop_front。类似的,forward_list不支持pop_back。
  • 从容器内部删除一个元素:成员函数erase从容器中指定位置删除元素。我们可以删除由一个迭代器指定的单个元素,也可以删除由一对迭代器指定的范围内的所有元素。两种形式的erase都返回指向删除的元素之后位置的迭代器。
  • 删除多个元素:接受一对迭代器的erase版本允许我们删除一个范围内的元素:

    迭代器elem1指向我们要删除的所有元素,elem2指向我们要删除的最后一个元素之后的位置。
  • 特殊的forward_list操作:
  1. 为了添加或删除一个元素,我们需要访问其前驱,以便改变前驱的链接。但是,forward_list是单向链表。在一个单向链表中,没有简单的方法来获取一个元素的前驱。处于这个原因,在一个forward_list中添加或删除元素的操作是通过改变给定元素之后的元素来完成的(前面提及的插入删除操作都是在指定迭代器位置之前进行的)。
  2. 由于这些操作与其他容器上的操作的实现方式不同,forward_list并未定义insert、emplace和erase,而是定义了名为insert_after、emplace_after和earse_after的操作。
  3. 为了支持这些操作,forward_list也定义了before_begin,它返回一个首前(off-the-beginning)迭代器。这个迭代器匀速我们在链表首元素之前并不存在的元素“之后”添加或删除元素(亦即在链表首元素之前添加删除元素)。表9.8
9.4 vector对象是如何增长的

为了支持快速随机访问,vector将元素连续存储——每个元素紧挨着前一个元素存储。

  • 管理容量的成员函数:如表9.10所示,vector和string类型提供了一些成员函数,允许我们与它的实现中内存分配部分互动。capacity操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。reserve操作允许我们通知容器它应该准备保存多少个元素。表9.10

NOTE:reverse并不改变容器中元素的数量,它仅影响vector预先分配多大的内存空间。

只有当需要的内存空间超过当前容量时,reserve调用才会改变vector的容量。如果需求大小大于当前容量,reserve至少分配与需求一样大的内存空间(可能更大)。这样reserve永远也不会减少容器占用的内存空间。类似的,resize成员函数只改变容器中元素的数目,而不是容器的容量。我们同样不能使用resize来减少容器预留的内存空间。

  • 在新标准库中,我们可以调用shrink_to_fit来要求deque、vector或string退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是,具体的实现可以选择忽略此请求。也就是说,调用shrink_to_fit也并不保证一定退回内存空间。
  • capacity和size:理解capacity和size的区别很重要。容器的size是指它已经保存的元素数目;而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。
  • 我们知道一个空vector的size为0,显然在我们的标准库实现中一个空vector的capacity也为0.当向vector中添加元素时,我们知道size与添加的元素数目相等。而capacity至少与size一样大,具体分配多少额外空间则视标准库具体实现而定。
9.5 额外的string操作

除了顺去容器共同的操作之外,string类型还提供了一些额外的操作。这些操作中的大部分要么是提供string类和C风格字符数组之间的相互转换,要么是增加了允许我们用下标替代迭代器的版本。

  • 构造string的其他方法:除了在3.2.1已经介绍过的构造函数,以及与其他顺序容器相同的构造函数外,string类型还支持另外三个构造函数:表9.11

这些函数接受一个string或一个const char*参数,还接受(可选的)指定拷贝多少个字符的参数。

  • substr操作:substr操作返回一个string,它是原始string的一部分或全部的拷贝。可以传递给substr一个可选的开始位置和计数值表9.12
  • 改变string的其他方法:sting类型支持顺序容器的赋值运算符以及assign、insert和erase操作。除此之外,还定义了额外的insert和erase版本。除了接受迭代器的insert和erase版本外,string还提供了接受下标的版本。下标指出了开始删除的位置,或是insert到给定值之前的位置。
  • append和replace函数:string定义了两个额外的成员函数:append和replace,这两个函数可以改变string的内容。表9.13

此例中调用replace时,插入的文本恰好与删除的文本一样长,这不是必须的,可以插入一个更长或更多的string。

  • string搜索操作:string提供了6个不同的搜索函数,每个函数都有4个重载版本。每个搜索操作都返回一个string::size_type值,表示匹配发生位置的下标。如果搜索失败,则返回一个名为string::npos的static成员。标准库将npos定义为一个const string::size_type类型,并初始化为值-1.由于npos是一个unsigned类型,此初始值意味着npos等于任何string最大的可能大小。表9.14

find函数完成最简单的搜索。它查找参数指定的字符串,若找到,则返回一个匹配位置的下标,否则返回npos:

一个更复杂一些的问题是查找与给定字符串中任何一个字符匹配的位置:

如果是要搜索第一个不在参数中的字符,我们应该调用find_first_not_of。例如,为了搜索一个string中第一个非数字字符:

  • 指定在哪里开始搜索:我们可以传递给find操作一个可选的开始位置。这个参数指出从哪个位置开始进行搜索。默认情况下,此位置被置为0.一种常见的程序设计模式是用这个可选参数在字符串中循环地搜索子字符串出现的所有位置:

逆向搜索:标准库还提供了类似的从右至左搜索的操作。rfind成员函数搜索最后一个匹配,即子字符串最靠右的出现位置:

类似的,find_last和find_first函数相似,只是它们返回最后一个而不是第一个匹配:

  1. first_last_of:搜索与给定string中任何一个字符匹配的最后一个字符。
  2. find_last_not_of:搜索最后一个不出现在给定string中的字符。

每个操作都接受一个可选的第二参数可用来指出从什么位置开始搜索。

  • compare函数:除了关系运算符外,标准库string类型还提供了一组compare函数,这些函数与C标准库的strcmp函数很相似。类似strcmp,根据s是等于、大于还是小于参数指定的字符串,s.compae返回0、正数或负数。表9.15,compare有6个版本。根据我们是要比较两个string还是一个string与一个字符数组,参数各有不同。表9.15
  • 数值转换:新标准引入了多个函数,可以实现数值数据与标准库string之间的转换:

    9.6 容器适配器(P329)

除了顺序容器外,标准库还定义了三个顺去容器适配器:stack、queue和priority_queue。适配器(adaptor)的标准库中的一个通用的概念。

容器、迭代器和函数都有适配器。本质上,一个适配器是一种机制,能使某种事物的行为看起来像另外一种事物一样。表9.17

《第9章 顺序容器》有1个想法

发表评论

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