本文介绍c++STL的基础用法，不涉及代码实现，主要从调用者角度熟悉一些基本的API。

容器

vector

概述

数组属于静态内存空间，一经分配内存便无法改变大小，为了使数组更为灵活，封装为vector。

vector底层实现为数组，封装之后的vector在外部看来是一个可变长的顺序容器。在创建vector时会申请一块长度为n的连续内存区域。

vector内部维护两个指标cur_len，max_len，分别表示当前元素的个数和总共可以填充元素个数。

当cur_len = max_len时，数组扩容，申请两倍大小的内存空间，将原来元素拷贝。

当cur_len = max_len / 4, 数组缩容，回收内存空间，并进行元素拷贝。

由于每次扩大和缩小都是成倍的，因此数组大小变化相对与每次操作是平均O(1)。

复杂度

从上面表格可以看出，数组适合随机访问，如果需要经常删除元素，则最好选用链表。

使用

#include <vector> 头文件
vector<int> v;  创建
vector<int> v[100]; 创建时显示声明大小

size 返回数组元素个数
empty 返回是否为空
clear 清空元素    
vector<int>:: iterator it; 迭代器，通过*运算符解除引用。仅支持++和--操作
begin 返回首元素的迭代器
end   返回末尾元素后的迭代器
front/back 首个元素/末尾元素
push_back(x) 插入元素x
pop() 删除末尾元素

queue

概述

与vector的实现基本类型，只是暴露出一部分接口供外部访问，使得queue满足抽象的先进先出数据结构。

使用

push(x) 在队尾插入元素x
pop() 弹出队头元素
front() 队头元素
back() 队尾元素

priority_queue

概述

优先队列也称为堆，是一种用数组实现的树形数据结构，其队头为容器中的最小值(c++默认为大根堆)。由于队头元素通过比较放在树根的位置，因此容器元素之间需要具备可比较性(重载operator <)。

支持的操作有查看队头元素，弹出队头元素，插入元素。

使用

push(x) 插入元素x，复杂度O(logn)
pop(x) 弹出队头元素，复杂度O(logn)
top() 查看队头元素，复杂度O(1)

如果需要使用小根堆，则使用下面代码：

priority_queue<int, vector<int>, greater<int>> q;

deque

概述

双端队列，与普通队列相比增加了一个队头元素的指针。当在队头/队尾增添元素时，队头/队尾指针+1；在队头/队尾删除元素时，队头/队尾指针-1。为了避免指针越界，双端队列可以用循环队列的方式实现。

使用

front/back 队头/队尾元素
push_front/push_back 在队头/队尾插入元素
pop_front/pop_back 弹出队头/队尾元素

set

概述

数学意义上的集合，满足无序性、唯一性。c++默认实现是树结构，如果想用哈希集则引入头文件unordered_set。

树实现的集合还保留了顺序性，哈希实现的集合是无序的。

树集合CRUD操作为O(logn)，哈希CRUD操作为O(1)。

哈希集合的增删改查都是O(1)，对比数组删除元素O(n)，链表随机访问O(n)。这种数据结构可以说是“完美的”。哈希集合的实现利用了计算机中经典的思想：以空间换取时间。

哈希表缺点就是为了避免哈希碰撞而产生的内存开销。

在需要有序性集合中只能用set，而不能用哈希集合。

使用

size/empty/clear 与通常的容器用法相同
begin/end  如果集合有序，则返回最小和最大的元素   
insert(x) 插入元素x
find(x) 查询元素x是否在集合中
erase(x/it) 删除元素x或迭代器it指向的元素
count(x) x在集合中的个数，常用于多重集

map

概述

map是存储键值对(key-value)的容器，一个set可以看成是value均相同的map。

map的实现与set类似，只是集合元素的不同。

使用

支持[]操作，使用与数组类似。

bitset

概述

相当于状态压缩的数组，用于记录状态。

使用

~s 按位取反
&，|，^ 将两个bitset进行按位与，或，异或操作
s[k] 第k位的取值
count() 返回1的个数
any/none 是否存在1和是否都是0
set 把所有位置为1
reset 把所有位置为0

算法

algorithm

概述

算法作用在容器上，通常接受两个参数/指针，表明要操作容器的区间。

用法

reverse 将元素反转
unique 去重，返回去重后容器的end
sort 排序，第三个参数是比较器，用于自定义比较方式
lower_bound/upper_bound 容器必须有序，返回第一个满足的和第一个不满足的，即大于等于x的元素和大于x的元素
upper_bound - lower_bound 表示满足的个数