C++标准模版库

本文最后更新于：2 个月前

STL即标准模板库(Standard Template Library)，隶属于C++标准库，包含了一些常用的模板化的数据结构和算法。STL作为模板，拥有极强的兼容性和普适性，大大提高了我们编写代码的效率，使得其在各大算法比赛中都得到了广泛的应用。

本文将STL的学习分为两个板块：container和algorithm，各个板块只介绍一些在ACM/ICPC等比赛中常用的函数和功能，如果哪里有内容错误还请同学们海涵和反馈。

容器container

img

一、向量Vector

std::vector是STL提供的能够存放任意类型的、内存连续的、可变长度（动态）的数组，可以提供线性复杂度的插入和删除。

Vector的优良特性

  • 可以动态分配内存
    • vector不像c++中普通数组一样需要在定义时设定大小，支持动态扩容，即数组的大小会随着你的插入/删除而变大/变小
    • 允许存储的size也要比普通数组大
  • 便利的初始化
  • 自带常用的函数

Vector使用方法

1.构造函数

为了可以使用vector，请在你的头文件中包含#include<vector>

1
2
3
4
5
6
7
8
// 提示，T代表数据类型，可以是int/string/...，也可以是自己定义的数据类型
vector<T> v1;				//定义一个空的vector v1,元素类型为T,这也是我们最常用的一种初始化方法
vector<T> v2(v1);			//v2中包含v1所有元素的副本
vector<T> v2 = v1;			//等价于v2(v1)
vector<T> v3(n,val);		//v3包含了n个重复的元素，每个元素的值都是val
vector<T> v4(n);			//v4包含了n个重复执行了值初始化的对象，换而言之就是规定了v4的size
vector<T> v5{a,b,c...};		//v5包含了初始化个数的元素，每个元素被赋予相应的初始值
vector<T> v5={a,b,c...};	//等价于上条

2.元素的增删改

  • v.push_back(element)：在尾部插入元素element
  • v.pop_back()：在尾部删除一个元素
  • v.insert(pos,n,element)：在pos位置前增加n个相同的元素element，n可省略不写，默认添加一个

  • v.erase(begin,end)：删除v中[begin,end)范围内的所有元素

  • v.clear()：清除所有元素

3.元素的访问

  • v.at(pos)：返回v中pos位置的引用
  • v.front()：返回v中首元素的引用
  • v.back()：返回v中尾元素的引用
  • v.data()：返回指向数组第一个元素的指针

4.迭代器

迭代器(Iterator)用来访问和检查STL容器中的对象，可以看作是一个数据指针

学过指针的朋友可以很简单的理解这里hahah

本文章暂时只介绍常用的一些迭代器，感兴趣的同学可以自学更多

  • v.begin()：返回指向v中首元素的迭代器，其中*begin=front
  • v.end()：返回指向v中尾元素的迭代器，其中*end=back

5.长度和容量

  • v.empty()：若v为空返回true，非空返回false
  • v.size()：返回v的元素个数（长度）
  • v.resize()：改变v的长度

6.容器的遍历

以下才是我们经常写的玩意

1
2
3
4
5
6
7
8
//1.最常用的
for(int i=0;i<v.size();i++){
    cout<<v[i]<<" ";
}
//2.利用迭代器
for(vector<int>::iterator it=v.begin();it<v.end();it++){
    cout<<*it<<endl;
}

二、双端队列Deque

std::deque是STL提供的双端队列数据结构。

vector对于头部的插入删除效率低，数据量越大，效率越低；deque相对而言，对头部的插入删除速度回比vector快

vector访问元素时的速度会比deque快,这和两者内部实现有关

Deque的优良特性

  • 随机访问的时间复杂度为常数$O(1)$
  • 在结尾或起始插入或移除元素的时间复杂度均为常数$O(1)$
  • 插入或溢出元素的时间复杂度同vector一样为线性$O(n)$

Deque使用方法

1.构造函数

为了可以使用deque，请在你的头文件中包含#include<deque>

1
2
3
// deque的构造函数基本同vector相同，下面只列出最常用的一种
deque<T> d;
...

2.元素的增删改

  • d.push_back(element)：在尾部插入元素element
  • d.push_front(element)：在头部插入元素element
  • d.pop_back()：在尾部删除一个元素
  • d.pop_front()：在头部删除一个元素
  • d.insert(pos,n,element)：在pos位置前增加n个相同的元素element，n可省略不写，默认添加一个
  • d.erase(begin,end)：删除d中[begin,end)范围内的所有元素
  • d.clear()：清除所有元素

3.元素的访问

  • d.at(pos)：返回d中pos位置的引用
  • d.front()：返回d中首元素的引用
  • d.back()：返回d中尾元素的引用
  • d[pos]：访问d中pos位置的值

4.长度和容量

  • d.empty()：若d为空返回true，非空返回false
  • d.size()：返回d的元素个数（长度）
  • d.resize()：改变d的长度

5.容器的遍历

1
2
3
4
5
6
7
8
9
10
11
12
//1.最常用的
for(int i=0;i<d.size();i++){
    cout<<d[i]<<" ";
}
//2.利用迭代器
for(deque<int>::const_iterator it=d.begin();it!=d.end();it++){
    cout<<*it<<" ";
}
//3.通过at方式访问元素
for(int i=0;i<d.size();i++){
    cout<<d.at(i)<<" ";
}

三、双向链表List

std::list 是 STL 提供的双向链表数据结构。能够提供线性复杂度的随机访问，以及常数复杂度的插入和删除。

list 的使用方法与 deque 基本相同，但是由于list本质是链表，不允许人们随机访问它，所以它与deque增删操作和访问的复杂度不同。

list 的迭代器、长度、元素增删及修改相关的函数与 deque 相同，因此不作详细介绍。

List使用方法

由于链表的特性，若想访问中间元素，必须使用迭代器才能进行（不能随机访问），常用的两个元素访问函数如下：

  • l.front()：访问第一个元素
  • l.back()：访问最后一个元素

四、关联式容器Set

std::set是STL提供的一种关联式容器，所有元素都会在插入时自动被排序。

set和数学概念中的集合含义相同，不允许容器中存在相同元素，若将要插入的元素在集合中存在，则无法插入。

set 内部采用红黑树实现。平衡二叉树的特性使得 set 非常适合处理需要同时兼顾查找、插入与删除的情况，因为它的搜索、移除和插入均为对数复杂度$O(logn)$。

Set的优良特性

  • 增删改查的时间复杂度非常优秀，均为对数级，懂自懂
  • 自动进行排序和查重操作，省了很多麻烦

Set使用方法

为了可以使用set/muliset，请在你的头文件中包含#include<set>

1.元素的增删改

  • s.insert(element)：当s中没有element时，将该元素插入set中
  • s.erase(element)：删除值为element的所有元素，并返回删除元素的个数
  • s.erase(pos)：删除迭代器为 pos 的元素，要求迭代器必须合法
  • s.erase(begin,end)：删除s中[begin,end)范围内的所有元素
  • s.clear()：清空集合

2.元素的查找和统计

  • s.count(element)：统计s中元素值为element的个数，在set中该值为0或1
  • s.find(element)：若s中存在element会返回该元素的迭代器，否则返回 end()
  • empty() 返回容器是否为空
  • size() 返回容器内元素个数

3.set指定排序规则

1
2
3
4
5
6
7
8
9
10
11
12
//由于set默认在插入元素时将元素从小到大排序，若想不遵循此排列方式需要自定义排序规则
#include<iostream>
#include<set>
using namespace std;
class MyCompare{
public:
    bool operator()(int v1,int v2){
        return v1>v2;
    }
};
set<int>s1;	//默认排序方式，从小到大
set<int,MyCompare>s2;	////自定义排序方式，从大到小

Mulitset

mulitset也存在于头文件set中

唯一与set不同的是，set不允许容器中有重复的元素，而multiset允许容器中有重复的元素

五、Pair

std::pair 是标准库中定义的一个类模板。用于将两个变量关联在一起，组成一个“对”，而且两个变量的数据类型可以是不同的。

当你需要返回成对出现的数据时，可能要用到pair嗷

Pair使用方法

  • p.first：访问pair的第一个数据（key），该元素起到索引作用
  • p.second：访问pair的第二个数据（value）

Pair创建方法

pair的创建不需要头文件，以下是pair创建的两种方法

  • pair<type, type> p ( value1, value2 )
  • pair<type, type> p = make_pair( value1, value2 )
1
2
3
4
5
6
7
8
// 对这两种方法进行实例化演示
pair<string,int>p("Tom",20);
cout<<"name : "<<p.first<<endl;
cout<<"age : "<<p.second<<endl;
//第二种方式
pair<string,int>p2=make_pair("Jerry",30);
cout<<"name : "<<p2.first<<endl;
cout<<"age : "<<p2.second<<endl;

六、有序键值对容器Map

std::map中的所有元素都是pair，所有元素都会根据元素的键值自动排序

map 内部采用红黑树实现，红黑树的好处懂自懂

如果你需要存储一些键值对，那就可以考虑使用map

Map的优良特性

  • 一对一处理数据提供了便捷
  • map内部已进行自动排序

Map使用方法

1.构造函数

为了可以使用map，请在你的头文件中包含#include<map>

1
2
3
4
map<int,int> m; 	//创建pair类型为<int,int>的map
map<T1,T2> m;		//创建pair类型为<T1,T2>的map
map<int,int>m2(m);	//拷贝构造m2
map<int,int>m3=m;	//赋值构造m3

2.元素的增删改

  • m.insert(pair<T,T>)：在容器中插入元素
  • m.erase(key)：删除容器中值为key的元素
  • m.erase(pos)：删除pos迭代器所指的元素，返回下一个元素的迭代器
  • m.erase(begin,end)：删除m中[begin,end)范围内的所有元素，返回下一个元素的迭代器
  • m.clear()：清空map

3.元素的查找和统计

  • m.count(key)：统计key的元素个数，返回非0及1
  • m.find(key)：查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回end()
  • m.empty() 返回容器是否为空
  • m.size() 返回容器内元素个数

Multimap

map和multimap区别：

map不允许容器中有重复key值元素，multimap允许容器中有重复key值元素

七、栈Stack

std::stack是STL提供的一种后进先出（LIFO）的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

Stack使用方法

1.构造方法

为了可以使用stack，请在你的头文件中包含#include<stack>

1
stack<T> s;

2.常用函数

  • top() 访问栈顶元素（如果栈为空，此处会出错）
  • push(x) 向栈中插入元素 x
  • pop() 删除栈顶元素
  • size() 查询容器中的元素数量
  • empty() 询问容器是否为空

八、队列Queue

std::queue是STL提供的一种先进先出（FIFO）的容器适配器，仅支持查询或删除第一个加入的元素（队首元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

1.构造方法

为了可以使用queue，请在你的头文件中包含#include<queue>

1
queue<T> s;

2.常用函数

  • front() 访问队首元素（如果队列为空，此处会出错）
  • push(x) 向队列中插入元素 x
  • pop() 删除队首元素
  • size() 查询容器中的元素数量
  • empty() 询问容器是否为空

算法algorithm

STL提供了非常多的实现算法的模板函数（查找、排序、操作），本版块将只介绍一些包含在<algorithm>常用的函数。完整的函数列表请单击链接：戳我

友情提醒：aogorithm函数的范围定义为 [first, last) ，其中 last 指代要查询或修改的最后元素的后一个元素。

一、排序Sort

sort()作为algorithm中最常用（自认为）的模板函数，在竞赛中若无特殊要求一般都会使用该函数对序列进行排序操作，时间复杂度达到$O(nlogn)$，很秀

sort使用方法

1
void sort( RandomIt first, RandomIt last, Compare comp );

函数中有三个参数，分别为first,last,comp.

使用sort后以不降序排序范围 [first, last) 中的元素。不保证维持相等元素的顺序，若不自定义comp则默认为less<T>()，即从小到大排序，也可以写入greater<T>()，使得从大到小排序。

如果看上面的这些不太直观，下面给出一些实例化的使用方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sort(a,a+10);		//代表从a[0]到a[9]
sort(a+j+1,a+n+1);	//代表从a[j]到a[n]
sort(a,a+10,less<int >());	//实现了从小到大，less可以不写
sort(a,a+10,greater<int >());	//实现了从大到小

////////使用结构体排序的例子////////
struct lizi{
  int begin;
  int end;
}
lizi m[maxn];
//实现了对m数组的以end从小到大排序
bool comp(lizi a,lizi b){
  return a.end<b.end;
}
//主函数里
sort(m,m+maxn,comp);//用comp的比较方法进行排序

二、查找Find

  • find：顺序查找。find(v.begin(), v.end(), value)，其中 value 为需要查找的值
  • find_end：逆序查找。find_end(v.begin(), v.end(), value)
  • binary_search：二分查找。binary_search(v.begin(), v.end(), value)，其中 value 为需要查找的值
  • lower_bound：在一个有序序列中进行二分查找，返回指向第一个 大于等于 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。lower_bound(v.begin(),v.end(),x)
  • upper_bound：在一个有序序列中进行二分查找，返回指向第一个 大于 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。upper_bound(v.begin(),v.end(),x)

三、操作Operation

  • reverse：翻转数组、字符串。reverse(v.begin(), v.end()) 或 reverse(a + begin, a + end)

  • unique：去除容器中相邻的重复元素。unique(ForwardIterator first, ForwardIterator last)，返回值为指向 去重后 容器结尾的迭代器，原容器大小不变。与 sort 结合使用可以实现完整容器去重

  • random_shuffle：随机地打乱数组。random_shuffle(v.begin(), v.end()) 或 random_shuffle(v + begin, v + end)

  • next_permutation：将当前排列更改为 全排列中的下一个排列。如果当前排列已经是 全排列中的最后一个排列（元素完全从大到小排列），函数返回 false 并将排列更改为 全排列中的第一个排列（元素完全从小到大排列）；否则，函数返回 true

Courses
C++ STL

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！