STL的API参数都是迭代器

vector （可以发现如果只是对当前数组的开头和结尾进行操纵，数组模拟比较好O(1),如果对中间进行操纵用哪个都是O(n)

切记 对结尾插入O(1)删除O(1) 其他都是O(n)

对开头和结尾进行操纵 用deque

仅对结尾操纵 直接数组模拟 或 vector

对开头进行操纵 最省时间 肯定是deque

1 支持任何位置插入 O(n)

    vector <int> alls;
    for(int i = 1 ; i <= 5 ; i ++)
    alls.push_back(i);
    for(auto t : alls)
    printf("%d ", t);//                    1 2 3 4 5 
    printf("\n");
    alls.insert(alls.begin() + 2, 6);//    1 2 6 3 4 5
    for(auto t : alls)
    printf("%d ",t); 

2 支持任何位置(段)删除

    vector <int> alls;
    for(int i = 1 ; i <= 5 ; i ++)
    alls.push_back(i);
    for(auto t : alls)           
    printf("%d ", t);           //                                                 1 2 3 4 5 
    printf("\n");
    alls.erase(alls.begin() + 2);//                                                1 2 4 5
    alls.erase(alls.begin(), alls.begin() + 2);//[alls.begin(), alls.begin() + 2)  3 4 5
    for(auto t : alls)
    printf("%d ",t); 

3 支持STL自带二分函数 O(logn)

    vector <int> alls;
    alls.push_back(0);  //为使下标从1开始 可以在开头插入一个无关的不影响条件的数
    for(int i = 1 ; i <= 5 ; i ++)
    alls.push_back(i);//
    int t = lower_bound(alls.begin(), alls.end(), 8) - alls.begin();
    if(t == alls.size())//                >= 8 的第一个数
    printf("No\n");
    else
    printf("%d\n", alls[t]);
    int t = upper_bound(alls.begin(), alls.end(), 8) - alls.begin(); // > 8 的第一个数

4 支持翻转数组 O(n)

    for(int i = 1 ; i <= 5 ; i ++)
    alls.push_back(i);
//    reverse(alls.begin(), alls.end()); 会改变容器本身
    vector <int> alls;
    for(int i = 0 ; i < 3 ; i ++)
    alls.push_back(0);
    for(auto t : vector <int> (alls.rbegin(), alls.rend())) //只是倒着读 不会改变本身
    printf("%d\n",t);
    if(alls == vector <int> (alls.rbegin(), alls.rend()))
    printf("YES\n");

5.sort用法

    sort(alls.begin() ,alls.end()); //正向从小到大排列
    for(auto t : alls)
    printf("%d\n", t);
    printf("\n"); 
    sort(alls.rbegin(), alls.rend()); //反向从小到大 正向从大到小
    for(auto t : alls)
    printf("%d\n", t);

6.邻接表

    vector <int> alls[maxn]; //相当于开了maxn个vector
    无法传入函数

7.vector二维数组

    vector < vector <int> > alls(n, vector <int> (m, 0)) ; //相当于开了 n * m 的矩阵 且初始化为0
    可以传入函数
    void bfs(vector <vector <int> > &alls) //会对alls原序列进行改变
    void bfs(vector <vector <int> alls) // 会对传入的东西 进行复制一份， 不改变原序列

multiset 和 set 自带排序 插入logn

    auto t = mt.lower_bound(0);    

*t 为当前>=0的第一个值 返回不了下标!!!!!!!!

两者仅有唯一的区别，multiset可存储重复元素，set只能存储唯一的元素
1 支持删除元素

    multiset <int> mt;
    for(int i = 1 ; i <= 5 ; i ++)
    mt.insert(i);      // 1 2 2 3 4 5
    mt.insert(2);        //                     (删除容器中第一个>=2的元素)
    mt.erase(2);//(删除所有值为2的元素)          mt.erase(mt.lower_bound(2))
    for(auto t : mt) //  1 3 4 5                1 2 3 4 5
    printf("%d ",t);
    mt.erase(mt.begin()); //删除单个元素
    mt.erase(mt.begin(), mt.end()) // 删除整段元素
//  mt.erase(mt.begin(), mt.begin() + 5)(这种不知道为什么 运行不了。。。。)

2 自带二分函数(比STL本身的快) (返回值为迭代器)

    multiset <int> mt;
    for(int i = 1 ; i <= 5 ; i ++)
    mt.insert(i);// 1 2 2 3 4 5
    mt.insert(2);
    auto t = mt.lower_bound(0);    //    *t 为 当前的值     返回不了下标!!!!!!!!
    if(t != mt.end())
    printf("%d\n", *t);//  *(--t) 为当前的前一个数  
    else
    printf("No\n");

附上某巨巨multiset详解

deque(支持开头和结尾插入和删除，O(1)) 其他都是O(n)

    deque <int> dq;
    dq.push_front(1); //在开头插入1
    dq.push_front(3); //在开头插入3
    dq.push_back(4);  //在结尾插入4
    dq.pop_front();   //从开头删除
    dq.pop_back();    //从结尾删除
    dq.insert(dq.begin() + 1, 5);//  在下标为1的位置上插入5    时间复杂度为O(n)
    dq.erase(dq.begin(), dq.begin() + 2); //  删除[0, 2) 之间的元素！！！