/*

vector，变长数组，倍增的思想
string，字符串， substr(), c_str()
queue, 队列, push(), front(), pop()//插入，队头元素，弹出
priority queue, 优先队列, push(), top(), pop()
stack, 栈, push(), top(), pop()
deque, 双端队列, 
set, map, multiset, multimap, 基于平衡二叉树（红黑数树), 动态维护有序序列
unordered_set, unordered_map, unordered_multiset, unotdered_multimap,哈希表
bitset, 压位

*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <bitset>

using namespace std;

//vecotr
/*
    vector<int> a;
    vector<int> b(10);//长度为10
    vector<int> c(10, 3);//长度为10, 每一个都为3
    vector<int> d[10];//vector数组, 定义10个vector

    a.size();//返回元素个数
    a.empty();//a是不是空的
    //这两个函数所有容器都有，时间复杂度为O(1)

    a.clear();//清空
    //并不是所有容器都有清空，如队列, stack

    //倍增的思想
    //系统为某一程序分配空间是，所需时间与空间大小无关，与申请次数有关
    //32->64……

    a.front(), a.back();//返回第一个数和最后一个数  
    a.push_back(3), a.pop_back();//向vector的最后插入一个数, 删掉最后一个数

    //迭代器
    a.begin(), a.end();//a的第一个数，a的最后一个数的后面一个数
    a[0];

    //支持比较运算，按字典序比较
    //vector<int> a(4, 3), b(3, 4);
    //a<b;
*/
//vector的遍历
/*
    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(auto) it = a.begin(); it != a.end(); it++) cout << *it << " ";
    cout << endl;

    //a.begin()->a[0], a.end()->a[a.size()];

    for (auto x : a) cout << x << " ";
    cout << endl;
*/

//pair
/*
    pair<int, string>p;
    p = make_pair(3, "aaa");
    p = { 20, "abc" };
    pair<int, pair<int, int>> p0;
    //p.first(); //第一个元素
    //p.second();//第二个元素
    //支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
*/

//string
/*
    string str;
    str.size(), str.length();//返回字符串长度
    str.empty();
    str.clear();

    string a = "abc";
    a += "def";
    a += 'g';

    //substr，返回一个子串，（子串的起始位置，子串的长度）当第二个参数很大，超过字符长度，输出到最后一个字符为止,第二个参数省略返回之后所有子串  
    cout << str.substr(1, 3) << endl;

    printf("%s", a.c_str());//字符a存储字符串的首地址
*/

//queue
/*
    queue<int> q;
    q.size();
    q.empty();
    q.push(3);//向队尾插入一个元素
    q.front();//返回队头元素
    q.back();//返回队尾元素
    q.pop();//弹出队头元素
    //没有empty
    q = queue<int>();//清空
*/

//priority_queue
/*
    priority_queue<int> heap;//默认是大根堆
    heap.push(3);//插入一个元素
    heap.top();//返回堆顶元素
    heap.pop();//弹出堆顶元素

    //从小到大：方式一：heap.push(-x);方式二：priority_queue<int, vector<int>, greater<int>> heap;
*/

//stack
/*
    stack<int> s;
    s.empty();
    s.size();
    s.push(3);//向栈顶插入一个元素
    s.top();//返回栈顶元素
    s.pop();//弹出栈顶元素
*/

//deque
/*
    //效率慢
    deque<int> d;
    d.size();
    d.empty();
    d.clear();
    d.front(), d.back();
    d.push_back(3), d.pop_back();//插入，弹出最后一个元素
    d.push_front(3), d.pop_front();//向队首插入，弹出第一个元素
    d.begin(), d.end();
    d[0];
*/

//set/multiset
/*
    set<int> s; //不能有重复元素，插入冲入元素该操作会被忽略
    multiset<int> ms;//可以有重复元素  
    s.size(), ms.size();
    s.empty(), ms.empty();
    s.clear(), ms.clear();
    //begin(), end(); ++ -- //返回前驱和后继 O(logn)
    s.insert(3), ms.insert(3);//插入一个数 O(logn)
    s.find(3), ms.find(3);//查找一个数，如果不存在会返回end()迭代器
    s.count(3), ms.count(3);//返回某一个数个数
    s.erase(3), ms.erase(3);//删除，参数：（1）一个数x，删除所有x， O(k(x 的个数) + logn);(2) 一个迭代器，删除这个迭代器
    s.lower_bound(3), s.upper_bound(3);
    //lower_bound 返回大于等于x的最小的数的迭代器，不存在返回end()
    //upper_bound 返回大于x的最小的数的迭代器，不存在返回end()
*/

//map/multimap
/*
    size();
    empty();
    clear();
    begin(), end(); ++ -- O(logn)
    insert();//插入的是一个pair
    erase();//pair 或迭代器
    find(); 
    [] 时间复杂度是O(logn)
        map<string, int> m;
        m["abc"] = 1;
        cout << m["abc"] << endl;
*/

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

//bitset
/*
    bitset<10000> b;
    ~, &, |, ^
    >>, <<
    ==, !=
    []
    count(), 返回有多少个1

    any()， 返回是否至少有一个1
    none(), 判断是否全为0

    set(), 把所有位置成1
    set(k, v), 将第k位变成v
    reset(), 把所有位变成0
    flip(), 等价于~
    flip(k), 把第k位取反
*/
int main()
{


    return 0;
}