wlisontj

wlisontj

关注
发信
关注(28)粉丝(399)

【C++ STL竞赛用】


**C++ STL（Standard Template Library）**标准模板库：包含一些常用数据结构与算法的模板的C++软件库。包含四个组件：算法（Algorithms）、容器（Container）、仿函数（Functors）、迭代器（Iterators）。
示例
  • 算法：sort(a.begin(),a.end())
  • 容器：priority_queue <int > pque
  • 仿函数：greater<int>()
  • 迭代器：vector<int>::iterator it = a.begin()

1. 前言

STL作为一个封装良好、性能合格的C++标准库，灵活正确使用STL可以节省非常多的时间。

2. 常用容器

2.1 vector数组

连续的顺序的存储结构（和数组一样的类别），但是有长度可变的特性

2.1.1 常用方法

构造
vector<int> arr(长度，初值)

vector<int> arr; // 构造int数组
vector<int> arr(100); // 构造长度为100的int数组
vector<int> arr(100,1); // 构造长度为100，所有数据元素初值为1的数组

vector<vetor<int>> mat(100,vector<int>()); // 构造100行，不指定列数的二维数组
vector<vetor<int>> mat(100,vector<int>(666,-1)); // 构造100行，666列的二维数组，初始值为-1

尾插&尾删
push_back(elem)
pop_back()

	vector<int>arr;
	// 尾插元素
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);
	// 尾删元素
	arr.pop_back();

	for (auto i : arr)
	{
		cout << i << endl;
	}

数组长度&数组空判断&改变长度
size()
empty()
resize(新长度,初值)

	vector<int>arr;
	arr.push_back(1);
	arr.push_back(2);
	arr.push_back(3);

	cout << arr.size() << endl;
	if(arr.empty())
	{
		cout<<"arr 为空"<<endl;
	}
	else
	{
		cout<<"arr 非空"<<endl;
	}
	arr.resize(10,2); // 改变长度，变长，初值为2，如果不设定初值默认为0
	arr.resize(1); // 改短，删除尾部多余元素

2.1.2 适用情形

一般情况下vector可以替换掉普通数组，另外vector存放在堆空间中。

2.1.3 注意事项

提前指定长度
如果长度已经确定，那么应当直接在构造函数指定长度，而不是一个一个push_back，这样会减少因为动态分配内存消耗的时常
当心size_t溢出
vector获取长度的方法size()返回值的类型是size_t，通常的OJ平台是32位的编译器，size_t类型的范围是[0,2^32）

vector<int>(65536);
long long a = a.size()*a.size(); // size_t会溢出

2.2 栈stack

#include <stack>
通过二次封装双端队列(deque)容器，实现先进后出(FILO)的数据结构

2.2.1 常用方法

	stack<double> stk;
	stk.push(1.0); // 入栈
	stk.push(1.4);
	stk.push(1.3);
	stk.push(1.2);

	cout << stk.size() << endl; // 查看大小
	cout << stk.top() << endl; // 取栈顶元素
	stk.pop(); // 出栈
	cout << stk.top() << endl;
	cout << stk.empty() << endl; // 判空

2.2.2 注意事项

stack是没法访问内部元素的，所以不要对它进行遍历操作

2.3 队列 queue

#include <queue>
通过二次封装双端队列(deque)容器，实现先进先出(FIFO)的队列数据结构

2.3.1 常用方法

	queue<int> que;

	que.push(1);
	que.push(2);
	que.push(3);
	cout << que.front() << endl; // 队头
	cout << que.back() << endl; // 队尾
	que.pop(); // 出队
	cout << que.front() << endl; // 队头
	cout << que.back() << endl; // 队尾
	que.pop(); // 出队
	cout << que.front() << endl; // 队头
	cout << que.back() << endl; // 队尾

	cout << que.size() << endl; // 队列大小
	cout << que.empty() << endl; // 判空

2.3.2 注意事项

和栈类似，不可访问内部元素

2.4 优先队列 priority_queue

#include <queue>
提供常数时间的最大元素查找，对数时间的插入和提取，底层原理是二叉堆

2.4.1 常用方法

构造
priority_queue<类型，容器，比较器> pque;

  • 类型：要存储的数据类型
  • 存储数据的底层容器，默认为vector<类型>
  • 比较器：比较大小使用的比较器，默认为less<类型>，可自定义

priority_queue<int> pque1; // 存储int的大顶堆
priority_queue<int,vector<int>,greater<int>> pque2; // 存储int的小顶堆

#include <iostream>
#include <queue>
using namespace std;

class Girl
{
public:
	Girl(int age)
	{
		m_age = age;
	}
	int m_age;
};

// 仿函数
class my_greater
{
public:
	bool operator()(const Girl& g1, const Girl& g2)
	{
		//return g1.m_age > g2.m_age; // 优先队列为小顶堆
		return g1.m_age <  g2.m_age; // 为大顶堆
	}
};


int main(void)
{
	priority_queue<int> pque; // 大顶堆，top取的是最大值

	priority_queue<int,vector<int>,greater<int>> pque2; // 小顶堆，top取的是最小值

	pque.push(1); // 入堆
	cout << pque.top() << endl; // 堆顶
	pque2.push(1); // 入堆
	cout << pque2.top() << endl; // 堆顶

	pque.push(3);
	cout << pque.top() << endl;
	pque2.push(3);
	cout << pque2.top() << endl;

	pque.push(2);
	cout << pque.top() << endl;
	pque2.push(2);
	cout << pque2.top() << endl;

	pque.push(4);
	cout << pque.top() << endl;
	pque2.push(4);
	cout << pque2.top() << endl;



	pque.pop(); // 堆顶出堆
	cout << pque.top() << endl;
	pque.pop(); // 堆顶出堆
	cout << pque.top() << endl;
	pque.pop(); // 堆顶出堆
	cout << pque.top() << endl;

	priority_queue<Girl, vector<Girl>, my_greater> pq3; // 自定义数据类型
	Girl g1(1);
	Girl g2(5);
	Girl g3(8);
	Girl g4(3);
	Girl g5(2);

	pq3.push(g1);
	cout << pq3.top().m_age << endl;
	pq3.push(g2);
	cout << pq3.top().m_age << endl;
	pq3.push(g3);
	cout << pq3.top().m_age << endl;
	pq3.push(g4);
	cout << pq3.top().m_age << endl;
	pq3.push(g5);
	cout << pq3.top().m_age << endl;

	return 0;
}

2.4.2 适用情形

持续维护元素的有序性：每次向队列插入大小不定的元素，或者每次从队列取最大/最小的元素

2.4.3 注意事项

  • 仅堆顶可读
  • 只可访问堆顶，其他元素都无法读取到
  • 堆中的所有元素是不可修改的

2.5 集合set

#include <set>
提供对数时间的插入、删除、查找的数据结构。底层原理是红黑树

2.5.1 常用方法

构造
set<类型，比较器>st

  • 类型：要存储的数据类型
  • 比较器：比较大小使用的比较器，默认为less<类型>，可自定义

遍历
可使用迭代器进行遍历

其他

	set<int> st;

	st.insert(1);// 插入
	st.insert(2); 
	st.insert(2);
	st.insert(0);
	st.insert(3);

	st.erase(2); // 删除

	if (st.find(1) != st.end()) // find查找元素
	{
		cout << "找到元素" << endl;
	}
	cout << st.count(2) << endl; // 查找元素的个数

	for (auto &elem:st)
	{
		cout << elem << endl;
	}
	cout << st.size() << endl; // set大小
	st.clear(); // 清空
	cout << st.empty() << endl; // 判断是否为空

2.5.2 适用情形

  • 元素去重： [ 1 , 1 , 3 , 2 , 4 , 4 ] → [ 1 , 2 , 3 , 4 ] [1,1,3,2,4,4]\rightarrow[1,2,3,4] [1,1,3,2,4,4]→[1,2,3,4]
  • 顺序维护： [ 1 , 5 , 3 , 7 , 9 ] → [ 1 , 3 , 5 , 7 , 9 ] [1,5,3,7,9]\rightarrow[1,3,5,7,9] [1,5,3,7,9]→[1,3,5,7,9]
  • 元素是否出现过

2.5.3 注意事项

不存在下标
set虽然可以遍历，但是只能使用迭代器进行遍历，不存在下标这一概念
元素只读
set的迭代器取到的元素是只读的，不可修改它的值
不可用迭代器计算下标
set的迭代器不能向vector一样相减得到下标

2.6 映射map

#include<map>
提供对数时间的有序键值对结构。底层原理是红黑树

2.6.1 常用方法

构造
map<键类型，值类型，比较器> mp

  • 键类型：要存储键的数据类型
  • 值类型：要存储值的数据类型
  • 比较器：键比较大小使用的比较器，默认为less<类型>，可自定义
map<int,int> mp1; // int -> int 映射 按键从小到大
map<int,int,greater<int>> mp2; // int -> int映射 按键从大到小

遍历
可使用迭代器进行遍历

// 遍历
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) // 利用迭代器
{
	cout << it->first << " " << it->second << endl; // first 是键，second是值
}

for (auto& i : mp)
{
	cout << i.first << " " << i.second << endl;
}

其他

2.6.2 适用场景

需要维护映射的场景可以使用：输入若干字符串，统计每种字符串出现的次数(map<string,int>mp;)

2.6.3 注意事项

中括号访问时默认值
如果使用中括号访问map时对应的键不存在，那么会新增这个键，并且值为默认值，因此中括号会影响键的存在。
不可用迭代器计算下 标
map的迭代器不能像vector一样，相减得到下标

2.7 字符串string

#include <string>
存储字符串

2.7.1 注意事项

尾接字符串一定要用+=
string的+=运算符，将会在原字符串末尾尾接字符串。而+了再=赋值，会创建临时对象，再赋值给string，效率低。
substr()的参数为，第一个参数起始子串下标，第二个参数为子串长度，不是终点下标
find()方法的复杂度是o(n2)，不是内置的KMP算法

2.8 二元组pair

#include<utility>
存储二元组（两个元素的一个组合）的数据结构

2.8.1 常用方法

构造
pair<第一个值类型，第二个值类型> pr

  • 第一个值类型：要存储的第一个值的数据类型
  • 第二个值类型：要存储的第二个值的数据类型
    赋值
    老式
pair<int,char> pr = make_pair(1,'a');

c++11，列表构造

pair<int,char> pr = {1,'a'};

3. 迭代器iterator

3.1 迭代器是什么

对于一个vector，我们可以用下标遍历：

for(int i=0;i<a.size();i++)
	cout<<a[i]<<endl;

也可以用迭代器遍历：

for(vector<int>::iterator it=a.begin();it!=a.end();it++)
	cout<<*it<<endl;
  • a.beign()是一个迭代器，指向的是第一个元素
  • a.end()是一个迭代器，指向的是最后一个元素再后面一位
  • 上述迭代器具有自增运算符，自增则迭代器向下一个元素移动
  • 迭代器和指针类似，对它解引用*it，就能取到容器中的值了

3.2 为什么需要迭代器

很多数据结构并不是线性的（例如红黑树），对于非线性数据结构，下标是无意义的。无法使用下标来遍历整个数据结构。
迭代器的作用就是定义某个数据结构的遍历方式，通过迭代器的增减，代表遍历到的位置，通过迭代器便能够成功遍历非线性结构了。

3.3 迭代器用法

对于vector容器，它的功能比较完整，使用它来举例：

  • .beign()，头迭代器
  • .end()，尾迭代器
  • .rbegin()，反向头迭代器
  • .rend()，反向尾迭代器
  • 迭代器+整型：将迭代器向后移动
  • 迭代器-整型：将迭代器向前移动
  • 迭代器++整型：将迭代器向后移动1位
  • 迭代器--整型：将迭代器向前移动1位
  • 迭代器-迭代器：两个迭代器的距离
  • prev(it)：返回it的前一个迭代器
  • next(it)：返回it的后一个迭代器

对于其他的容器，由于其结构特性，上面的功能不一定都有（例如set的迭代器是不能相减求距离的）

3.4 常见问题

.end()和.rend()指向的位置是无意义的值
对于一个长度为10的容器：for(auto it = a.begin();it!=a.end();it++)的.end()是无法访问的
不同容器的迭代器功能可能不一样
迭代器细化有：正向、反向、双向，每个容器的迭代器支持的运算符也可能不同，因此不同容器的迭代器细节很有可能是不一样的。
删除操作需要警惕

vector<int> a{1,2,3,4};
for (auto it = a.begin();it!=a.end();it++)
	if(*it==2||*it==3)
	a.erase(it);
// 之后a={1,3,4}
// 因为在使用迭代器删除2之后，3，4向前移动，迭代器下一次指向就到了4

vector<int> a{1,2,3,4};
for (auto it = a.begin();it!=a.end();it++)
	if(*it==4)
	a.erase(it);
// RE，报错：
// 因为在使用迭代器删除4之后，it指向了a.end()，此时再++越界了

建议：如无必要，别用迭代器操作容器（遍历与访问没关系）

4. 常用算法

4.1 swap

交换元素

template<typename T>
void swap(T& a,T& b);

用法示例

string a = "a", b = "b";
cout << "a:" << a << ",b:" << b << endl;

swap<string>(a, b);
cout << "a:" << a << ",b:" << b << endl;

注意事项
swap的参数是引用

4.2 sort

使用快速排序给一个可迭代对象排序
用法示例

vector<int> arr{ 1,9,5,8,96,37,45,6,2 };
sort(arr.begin(), arr.end(), greater<int>()); // 从小到大排序

for (auto i : arr)
{
	cout << i << endl;
}

默认排序方式是从大到小，如果需要从小到大，传入比较器
如果需要完成特殊情况的排序，则需要传入自定义比较器进去。
比较器的返回值是bool，传参是需要比较的两个元素。记我们定义的比较方法为 ⊗ \otimes ⊗:

  • 如果a ⊗ \otimes ⊗b，即满足比较，则比较器函数应当返回:true
  • 如果a ⊗̸ \not\otimes ⊗b，即不满足比较，则比较器函数应当返回:false
  • 如果a = = == ==b，比较器函数应当返回:false

4.3 lower_bound/upper_bound

在已升序排序的元素中，应用二分查找检索指定元素，返回对应元素迭代器位置，找不到则返回尾迭代器。

  • lower_bound()：寻找 ≥ x \ge{x} ≥x的第一个元素的位置
  • upper_bound()：寻找 > x >x >x的第一个元素的位置
    怎么找 ≤ x \le{x} ≤x或者 < x <x <x的第一个元素呢？
  • > x >x >x的第一个元素的前一个元素，便是 ≤ x \le{x} ≤x的第一个元素
  • ≥ x \ge{x} ≥x的第一个元素的前一个元素，便是 < x <x <x的第一个元素

如何转换成下标？减去头迭代器即可。
用法示例

	vector<int> arr{ 0,1,1,1,8,9,9 };
	int pos_1 = lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 找>=8的第一个元素的位置
	int pos_2 = upper_bound(arr.begin(), arr.end(), 8)-arr.begin(); // 找>8的第一个元素的位置
	cout << pos_1 << endl;
	cout << pos_2 << endl;

4.4 reverse

反转一个可迭代对象的元素顺序

template<class BidirIt>
void reverse(BidirIt First,BidirIt Last);

用法示例

vector<int> arr{ 0,1,1,1,8,9,9 };
reverse(arr.begin() + 2, arr.end());// 从第二位开始反转，结果应该是：0，1，9，9，8，1，1
for (auto i : arr)
{
	cout << i << endl;
}

4.5 max/min

返回最大值 / 最小值的数值
用法示例

// c++
int mx = max(max(1,2),max(3,4)); // 4
int mn = min(min(1,2),min(3,4)); // 1
// c++11之后
int mx = max({1,2,3,4});
int mn = min({1,2,3,4});

4.6 unique

消除数组的重复相邻元素，数组长度不变，但是有效数据缩短，返回的是有效数据位置的尾迭代器
例如： [ 1 , 1 , 4 , 5 , 1 , 4 ] → [ 1 , 4 , 5 , 1 , 4 , ? ] [1,1,4,5,1,4]\rightarrow[1,4,5,1,4,?] [1,1,4,5,1,4]→[1,4,5,1,4,?]， ? ? ?位置为返回的迭代器指向的位置

template<class ForwardIt>
ForwardIt unique(ForwardIt First,ForwardIt Last);

单独使用unique是无法完全消除重复元素的，只能消除相邻重复元素。如果序列有序，那么它就能去重了。
但是它去重后，序列尾部会产生无效数据，为了去掉这些无效数据，我们需要结合erase
例如： [ 1 , 2 , 3 , 4 , 4 , 4 ] → [ 1 , 2 , 3 , 4 , ? ‾ , ? ] [1,2,3,4,4,4]\rightarrow[1,2,3,4,\underline?,?] [1,2,3,4,4,4]→[1,2,3,4,?​,?]

vector<int> arr{ 1,2,1,4,5,4,4 };
// 先排序
sort(arr.begin(), arr.end()); // 降序排列

arr.erase(unique(arr.begin(), arr.end())); // 去重 // 删除无效数据
for (auto i : arr)
{
	cout << i << endl;
}
return 0;

4.7 数学函数

所有函数参数均支持int/long long/float/double/long double

4.8 gcd/lcm

返回最大公因数和最小公倍数
c++17

int x = gcd(8,12); // 4
int y = lcm(8,12); // 24

直接实现gcd/lcm

int gcd(int a,int b)
{
	if(!b)
		return a;
	return gcd(b,a%b);
}
int lcm(int a,int b)
{
	return a/gcd(a,b)*b;
}
04-17 12:28
Powered by LMLPHP ©2024 wlisontj 0.001935