ACwing（基础）--- C++STL库

vector

变长数组，倍增的思想

    size() 返回元素个数
    empty() 返回是否为空
    clear() 清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int,int>

    first 第一个元素
    second 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string 字符串

    substr(起始位置，截取长度)
    c_str() 字符串转换字符数组
    empty()
    clear()

queue 队列

    size()
    empty()
    push() 向队尾插入一个元素
    pop() 弹出队头元素
    front() 返回队头元素
    back() 返回队尾元素
    因为queue没有clear() 所以可以这样清空：q = queue<int>();

priority_queue 优先队列，默认是大根堆

    size()
    empty()
    push() 插入一个元素
    top() 返回堆顶元素
    pop() 弹出堆顶元素
    定义成小根堆的方式：priority_queue<int,vector<int>,greater<int>>q;

stack 栈

    size()
    empty()
    push() 向栈顶插入一个元素
    top() 返回栈顶元素
    pop() 弹出栈顶元素

deque 双端队列

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

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

    size()
    empty()
    clear()
    begin()/end() ++,-- 返回前驱和后继，时间复杂度 O（logn）
    
    set/multiset
        insert() 插入一个元素
        find() 查找一个元素
        count() 返回某一个元素的个数
        erase()
            (1) 输入时一个元素x，删除所有x O（k + logn）
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x) 返回大于等于x的最小的数的迭代器
            upper_bound(x) 返回大于x的最小的数的迭代器
    map/multimap
        insert() 插入的数是一个pair
        erase() 输入的参数是pair或者迭代器
        find() 
        [] 时间复杂度是O(logn)
        lower_bound()/upper_bound()

unordered_set,unordered_map,unodered_multiset,unordered_multimap, 基于哈希表

跟上面类似
    优点：增删改查时间复杂度为O(1)
    缺点：不支持lower_bound()/upper_bound() 、 迭代器的++,--

bitset 压位

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