引入
最近看了《STL源码剖析》的第 4 章和第 5 章,介绍了 C++ STL 中的序列式容器和关联式容器,本文将总结序列式容器的基础概念,不会详细它们的实现原理(想知道自个儿看书吧,我目前只想了解它们的基本原理,用的时候心里有数就行)。
容器概念
容器是存储数据的地方。C++ STL 容器是一些常见数据结构的实现。任何数据结构都是为了特定的算法服务的。
数据结构:数据的特定排列方式。
根据数据在容器中的排列方式,将容器分为序列式容器和关联式容器。
接下来将介绍序列式容器:array
, vector
, list
, deque
以及它们的适配器:stack
, queue
, heap
, priority_queue
。
序列式容器与容器适配器
基础容器
STL 中的底层容器,可以作为其他容器的底层结构(array
除外)。
1.array
-
内置的静态数组类型,空间大小指定后不能改变,元素存储在连续的线性内存空间,不具备动态扩容的能力,实际应用中几乎没有。
-
其迭代器类型为
Random Access Iterator
随机访问迭代器。
2.vector
-
动态数组,元素存储在连续的线性内存空间,其空间可以动态缩小或扩大,实际应用中非常普遍。
-
动态扩容策略:申请更大的新空间(一般是旧空间大小的
2
倍),进行旧数据迁移,释放旧空间,$O(n)$ 线性时间开销。 -
动态缩容策略:只需要将表达
vector
数据结构的指针前移即可,$O(1)$ 时间开销。 -
为了避免频繁发生扩容,
vector
有容量的概念,即它的实际大小比客户端需求量更大一些。 -
引起
vector
内存空间重新配置的操作(如插入、删除操作),会导致之前定义的迭代器失效。 -
其迭代器类型为
Random Access Iterator
随机访问迭代器,支持算术运算。
3.list
- 双向循环链表,元素存储在非线性内存空间,实际应用中非常普遍。
list
不会重新配置空间,因此只有被删除元素的迭代器会失效,其他原先的迭代器不会失效。- 其迭代器类型为
Bidirectional Iterator
双向迭代器,只支持自增(++
)和自减(--
)运算。
4.deque
-
双端队列,采用二级结构实现。一级结构称为中控器,是一个元素均为指针的数组,每个指针指向一段连续的线性空间,这段空间即为二级结构,真正存储数据的地方。
-
deque
的迭代器实现营造了一种“它是连续空间”的假象,其实它只是“一段一段的定量连续空间”。 -
deque
的扩容策略说起来简单:如果一级结构中控器仍有空间,就增加一个指针,指向一段新的连续空间用于存放新元素;否则申请更大的空间迁移一级结构的指针,然后如前所述。 -
deque
没有容量概念,因为如第 3 点所述,它可以随时申请一段新空间与旧空间“拼接”起来,不会发生“申请新空间 -> 迁移元素 -> 释放旧空间”(指的是二级结构即真正的数据不会发生迁移,一级结构中的指针还是会发生迁移的)。 -
书中提到
deque
的迭代器比较复杂,若需要对deque
排序,最好借助vector
完成。 -
其迭代器类型为
Random Access Iterator
随机访问迭代器,支持算术运算。
5.补充
在新的 C++ 标准中增加了 forward_list
单向链表,应该也算基础容器吧,但它的应用限制太多,只有在特定场合下才能使用。
容器适配器
以某种容器作为底层结构,改变其接口,使之符合某种特性。
1.stack
-
stack
栈的特性是“后进先出”,默认采用deque
作为底层结构。 -
其实
vector
和list
也可以作为底层结构,可以根据应用场景分别测试这 3 种底层结构的性能差异进行选择。 -
stack
没有迭代器,因为提供迭代器会破坏它“后进先出”的特性。
2.queue
-
queue
队列的特性是“先进先出”,默认采用deque
作为底层结构。 -
其实 vector 和 list 也可以作为底层结构,但是显然不应该用 vector,因为 vector 删除首元素的时间开销是 $O(n)$,同样的操作 list 只要 $O(1)$ 时间,因此实际应用中只需要测试
deque
和 list 作为queue
底层结构时的性能差异。 -
queue
没有迭代器,因为提供迭代器会破坏它“先进先出”的特性。
3.heap
-
我倾向于把
heap
归类为容器适配器,因为其依赖底层结构 vector 存储数据。众所周知的一个小技巧,使用数组表示堆,可以通过下标快速定位一个节点的父节点和子节点。 -
STL 中
heap
采用隐式表述的方式,不开放给外部使用,而是通过heap
作为底层结构实现priority_queue
优先队列开放给外部使用。 -
heap
算法中有一个 make_heap 算法,其作用是将一个vector
中的元素进行调整使之符合堆特性。在make_heap
算法中需要调用一个perlocate down
算法下拉调整每个节点(在vector
中从后往前寻找第一个非叶子节点开始),此时默认采用<
小于比较操作,即较小的节点被下拉了,那么较大的节点自然成为父节点,因此默认情况下是最大堆。 -
heap
没有迭代器,不提供遍历功能,因为heap
是完全二叉树,其元素需要遵循完全二叉树的排列规则。
4.priority_queue
-
优先队列,默认采用
vector
作为底层结构,且默认采用max_heap
实现。 -
根据上述
heap
的make_heap
算法所述,采用<
小于比较操作得到的是最大堆,相反采用>
大于比较操作得到的是最小堆。
#include <`queue`>
int main() {
priority_`queue`<int, vector<int>, less<int>> pq1; // 最大堆
priority_`queue`<int, vector<int>, greater<int>> pq2; // 最小堆
return 0;
}
标签:容器,迭代,deque,STL,queue,vector,heap,序列
From: https://www.cnblogs.com/zwjason/p/17038449.html