哈希表和字符串哈希

存储结构：开放寻址法、拉链法
哈希函数：①：一般直接取模，一般模的数要取质数，而且该质数要离二的整次幂尽可能地远 ②：冲突 ③：处理冲突（开放寻址法、拉链法)
 ④ 一般情况下，哈希表的时间复杂度都可以看成O(1) ⑤：算法题里一般只需要添加和查找操作，如果真的涉及到删除操作，也不会真正删除，一般都会开一个bool数组，打个标记，实现删除。

拉链法：开一个一维数组来存储所有的哈希值。

字符串哈希方式：字符串前缀哈希法
如何定义某一个前缀的哈希值：
1.将字符串看成p进制的数
2.每一个字符表示p进制的每一位数字
3.将这一个字符串变成一个十进制的数
4.然后模上一个比较小的数q，通过取模，就可以将数字映射到0~q-1
5.通过这种方式，可以将任意一个字符串映射到0~n-1上
6.注意！不能把某个字母映射为0
7.假定人品足够好，不会产生冲突hh
8.经验之谈：当进制为131或13331时，可取q为2的64次方
9.用unsigned long long 来代替%2的64次方，因为unsigned long long 溢出就相当于取模了

vector

vector,可变数组，倍增的思想
    size() 返回元素个数，所有容器都有
    empty() 返回是否为空，所有容器都有
    clear() 清空
    front() 返回第一个数
    back() 返回最后一个数
    push_back() 在最后插入一个元素
    pop_back() 将最后一个元素弹出 
    begin() 迭代器，vector的第0个数即a[0]
    end() 迭代器，vector的最后一个数的后面一个数即a[a.size()]
    erase()
    vector支持随机寻址
    vector 还支持比较运算，按字典序来比较
    倍增的思想：一下增加一倍，每一次数组长度不够时，就将长度乘以2

pair

pair<变量类型, 变量类型> 可以存储一个二元组 e.g.  pair<int, string> p;
    p.first 第一个元素 p.second 第二个元素
    pair支持比较运算，按字典序来比较，以first为第一关键字，以second为第二关键字
    pair初始化的两种方式
        p = make_pair(10, "wt");
        p = {20, "wt"};
    pair的用法：如果某个东西有两种属性，则可以存到pair，若需要按照其中一种属性进行排序，则可以将该属性放到first，另一个属性放到second。就很方便
    拓展：如果某个东西有三种属性，则可以 pair<int, pair<int, string>>,将一个pair嵌套进去即可

string

string，字符串
    支持'+'运算，即拼接字符串
    size() / length() 返回字符串长度
    empty() 返回字符串是否为空
    clear() 清空字符串
    substr(起始下标，子串长度) 可以返回某一个子串，当子串长度超过字符串长度，就输出到最后一个字符，若省略第二个参数，直接返回到最后一个字符
    c_str() 返回string对应的字符数组的起始地址

queue

queue 队列，
    size()
    empty()
    push() 向队尾插入一个元素
    front() 返回队头元素 
    pop() 弹出队头元素
    back() 返回队尾元素
    queue是没有clear函数的，如要清空，可以再初始化一个queue

priority_queque

priority_queue，优先队列（基于堆实现）
    priority_queue<int> heap; 默认大根堆
    push() 往堆里插入一个元素
    top() 返回堆顶元素
    pop() 弹出堆顶元素
    没有clear函数
    默认大根堆，如果想构造小根堆 
        1.可以插入负数
        2.直接定义小根堆 priority_queue<int, vector<int>, greater<int>> heap;

stack

stack，栈
    push() 栈顶添加一个元素
    top() 返回栈顶元素
    pop() 弹出栈顶元素
    empty()
    size()
    没有clear函数

deque

deque，双端队列(加强版的vector)
    size()
    empty()
    clear()
    front() 返回第一个元素
    back() 返回最后一个元素
    push_back() 向队尾插入一个元素
    pop_back() 弹出队尾元素
    push_front() 向队头插入一个元素
    pop_front() 弹出队头元素
    支持随机存取[]
    支持迭代器 begin(), end()
    deque虽然很强，但是deque很慢

set,multiset,map,multimap

set,multiset,map,  multimap(都是基于平衡二叉树(红黑树)来实现的，本质：动态维护有序序列)
    size() 时间复杂度O(1)
    empty()
    clear()
    begin() / end()  支持 ++ -- 时间复杂度为logn

set / multiset

    set / multiset(所有操作时间复杂度为logn)
    set里不能有重复元素，若重复插入元素，则操作会被忽略掉
    multiset可以有重复元素
    insert() 插入一个元素
    find() 查找一个元素，若不存在返回end()迭代器
    count() 返回某一个数的个数,set里只返回0/1,multiset有几个就返回几
    erase()
        1.输入是一个数x，删除所有x O(k + logn) k是x的个数
        2.输入一个迭代器，删除这个迭代器
    lower_bound() / upper_bound() 
        lower_bound(x) 返回大于等于x的最小的数的迭代器，若不存在返回end()
        upper_bound(x) 返回大于x的最小的数，若不存在返回end()

map / multimap

    map / multimap(map里是把两个东西做映射,把a映射到b)
    insert() 参数是一个pair 
    erase() 参数是一个pair或者迭代器
    find() 
    [] 像用数组一样用map  时间复杂度O(logn)
        map<string, int> a;
        a["abc"] = 1;
        cout << a["abc"] << endl;
    lower_bound() / upper_bound() 
        lower_bound(x) 返回大于等于x的最小的数的迭代器，若不存在返回end()
        upper_bound(x) 返回大于x的最小的数，若不存在返回end()

unordered_set, unordered_map, unordered_multiset, unordered_multimap

unordered_set, unordered_map, unordered_multiset, unordered_multimap(无序的，基于哈希表实现)
    和上面类似，增删改查时间复杂度为O(1)
    缺点：不支持lower_bound() 和 upper_bound()
          不支持++ --

bitset

bitset(位存储，状态压缩，压位)
    很多题目想压位来算
    省8倍的空间
    bitset<个数> 例如 bitset<10000> s;
    支持所有位运算
        ~, &, |, ^
        >>, << 
        ==, != 
        []
        count() 返回有多少个1
        any / none()
            any() 返回是否至少有一个1
            none() 判断是否全为0
        set() 把所有位置成1
        set(k, v) 将第k位变成 v
        reset() 把所有位变成0
        flip() 把所有位取反， 等价于 ~
        flip(k) 把第k位取反

C++11 auto

    for(auto x : a)
        C++11中，相当于是用临时变量x遍历了a数组，该用法可以遍历各种容器