C++ STL 标准库合集

什么是STL

STL（Standard Template Library），即标准模版库，是一个效率非常高的C++程序库。其中包含了许多在计算机中最常用的数据结构和基本算法，高度体现了程序的可复用性。

STL组件

重要的三部分

容器

是一种数据结构，例如vector(向量)、list(链表)、stack(栈)、queue(队列)，以模版的方式提供，为了访问容器中的数据，可以使用迭代器。

迭代器

是一种特殊的指针，它提供了访问容器中对象的方法。在程序中，我们利用迭代器可以快速而安全的对容器内容进行操作，或是进行算法模板的使用。

算法

很多也称之为泛型算法，是一类常用的算法模板，既可以对容器进行操作，同时其开放性也可以针对数组或者是自定义结构体等结构进行直接的操作。

vector

什么是vector

vector名字叫做向量，是C++中的一种容器，简单说就是一个可变长度的数组，支持随机访问，不支持在任意位置插入 $$O(1)$$。为了保证效率，元素的增删一般应该在末尾进行，同数组一样，下标也是从0开始。

优点

长度可变，内存动态分配，封装了很多函数。

声明方法

1

vector <数据类型> 名称;

声明样例

1
2
3
4
5
6
7
8
9
10

#include<vector>
using namespace std;
struct Node{
    int x,y;
};
vector <int> a;
vector <Node> b;
int main(){
    return 0;
}

push_back

在末尾添加元素，时间复杂度O(1)

1
2

vector <int> a;
a.push_back(5);

简单遍历

vector可以用数组下标的方式去访问和遍历,下标从0开始。

1
2
3
4
5
6
7
8
9
10
11
12

#include<iostream>
#include<vector>
using namespace std;
vector <int> a;
int main(){
    for(int i=1;i<=10;i++){
        a.push_back(i);
    }
    for(int i=0;i<a.size();i++){
        cout<<a[i]<<" ";
    }
}

insert

insert可以将元素插入到指定位置，结合begin()和end()使用，时间复杂度()O(n)

1
2

vector <int> a;
a.insert(a.begin()+3,666);//在第四个位置处插入666这个元素（下标为3）

erase

erase可以删除元素，既可以删除某一个的元素，也可以删除某一段元素，删除某一个元素时，给出的参数是一个位置，这个位置不是下标，也不是一个简单的数字，而是通过begin()和end()计算出来的，例如想删除下标为3的元素，不能直接写erase(3)，而是写a.erase(a.begin()+3)，如果想删除某一段元素时，需要写出两个参数，对应开始位置和结束位置。

1
2
3
4

vector <int> a;
a.erase(a.begin()+5);//删除下标为5的元素，第六个元素
a.erase(a.begin()+2,a.end()-1);//删除下标从2开始，到倒数第二个元素结束
a.erase(a.begin()+2,a.begin()+4);//删除下标从2-4的元素

基本操作

结合操作

1

a.erase(unique(a.begin(),a.end()),a.end());//去重

迭代器

迭代器就像STL容器的"指针",它是直接通过地址去访问和更改元素，可以用星号*操作符去引用。

语法格式：

1

vector<数据类型> ::iterator 自定义标识符;

例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include<iostream>
#include<vector>
using namespace std;
vector<int> a;
int main(){
    vector<int> :: iterator it;
    for(int i=1;i<=10;i++){
        a.push_back(i);
    }
    for(it=a.begin();it!=end();it++){
        cout<<*it;
    }
    return 0;
}

auto关键字

auto关键字是一个自动存储变量的关键字

C++11标准后可以使用auto关键字设定迭代器

语法格式：

1
2
3

for(auto it=a.begin();it!=end();it++){
        cout<<*it;
}

vector排序

sort函数可以对vector进行排序。

1
2

vector<int> a;
sort(a.begin(),a.end(),cmp);

二维vector

就是在vector中的每一个元素替换成一个vector，本质是关于vector的vector。对于二维的vector的初始化我们需要额外注意，直接使用 vector<vector<int> >a; 定义出来的是大小为0的二维数组， 我们没办法访问他，也不能直接 push_back

1
2
3
4
5

int N=5, M=6; 
vector<vector<int>> a(N); //定义二维动态数组大小5行 
for(int i =0; i< a.size(); i++) { //动态二维数组为5行6列，值全为0
	a[i].resize(M); //resize可以重设数组的大小 
}

队列

什么是队列

队列是一种特殊的线性表。队列的原则是先进先出（ FIFO — first in first out ）。比如洗车通道，先进去的车，会先从出口出来，最后进的最后洗完。

队列在队头做删除操作，在队尾做插入操作：

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（ FIFO — first in first out ）线性表。

基本操作

建立队列

1

queue<数据类型> 队名

优先队列(priority_queue)

优先队列：本质是堆实现。与队列不同的是，优先队列只能访问队列头部的信息（使用top），且插入元素后，会自动排序log**n。

常用题型:

贪心算法，需要维护动态元素的排序。

声明方式

1

priority_queue<type,Container,Functional>;

type：

数据类型，就是优先队列中每一个元素的数据类型

Container

容器类型，用哪种容器实现的优先队列，可以是vector，queue等。

Functional

比较方式

小顶堆(队头最小)

1

priority_queue <int,vector<int>,greater<int> > q;

大顶堆(队头最大)

1

priority_queue <int,vector<int>,less<int> > q;

注意：比较方式不写默认是大顶堆

基本操作

set

set也叫做关联式容器，也叫集合，它用于存储同一种数据类型的容器，并且能从一个数据集合中取出数据，在set集合中，每个元素的值都是唯一的，系统可以将元素的值自动进行排序,set中元素的值不能直接改变。

set定义（头文件set）

1
2

set<类型> 对象名;
set<int> s;

添加元素

1
2
3
4

set<int> s;
s.insert(5);
s.insert(8);
s.insert(5);//重复的元素添加不进去，但不会报错

set遍历

set的遍历也是使用迭代器进行遍历，可以正序遍历也可以反序遍历。

正序遍历

1
2

set<int> s;
for(auto it=s.begin();it!=s.end();it++)	cout<<*it<<" ";

反序遍历

1
2

set<int> s;
for(auto it=s.rbegin();it!=s.rend();it++)	cout<<*it<<" ";

常用函数

**注意：**插入元素和删除元素复杂度都是$O(logn)$

map

它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个称为该关键字

的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快

速通道 map就是从键（key）到值（value）的映射。因为重载了[]运算符，map像是数组的“高级版”。

如果没有 map ，我们利用结构体数组查找某个键对应的值，就需要遍历整个数组，这样很低效。 map 的内部实现是一种名为红黑树的数据结构，当我们将不同的键值放入 map ，这种数据结构会自动将所有键值变为有序的（按照键 key 排序）。

例如可以用一个 map<string, int>month_name来表示“月份名字到月份编号”的映射，然后用

monthname[“July”]=7这样的方式来赋值。

在之前我们学习桶排序时遇到的无法开很大的问题可以得到解决。

声明

1
2
3

map<key_name,value_name> name;
map<long long,bool>vis;
map<string,int> a;

插入元素

1
2
3
4

my_Map["a"]=1; // 最常用的方法
my_Map.insert(map<string,int>::value_type("b",2)); 
my_Map.insert(pair<string,int>("c",3));
my_Map.insert(make_pair<string,int>("d",4));

查找并获取map中的元素

1

int x = my_Map["a"];//最常用

但只有当 map 中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值。

因此使用 map 判断一个值是否存在要用 find 。

1
2
3
4

auto it=a.find(key);
if(it != a.end()) { 
    string s = it->second;
}

使用 find 来查找元素是否存在。

存在则返回一个迭代器的地址，该地址对应一个 pair ，因此如果 map 的类型是 map<string,int> ，返回的 pair<string,int> ，我们可以通过迭代器的 it−>second 来读取元素的值。

不存在则返回 map.end() 。

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 迭代器
//可以用 map::iterator it; 定义一个迭代指针it。c++11开始支持auto关键字
//it->first 为索引键值，it->second 为值。
#include <bits/stdc++.h>
using namespace std;
int main() {
    map<int, string> mapStudent;
    mapStudent[1] = "student_one";
    mapStudent[2] = "student_two";
    mapStudent[3] = "student_three";
    for (auto it = mapStudent.begin(); iter != mapStudent.end(); iter++) {
        cout << iter->first << "" << iter->second << endl;
    }
}

常用函数

1
2
3

my_Map.size()       //返回元素数目 
my_Map.empty()      //判断是否为空 
my_Map.clear()      //清空所有元素

许可协议

本文由 AirTouch 编写，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章