sort

排序,复杂度为O(nlogn)

sort(Iterator begin, Iterator end, Function comp)

nth_element

将第n小的数字移动到第n位,复杂度O(n)

nth_element(Iterator begin, Iterator nth, Iterator end, Function comp)

nth_element(a,begin(), a.begin()+ k, a.end());

此时输出a[k]的值能得到第k小的数字

lower_bound & upper_bound

传入参数相同皆为Iterator begin, Iterator end, Type v, Function comp

在有序的数组中 lower_bound -> 找到第一个大于等于v的迭代器

​ upper_bound -> 找到第一个大于v的迭代器

复杂度为O(logn)

next_permutation & prev_permutation

unique

vector

queue stack deque

queue 队列

操作: push/emplace pop front empty size

pop <— [0, 1, 2, 3] <— push

不支持下标访问

stack 栈

操作: push/emplace pop top empty size

[ ] <—- push [ ] —-> pop

不支持下标访问

deque 双端队列

操作: push_back/emplace_back pop_back push_front/emplace_front pop_front

front back empty size

支持下标访问

priority_queue

==优先队列 / 堆 大顶堆 小顶堆==

操作: push/emplace pop top empty size

属于队列的一种 但pop时按大小进行pop

eg. <— [3 2 100 0] <— 执行pop操作依次pop出 100 3 2 0 (从大到小)

set

集合: set 有序唯一

​ multiset 有序 不唯一

​ unordered_set 无序 唯一

操作: insert erase find count

有序 元素支持 < 无序 元素支持hash

map