C++初学者指南-5.标准库(第一部分)–顺序容器
文章目录
- C++初学者指南-5.标准库(第一部分)--顺序容器
- 标准顺序容器
- 常见特点
- 规律性:复制,分配,比较
- 类型推导(C++17)
- 常用接口部分
- array<T,size>
- vector\<T>
- C++ 的默认容器
- 快速回顾
- 迭代器范围
- 插入元素
- 插入和原地构造(C++11)
- 删除元素
- 释放内存 / 释放空间
- 注意!插入/删除之后!
- Vector接口概览
- deque\<T>
- deque接口概览
- list\<T>
- list接口概览
- forward_list\<T>
- forward_list接口概览
- 指导方针
- 相关链接
标准顺序容器
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个数据结构
顺序容器概览表
附上原文链接
如果文章对您有用,请随手点个赞,谢谢!^_^