
vector
vector 是变长数组,支持动态扩容。系统为程序分配空间时,所需时间主要与申请次数有关,而非空间大小。因此,变长数组应尽量减小申请空间的次数。当空间不足时,通常采用倍增策略重新申请。vector 支持比较运算,按字典序大小排序比较。
常用函数
- size(): 返回元素个数
- empty(): 返回是否为空
- clear(): 清空
- front()/back(): 访问首尾元素
- push_back()/pop_back(): 尾部插入/弹出
- begin()/end(): 迭代器遍历
- []: 下标访问
遍历方式
支持范围 for 循环及迭代器遍历。
pair
pair 存储一个二元组,可视为有两个变量的结构体,内部有比较函数定义。这两个数据类型放什么都行。它支持比较运算,排序时按字典序排列,以 first 为第一关键字,second 为第二关键字。
构造与用途
最常用的是存储具有两种不同属性的对象。若需按一种属性排序,将属性放在 first。若有三个属性,可使用嵌套 pair,如 pair<int, pair<int, int>> p。
string
C++ 对字符串进行了封装。
常用函数
- size()/length(): 返回字符串长度
- empty(): 判断是否为空
- clear(): 清空
- substr(起始下标,子串长度): 返回子串
- c_str(): 返回字符串所在字符数组的起始地址
queue 队列
先进先出(FIFO)结构。
常用函数
- size(): 返回元素个数
- empty(): 判断是否为空
- push(): 向队尾插入一个元素
- front(): 返回队头元素
- back(): 返回队尾元素
- pop(): 弹出队头元素
priority_queue 优先队列
原理基于堆实现,默认是大根堆。
常用函数
- size(): 返回元素个数
- empty(): 判断是否为空
- push(): 插入一个元素
- top(): 返回堆顶元素
- pop(): 弹出堆顶元素
如何构造小根堆
- q.push() 时直接插入负值。
- 定义时指定比较器:
priority_queue<int, vector<int>, greater<int>> q;
stack 栈
后进先出(LIFO)结构。
常用函数
- size(): 返回元素个数
- empty(): 判断是否为空
- push(): 向栈顶插入一个元素
- top(): 返回栈顶元素
- pop(): 弹出栈顶元素
deque 双端队列
功能强大的加强版 vector,支持两端插入和删除。但由于时间开销较大,不常用。


