C++ STL 在算法中的应用

1、vector变长数组

  • 有clear清空操作。
  • 支持比运算，两个vector按字典序比较大小

2、string

substr

string substr (size_t pos = 0, size_t len = npos) const;

返回一个string中下标pos开始，长度为len的子字符串，若len超过最大长度则直接返回从pos到末尾。

c_str

c_str()返回一个string中首元素的下标。用于用scanf输出一个string：

scanf("%s", a.c_str());

3、queue

push()向队尾插入一个元素
empty()判空
size()返回队列大小
front()返回队头元素
back()返回队尾元素
pop()弹出队头元素

4、pair

支持比较运算，以first为第一关键字，以second为第二关键字，进行字典序比较

5、priority_queue优先队列（实现原理是堆，默认是大根堆）

需要include<queue>头文件才能使用。

  • 没有clear。
  • push插入一个元素
  • top返回堆顶元素
  • pop弹出堆顶元素

如何定义小根堆？

  • 法一：插入元素时，插入-x。这可太妙了！
  • 法二：priority_queue<int, vector<int>, greater<int>> heap;

6、stack栈

  • size
  • empty
  • push栈顶插入
  • top返回栈顶
  • pop弹出栈顶

7、deque双端队列（用的很少，效率太低了）

  • size
  • empty
  • clear
  • front / back
  • push_back / pop_back
  • push_front / pop_front
  • begin / end
  • []

8、set，map，multiset，multimap（基于平衡二叉树(红黑树)，动态维护有序序列）

他们都支持：
size
empty
clear
begin / and 及其++ -- （时间复杂度也为O(logn) ）

set / multiset（下面所有操作时间复杂度为logn）

insert插入一个数
find查找一个数
count返回某一个数的个数
erase：

  • ——输入是一个具体数x，参数所有x 时间复杂度：O(k + logn) ，k是x的个数，n是元素个数
  • ——输入一个迭代器，删除这个迭代器

set的核心操作：
lower_bound ：返回>=x的最小的数的迭代器
upper_bound： 返回>x的最小的数的迭代器

map / multimap（）

insert插入一个pair(用的不多)
erase输入参数是pair或迭代器（常用）
find
[]（时间复杂度是O(logn) ）

9、unordered_set unordered_map unordered_multiset unordered_multimap（哈希表实现）

和上面的操作类似，增删改查的时间复杂度是O(1)
不支持迭代器的++ -- （也就是：凡是和排序有关的操作都不支持）
不支持 lower_bound 和 upper_bound

10、bitset压位

bitset<10000> s;

支持：

  • ~ & | ^
  • >> <<
  • == !=
  • []
  • count()返回有多少个1
  • any()判断是否至少有一个1
  • none()判断是否全为0
  • set()把所有位置为1
  • set(k, v)把第k位变成v
  • reset()把所有位变成0
  • flip()等价于~
  • flip(k)第k位取反