s

本文主要仿于【C++】蓝桥杯必备 算法竞赛常用STL万字总结_算法竞赛允许哪些stl-CSDN博客

STL总结

应该整合一下这方面的知识点了。

一、什么是STL？

STL（Standard Template Library），即标准模板库

STL的作用:加快书写速度

二.各种STL

1、vector 【可变数组】

数组加强版

①头文件：

1
#include<vector>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
using namespace std;
int main () {
	//几种初始化的方法
    vector<int> a;//定义一个vector  未初始化 输出》 0
vector<int> a(3);//定义一个长度为3的vector  未初始化 输出》0 0 0

vector<int> a(10, 3); //定义一个长度为10，且每个数赋值为3

//将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
//它的初始化不和数组一样 
vector<int>a(b.begin(),b.begin+3);

//从数组中获得初值
int b[7]={1,2,3,4,5,6,7};
vector<int> a(b,b+7）;

for(auto x : a) {//遍历输出 
    cout << x << " ";
}
return 0;
}

③size()

1
a.size( )//返回元素个数

④a.resize( )

1
a.resize( )//改变大小

⑤empty()

1
2
a.empty();
//判断a是否为空，空则返回true，非空则返回false

⑥front()和 back()

1
2
3
4
a.front();
//返回a的第1个元素,当且仅当a存在
a.back(); 
//返回vector的最后一个数

⑧clear()

1
2
a.clear();
//清空a中的元素

⑨支持比较运算 比较操作==，！=，<，<，<=，>，>=

1
2
3
4
5
6
7
8
9
10
int main () {
    //支持比较运算
    vector<int> a(4, 3), b(3, 4);
    //a: 3 3 3 3   b:4 4 4 
    //比较原理字典序 (根据最前面那个判断，如果一样就往后比较)
    if (a < b) {
        puts("a < b"); 
    } 
    return 0;
}

⑩push_back()和pop_back();

1
2
3
4
a.pop_back();
//删除a向量的最后一个元素
a.push_back(5);
//在a的最后一个向量后插入一个元素，其值为5

⑪begin()和end()

1
2
3
a.begin();// vector的第0个数
a.end();// vector的最后一个的数的后面一个数
//通常与for循环结合使用

⑫遍历vector的三种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int main () {
    vector<int> a;
    for (int i = 0; i < 10; i ++) {
        a.push_back(i);
    }
    //三种遍历vector的方法
    for (int i = 0; i < a.size(); i ++) {
        cout << a[i] << ' ';
    }
    cout << endl;

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

    //C++11的新语法
    for (auto x : a) {
        cout << x << ' ';
    }
    cout << endl;  
    return 0;
}

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++)
    cout<<*it<<endl;

强烈建议使用最后一种：

因为真是太简洁了

1
2
3
for (auto x : a) {
    cout << x << ' ';
}

⑬结合算法erase() reverse()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
  vec.erase(vec.begin()+2);删除第3个元素

vector<int> a={1,2,3,4,5};
reverse(a.begin(),a.end());//a的值为5，4，3，2，1  倒置

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).
    
定义排序比较函数：

bool Comp(const int &a,const int &b)
{
    return a>b;
}
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

2、pair [ x,y ]

可以理解为（x,y）数学中的坐标表示 小技巧：使用typedef定义 typedef pair<int, int> PII ①头文件

1
#include<utility>

②初始化 使用：pair<first数据类型,second的数据类型>元素名； pair中只有两个元素，first和second。

1
2
3
//俩种方法初始化
pair<string,int> p("hello",1);
p = make_pair("hello",1);

③first() 和second()

1
2
3
p("hello",1);
p.first; //第一个元素 =hello
p.second; //第二个元素 = 1

④嵌套

1
vector< vector<pair<int, int> > >//与vector结合【再写个vector结合即可】
1
2
//套娃操作 用pair存储3个数据
 pair<int, pair<int, int>> p(1,{2,3});

⑥当pair 结合 sort()函数使用的时候， pair 默认对first升序，当first相同时对second升序（从小到大）。

自定义：

1
2
3
4
int cmp(pair<int,int>a,pair<int,int>b){
    if(a.first!=b.first)return a.first>b.first;
    else return a.second<b.second;
}

3、string【字符串】

支持比较操作符>,>=,<,<=,==,!=

①头文件

1
#include <string>

②初始化

1
string a = "ac";

③ substr()

实用性尤其广泛，经常能在各种子串题目见到，前些天的图灵杯一道题也可以用该种方法截取水过去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream> 
#include<string>
using namespace std;

int main () {
    string a = "ac";
    a += "w";//支持比较操作符>,>=,<,<=,==,!=
    cout << a << endl; //输出子串a :acw

    a += "ing";  
    cout << a << endl;
    //以字符串数组理解
    cout << a.substr(0, 3) << endl; //当第一个数是0 则后一位数:输出从头开始的长度为3的子串
    cout << a.substr(0, 3) << endl; //当第一个数是1 则输出下标为1 到下标为3的子串  
    cout << a.substr(0, 9) << endl;//如果超出长度范围 则输出原子串
    cout << a.substr(1) << endl; //从下标为1开始输出
    cout << a.substr(0) << endl; //原子串
    printf("%s\n", a.c_str());//如果用printf输出  

    return 0;
}

⑤push_back() 和 insert()

1
2
3
4
5
6
7
8
9
// 尾插一个字符
    a.push_back('a');
// insert(pos,char):在制定的位置pos前插入字符char
    a.insert(a.begin(),'1'); //输出 1a
  //插入字符串
  string str2="hello";
    string s2="weakhaha";
    str2.insert(0,s2,1,3);
//将字符串s2从下标为1的e开始数3个字符，分别是eak，插入原串的下标为0的字符h前

⑥empty() 判断a是否为空，空则返回true，非空则返回false ⑦size() length() 都是 返回字母个数 !!注意他们的类型都是 注：std::string 的成员函数 length() 的返回值类型为 unsigned 类型，因此当 s.length() < t.length() 时，二者相减会得到一个很大的数产生运行时错误，所以相减之前需要先将二者强制类型转换为 int 类型。

⑧clear() 把字符串清空

4、queue【队列】 和priority_queue 【优先队列、堆】

队列是一种数据结构 原理：先进先出，元素从一端入队，从另一端出队，就像是排队。 优先队列和队列特性不同：按优先级排序 和 获取 ①头文件

1
#include < queue >

②初始化

1
2
3
4
5
6
//queue <类型> 变量名  
//priority_queue <类型> 变量名;
queue <int> q; //定义一个名为q队列
priority_queue <int> q; //默认是大根堆
//定义小根堆
小根堆：priority_queue <类型,vecotr <类型>,greater <类型>> 变量名

③共同函数

1
2
3
4
q.size();// 这个队列的长度
q.empty();//用于判断这个队列是否为空，空则返回true，非空则返回false
q.push(); //往队尾插入一个元素
q.pop(); //队列：把队头弹出  优先队列 ：弹出堆顶元素

④区别 队列：

1
2
q.front();// 返回队头元素
q.back(); //返回队尾元素

优先队列：

1
q.top();// 返回堆顶元素

注意：队列和堆没有Clear函数。

5、stack 【栈】

①头文件

1
include<stack>

②初始化

1
2
3
//stack<类型> 名字;
stack<int> s;
12

③size() 返回这个栈的长度 ④push() 向栈顶插入一个元素 ⑤top() 返回栈顶元素 ⑥pop() 弹出栈顶元素

6、deque【双向队列】

1
#include <deque>

②初始化

1
deque<int> dq;//定义一个int类型的双向队列

③常用函数

1
2
3
4
5
6
7
8
9
10
11
dq.size(); //返回这个双端队列的长度
dq.empty(); //返回这个队列是否为空，空则返回true，非空则返回false
dq.clear(); //清空这个双端队列
dq.front(); //返回第一个元素
dq.back(); //返回最后一个元素
dq.push_back(); //向最后插入一个元素
dq.pop_back(); //弹出最后一个元素
dq.push_front(); //向队首插入一个元素
dq.pop_front();//弹出第一个元素
dq.begin(); //双端队列的第0个数
dq.end(); //双端队列的最后一个的数的后面一个数

7、set 【集合】和 multiset

集合与映射也是两个常用的容器,set类似于数学上的集合 ①头文件 include<set> ②初始化

1
set<string> s;*//string 集合*

③区别 set不允许元素重复，如果有重复就会被忽略，但multiset允许. ④常用函数

1
2
3
4
5
6
7
8
9
10
size();// 返回元素个数
empty(); //返回set是否是空的
clear(); //清空
begin(); //第0个数，支持++或--，返回前驱和后继
end(); //最后一个的数的后面一个数，支持++或--，返回前驱和后继
insert(); //插入一个数
find(); //查找一个数
count(); //返回某一个数的个数
erase(x); //删除所以x  时间复杂度 O(k + logn)
 erase(s.begin(),s.end());//删除一个迭代器

⑤核心函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 		lower_bound(x); //返回大于等于x的最小的数的迭代器  核心操作
        upper_bound(x); //返回大于x的最小的数的迭代器  不存在返回end()
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long ll;
int N;
//lowwe_bound：返回第一个>=x的迭代器
//set从小到大排序 
set<int>se;
int main()
{
	//如果set存在比某个数大的数， 输出的是set中的数
	//如果不存在，直接返回迭代器.end() 
	se.insert(2);
	se.insert(4);
	se.insert(10);
	set<int>::iterator it;
	it=se.lower_bound(9);
	cout<<*it<<endl;
	it=se.end();
	cout<<*it<<endl;
	/*
	set中{2 4 10} 
	输出：
		10 3
	*/ 
	return 0;
}

8、map 【映射】 /multimap map就是从键（key）到值（value）的映射。因为重载了[ ]运算符，map像是数组的“高 级版”。例如可以用一个map<string，int>month_name来表示“月份名字到月份编号”的映射， 然后用month_name["July"]=7这样的方式来赋值 ①头文件

1
2
include <map>
    map<string,int>m

②常用函数

1
2
3
4
5
6
7
insert(); //插入一个数，插入的数是一个pair
erase(); 
    //（1）输入是pair
    //（2）输入一个迭代器，删除这个迭代器
find(); //查找一个数
lower_bound(x); //返回大于等于x的最小的数的迭代器
upper_bound(x); //返回大于x的最小的数的迭代器

③常用函数

1
2
3
4
5
6
7
insert(); //插入一个数，插入的数是一个pair
erase(); 
    //（1）输入是pair
    //（2）输入一个迭代器，删除这个迭代器
find(); //查找一个数
lower_bound(x); //返回大于等于x的最小的数的迭代器
upper_bound(x); //返回大于x的最小的数的迭代器

④ 映射 [ ] 时间复杂度 O(logn)

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <string>
#include<map>
using namespace std;
int main()
{
  	map<string,int>a;
  	a["abc"] = 1;//把字符串"abc" 映射为1
  	cout << a["abc"] << endl; //查找abc  程序输出 1
    return 0;
}

⑤应用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
#include<map>
using namespace std;
typedef pair<string,int> PSI;
int main()
{
    map<string,int> mp;
    mp.insert(make_pair("heihei",5));
    mp.insert(PSI("haha",10));//简化
    map<string,int>::iterator it=mp.begin();//迭代器：map<int, char>::iterator it
    for(;it!=mp.end();it++)
       cout<<it->first<<"  "<<it->second<<endl;
    return 0;
}

9、unordered【哈希表】

unordered_map 内部并不按照键的大小顺序存储元素，而是根据哈希值将元素散列到不同的桶中，因此元素的存储顺序是无序的。

unordered_map 适用于需要快速查找和插入元素，且不要求元素存储顺序的场景

因为哈希表的原因，unordered_map 并不支持 lower_bound 和 upper_bound 等操作

因此在需要按照键的大小顺序查找元素时，可以考虑使用 map。

1
2
3
4
5
6
7
unordered_map和unordered_set区别：
存储元素的方式：unordered_map 存储键值对，而 unordered_set 只存储键，没有值。
元素的唯一性：unordered_map 中每个键只能对应一个值，而 unordered_set 中每个键只能出现一次。
元素的访问：unordered_map 可以通过键来访问值，而 unordered_set 只能通过键来判断元素是否存在。
内部实现：unordered_map 和 unordered_set 都是使用哈希表实现的，但是 unordered_map
需要同时保存键和值，因此在内部实现上需要比 unordered_set 多一些开销。

unordered_set 用法示例：

1.insert()函数：用于插入元素，语法为：

1
2
3
4
std::unordered_set<int> myset;
myset.insert(3);
myset.insert(1);
myset.insert(7);

2.find()函数：用于查找元素，语法为：

1
2
3
4
5
6
7
std::unordered_set<int> myset = {1, 2, 3};
auto it = myset.find(2);
if (it != myset.end())
    std::cout << "Element found in unordered_set: " << *it << std::endl;
else
    std::cout << "Element not found in unordered_set" << std::endl;

3.erase()函数：用于删除元素，语法为：

1
2
std::unordered_set<int> myset = {1, 2, 3};
myset.erase(2);

4.size()函数：返回unordered_set中元素的数量，语法为：

1
2
std::unordered_set<int> myset = {1, 2, 3};
std::cout << "unordered_set size: " << myset.size() << std::endl;

5.empty()函数：检查unordered_set是否为空，语法为：

1
2
3
4
5
6
std::unordered_set<int> myset;
if (myset.empty())
    std::cout << "unordered_set is empty" << std::endl;
else
    std::cout << "unordered_set is not empty" << std::endl;

6.clear()函数：用于清空unordered_set中的所有元素，语法为：

1
2
std::unordered_set<int> myset = {1, 2, 3};
myset.clear();

unordered_map

1.unordered_map::insert(): 向 unordered_map 中插入元素，接受一个 pair 类型的参数或两个迭代器。

1
2
3
4
unordered_map<int, string> map;
map.insert(make_pair(1, "one"));
map.insert({2, "two"});
map.insert(map.end(), {3, "three"});

2.unordered_map::find(): 查找指定键值的元素，返回一个指向该元素的迭代器，如果未找到则返回 unordered_map::end()。

1
2
3
4
5
6
unordered_map<int, string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = map.find(2);
if (it != map.end()) {
    cout << "Found " << it->second << endl;
}

3.unordered_map::erase(): 从 unordered_map 中删除指定键值的元素，接受一个键值作为参数。

注意删除传入的是键，而不是值

1
2
3
unordered_map<int, string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
map.erase(2);

4.unordered_map::size(): 返回 unordered_map 中元素的数量。

1
2
unordered_map<int, string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
cout << "Size of map: " << map.size() << endl;

5.unordered_map::empty(): 返回 unordered_map 是否为空。

1
2
3
4
unordered_map<int, string> map;
if (map.empty()) {
    cout << "Map is empty" << endl;
}

6.unordered_map::clear(): 删除 unordered_map 中的所有元素。

1
2
unordered_map<int, string> map = {{1, "one"}, {2, "two"}, {3, "three"}};
map.clear();

C++常用算法函数

①、sort();【具有和快排一样的速度】 时间复杂度O (n*logn)

1
2
3
4
int a[5] = {4,2,1,3,5};
vector<int> b(a,a+5);
sort(a,a+5);//搭配数组  从小到大排序
sort(b.begin(),b.end());
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int cmp(int a, int b)
{
  return a > b; 
  //蚂蚁感冒的正负数绝对值 return abs(a) < abs(b); 
}
int main () {
    int a[5] = {4,2,1,3,5};
    vector<int> b(a,a+5);
    sort(a,a+5);//搭配数组  从小到大排序
    sort(b.begin(),b.end());//搭配容器     //从小到大
    for (int i = 0; i < 5; i ++) {
        cout << a[i] << " ";
    }
    cout << endl;
    sort(b.begin(),b.end(),cmp); //从大到小
for (auto x:b) {
    cout << x << " ";
}
return 0;
}

②__gcd 最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    int k=__gcd(n,m);//最大公约数
    printf("%d ",k);
    printf("%d", n * m / k); //最小公倍数
    return 0;
}

③max()、min()、abs()比较数字

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << max(a, b) << endl;
    cout << min(a, b) << endl;
    cout << abs(a - b) << endl;
    return 0;
}

扩展到比较容器的话：

max_element()、min_element()比较容器（数组、字符串等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// min_element/max_element example
#include <iostream>     // std::cout
#include <algorithm>    // std::min_element, std::max_element

bool myfn(int i, int j) { return i<j; }

struct myclass {
  bool operator() (int i,int j) { return i<j; }
} myobj;

int main () {
  int myints[] = {3,7,2,5,6,4,9};

  // using default comparison:
  std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';
  std::cout << "The largest element is "  << *std::max_element(myints,myints+7) << '\n';

  // using function myfn as comp:
  std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myfn) << '\n';C++
  std::cout << "The largest element is "  << *std::max_element(myints,myints+7,myfn) << '\n';

  // using object myobj as comp:
  std::cout << "The smallest element is " << *std::min_element(myints,myints+7,myobj) << '\n';
  std::cout << "The largest element is "  << *std::max_element(myints,myints+7,myobj) << '\n';

  return 0;
}

注意，min_element和max_element要加星号*，因为iterator迭代器，就加上就行了 下面是比较动态数组伪代码

1
2
3
4
5
std::vector<int>v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
std::cout << *max_element(v.begin(), v.end()) << std::endl;

④swap

1
swap(a,b);//交换a和b

⑤lower_bound()与upper_bound() [二分查找]

第一个大于等于x的数的地址

第一个大于x的数的地址

⑥reverse 【倒置】

1
2
ector<int> v={1,2,3,4,5};
reverse(v.begin(),v.end());//v的值为5，4，3，2，1  倒置

⑦find

1
2
3
//在a中的从a.begin()（包括它）到a.end()（不包括它）的元素中查找10，
//若存在返回其在向量中的位置
  find(a.begin(),a.end(),10);

⑧、erase【删除】

1
2
3
4
//从c中删除迭代器p指定的元素，p必须指向c中的一个真实元素，不能等于c.end()
c.erase(p)
//从c中删除迭代器对b和e所表示的范围中的元素，返回e
c.erase(b,e)

持续输入：

1
while (cin >> a >> b){}

快读：

1
2
3
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

或者

1
2
3
4
5
6
7
8
9
inline int read()//快读
{
    int x=0,f=0;
    char ch=getchar();
    while(ch>'9'||ch<'0'){f|=(ch=='-');ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?-x:x;
}

1
2
3
4
5
6
7
8
9
inline void write(int x)
{
    char f[200];
    int cnt=0,tmp=x>0?x:-x;
    if(x<0)putchar('-');
    while(tmp>0)f[cnt++]=tmp%10+'0',tmp/=10;
    while(cnt>0)putchar(f[--cnt]);
}

⑤exit(0)

直接中断程序

⑥无穷大

0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即109数量级

⑦ next_permutation （全排列）

作用： 将当前排列更改为全排列中的下一个排列。

  1. atoi(char);把字符串（字符char）转换成整型数的一个函数
1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <stdlib.h>
int main ()
{
    int data;
    data=atoi("123");
    printf("%d\n",data);
    return 0;
}

容器填充函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fill(first,last,value)将区间first到last区间全部初始为value

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> v(8);
    fill(v.begin(),v.end(),1);
    for(int i=0; i<v.size(); i++)
        cout<<v[i]<<" ";
    cout<<endl;
    return 0;
}

查找函数 find(first,last,value)查找first到last区间第一个值为value元素的位置，返回一个迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int num[]= {1,2,3,4,5};
    int *p;
    p=find(num,num+5,3);
    if(p==num+5)
        cout<<"Not found!"<<endl;
    else
        cout<<*p<<endl;
    return 0;
}

还是想再提一嘴这个auto的遍历

1
2
3
4
5
vector<int> line={1,2,3,4,5,6,7,8,9};
//定义一个vector
for (auto lin : line) {
    cout << lin;
  }
1
2
3
4
5
6
7
8
map<int, string> mp;
    mp.insert(pair<int,string>(2,"hello"));
    mp.insert(pair<int,string>(1,"miaomiaomiao"));
    mp.insert(pair<int,string>(3,"world"));
    
    for(auto &p : mp)
	    cout << p.first << endl; 
    return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(){
	Solution Solution;
	int num; num = 10;
	set<int> int_set;
	while (num--){
		int_set.insert(num);
	}
	for (int idx = 0; idx < 15; idx++){
		int_set.insert(idx);
	}
	
	for (auto item : int_set){
		cout << item << " ";
	}
	int end; cin >> end;
	return 0;
}
// 输出 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14