首页 10-C++标准库之顺序容器
文章
取消

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

发表于 2022/11/01 更新于 2023/10/10
作者 Ping
38 分钟阅读

容器的定义：一个容器就是一组特定类型对象的集合。

顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

标准库还提供了三种容器适配器，分别为容器操作定义了不同的接口，来与容器类型适配。但，什么叫容器适配器？二次巩固后回答：

  • 容器适配器是基于现有容器实现的封装，它们可以修改或扩展现有容器的接口，以提供不同的行为或功能。
  • 容器适配器有三种：std::stack、std::queue、std::priority_queue；

顺序容器概述

所有顺序容器都提供了快速顺序访问元素的能力，但是这些容器在以下方面都要考虑性能损耗：向容器添加或从容器中删除元素的代价；非顺序访问容器中元素的代价。

顺序容器的类型列举：

  • vector-可变大小数组：支持快速随机访问；尾部之外的位置插入或删除元素可能很慢。
  • deque-双端队列：支持快速随机访问；在头尾位置插入/删除。
  • list-双向链表：只支持双向顺序访问；在list中任何位置进行插入/删除操作速度都很快。
  • forward_list-单向链表：只支持单项顺序访问；链表任何位置进行插入/删除操作速度都很快。
  • array-固定大小数组：支持快速随机访问；不能添加或删除元素。
  • string-与vector相似的容器：专门用于保存字符；随机访问快；在尾部插入/删除速度快。

针对上述顺序容器的一些说明：

  • string、vector访问快，因为是连续存储，计算下标是非常迅速的；添加元素慢主要是因为在一次插入或删除操作之后，需要移动插入/删除位置之后的所有元素。
  • list、forward_list则是针对上述问题的缺点而提出的一种新的数据结构，使插入删除操作更为便捷；但作为代价，不支持元素的随机访问，内存开销大。
  • deque是一个更为复杂的数据结构，同样支持快速随机访问。但是在deque两端添加或删除元素都是很快的。
  • forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作。

Notes：现代C++程序应该使用标准库容器，而不是更原始的数据结构，如内置数组！因为标准库容器的性能几乎肯定与最精心优化过的同类数据结构一样好(通常会更好！)

确定使用哪种顺序容器：通常，使用vector是最好的选择，除非你有很好的理由选择其他容器！

容器库概览

容器类型上的操作形成了一种层次：某些操作是所有容器类型都提供的；另外一些操作仅针对顺序容器、关联容器或无序容器；还有一些操作只适用于一小部分容器。

一般而言，每个容器都定义在一个头文件中，文件名与类型名相同。deque定义在头文件deque中，list定义在头文件list中，以此类推。容器均定义为模板类。

对容器可以保存的元素类型的限制

顺序容器几乎可以保存任意类型的元素。我们甚至可以定义一个容器，其元素类型是另一个容器。

1
2
3

// vector的vector(可以理解为一段句子)
// (较旧的编译器可能需要在两个尖括号之间键入空格，不然会误认为移位操作)
vector<vector<string>> lines;

我们需要考虑的一个问题是，某些容器操作对元素类型有其自己的特殊要求。我们可以为不支持特定操作需求的类型定义容器，但此情况下就只能使用没有特殊要求的容器操作。

举例：顺序容器构造函数的一个版本接受容器大小参数，它使用了元素类型的默认构造函数。但某些类没有构造函数，我们可以尝试定义一个保存这种类型对象的容器，但我们在构造这种容器时不能只传递给它一个元素数目参数：

1
2
3

// 假定noDefault是一个没有默认构造函数的类型
vector<noDefault> v1(10, init);		// 正确，需要提供元素初始化器init
vector<noDefault> v2(10);		// 错误：必须提供一个元素初始化器

容器操作详表：

类型别名具体意义
iterator容器类型的迭代器类型
const_iterator可以读取元素，但不能修改元素的迭代器类型
size_type无符号整数类型，保存此种容器类型最大可能容器的大小
difference_type带符号整数类型，足够保存两个迭代器之间的距离
value_type元素类型
reference元素的左值类型(引用)，等价于value_type&
const_reference元素的const左值类型(即，const value_type&)
构造函数具体意义
C c;默认构造函数，构造空容器
C c1(c2);构造c2的拷贝-c1
C c(b, e);构造c，将迭代器b和e指定的范围内的元素拷贝到c
C c{a, b, c...};列表初始化c
赋值与swap具体意义
c1=c2;将c1中的元素替换为c2中的元素
c1={a, b, c...};将c1中的元素替换为列表中元素(array不支持)
a.swap(b);交换a和b的元素
swap(a, b);同上等价
大小具体意义
c.size();c中元素的数目(不支持单链表forward_list)
c.max_size();c中可保存的最大元素的数目
c.empty();判断是否为空
添加删除元素(不适用array)具体意义
c.insert(*args*);将args中的元素拷贝进c
c.emplace(*inits*);使用inits构造c中的一个元素
c.erase(*args*);删除args指定的元素
c.clear();清空，返回void
获取迭代器具体意义
c.(c)begin(),c.(c)end();显然，不表
反向容器的额外成员(不支持forward_list)具体意义
reverse_iterator;按逆序寻址元素的迭代器
const_reverse_iterator;不能修改元素的逆序迭代器
c.(c)rbegin(),c.(c)rend();返回尾元素以及首元素之前位置的迭代器

以上是涉及到一些经常使用的类型成员以及构造函数信息。

迭代器

与容器一样，迭代器有着公共的接口；如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。

标准容器类型上所有迭代器都允许我们访问容器中的元素，而所有迭代器都是通过解引用运算符来实现这个操作！

标准库容器的所有迭代器都定义了递增运算符，从当前元素移动到下一个元素；

单向链表forward_list迭代器不支持递减运算符；；

迭代器支持的运算：iter + n、iter - n、iter1 += n、iter1 -= n、iter1 - iter2、> >= < <=之所以单独提出这些，是因为这些运算只能应用于string、vector、deque、array的迭代器(因为这一类容器类型支持随机读取访问)

迭代器范围(iterator range)：由一对迭代器表示，两个迭代器分别指向同一个容器中开始的元素以及尾元素之后的位置。数学上的表示：[begin, end)

容器类型成员

每个容器都定义了多个类型，书中之前内容提及较多的是：size_type、iterator、const_iterator;

大多容器同时提供反向迭代器，反向迭代器中各种操作的含义也都发生了颠倒！

对于类型别名，我们可以在不了解容器中元素类型的情况下使用它，需要元素类型的情况下可以使用容器的value_type。如果需要元素类型的一个引用，可以使用reference或const_reference。这种元素相关的类型别名在泛型编程中非常有用。

1
2

list<string>::iterator iter;        // 定义迭代器类型
list<int>::difference_type count;   // 定义距离，可正可负

begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器；存在多个版本，其中带r的版本返回反向迭代器；c开头的版本则返回const迭代器：

1
2
3
4
5

list<string> a = {"Milton", "Shakespeare", "Austen"};	//定义一个双向链表容器
auto it1 = a.begin();	//iterator
auto it2 = a.rbegin();	//reverse_iterator
auto it3 = a.cbegin();	//const_iterator
auto it4 = a.crbegin();	//const_reverse_iterator，总之就是这四种迭代器类型

针对const_iterator进行说明：需要与const iterator进行区分，const_iterator迭代器可以变，但迭代器指向的对象不能变，const iterator则是迭代器不能变，指向的对象可以变。

以c开头的版本是C++新标准所引入的，用以支持auto与begin和end函数结合使用。由此我们也可以看到，当不需要写访问时，应使用cbegin和cend。

容器定义和初始化

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

关键概念：容器元素是拷贝——当我们用一个对象来初始化容器时，或者将一个对象插入到容器中时，实际上放入到容器中的是对象值的一个拷贝，而不是对象本身。有点类似我们将一个对象传递给非引用参数一样，容器中的元素与提供值得对象之间没有任何关联。

只有顺序容器(不包括array)的构造函数才能接受大小参数

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

创建一个容器为另一个容器的拷贝，两个容器的类型及其元素类型必须匹配；传递迭代器参数来拷贝一个范围时，就不要求容器类型相同了，同时新容器和原容器中的元素类型也可不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

list<string> authors = {"Milton", "Shakespeare", "Austen"};

// 容器内元素类型为const char*，指向char数组的首地址
vector<const char*> articles = {"a", "an", "the"};

// 类型匹配，没问题
list<string> list2(authors);

// 错误：容器类型不匹配
deque<string> authList(authors);

// 错误：容器元素类型不匹配
vector<string> words(articles);

// 迭代器范围可以整成拷贝
forward_list<string> words(articles.begin(), articles.end());

可以利用迭代器拷贝一个容器中的子序列。

列表初始化(区分于初始化列表)

新标准中，我们可以对一个容器进行列表初始化：

1
2
3

// 通过给定的列表进行初始化
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

与顺序容器大小相关的构造函数

除了与关联容器相同的构造函数外，顺序容器还提供一个接受容器大小和一个(可选的)元素初始值的构造函数(即关联容器不支持大小参数)，如没有元素初始值，那么标准库会创建一个值初始化器；

1
2
3
4

vector<int> ivec(10, -1);
list<string> svec(10, "hi!");
forward_list<int> ivec(10);
deque<string> svec(10);

提示：如果元素类型是内置类型或者是具有默认构造函数的类类型，可以只为构造函数提供一个容器大小参数。

  • 因为一般构造函数会提供默认值

array容器类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 用法通过代码列出
array<int, 42>
array<string, 10>
// 使用array类型
array<int, 10>::size_type i;    // 数组类型包括元素类型和大小
array<int>::size_type i;        // 错误写法
//-------array的初始化----------//
array<int, 10> ia1;
array<int, 10> ia2 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};  // 通过列表进行初始化
array<int, 10> ia3 = {42};           // 第一个元素被初始化，剩余元素为0
//--------与内置数组类型的区分-----------//
int digs[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int cpy[10] = digs;     // 错误：内置数组不支持拷贝或赋值操作
array<int, 10> digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
array<int, 10> copy = digits;   // array容器支持拷贝以及赋值操作，只要数组类型匹配即合法

容器大小操作

除了一个例外外(该例外指的是forward_list)，每个容器类型都有三个与大小相关的操作：

  • empty检测是否为空；
  • size返回容器中元素数目；
  • max_size返回一个大于或等于该类型容器所能容纳的最大元素数的值；

赋值和swap操作

先列举这么一段代码，了解赋值的过程

1
2
3
4
5
6
7
8

// 与赋值相关的运算符可用于所有容器
c1 = c2;        // 将c1的内容替换为c2中元素的拷贝
c1 = {a, b, c}; // 赋值之后，c1大小为3
// 标准库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};   // 错误：类型不同，因为a2大小为10

一些常用的容器赋值运算：

1
2
3
4
5
6
7

c1 = c2;
c = {a, b, c....};
swap(c1, c2), c1.swap(c2);  // 交换c1和c2中的元素
// assign操作，该操作不适用于关联容器和array
seq.assign(b, e);   // 将seq中的元素替换为迭代器b和e所表示范围的元素
seq.assign(il);     // 将seq中的元素替换为初始化列表il中的元素
seq.assign(n, t);   // 将seq中的元素替换为n个值为t的元素

一个很重要的细节：赋值相关运算会导致指向左边容器内部的迭代器、引用和指针失效，而swap操作将容器内容交换不会(array和string的情况除外)。

赋值运算符要求左边和右边的运算对象具有相同的类型。考虑到这一类型限制，顺序容器(array除外)还定义了一个名为assign的成员，允许我们从一个不同但相容的类型赋值：

1
2
3
4
5
6
7
8

list<string> names;
vector<const char*> oldstyle;
names = oldstyle;   // 错误，类型不匹配
names.assign(oldstyle.cbegin(), oldstyle.cend());   // 两个参数为迭代器类型

// assign的另一个版本，接受一个整型值和一个元素值。
list<string> slist1(1); // 一个元素，为空string
slist1.assign(10, "Hiya!");

使用swap

swap操作交换两个相同类型容器的内容。调用swap之后，两个容器中的元素将会交换：

1
2
3

vector<string> svec1(10);	// 10个元素的vector
vector<string> svec1(24);	// 24个元素的vector
swap(svec1, svec2);

swap操作很快，因为元素本身并未交换，swap只是交换了两个容器的内部数据结构(这意思有点类似浅拷贝？)

  • 对于string而言，swap之后指向容器的迭代器、引用和指针在swap操作之后会失效。
  • string和array之所以会失效，是因为空间分配的策略原因；
  • 对于array而言，swap两个array会真正交换他们的元素，但是指针、引用和迭代器所绑定的元素保持不变。

Notes：书中有这么一点，新标准库提供成员函数版本以及非成员函数版本的swap，从泛型编程的角度考虑，建议统一使用非成员版本的swap。

关系运算符

主要来说就是容器大小的判断，要求关系运算符左右两边的运算对象必须是相同类型的容器，且必须保存相同类型的元素！

  • 容器大小相等，所有元素两两相等，则两容器相等；
  • 容器大小不同，较小容器中每个元素都等于较大容器中的对应元素，则较小容器小于较大容器；
  • 若两容器都不是另一容器的前缀子序列，则他们的比较结果取决于第一个不相等元素的比较结果；

容器的关系运算符使用元素的关系运算符完成比较：因此需要注意的是只有当容器的元素类型也定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。

顺序容器操作

上述内容基本介绍的是所有容器都支持的操作，这部分主要介绍一些顺序容器所特有的操作：

向顺序容器添加元素

除array外，所有标准库容器都提供灵活的内存管理。在运行时可以动态添加或删除元素来改变容器大小。向顺序容器添加元素的操作主要有如下几种：

  • 使用push_back：追加到容器尾部

  • 使用push_front：将元素插入到容器头部，但这部分只有list、forward、deque支持。(是不是因为插入到vector的头部太过耗时)

  • 使用insert在容器特定位置添加元素：forward_list提供了特殊版本的insert成员。insert接受一个迭代器作为其第一个参数。且是将元素插入到迭代器所指定的位置之前，且返回的是新加入元素的位置。

  • 代码用法：slist.insert(iter, "Hello!");

  • 某些容器不支持push_front操作，可以使用insert操作实现类似的功能；

  • 对于vector、deque、string而言，插入进相应位置合法，然而可能很耗时；

  • 使用insert插入范围内元素：迭代器作为第一个参数，元素数目作为第二个参数，元素值作为第三个参数。

    • 代码用法1：svec.insert(svec.end(), 10, "Anna");

  • 使用insert插入范围内元素：第一个参数同样为迭代器，第二第三个参数给定所选范围。

    • 代码用法2：slist.insert(slist.begin(), v.end() - 2, v.end());
    • 代码用法3：slist.insert(slist.end(), {"these", "words", "will"});
    • 注意事项：迭代器表示要拷贝的范围，不能指向与目的位置相同的容器！

  • insert的返回值：接受元素个数或范围的insert版本返回指向第一个新加入元素的迭代器。如果范围为空，insert会将第一个参数返回！

    1
2
3
4

      list<string> lst;
  auto iter = lst.begin();
  while (cin >> word)
      iter = lst.insert(iter, word);	// 等价于调用push_front

  • 使用emplace操作：包括emplace_front、emplace、emplace_back等成员，这些操作构造而不是拷贝元素；分别对应push_front、insert、push_back。直接上代码：

    1
2
3
4
5
6
7

    // 假定c保存Sales_data，在c的末尾构造一个Sales_data对象

// emplace_back的操作
c.emplace_back("978-0590353403", 25, 15.99);

// 要先创建一个临时的Sales_data对象
c.push_back(Sales_data("978-0590353403", 25, 15.99));

    从上述代码可以看出的是，当我们调用一个emplace成员函数时，是将参数传递给元素类型的构造函数。emplace成员使用这些参数在容器管理的内存空间中直接构造元素。

    emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配

    1
2
3
4
5
6
7
8

    // 使用Sales_data的默认构造函数
c.emplace_back();

// 使用Sales_data(string)一个参数的构造函数
c.emplace(iter, "999-999999999");

// 同样会调用Sales_data的相应构造函数
c.emplace_front("978-0590353403", 25, 15.99);

访问元素

包括array在内的每个顺序容器都有一个front成员函数，除forward_list之外的所有顺序容器都有一个back成员函数(单向链表嘛)，同时不能递减forward_list迭代器。

下面的代码需要注意的一点事项就是：front与 back返回的是首尾元素的引用！

1
2
3
4
5
6
7
8
9
10
11
12
13

// 在解引用一个迭代器或调用front或back之前检查是否有元素
if (!c.empty()) {
    // val1和val2是c中第一个元素值的拷贝
    // begin代表迭代器，front返回首元素的引用
    auto val1 = *c.begin(), val2 = c.front();
    auto last = c.end();

    // 不能递减forward_list迭代器
    auto val3 = *(--last);

    // 返回尾元素的引用
    auto val4 = c.back();
}

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

string、vector、deque、array等提供快速随机访问的容器也都会提供下标运算符，程序员需要保证下标有效。(需要确保下标合法，可以使用at成员函数，如越界，抛出一个out_of_range异常)

1
2
3

vector<string> svec;    // 空vector
cout << svec[0];    // 运行时错误：svec中没有元素！
cout << svec.at(0); // 抛出一个out_of_range异常

删除元素

容器同时也有诸多删除元素的方式，但诸多操作不适用于array。

  • pop_back()：删除尾元素；
  • pop_front()：删除首元素；
  • erase(p)：删除迭代器p所指定的元素；
  • erase(b, e)：删除迭代器b和e所指定范围内的元素；
  • c.clear()：删除c中的所有元素；

注意事项：

  • forward_list有特殊版本的earse；
  • forward_list不支持pop_back；

  • vector和string不支持pop_front；

  • 程序员需要保证删除的元素是存在的；

erase的返回值：返回指向最后一个被删元素之后位置的迭代器

特殊的forward_list操作

由于forward_list是单向链表，有指针指向的问题，因此有些操作是特有的。

  • lst.before_begin()与lst.cbefore_begin()：返回指向链表首元素之前并不存在的元素的迭代器。
  • lst.insert_after(p, t)与lst.insert_after(p, n, t)与lst.insert_after(p, b, e)与lst.insert_after(p, il)：在迭代器p之后的位置插入元素。t是一个对象，n是数量，b和e是表示范围的一对迭代器，il是一个花括号列表，返回一个指向最后一个插入元素的迭代器。
  • emplace_after(p, args)使用args在p指定的位置之后创建一个元素。返回一个指向这个新元素的迭代器。
  • lst.erase_after(p)与lst.erase_after(b, e)：返回一个指向被删元素之后元素的迭代器，若不存在这么一个元素，则返回尾后迭代器。

改变容器大小

通过resize来增大或缩小容器(同样，array不支持resize)。

1
2
3
4

list<int> ilist(10, 42);
ilist.resize(15);
ilist.resize(25, -1);	// 添加到ilist的末尾
ilist.resize(5);	// 从ilist末尾删除20个元素

Notes: resize接受一个可选的元素值参数，用来初始化添加到容器中的元素，若未提供此参数，则新元素进行值初始化。

如果保存的是类类型，则我们必须提供初始值，或者元素类型必须提供一个默认构造函数。

很多涉及到顺序容器的操作，push，resize，erase等操作都可能会导致迭代器、指针和引用失效。

迭代器失效的原因

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

，很可能引起与使用未初始化指针一样的问题。

向容器添加元素时：

  • 对于vector或string，若存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效；若存储空间未重新分配，指向插入位置之前的有效，之后无效。
  • 对于deque，除首尾之外的任何位置都会导致全部失效。在首尾添加元素，迭代器会失效，但引用和指针不会失效。
  • 对于list以及forward_list，指向容器的迭代器、指针和引用仍有效。

向容器删除元素时：

首先指向被删除元素的迭代器、指针和引用都会失效，但是其他位置呢？

  • 对于list以及forward_list，指向容器其他位置的，都有效。
  • 对于deque，首尾之外的任何位置删除元素，都会失效；删除尾元素，尾后迭代失效，其他不受影响。
  • 对于vector和string，指向之前的都有效，之后的都失效。

每次改变容器的操作之后都需要正确地重新定位迭代器；展开来讲就是：

  • 不要保存end返回的迭代器，因为每次添加/删除之后原来end返回的迭代器总是会失效。

有关顺序容器操作的源码，详见Github；

容器适配器

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue、priority_queue。适配器(adaptor)是标准库中的一个通用概念。容器、迭代器、函数都有适配器。本质上，一个适配器是一种机制，使某种事物的行为看起来像另外一种事物一样。

定义一个适配器

每个适配器都定义两个构造函数：默认构造函数创建一个空对象，接受一个容器的构造函数拷贝该容器来初始化适配器。

1

stack<int> stk(deq);	// 从deq拷贝元素带stk

默认情况下，stack和queue是基于deque实现的，priority_queue是在vector之上实现的。

我们可以在创建一个适配器时，将一个命名的顺序容器作为第二个类型参数，来重载默认容器类型。

1
2
3
4
5

// 在vector上实现的空栈，第二个参数代表用vector容器的构造函数来初始化适配器
stack<string, vector<string>> str_stk;

// 基于vector实现，初始化时保存svec的拷贝
stack<string, vector<string>> str_stk2(svec);

栈适配器

stack类型定义在stack头文件中，下面的程序展示了stack的使用：

1
2
3
4
5
6
7
8

stack<int> intStack;	// 空栈
for(size_t ix = 0; ix != 10; ++ix)
    intStack.push(ix);
while (!intStack.empty()) {
    int value = intStack.top();
    intStack.pop();	
}
// 弹出顺序与弹入顺序是完全相反的

队列适配器

queue和priority_queue适配器定义在queue头文件中；priority_queue相比queue可以定义其中数据的优先级，即便是新加入的元素，它也会排在所有优先级比它低的已有元素之前，功能相当于构建了一个大顶堆或小顶堆。

CPP, C++_Primer
Programming C++/C cpp
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容

09-C++标准库之IO库

11-C++标准库之关联容器