标准库-容器浅析-2-C++顺序容器
- 2021-04-25
顺序容器浅析
概述
顺序容器介绍
顺序性容器是一种各元素之间由顺序关系的线性表，是一种线性结构的可序群集。顺序性容器的每个元素均有固定位置，除非用删除或者插入改变这个位置。这个位置和元素本身无关，而和操作的时间和地点有关，顺序性容器不会根据元素的特点排序而是直接保存了元素操作时的逻辑顺序。[1]
所有顺序容器都提供了快速访问元素的能力，但是这些容器在一下方面都有不同的性能折中：
- 向容器添加或者从容器中删除元素的代价
- 非顺序访问容器的代价
| 容器类型 | 特性 |
|---|---|
| vector | 可变数组大小。 支持快速随机访问。在尾巴之外的位置插入或删除元素可能很慢 |
| deque | 双端队列。支持快速随机访问。在头尾位置插入或者删除元素可能很慢 |
| list | 双向链表。只支持双向顺序访问。在list的任何位置插入/删除操作速度都很快 |
| forward_list | 单向链表。只支持单向顺序访问。在链表任何位置插入/删除操作速度都很快 |
| array | 固定大小的数组。支持快速随机访问。不能添加或者删除元素 |
| string | 与vector相似的容器，但是专门用于保存字符。随机访问快，在尾巴插入/删除快 |
浅析方法介绍
在C++中容器是使用模板编写的，vector、deque、list、forward_list等顺序容器的模板参数为
template < class T, class Alloc = allocator<T> >STL容器采用分配器来完成对内存空间的动态分配，迭代器可以访问容器的底层实现，即迭代器可以访问分配器。
分析包括容器的常见接口、容器迭代器
LLVM是C++标准的一个实现。
源码的github地址: https://github.com/llvm/llvm-project/tree/main/libcxx/include
GNU G++ 是C++标准的一个实现,
源码的github地址: https://github.com/gcc-mirror/gcc/tree/releases/gcc-11/libstdc%2B%2B-v3/include
Primer c++ 第5版 page375