vector

vector, 变长数组, 倍增思想
    头文件#include <vector>
    size() 返回元素个数
    empty() 返回是否为空
    clear() 清空
    front()/back() 第一个元素/最后一个元素
    push_back()/pop_back() 在最后一个位置插入元素/弹出最后一个元素
    begin()/end()
    []
    支持比较运算(按字典序)
    系统为某一程序分配空间时，所需时间，与空间大小无关，与申请次数有关
    定义
    vector <int> a;
    vector<int> a[10]; // 定义10个vector
    vector<int> a(10); // 定义一个长度为10的vector
    vector<int> a(10,3); // 定义一个长度为10的vector,并初始化为3
    遍历
    for (int i = 0; i < a.size(); i ++ ) cout << a[i] ; // 用数组下标遍历
    for(auto x : a) cout << x ; // C++11新特性 范围遍历
    for(vector<int>::iterator i = a.begin();i != a.end(); i ++ ) cout << *i ; // 用迭代器遍历
    (a.begin()是a[0]，a.end()就是a[a.size()]，也就是a最后一个元素的下一个元素)

pair

pair<int,int>, 二元组
    头文件#include <utility>
    里面类型随意
    pair<int,string> p = make_pair(10,"lyt");
    p = {20,"cctv"};
    first()/second() 
    支持比较运算(按字典序)

string

string
    头文件#include <string>
    string a = "yxc";
    size()/length()// 返回字符串长度
    empty()
    clear()
    substr(起始下标,子串长度) // 返回子串
    c_str()  // 返回字符串所在字符数组的起始地址
    支持加法运算 

priority_queue

priority_queue 优先队列, 默认是大根堆
    头文件#include <queue>
    push()/pop()/top()
    实现小根堆
    priority_queue<int> heap;
    heap.push(-x);
    定义成小根堆 priority_queue<int,vector<int>,greater<int>> heap;

queue,stack,deque

queue, 队列
   size()
   empty()
   push() // 向队尾插入一个元素
   front() // 返回队头元素
   back() // 返回队尾元素
   pop() // 弹出队头元素

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

deque, 双端队列
   size()
   empty()
   clear()
   front()/back()  // back()速度稍慢
   push_back()/pop_back()
   push_front()/pop_front()
   begin()/end()
   []

set,map,multiset,multmap

set,map,multiset,multmap 基于平衡二叉树(红黑树), 动态维护有序序列
    size()
    empty()
    clear()
    begin()/end() // ++,-- 返回前驱和后继  O(logn)

    set/multset  
    set不能有重复元素/multiset允许有重复元素
    insert() // 插入一个数
    find() // 查找一个数, 找不到返回end()迭代器
    count() // 返回某一个数的个数
    erase()
        (1)输入是一个数x,删除所有x  O(k + logn) k是x的个数
        (2)输入是一个迭代器,删除这个迭代器
    lower_bound()/upper_bound()
        lower_bound(x) // 返回大于等于x的最小的数的迭代器 (最小上界)
        upper_bound(x) // 返回大于x的最小的数的迭代器 (最大下界)
    map/multmap
    insert() // 输入的数是一个pair
    erase() // 输入的参数是pair或迭代器
    find()
    [] // O(logn)
    map<string,int> a; a["ysl"]=1;
    lower_bound()/upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multmap

unordered_set,unordered_map,unordered_multiset,unordered_multmap, 哈希表
    和上面类似，增删改查的时间复杂度为O(1)
    不支持lower_bound()/upper_bound(), 迭代器的++,--

bitset

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