1. vector

变长数组， 倍增的思想

• size() 返回容器中元素个数(所有容器都有)

• empty() 判断是否为空(所有容器都有)

• clear() 清空(不是所有容器都有)

// 1. 初始化
    vector<int> a;
    vector<int> b(10);
    vector<int> c(10, 3);

// 2. 返回容器中元素个数
    int num = a.size();

// 3. 判段容器是否为空
    bool = a.empty();

// 4. 清空
    a.clear();

// 5. 获取第0个元素/最后一个元素
    int fir = a.front(), end = a.back();


// 6. 向vector最后插入一个元素
    a.push_back(6);

// 7. 删除vector最后一个元素
    a.pop_back();

// 8. 迭代器，返回第0个元素/最后一个元素的后一个元素的迭代器
    // a.begin(), a.end();


// 9. 三种遍历方式
    for(int i=0; i<10; i++) a.push_back(i);
    for(int i=0; i<a.size(); i++) cout<<a[i]<<" ";
    cout<<endl;
    for (vector<int>::iterator i=a.begin(); i!=a.end(); i++) cout<<a[i]<<" ";
    cout<<endl;
    for (auto x : a) cout<<x<<" ";
    cout<<endl;

// 10. 比较运算(按照字典序比较)
    vector<int> m(3, 4);
    vector<int> n(4, 3);
    if (m < n) cout<<"m < n"<<endl;
    else cout<<"m > n"<<endl;

2. pair

存储二元组

// 1. 初始化
    pair<string, int> pii;
    p = make_pair("yzh", 6);
    p = {"yzh", 8};

// 2. 获取第一个元素/第二个元素
    int fir = p.first(), sec = p.second();

// 3. 支持比较运算(以第一个元素为第一关键字, 第二个元素为第二关键字)

3. string

字符串

• substr(int begin, int length): 获取字串, begin为子串开始位置 length为子串长度

• c_str() : 将字符串转换为字符数组，便于使用printf输出

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

// 1. 初始化
    string str = "abcdefyzh";

// 2. 字符串拼接
    str += "clu";

// 3.获取字串
    string son1 = str.substr(3, 5);
    string son2 = str.substr(3);

// 4. 输出字符串序列(字符数组序列)
    printf("%s\n", str.c_str());    //printf不能直接输出字符串
    cout<<str<<endl;

4. queue

队列

• size() 返回容器中元素个数(所有容器都有)

• empty() 判断是否为空(所有容器都有)

• clear() 清空

• push() 向队尾插入一个元素

• pop() 弹出并返回队头元素

• front() 返回队头元素

• back() 返回队尾元素

// queue 初始化

quque<int> q;

// 重新构造

q = queue<int>();

5. priority_queue

优先队列, 堆实现(默认是大根堆)

• push() 插入一个元素

• top() 返回堆顶元素

• pop() 弹出堆顶元素

// 初始化
    priority_queue<int> heap;

// 定义小根堆
// 方法一： 插入负x
    heap.push(-x);
// 方法二
    priority_queue<int, vector<int>, greater<int>> heap;

6. stack

栈

• size() 返回容器中元素个数(所有容器都有)

• empty() 判断是否为空(所有容器都有)

• push() 元素入栈

• top() 返回栈顶元素

• pop() 弹出栈顶元素

7. deque 双端队列

加强版的vector, 但是效率低

• 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() 支持迭代器，即支持++, --操作， 返回的是后继和前驱

++/–

增删改查的时间: $O(logn)$

8.1 set/multiset

set不能有重复元素，multiset可以有重复元素

• insert() 插入一个元素

• find() 查询一个元素

• count() 获取某一个元素的个数

• erase() (1)参数是一个元素x，则删除所有的x (时间复杂度 $O（k+logn）$)；（2）参数是迭代器，删除这个迭代器

• lower_bound()/upper_bound() 核心操作

  • lower_bound(int x) 返回大于等于x的最小的数的迭代器
  • upper_bound(int x 返回大于x的最小的数的迭代器

// 初始化
set<int> s;

multiset<int> ms;

8.2 map, multimap

• insert() 插入的元素是一个pair

• erase() 参数是pair或迭代器

• find() 查询一个元素，参数是pair

• [] 随机存储，像使用数组一样使用map，时间复杂度是$O(logn)$

• lower_bound()/upper_bound() 核心操作

  • lower_bound(int x) 返回大于等于x的最小的数的迭代器
  • upper_bound(int x 返回大于x的最小的数的迭代器

// 初始化
map<string, int> a;

a["yzh"] = 1;

cout<<a["yzh"]<<endl;

9. unorder_set, unorder_map, unorder_multiset, unorder_multimap

• 哈希表实现, 函数和上面类似

• 增删改查的时间 $O(1)$

• 不支持 lower_bound()/upper_bound()， 即不支持迭代器的++, --操作

10. bitset

压位

应用举例:

// bool 1字节

// 1024B = 1KB

// 压位  每一位存储一个bool(8B)
// 存储1024B 只需要 1024/8 = 128B

举例二：

// 1000 * 1000 布尔矩阵

// 10^8 布尔    100MB, 题目限制64MB

// 用bitset存储，需要12MB

代码:

// 1. 初始化
bitset<1000> s; // 中括号写的是个数

// 2. 支持的运算: 
//      ~  &   |    ^   >>    <<
//      ==    !=

// 3. 支持[] 随机存储取出某位

// 4. count()       返回有多少个1

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

// 6. none()        判断是否全为0

// 7. set()         把所有位置为1

// 8. set(k, v);    将第k位变为v

// 9. reset()       把所有位置为0

// 10. flip()       等价于 ~

// 11. flip(k)      把第k位取反