应该要掌握的STL

发表于 更新于

应该要掌握的STL

1. vector

​ 假设我们有一个vector<typename> 变量v，那么我们就可以有如下操作：

  • v.push_back(obj)，可以在v的最后插入一个obj

  • v.pop_back()可以弹出v最后一个元素

  • v.size()可以返回v中元素的个数

  • 可以直接通过v[i]访问vector中的元素 

    1
    2
    for (int i=0; i<v.size(); i++)
        #可以直接用v[i]访问vector中的元素

  • sort(v.begin(),v.end(),cmp)可以对v进行排序

  • v.clear()清空vector v

2.priority_queue（优先队列，即堆，默认大根堆）

​ 假设我们有一个priority_queue<node>变量heap，那么我们就可以有如下操作：

  • heap.push(obj)可以把一个元素加入堆

  • heap.pop()可以弹出堆顶元素

  • node tmp = heap.top()可以获得堆顶元素

  • 自定义结构体类型的重载运算符

    1
    2
    3
    4
    5
    6
    7
    struct node {
        int x,id;
    }
    bool operator < (const node &a, const node &b) {
        return a.x < b.x; //以x为关键字从大到小实现大根堆
        return a.x > b.x; //以x为关键字从小到大实现小根堆
    }

3.lower_bound & upper_bound（可以对数组和vector ）（注意需要事先排序）

  • int tmp1 = lower_bound(a + 1,a + n + 1,obj) - a返回数组a中第一个大于等于obj的元素的下标

  • int tmp2 = upper_bound(a + 1,a + n + 1,obj) - a返回数组a中第一个大于obj的元素的下标。

  • int tmp1 = lower_bound(v.begin(),v.end(),obj) - v.begin()返回数组a中第一个大于等于obj的元素的下标

  • int tmp1 = upper_bound(v.begin(),v.end(),obj) - v.begin()返回数组a中第一个大于obj的元素的下标

4.unqiue (可以对数组和vector) （注意需要事先排序）

1
2
3
4
5
6
int a[] = {0,2,5,3,2,3,5};
sort(a + 1,a + 7);
int m = unique(a + 1,a + 7) - a - 1;
printf("m = %d\n",m);
for (int i=1; i<=m; i++)
	printf("%d\n",a[i]);

输出：

1
2
3
4
m = 3
2
3
5

5.bitset

  • 新建一个长度为30的bitset并给它赋值为a： bitset<30> s(a);
  • 可以直接用s[i]访问这个bitset，既可以取值，也可以修改。注意：s[0]是最低位，s[29]是最高位。
  • 可以把两个bitset互相做位运算，也可以对两个bitset做== != 的比较，还可以对bitset进行左移右移。
  • s.count()返回有几个1
  • 如果s所有位全部是0，那么s.any()返回False，s.none()返回True
  • 如果s至少有一位是1，那么s.any()返回True，s.none()返回False
  • 一个使用实例
1
2
3
a = 20;
bitset<20> s(a);
printf("%d\n",s);
1
20
  • 注意：s[0]的类型不是int，但可以强制转换为int，所以可以这样int tmp = s[0]，但不能printf("%d\n",s[0])，如果要直接printf，那么应该printf("%d\n",(int)s[0]).

6. multiset/set

所有multiset的操作只要把“multiset”换成”set"就可以了，故下面用multiset演示

  • 声明方式：multiset<int> s 或multiset<node> s;

    ​ 注意，如果用了后者，那么需要重载<运算符，重载方法和前面在priority_queue里面重载的方法一样。然后，set和multiset默认都是从小到大排序的，所以如果要按照node里的x关键字排序，重载函数应该这样写：

    1
    2
    3
    bool operator < (const node &a, const node &b) {
        return a.x < b.x;
    }

  • multiset的迭代器的概念：

    • 声明一个multiset的迭代器：multiset<node>::iterator it;
    • multiset的迭代器仅支持++和--两个操作，分别表示在multiset中向后或者向前一个元素
    • 如果我们有一个multiset的迭代器it，可以通过*it来表示迭代器it指向的元素（有点像一个指针）

假设我们有一个multiset<int> s;

  • s.size(), s.erase(), s.clear()均支持。

  • s.insert(obj)可以实现往里面插入元素的功能

  • s.find(obj)可以返回一个multiset的迭代器，如果找不到对应元素那么就会返回s.end()，否则返回对应元素的迭代器，可以通过*运算得到对应元素。

  • 设it是一个multiset的迭代器，那么s.erase(it)可以删除这个迭代器对应的元素。

  • s.erase(obj)可以删除所有对应元素。

  • s.count(obj)可以返回s中有多少个元素等于obj

  • s.lower_bound(obj)可以返回第一个大于等于obj的元素的迭代器

    s.upper_bound(obj)可以返回第一个大于obj的元素的迭代器

  • 可以通过这个方式输出multiset s中的元素（默认是从小到大排序的）

    1
    2
    for (multiset<int>::iterator it = s.begin(); it != s.end(); it++)
        printf("%d ",*it);

7. pair

  • 声明方法：pair<typename1,typename2> tmp;

    例如：pair<pair<int,int>, vector<int> > tmp;

  • 一种构造方法：pair<int, int> p = make_pair(2,3)

  • 假设我们有一个pair<int, int> p; 那么可以通过p.first和p.second分别访问第一个元素和第二个元素。

8. map

  • map也有insert(), clear(), empty()的操作

假设我们有一个map<int,int> mp;和一个map<int,int>::iterator it; - 往map里插入一个键值对：mp.insert(make_pair(2,3))

  • 删除迭代器it对应的元素：mp.erase(it)

  • 删除map中的pair：mp.erase(make_pair(2,3))

  • 通过key来删除map中的pair： mp.erase(2)

  • mp.find(make_pair(2,3))在m中找对应元素，返回迭代器。如果不存在，返回mp.end()

  • mp[key]返回key值对应的value，可以直接赋值或访问（和python里的字典一样），如果不存在mp[key]，则直接新建一个空二元组(key,zero)