C++初学者指南-5.标准库(第一部分)–顺序容器

标准顺序容器

array<T,size>	固定尺寸连续数组
vector<T>	动态连续数组；O(1)时间复杂度的增长策略；C++的“默认”容器。
deque<T>	双向队列，可以快速的在两端插入和删除。
list<T>	双向链表；O(1)时间复杂度的插入、删除和剪接；实际上通常比vector要慢。
forward_list	单向链表；O(1)时间复杂度的插入、删除和剪接；比list需要更少的内存；实际上比vector要慢。

常见特点

规律性：复制，分配，比较

所有标准序列容器都是规则类型：

• 深度复制：复制将创建一个新的容器对象并复制所有包含的值
• 深度赋值：从源到目标的所有包含对象都会被复制
• 深度比较：比较两个容器比较包含的对象
• 深层所有权：销毁容器将销毁所有包含的对象

std::vector<int> a {4,7,1,9};
std::vector<int> b {1,2,3};
bool equal1 = (a == b);  // false
b = a;  // 复制赋值 ⇒ b: 4 7 1 9
bool equal2 = (a == b);  // true
a[0] = 3;     // a: 3 7 1 9     b: 4 7 1 9
bool equal3 = (a == b);  // false
// 制作精确复制品的不同方式,
// 用拷贝构造新容器
std::vector<int> a2 {a};
std::vector<int> a3 (a);
std::vector<int> a4 = a;
auto a5 {a};
auto a6 (a);
auto a7 = a;

类型推导(C++17)

从C++17开始，可以从构造函数调用中推断元素类型。

std::vector v {1, 2, 3, 4};	std::vector<int>
std::vector v {1.f, 2.3f, 4.5f};	std::vector<float>
std::vector v {1., 2.3, 4.6};	std::vector<double>
struct p2 { int x; int y; };
std::vector v {p2{1,2}};	std::vector<p2>

常用接口部分

正向遍历的迭代器

可以通过标准序列容器的成员函数从中获取：
container.begin() → @first_element
container.end() → @one_behind_last_element

或者使用独立函数: (C++11)
std::begin(container) → @first_element
std::end(container) → @one_behind_last_element

如果你不熟悉迭代器是什么，请参考这篇文章。

前向遍历的常量迭代器

可以通过标准序列容器的成员函数从中获取：
container.cbegin() → @first_element
container.cend() → @one_behind_last_element

或者使用独立函数: (C++11)
std::cbegin(container) → @first_element
std::cend(container) → @one_behind_last_element

空查询
要么用成员函数：
container.empty() → true, 如果容器没有元素
或者用独立函数：
std::empty(container) → true, 如果容器没有元素

类型接口

• container::value_type
• container::size_type
• container::iterator
• container::const_iterator
  ,

using con_t = std::vector<double>;
con_t::size_type i = 0;         // std::size_t
auto x = con_t::value_type{0};  // double

array<T,size>

• 无开销随机存取
• 快速遍历；适用于线性搜索
• size 必须是常量表达式（= 编译时已知）
• 不支持大小更改操作（调整大小、插入、擦除等）
• 如果元素类型具有较高的复制/赋值开销(重新排序元素需要复制/移动它们)，则可能会变慢

运行示例代码

vector<T>

C++ 的默认容器

• 无开销随机存取
• 快速遍历；适用于线性搜索
• 以平摊常数时间插入
• 如果在开头或随机位置频繁进行插入/删除操作，可能会变得很慢
• 如果元素类型具有较高的复制/赋值开销(重新排序元素需要复制/移动它们)，则可能会变慢
• 所有可以改变容量的操作（插入，尾部添加，等等）可能会使任何向量元素的引用/指针失效
• 对于非常大量的值，分配时间可能很长（可以缓解，看这里）

快速回顾

运行示例代码

迭代器范围

注意：迭代器范围的末尾迭代器 q 指向最后一个元素的后面的位置。

插入元素

【】
迭代器范围

插入和原地构造（C++11）

删除元素

删除不会影响容量，也就是说，向量vector的任何内存都不会被释放。

释放内存 / 释放空间

从向量中删除元素永远不会改变容量，因此也永远不会释放任何内存。

.shrink_to_fit() （可能有效）

• ISO标准并不要求它实际收缩
• 标准库的实现可能决定不进行收缩

vector<int> v;
// add a lot of elements …
// erase elements …
v.shrink_to_fit(); C++11

保证有效：

• 制作临时副本 ⇒ 副本恰好与元素相匹配
• 通过交换/移动交换内存缓冲区
• 临时的东西会自动销毁

vector<int> v;
// add a lot of elements …
// erase elements …
// shrink: make a new copy and
// replace v's content with it:
v = vector<int>(v);       C++11-20
// or:
v.swap( vector<int>(v) ); C++98-20

注意！插入/删除之后！

如果一个向量的容量被改变或元素被insert、push_back、emplace、emplace_back、erase、=、assign、resize、reserve等操作移动时，所有迭代器都会无效化。（交换两个向量的内容并不会使迭代器无效，除了末尾的迭代器。）

迭代器失效操作概览

操作	无效的迭代器
只读操作	无
swap, std::swap	仅在结束位置end()
reserve, shrink_to_fit	如果容量改变了：全部无效。 否则：无
push_back, emplace_back	如果容量变了：全部无效。 否则：只有end()
insert, emplace	如果容量改变：全部无效 否则：仅在插入点或之后（包括末尾end()）
resize	如果容量改变：全部无效：只有 end() 和用于擦除的元素的迭代器
pop_back	迭代器指向被删除元素和末尾位置
erase	用于擦除元素及其后面所有元素的迭代器(包括. end())
clear, operator=, assign	全部无效

Vector接口概览

deque<T>

双端队列

• 常数时间的随机访问（极小的开销）
• 快速遍历；适合线性搜索
• 两端具有良好的插入和删除性能
• 插入操作不会使元素的引用或指针失效
• 如果随机位置的插入/删除操作占主导地位，可能会变得比较慢
• 如果元素类型具有较高的复制/赋值开销(重新排序元素需要复制/移动它们)，则可能会变慢
• 大量值的分配可能需要很长时间（可以通过一些方法来缓解，参见这里）

deque接口概览

list<T>

双向链表

• 重组操作不需要移动/复制元素（适合存储拷贝/赋值成本高的大对象）
• 常量时间拼接(完整列表)
• 只能在线性时间内进行随机访问
• 由于内存局部性差，遍历速度慢
  

list接口概览

forward_list<T>

前向链表

• 比list占用更少的内存

• 重组操作不需要移动/复制元素（适合存储拷贝/赋值成本高的大对象）

• 常量时间拼接(完整列表)

• 随机访问只能在线性时间内完成

• 由于内存局部性不好，导致遍历速度慢

• 只能向前遍历

• 由于仅支持前向链接，接口有点复杂

  • 不能: size(), back(), push_back(), pop_back(), insert()
  • 替代: insert_after(), splice_after(), before_begin()

  

forward_list接口概览

指导方针

我应该使用哪种顺序容器？
默认选择：std::vector ！

相关链接

std::vector
cppreference: 容器库
一个C++容器和算法教程
5分钟5个数据结构

顺序容器概览表

附上原文链接

如果文章对您有用，请随手点个赞，谢谢！^_^