STL序列容器简介
包含以下内容:
- 容器的概念
- 序列容器的基本要求与可选要求
- 几种序列容器特点与基本操作
容器的概念
STL具有容器概念和容器类型;
容器概念是指具有名称(序列/关联容器)的通用类别;
容器类型是指可用于创建具体容器对象的模板;
所以,序列容器是一类容器类型的统称;
容器是存储其它对象的对象,不能将任何数据类型存储到容器中。
序列容器的基本要求与可选要求
序列容器有七种:vector、deque、queue、priority_queue、list、forward_list、stack;
注意,array不是STL容器;
序列容器通用要求:
- 初始化
- 插入
- 擦除
//初始化重要的两个方式 X a(n, t); X b(a.begin(), a.end()); //插入重要的两个方式 a.insert(a.begin(), t); a.insert(a.begin(), b.begin(), b.end()); //擦除区间 a.erase(a.begin(), a.end());
序列可选要求:
- front()、back()
- 返回开头、结尾的元素,注意是元素
- push_back、pop_back、push_front、pop_front
- 在开头/结尾进行插入/删除操作
- vector不推荐在头插入删除
- list、deque都可以(list指双链表)
- a[n]、 a . at(n)
- 返回第n个元素
- at具有边界检查,如果越界会有out_of_range异常
几种序列容器的特点与基本操作
vector —— 最简单的序列容器
除非需要在头部插入、删除元素,其余推荐使用vector
vector强调快速随机访问
- < vector >头文件
- 尾部插入/删除为固定时间操作
- 头部/中间插入/删除为线性时间操作
- 支持反转(rbegin、rend)
- 支持随机访问
deque —— 双端队列
频繁在头插入删除元素,可以使用deque
- < deque >头文件
- 支持随机访问(比vector稍慢)
- 头尾插入/删除都是固定时间操作
- 中间插入/删除为线性时间(比vector稍慢)
- 支持反转
list —— 双链表
任意一处插入/删除都是固定时间;
list强调快速随机插入/删除;
- < list >头文件
- 不支持随机访问、数组表示法
- 有merge(合并)、sort(排序)、unique(删除重复元素)方法(primer,P699)
forward_list —— 单链表
- < forward_list >头文件
- 只能正向迭代
- 不可反转
queue —— 队列
底层默认为deque;
先入先出,所以只能在头删除元素、尾添加元素
- < queue >头文件
- 不允许随机访问
- 不允许遍历
- empty()、size()、front()、back()、push()、pop()方法
- pop()直接删除头,所以需要先用front查看头
priority_queue —— 优先队列
底层默认为vector;
最大的元素将被移到队首;
- < queue >头文件
stack —— 栈,先入后出
底层默认为vector;
- < stack >头文件
- empty()、size()、top()、push()、pop()方法
- pop()直接删除尾,所以需要用top()查看尾
array —— 非STL容器
固定大小,无法调整
- < array >头文件
- 无push、insert等方法
- 有at()等方法