《C++ Primer》读书笔记 第九章 顺序容器

第九章 顺序容器

9.1 顺序容器概述

选用原则:

  • 除非有更好的理由,否则应用 vector。
  • 如果元素小而多,空间开销很重要,不要用 list 或 forward_list。
  • 要求随机访问:vector、deque。
  • 在中间插入删除:list、forward_list。
  • 在头尾插入删除:deque。

9.2 容器库概览

本节介绍对所有容器都适用的操作。


9.2.1 迭代器

9.2.2 容器类型成员

9.2.3 begin 和 end 成员

9.2.4 容器定义和初始化

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

  • 拷贝整个容器:容器类型和元素类型必须都匹配。
  • 拷贝一对迭代器指定的范围:只需要元素类型匹配,甚至是可转换。

定义 array 容器不但要指定元素类型,还要制定容器大小:

1
array<string, 10>

如果元素类型是类类型,则它必须有一个默认构造函数,以使值初始化能够进行。

9.2.5 赋值和 swap

array 允许赋值,但类型和大小必须相同,且不允许用花括号包围的值列表进行赋值。

assign 不用保证容器类型要相同,只需元素类型相容即可。

除 array 外,swap 不对任何元素进行拷贝、删除、插入操作,保证在常数时间完成,只是交换了两个容器的内部数据结构。因此指向容器的迭代器、引用、指针都不会失效(除 string)。

统一使用非成员版本的 swap 是一个好习惯。(泛型编程很重要)

9.2.6 容器大小操作

size()、empty()、max_size()

9.2.7 关系运算符

==、!=、>、>=、<、<=

9.3 顺序容器操作

9.3.1 向顺序容器添加元素

emplace 是构造而不是拷贝元素。其参数根据元素类型而变化,参数必须与元素类型的构造函数相匹配。

9.3.2 访问元素

下标访问若是越界,[]报运行时错误,at 抛出 out_of_range 异常。

9.3.3 删除元素

9.3.4 特殊的 forward_list 操作

核心思想:单向列表的添加删除,影响的是其前驱元素。所以,如果是遍历过程中进行添加或删除,往往要关注两个迭代器:

1
2
3
4
5
6
7
8
9
10
11
forward_list<int> flst = {0,1,2,3,4};
auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end()){
if (*curr % 2)
curr = flst.erase_after(prev);
else{
prev = curr;
++curr;
}
}

9.3.5 改变容器大小

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

9.4 vector 对象是如何增长的

vector 和 string 一定是连续的,空间不够了会移动所有元素。

reserve 不改变元素的数量,且永远也不会减少容器占用的内存空间。
resize 只改变容器中的元素数目。

9.5 额外的 string 操作

9.5.1 构造 string 的其他方法

9.5.2 改变 string 的其他方法

  • 额外的 insert、erase 版本,在指定位置插入指定数量的指定字符。
  • 接受 C 风格字符数组的 insert 和 assign 版本。
  • append、replace。


9.5.3 string 搜索操作


9.5.4 compare 函数

9.5.5 数值转换

9.6 容器适配器

stack、queue、priority_queue。

定义一个适配器:

  • 默认情况下,stack 和 queue 是基于 deque 实现的,priority_queue 是在 vector 之上实现的。
1
2
3
stack<int> std(deq);
stack<string, vector<string>> str_stk;
stack<string, vector<string>> str_stk2(svec);

所有适配器都要求容器具有添加、删除、访问尾元素的能力,所以不能使用 array、forward_list。剩下的:

  • 都可用于构造 stack,因为它只要求 push_back、pop_back、back。
  • 只有 list 或 deque 能构造 queue,因为它要求 back、push_back、front、push_front。
  • 只有 vector 或 deque 能构造 priority_queue,因为它要求 front、push_back、pop_back、随机访问。