c++算法学习笔记 (21) STL

1.vector:

        变长数组，倍增的思想

        size()返回元素个数

        empty()返回是否为空

        clear()清空

        front()/back()元素

        push_back()/pop_back()

        begin()/end()迭代器

        []

        支持比较运算

2.pair<int,int>:

        first:第一个元素

        second:第二个元素

        支持比较运算，先比较first再比较second

        make_pair()/{}初始化

3.string:字符串

        substr()截取字串

        c_str()把string转化成char*,用法strcpy(c,s.c_scr())

        size()/length()返回字符串长度

        empty()返回是否为空

        clear()清空

4.queue:队列

        push():队尾插入

        pop():队尾弹出

        front():返回队头

        back():返回队尾

        size()返回元素个数

        empty()返回是否为空

        (无clear)

5.priority_queue:优先队列，默认大根堆

        priority_queue（int,vector<int>)

        push():插入

        pop():弹出堆顶

        top():返回堆顶

        可以自定义比较规则

6.stack:栈

        push():栈顶插入

        pop():栈顶弹出

        top():返回栈顶元素

        size()返回元素个数

        empty()返回是否为空

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()/end() 

        ++/--返回前驱和后驱

set/multiset:不能有重复元素

        insert()插入

        find()查找

        count()查找某数的个数

        erase()删除所有指定的数/删除迭代器 O(k+logn)

        lower_bound()/upper_bound()：返回>=x的最小的数的迭代器/返回>x的最小的数的迭代器

map/multimap:不能有重复元素

        insert()插入的数是pair

        find()查找

        erase()删除所有指定的数/删除迭代器

        []     O(logn)

        lower_bound()/upper_bound()：返回>=x的最小的数的迭代器/返回>x的最小的数的迭代器

9.unordered_set,unordered_map,unordered_multiset,unordered_multimap:哈希表

        和8类似，增删改查的时间复杂度为O(1)

        不支持lower_bound()/upper_bound(),++,--

10.bitset:压位

8B->8bit=1B，节省8倍内存空间

bitset<10000> s;

~,&,|,^

>>,<<

==,!=

[]

count()返回有多少个1

any()判断是否至少有一个1

none()判断是否全为0

set()所有位置置1

set(k,v)第k位变成v

reset()所有位变成0

flip()等价于~

flip(k)把第k位取反