STL——提高C++编写效率的利器

vector

#include<iostream>
#include<vector>    //vector是一个可以自动改变长度的数组

using namespace std;

int main()
{
    vector<int> a({1,2,3});

    cout << a[0] << ' ' << *a.begin() << endl;;


    // 遍历
    // 第一种，直接像数组一样遍历
    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;

    //当然，还可以直接用auto
    for(auto i = a.begin();i!=a.end();i++) cout << *i << ' ';

    cout << endl;

    // 第三种，范围遍历
    for(int x:a)    cout << x << ' ';
    cout << endl;


    a.push_back(4); //往最后面加一个元素
    //平均计算量是常数

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

    a.pop_back();   //删除最后一个元素
    for(auto x: a)    cout << x << ' ';
    cout << endl;
}

queue

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    queue<int> q;   //队列
    priority_queue<int> a;  // 大根堆
    priority_queue<int,vector<int>,greater<int>> b; // 小根堆

    struct Rec
    {
        int a,b;
        // bool operator > (const Rec& t)  const
        // {
        //     return a > t.a; // 返回大根堆用 < 
        // }

        bool operator > (const Rec& t)  const
        {
            return b > t.a;     //
        }
    };

    priority_queue<Rec,vector<Rec>,greater<Rec>> d; //小根堆，结构体中用大于号
        //如果是大根堆，结构体中用大于号

    d.push({1,2});


    q.push(1);  // 在队头插入一个元素
    q.pop();    //弹出队尾元素
    q.front();  //返回第一个元素
    cout << q.back();   //返回队尾

    // 优先队列的函数
    a.push(1);
    a.top();    // 取最大值
    a.pop();    // 删除最大值

    // 清空队列，队列没有clear()  函数
    q = queue<int>()    // 直接再初始化一下就可以


}

stack——先进后出

#include<iostream>
#include<stack>

using namespace std;

int main()
{
   stack<int> stk;
   stk.push(1);
   stk.pop();
   stk.top();
}

队尾插入，队尾弹出

deque——双端队列，两头都可以进出

#include<iostream>
#include<deque>

using namespace std;

int main()
{
   deque<int> a;
   a.begin(); a.end();
   a.front(); a.back();

   a.push_back(1),a.push_front(2);
   a[0];
   a.pop_back(),a.pop_front();

   a.clear();

   return 0;
}

set

头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。

声明

        set<int> s;
        struct rec{…}; set<rec> s;  // 结构体rec中必须定义小于号
        multiset<double> s;

size/empty/clear 与vector类似

迭代器

set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持”++”和--“两个与算术相关的操作。
设it是一个迭代器，例如set<int>::iterator it;
若把it++，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it--，则it将会指向排在“上一个”的元素。

begin/end

返回集合的首、尾迭代器，时间复杂度均为O(1)。
s.begin()是指向集合中最小元素的迭代器。
s.end()是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此--s.end()是指向集合中最大元素的迭代器。

insert

s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。

find

s.find(x)在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为O(logn)。

lower_bound

upper_bound

这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。
s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

erase

设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素，时间复杂度为O(logn)
设x是一个元素，s.erase(x)从s中删除所有等于x的元素，时间复杂度为O(k+logn)，其中k是被删除的元素个数。

count

s.count(x)返回集合s中等于x的元素个数，时间复杂度为 O(k +logn)，其中k为元素x的个数。

map

#include <map>

map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。

声明

        map<key_type, value_type> name;
        例如：
        map<long, long, bool> vis;
        map<string, int> hash;
        map<pair<int, int>, vector<int>> test;

size/empty/clear/begin/end均与set类似。

Insert/erase

与set类似，但其参数均是pair<key_type, value_type>。

find

h.find(x)在变量名为h的map中查找key为x的二元组。

[]操作符

h[key]返回key映射的value的引用，时间复杂度为O(logn)。
[]操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。