// 十三个STL标准库

// 容器：

// 序列容器：每个元素都有固定位置，取决于插入时机和地点，与值无关

#include <vector>

#include <deque>

#include <list>

// 适配器容器：依赖序列容器，默认底层容器是deque实现，设计是为了限制功能

#include <stack>

#include <queue>

// 关联容器：元素位置取决于固定的排序准则，如set,map,multiset,multimap

#include <map>

#include <set>

// 算法：

#include <algorithm>

#include <numeric>

// 函数对象：

#include <functional>

// 迭代器：

#include <iterator>

// 其它：

#include <memory>

#include <utility>

using namespace std;

int main()

{

    // 序列容器：

    // vector:值存储在动态数组中，可以随机存取，底层是连续内存，类似于数组，在尾部增删较快，头中部增删较慢，因为每次增删都要移动该位置之后的所有元素

    // 随机访问O(1)，尾部增删O(1)，头中部增删O(n)

    // deque:双端队列，相当于两个尾部的vector，底层是分段连续内存，头尾增删都快

    // 随机访问o(1)，略慢于vector，头尾增删O(1)，中间增删O(n)

    // list：双向链表，查找和增删时间复杂度都是o（n），不支持随机存取，所以不能用[]或者.at访问元素，同时迭代器只能自加自减，不能加减常数

    // 任意位置增删O(1)，只需要修改指针，不支持随机访问，所以访问第n个元素O(n)

    // 容器通用方法，其中stack和queue没有迭代器

    // 构造：vector<类型> 名字;

    vector<vector<int>> my_vecvec;                                              // vector<int>类型vector，后续push_back相当于声明新的vector<int>

    my_vecvec.push_back(vector<int>(10, 0));                                    // 带参构造：vector(n,value)：构造一个长度为n的vector，每个元素都为value

    my_vecvec.push_back(vector<int>(my_vecvec[0].begin(), my_vecvec[0].end())); // 区间构造：vector(beg,end)：构造一个vector，将beg到end之间的元素拷贝过来，左闭右开，会拷贝左值，但是不拷贝右值

    my_vecvec.push_back(vector<int>(my_vecvec[1]));                             // 拷贝构造：vector(const vector &v):构造一个vector，将v的元素拷贝过来

    // 赋值：v.assign()参数和构造一样,v1.swap(v2)

    deque<int> my_deque, my_deque1, my_deque2, my_deque3;

    my_deque.assign(10, 0);

    my_deque1.assign(my_deque.begin(), my_deque.begin() + 5);

    my_deque2 = my_deque1;

    my_deque2.swap(my_deque1); // 交换my_deque2和my_deque1，所有容器都是O(1)效率

    // 长度：

    my_deque.size();        // 返回my_deque的长度

    my_deque.empty();       // 判断my_deque是否为空

    my_deque.resize(10, 1); // 将my_deque的长度变为10,超出的元素会被删除，若缺少元素，则用1填充，默认用零初始化或空状态填充

    // 迭代器：提供一个对各种容器的通用访问方法，还能减少越界风险

    deque<int>::iterator itbeg, itend;           // 迭代器在容器插入导致动态扩容时可能仍指向原空间导致失效

    deque<int>::reverse_iterator itrbeg, itrend; // 反向迭代器，适用于一些双向容器

    itbeg = my_deque.begin();                    // 返回容器的起始迭代器，即第一位元素

    itend = my_deque.end();                      // 返回容器的结束迭代器，即最后一位元素的再后一位，可以直接给迭代器加减来移动访问位置

    itrbeg = my_deque.rbegin();                  // 返回容器的反向迭代器，即最后一位元素

    itrend = my_deque.rend();                    // 返回容器的反向结束迭代器，即第一位元素的再前一位

    // 序列容器vector，deque，list的通用方法，其中vector仅支持尾部back操作，不能用front，list不支持随机访问，所以不支持[]和.at

    // 访问元素：

    my_deque[0];      // 返回第0个元素，越界会导致异常终止

    my_deque.at(0);   // 返回第0个元素，越界会抛出异常

    my_deque.front(); // 返回第一个元素

    my_deque.back();  // 返回最后一个元素

    // 插入和删除：

    my_deque.push_back(1);                                                     // push_back()将元素插入到vector的尾部，resize后vector长度还是动态的

    my_deque.push_front(2);                                                    // push_front()将元素插入到vector的头部

    my_deque.pop_back();                                                       // 删除末尾元素

    my_deque.pop_front();                                                      // 删除第一个元素

    my_deque.insert(my_deque.begin(), 1);                                      // insert，从指定位置插入元素，第一个元素为指针，第二个为插入值

    my_deque.insert(my_deque.begin() + 1, 2, 1);                               // 在指定位置插入n个元素，第一个元素为指针，第二个为插入个数，第三个为插入值

    my_deque.insert(my_deque.begin() + 3, my_deque2.begin(), my_deque2.end()); // 通过迭代器插入，第一个元素为指针，第二个为迭代器起始位置，第三个为迭代器结束位置

    my_deque.erase(my_deque.begin() + 1);                                      // 删除指定元素

    my_deque.erase(my_deque.begin() + 1, my_deque.begin() + 3);                // 删除指定区间的元素

    my_deque.clear();                                                          // 清空容器

    // vector方法：

    my_vecvec.capacity(); // 返回目前分配内存可容纳的元素数量

    my_vecvec.reserve(5); // 为vector预留五个元素的空间，与resize()不同，reserve()不会改变vector的大小

    // list方法：

    list<int> my_list;

    my_list.remove(1); // 移除所有为1的元素

    my_list.unique();  // 移除所有连续的重复元素，若先sort再使用unique，可以消除所有重复元素

    // 这都是基于指针变动的原生方法，其它容器需结合迭代器操作，将待删除元素移到一起手动删除

    my_list.reverse(); // 反转

    my_list.sort();    // 排序

    // 序列容器通用，但是list依赖自身的指针，而vector和deque依赖于全局方法std::reverse，因此效率更高

    // 适配器容器：

    // stack：栈，依赖于deque实现，后入先出，只支持尾部插入和删除

    // queue：队列，依赖于deque实现，先入先出，只支持尾部插入和头部删除

    // 适配器容器方法：其中栈和队列的push和pop方法都是O(1)

    stack<int> my_stack;

    queue<int> my_queue;

    my_stack.push(1); // 插入元素1到尾部

    my_stack.pop();   // stack删除尾部元素,queue删除头部元素

    // 二者的独特方法：

    my_stack.top();   // 返回栈顶元素

    my_queue.front(); // 返回队列头部元素

    my_queue.back();  // 返回队列尾部元素

    // 关联容器:储存键盘或键值对，将key与val对应起来，底层为红黑树，按键升序排列，增删查效率O(logn)，构建和修改性能O(logn)

    // pair：键值对，可以通过pair.first和pair.second访问键和值

    pair<int, string> my_pair(1, "one"); // pair<type,type> p(key,val)直接构造pair对象

    make_pair(2, "two");                 // make_pair(key,val)通过make_pair()构造pair对象

    // map：映射，储存pair，用key作为索引，val作为值，类似于python 的字典

    // multimap：储存可重复的pair，相同key的pair按插入顺序排列

    // pair中的key是只读的，检索会得到key值对应val的引用，若key不存在，则增加一个节点，并返回其val的引用，并由此修改val

    // set：集合，储存唯一的key，key=val，无重复元素，不支持随机访问

    // multiset：储存可重复的key

    // 构造，大小，状态，迭代器，增删查同序列容器，但是由下标索引改为key

    set<int> my_set;

    map<int, string> my_map;

    my_map.insert(pair<int, string>(1, "one"));     // map.insert(pair p)可以直接创建pair

    my_map.insert(make_pair(2, "two"));             // 也可以插入现成的pair

    my_map[3] = "three";                            // map[key]=val还可以通过下标插入或修改

    map<int, string>::iterator it = my_map.find(1); // 通过寻找key来创建迭代器，会指向第一个匹配的key，若没找到则会返回.end()

    my_map.count(1);                                // 返回key的个数，map为0或1，multi的为重复次数

}