跳转至

第九章 顺序容器

顺序容器概览

顺序容器有：vector, deque, list, forward_list, array, string。见p292表9.1。

所有顺序容器都提供了快速顺序访问元素的能力。但是，这些容器在以下方面都有不同的性能折中：

  • 向容器添加或从元素中删除元素的代价

  • 非顺序访问容器中元素的代价

string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在其中间添加或删除元素就会非常耗时，因为这需要移动插入或删除位置之后的所有元素。而且，添加元素可能导致分配额外的存储空间，这种情况下，每个元素都会移动到新的存储空间中。

list和forward_list两个容器添加和删除操作都很快速。作为代价，它们不支持元素的随机访问，为了访问一个元素，只能遍历整个容器。与vector、deque和array相比，这两个容器的额外内存开销也很大。

deque支持快速随机访问，在deque的中间位置插入或删除元素的代价（可能）很高。但是，在deque的两端添加或删除元素都是很快的。

确定使用哪种容器

Tip

通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。

见书本p293的详细讨论。

容器库概览

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

  • 某些操作是通用的，见表9.2，295页。

  • 某些操作仅针对顺序容器（表9.3，299页）、关联容器（表11.7，388页）或无序容器（表11.8，395页）。

  • 还有一些操作只适用于一小部分容器。

迭代器

迭代器有着公共的接口：如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。比如解引用操作。

表3.6（96页）列出了容器迭代器支持的所有操作。表3.7（99页）列出了迭代器支持的算术运算，这些运算只能应用于string、vector、deque和array。

迭代器范围

迭代器范围由一对迭代器表示，通常被称为begin和end，它们标记了容器中元素的一个范围。这个范围被称为左闭合区间：[begin, end)

使用左闭合区间蕴含的编程假定

假定begin和end构成一个合法的迭代器范围，则：

  • 如果begin与end相等，则范围为空

  • 如果begin与end不等，则范围至少包含一个元素，且begin指向该范围中的第一个元素

  • 我们可以对begin递增若干次，使得begin == end

容器定义和初始化

每个容器类型都定义了一个默认构造函数。除array之外，其他容器的默认构造函数都会创建一个指定类型的空容器，且都可以指定容器大小和元素初始值的参数。

见表9.3，p299。

将一个容器初始化为另一个容器的拷贝

方法有两种：

  • 直接拷贝整个容器，两个容器的类型和元素的类型都必须匹配。

  • 拷贝一个迭代器范围，容器类型不一定匹配，且元素类型只要能够转换即可。

赋值和拷贝

赋值运算符将其左边容器中的全部元素替换为右边容器中的元素的拷贝。具体见p302。

使用assign(仅顺序容器)

赋值运算要求两边容器类型和元素类型相同。顺序容器（除了array）还定义了一个名为assign的成员，允许从一个相容的序列中赋值。

使用swap

调用swap操作后，两个容器中的元素将会交换。

除了array，交换两个容器的操作保证会很快，因为元素本身并未交换，swap只是交换了两个容器的内部数据结构。

容器大小操作

每个容器都支持这些大小相关的操作：

  • 成员函数size，返回容器中元素的数目，forward_list不支持；

  • empty，当size为0时返回true，否则返回false；

  • max_size，返回一个大于或等于该容器所能容纳的最大元素数的值，这是一个很大的值。

关系运算符

每个容器都支持相等运算符（==和!=），除了无序关联容器外的所有容器都支持关系运算符（>, >=, <, <=）。关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素。

比较两个容器实际上是进行元素的逐对比较。

Note

只有当元素类型定义了相应的比较运算符时，才可以使用关系运算符比较两个容器。

顺序容器操作

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

向顺序容器添加元素

标准库容器提供了灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。表9.5，p305。

Warning

向一个deque、string或vector插入元素会使所有指向容器的迭代器、引用和指针失效。

将元素插入到deque、string或vector中的任何位置都是合法的。然而，这样做可能很耗时。

关键概念：容器元素是拷贝

当我们用一个对象来初始化容器时，或将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝。

访问元素

表9.6（p310）列出了我们可以用来在顺序容器中访问元素的操作。如果容器中没有元素，访问操作的结果是未定义的。

下标操作和安全的随机访问

提供快速随机访问的容器（string、vector、deque和array）也都提供下标运算符。保证下标合法是程序员的责任，编译器不检查越界错误。

如果想确保下标是合法的，可以使用at成员函数。at成员函数类似下标运算符，如果下标越界，at会抛出一个out_of_range异常。

删除元素

见表9.7，p311页。

Warning

删除deque中除首尾之外的任何元素都会使所有迭代器、引用、指针失效。指向vector或string中删除点之后位置的迭代器、引用和指针都会失效。

删除元素之前，程序员必须确保它们是存在的。

改变容器大小

可以使用resize来增大或缩小容器。如果当前大小大于所要求的大小，容器后部的元素会被删除；如果当前大小小于新大小，会将新元素添加到容器后部。

resize接受一个可选的元素指参数，用来初始化新添加的元素。如果未提供，新元素进行值初始化。

容器操作可能使迭代器失效

使用失效的迭代器、引用、或指针是一种严重的错误。

向容器添加元素后：

  • 如果容器是vector或string，且存储空间被重新分配，那么所有的迭代器都会失效。如果空间未重新分配，指向插入位置之前的元素的迭代器仍有效，但之后的迭代器会失效。

  • 对于list和forward_list，指向容器的迭代器仍有效。

当从容器中删除元素后：

  • 对于list和forward_list，指向容器其他位置的迭代器仍有效。

  • 对于string和vector，被删除元素之前的元素的迭代器仍有效。

详细见书本p315。

额外的 string 操作

除了顺序容器共同的操作之外， string 类型还提供了一些额外的操作。

构造 string 的其他方法

使用下面这些方法可以构造 string ：

以下 n, len2, pos2 都是无符号值。

方法 说明
string s(cp, n) s是cp指向的数组中前n个字符的拷贝
string s(s2, pos2) s是 string s2 从下标 pos2 开始的字符拷贝
string s(s2, pos2, len2) s是 string s2 从下标 pos2 开始 len2 个字符的拷贝，不管 len2 的值是多少，构造函数至多拷贝 s2.size() - pos2 个字符。

substr 操作

substr 返回一个 string ，它是原始 string 的一部分或全部的拷贝。

s.substr(pos, n) 返回一个 string ，包含s中从pos开始的n个字符的拷贝。pos默认为0,n默认为 s.size() - pos ，即拷贝从 pos 开始的所有字符。

改变 string 的其他方法

string 类型支持顺序容器的赋值运算符以及 assign, insert, erase 操作。除此之外，它还定义了额外的 insert 和 erase 版本。即使用下标的版本。

这些函数都拥有许多重载的版本。

assign 版本还接受C风格字符串。

append 和 replace 是额外的成员函数， append 在 string 末尾进行插入操作， replace 替换内容，它是调用 erase 和 insert 的一种简写形式。

string 搜索操作

string 提供了6个搜索函数，它们都有4个重载版本。它们都返回一个 string::size_type 的值作为匹配位置（下标）。如果搜索失败，返回 string::npos ，其值为 -1 。

可以给函数一个搜索的起始位置 pos ，它默认值是0：

auto pos = s.find_first_of(numbers, pos);

compare 函数

这是字符串比较函数，和C标准库的 strcmp 很相似。

数值转换

标准库提供了数值转换的函数。

如果 string 不能转换成一个数值，那么会抛出一个 invalid_argument 的异常。如果转换得到的数值无法用任何类型来表示，则抛出一个 out_of_range 异常。

这些函数有：

  • to_string
  • stoi, stol, stoul, stof等