C++标准库--顺序容器

作者 by adtxl / 2021-03-08 / 暂无评论 / 420 个足迹

顺序容器

一个容器就是一些特定类型对象的集合。顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值,而是与元素加入容器时的位置相对应。
标准库还提供了三种容器适配器,分别为容器操作定义了不同的接口。来与容器类型适配。

1. 顺序容器概览

下标列出了标准库中的顺序容器,所有顺序容器都提供了快速顺序访问元素的能力。但是,这些容器在以下方面都有不同的性能折中:

  • 向容器添加或从容器中删除元素的代价
  • 非顺序访问容器中元素的代价

image.png

除了固定大小的array外,其他容器都提供高效、灵活的内存管理。

确定使用哪种顺序容器
通常,使用vector是最好的选择,除非你有很好的理由选择其他容器
以下是一些选择容器的基本原则:

  • 除非你有很好的理由选择其他容器,否则应使用vector
  • 如果你的程序有很多小的元素,且空间的额外开销很重要,则不要使用list或forward_list。
  • 如果程序要求随机访问元素,应使用vector或deque
  • 如果程序要求在容器的中间插入或删除元素,应使用list或forward_list。
  • 如果程序需要在头尾位置插入或删除元素,但不会在中间位置进行插入或删除操作,则使用deque
  • 如果程序只有在读取输入时才需要在容器中间位置插入元素,随后需要随机访问元素,则
    首先,确定是否真的需要在容器中间位置添加元素。当处理输入数据时,通常可以很容易地向vector追加数据,然后再调用标准库的sort函数来重排容器中的元素,从而避免在中间位置添加元素。
    如果必须在中间位置插入元素,考虑在输入阶段使用list,一旦输入完成,将list中的内容拷贝到一个vector中。

2. 容器库概览

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

  • 某些操作是所有的容器类型都提供的
  • 另外一些操作仅针对顺序容器、关联容器或无序容器
  • 还有一些操作只适用于一小部分容器

一般来说,每个容器都定义在一个头文件中,文件名与类型名相同。容器均定义为模板类。例如vector,我们必须提供额外信息来生成特定的容器类型。对大多数,但不是所有容器,我们还需要额外提供元素类型信息。

image133d41aa3b7e623f.png
image528c91545a5281fa.png

下面主要介绍所有容器都支持的操作。

2.1 迭代器

一个迭代器范围由一对迭代器表示,两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置
数学描述: [begin, end)
使用左闭合范围蕴含的编程假定
标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和end构成一个合法的迭代器范围,则

  • 如果begin和end相等,则范围为空
  • 如果begin与end不相等,则范围至少包含一个元素,且begin指向该范围中的第一个元素
  • 我们可以对begin递增若干次,使得begin==end

2.2 容器和类型成员

每个容器都定义了多个类型。如size_type、iterator和const_iterator,以及反向迭代器,类型别名等。
为了使用这些类型,我们必须显式使用其类名:

// iter是通过list<string>定义的一个迭代器类型
list<string>::iterator iter;
// count是通过vector<int>定义的一个difference_type类型
vector<int>::difference_type count;

2.3 begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。
begin和end有多个版本:以c开头的版本则返回const迭代器,以r开口的版本返回反向迭代器
当不需要写访问时,应该使用cbegin和cend。

2.4 容器定义和初始化

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

将一个容器初始化为另一个容器的拷贝
将一个新容器创建为另一个容器的拷贝的方法有两种:可以直接拷贝整个容器,或者(array除外)拷贝由一个迭代器对指定的元素范围。

2.5 赋值和swap

与内置数组不同,标准库array类型允许赋值。赋值号左右两边的运算对象必须具有相同的类型:

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0};    // 所有元素值为0
a1 = a2;        // 替换a1中的元素
a2 = {0};       // 错误:不能将一个花括号列表赋予数组

由于右边运算对象的大小可能与左边运算对象的大小不同,因此array类型不支持assign,也不允许用花括号包围的值列表进行赋值。
image24fced0067ae060b.png

使用assign(仅顺序容器)

赋值运算符要求左边和右边的运算对象具有相同的类型。它将右边运算对象中所有元素拷贝到左边运算对象中。顺序容器(array除外)还定义了一个名为assign的成员,允许我们从一个不同但相容的类型赋值,或者从容器的一个子序列赋值。assign操作用参数所指定的元素(的拷贝)替换左边容器中的所有元素。
例如,我们可以用assign实现将一个vector中的一段char*值赋予一个list中的string:

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;   // 错误: 容器类型不匹配
// 正确:可以将const char*转换为string
names.assign(oldstyle.cbegin(), oldstyle.cend());

2.6 容器大小操作

成员函数size返回容器中元素的数目;
empty当size为0时返回布尔值true,否则返回false;
max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值;
forward_list支持max_size和empty,但不支持size

2.7 关系运算符

每个容器类型都支持相等运算符(==和!=);除了无序关联容器外的所有容器都支持关系运算符(>、>= 、<、 <=)。关系运算符两边必须是相同的类型。
比较两个容器实际是进行元素的逐对比较。这些运算符

3. 顺序容器操作

4. vector对象是如何增长的

5. 额外的string操作

6. 容器适配器

独特见解