/*
vector 变长数组,倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/ back()  返回第一个/最后一个元素
    push_back()/ pop_back()  在最后插入/删除一个元素
    begin()/ end()  第0个元素/最后一个数的后面一个数
    支持比较运算,按字典序
    支持随机选取

pair<int, int>  二元组
    first  第一个元素
    second  第二个元素
    支持比较运算,以first为第一关键字,以second为第二关键字(按字典序)

string  字符串,substr(), c_str()
    size()/length()  返回元素个数
    empty()  返回是否为空
    clear()  清空

queue  队列
    push()  在队尾插入元素
    pop()  弹出队头元素
    front()  返回队头元素
    back()  返回队尾元素

priority_queue  优先队列,默认是大根堆
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>>

stack  栈
    size()  返回元素个数
    empty()  返回是否为空
    push()  栈顶插入一个元素
    pop()  返回栈顶元素
    top()  弹出栈顶元素

deque 双端队列
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/ back()  返回第一个/最后一个元素
    push_back()/ pop_back()  在队尾插入/弹出一个元素
    push_front()/ pop_front()  在队首插入/弹出一个元素
    begin()/ end()  第0个元素/最后一个数的后面一个数
    支持随机选取

set, map, multiset, multimap  基于平衡二叉树(红黑树),动态维护有序序列
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    begin()/ end() ++, --  第0个元素/最后一个数的后面一个数  前驱,后继 时间复杂度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()  查找一个参数(pair或者迭代器)
        []  可以像数组一样使用,时间复杂度O(logn)
        lower_bound()/ upper_bound()
            lower_bound(x) 返回大于等于x的最小的数的迭代器
            upper_bound(x) 返回大于x的最小的数的迭代器

unordered_set, unordered_map, unordered_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(k)  把第k位取反
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
    //vector
    /*
    vector<int> a(10);  建立一个长度为10的vector数组
    vector<int> a(10, -3);  建立一个长度为10的vector数组，数组中的每一位初始化为-3
    vector<int> a;

    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 << *i << ' ';//用迭代器进行遍历
    cout << endl;

    for(auto c: a) cout << c << ' ';
    cout << endl;

    vector<int> a(4, 3), b(3, 4);

    if(a < b) puts("a < b");
    */

    //pair
    /*
    pair<int, string> p;
    pair<int, pair<int, int>> p;
    p.first
    p.second

    p = make_pair(10, "tt");
    p = {20, "11"};
    */

    //string
    /*
    string a = "tt";
    a += "cc";
    a += 'q';

    cout << a << endl;//输出"ttccq"
    cout << a.substr(1) << endl;//输出"ttccq",即输出从下标为1的位置开始的整个字符串
    cout << a.substr(1, 2) << endl;//输出"tc",即输出从下标为1的位置开始的2个字符
    cout << a.c_str() << endl;//输出"ttccq",即输出string a存储字符串的起始地址
    */

    //queue
    /*
    queue<int> q;

    q = queue<int>();因为queue没有clear函数,如果想将队列清空,则只需要重新创建一个空队列即可
    */

    //priority_queue
    /*
    priority_queue<int> heap;//大根堆
    priority_queue<int, vector<int>, greater<int>>;//小根堆
    */

    //set
    /*
    set<int> S;
    multiset<int> MS;
    */

    //map
    /*
    map<string, int> a;

    a["tt"] = 1;

    cout << a["tt"] << endl;
    */

    //unordered_set、 unordered_map
    /*
    unordered_set<int> a;
    unordered_map<int, int> b;
    */
    return 0;
}