适合初学者模仿的网站,网页设计与制作实训报告书,定制车需要多少钱,桐庐城乡建设局网站声明#xff1a;大佬们~这是Tubishu在追寻stl过程中偶然得到了“颢天”大佬的笔记#xff0c;shushu感觉非常有帮助#x1f525;又颢天佬未曾来过CSDN#xff0c;索性在此传达颢天大佬的功德#x1f9ce; 传送门在此➡️颢天笔记✨✨ C 标准模板库 (STL, Standard Templa… 声明大佬们~这是Tubishu在追寻stl过程中偶然得到了“颢天”大佬的笔记shushu感觉非常有帮助又颢天佬未曾来过CSDN索性在此传达颢天大佬的功德 传送门在此➡️颢天笔记✨✨ C 标准模板库 (STL, Standard Template Library)包含一些常用数据结构与算法的模板的 C 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators). 示例
算法sort(a.begin(), a.end())容器priority_queueint pque仿函数greaterint()迭代器vectorint::iterator it a.begin()
1 前言
STL 作为一个封装良好性能合格的 C 标准库在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间这一点不仅是由于可以直接调用还是因为它封装良好可以让代码的可读性变高解题思路更清晰调试过程 往往 更顺利。
不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此在实际比赛中要权衡 STL 的利弊不过这一点就得靠经验了。
接下来我会分享在算法竞赛中常用的 STL 容器和算法对于函数和迭代器就不着重展开讲了。
2 常用容器
2.1 内容总览
打勾的是本次将会详细讲解的加粗的是算法竞赛中有必要学习的。 顺序容器 array vector deque forward_list list 关联容器 set map multiset multimap 无序关联容器 unordered_set unordered_map unordered_multiset unordered_multimap 容器适配器 stack queue priority_queue flat_set flat_map flat_multiset flat_multimap 字符串 string (basic_stringchar) 对与元组 pair tuple
2.2 向量 vector
#include vector
连续的顺序的储存结构和数组一样的类别但是有长度可变的特性。
2.2.1 常用方法
构造
vector类型 arr(长度, [初值])
时间复杂度 O ( n ) O(n) O(n)
常用的一维和二维数组构造示例高维也是一样的就是会有点长.
vectorint arr; // 构造int数组
vectorint arr(100); // 构造初始长100的int数组
vectorint arr(100, 1); // 构造初始长100的int数组初值为1vectorvectorint mat(100, vectorint ()); // 构造初始100行不指定列数的二维数组
vectorvectorint mat(100, vectorint (666, -1)) // 构造初始100行初始666列的二维数组初值为-1构造二维数组的奇葩写法千万别用
vectorint arr[100]; // 正确构造初始100行不指定列数的二维数组可用于链式前向星存图
vectorint arr[100](100, 1); // 语法错误
vectorint arr(100, 1)[100]; // 语法错误
vectorint arr[100] {{100, 1}, 这里省略98个 ,{100, 1}}; // 正确但奇葩使用列表初始化尾接 尾删
.push_back(元素)在 vector 尾接一个元素数组长度 1 1 1..pop_back()删除 vector 尾部的一个元素数组长度 − 1 -1 −1
时间复杂度均摊 O ( 1 ) O(1) O(1)
// init: arr []
arr.push_back(1);
// after: arr [1]
arr.push_back(2);
// after: arr [1, 2]
arr.pop_back();
// after: arr [1]
arr.pop_back();
// after: arr []中括号运算符
和一般数组一样的作用
时间复杂度 O ( 1 ) O(1) O(1)
获取长度
.size()
获取当前 vector 的长度
时间复杂度 O ( 1 ) O(1) O(1)
for (int i 0; i arr.size(); i)cout a[i] endl;清空
.clear()
清空 vector
时间复杂度 O ( n ) O(n) O(n)
判空
.empty()
如果是空返回 true 反之返回 false.
时间复杂度 O ( 1 ) O(1) O(1)
改变长度
.resize(新长度, [默认值])
修改 vector 的长度
如果是缩短则删除多余的值如果是扩大且指定了默认值则新元素均为默认值**旧元素不变**
时间复杂度 O ( n ) O(n) O(n)
2.2.2 适用情形
一般情况 vector 可以替换掉普通数组除非该题卡常。
有些情况普通数组没法解决 n × m n\times m n×m 的矩阵 1 ≤ n , m ≤ 1 0 6 1\leq n,m\leq 10^6 1≤n,m≤106 且 n × m ≤ 1 0 6 n\times m \leq 10^6 n×m≤106
如果用普通数组 int mat[1000010][1000010]浪费内存会导致 MLE。如果使用 vectorvectorint mat(n 10, vectorint (m 10))完美解决该问题。
另外vector 的数据储存在堆空间中不会爆栈。
2.2.3 注意事项
提前指定长度
如果长度已经确定那么应当直接在构造函数指定长度而不是一个一个 .push_back(). 因为 vector 额外内存耗尽后的重分配是有时间开销的直接指定长度就不会出现重分配了。
// 优化前: 522ms
vectorint a;
for (int i 0; i 1e8; i)a.push_back(i);
// 优化后: 259ms
vectorint a(1e8);
for (int i 0; i a.size(); i)a[i] i;当心 size_t 溢出
vector 获取长度的方法 .size() 返回值类型为 size_t通常 OJ 平台使用的是 32 位编译器有些平台例如 cf 可选 64 位那么该类型范围为 [ 0 , 2 32 ) [0,2^{32}) [0,232).
vectorint a(65536);
long long a a.size() * a.size(); // 直接溢出变成0了2.3 栈 stack
#include stack
通过二次封装双端队列 (deque) 容器实现先进后出的栈数据结构。
2.3.1 常用方法
作用用法示例构造stack类型 stkstackint stk;进栈.push(元素)stk.push(1);出栈.pop()stk.pop();取栈顶.top()int a stk.top();查看大小 / 清空 / 判空略略
2.3.2 适用情形
如果不卡常的话就可以直接用它而不需要手写栈了。
另外vector 也可以当栈用vector 的 .back() 取尾部元素就相当于取栈顶.push_back() 相当于进栈.pop_back() 相当于出栈。
2.3.3 注意事项
不可访问内部元素下面都是错误用法
for (int i 0; i stk.size(); i)cout stk[i] endl;
for (auto ele : stk)cout stk endl;2.4 队列 queue
#include queue
通过二次封装双端队列 (deque) 容器实现先进先出的队列数据结构。
2.4.1 常用方法
作用用法示例构造queue类型 quequeueint que;进队.push(元素)que.push(1);出队.pop()que.pop();取队首.front()int a que.front();取队尾.back()int a que.back();查看大小 / 清空 / 判空略略
2.4.2 适用情形
如果不卡常的话就可以直接用它而不需要手写队列了。
2.4.3 注意事项
不可访问内部元素下面都是错误用法
for (int i 0; i que.size(); i)cout que[i] endl;
for (auto ele : que)cout ele endl;2.5 优先队列 priority_queue
#include queue
提供常数时间的最大元素查找对数时间的插入与提取底层原理是二叉堆。
2.5.1 常用方法
构造
priority_queue类型, 容器, 比较器 pque
类型要储存的数据类型容器储存数据的底层容器默认为 vector类型竞赛中保持默认即可比较器比较大小使用的比较器默认为 less类型可自定义
priority_queueint pque1; // 储存int的大顶堆
priority_queueint, vectorint, greaterint pque2; // 储存int的小顶堆对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。如果想要了解可以查阅 cppreference 中的代码示例。 其他
作用用法示例进堆.push(元素)que.push(1);出堆.pop()que.pop();取堆顶.top()int a que.top();查看大小 / 判空略略
进出队复杂度 O ( log n ) O(\log n) O(logn)取堆顶 O ( 1 ) O(1) O(1).
2.5.2 适用情形
持续维护元素的有序性每次向队列插入大小不定的元素或者每次从队列里取出大小最小/最大的元素元素数量 n n n插入操作数量 k k k.
每次插入后进行快速排序 k ⋅ n log n k\cdot n\log n k⋅nlogn使用优先队列维护 k ⋅ log n k\cdot\log n k⋅logn
2.5.3 注意事项
仅堆顶可读
只可访问堆顶其他元素都无法读取到。下面是错误用法
cout pque[1] endl;所有元素不可写
堆中所有元素是不可修改的。下面是错误用法
pque[1] 2;
pque.top() 1;如果你恰好要修改的是堆顶元素那么是可以完成的
int tp pque.top();
pque.pop();
pque.push(tp 1);2.6 集合 set
#include set
提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。
集合三要素解释setmultisetunordered_set确定性一个元素要么在集合中要么不在✔✔✔互异性一个元素仅可以在集合中出现一次✔❌任意次✔无序性集合中的元素是没有顺序的❌从小到大❌从小到大✔
2.6.1 常用方法
构造
set类型, 比较器 st
类型要储存的数据类型比较器比较大小使用的比较器默认为 less类型可自定义
setint st1; // 储存int的集合从小到大
setint, greaterint st2; // 储存int的集合从大到小对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。 遍历
可使用迭代器进行遍历
for (setint::iterator it st.begin(); it ! st.end(); it)cout *it endl;基于范围的循环C 11
for (auto ele : st)cout ele endl;其他
作用用法示例插入元素.insert(元素)st.insert(1);删除元素.erase(元素)st.erase(2);查找元素.find(元素)auto it st.find(1);判断元素是否存在.count(元素)st.count(3);查看大小 / 清空 / 判空略略
增删查时间复杂度均为 O ( log n ) O(\log n) O(logn)
2.6.2 适用情形
元素去重 [ 1 , 1 , 3 , 2 , 4 , 4 ] → [ 1 , 2 , 3 , 4 ] [1,1,3,2,4,4]\to[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]\to[1,3,5,7,9] [1,5,3,7,9]→[1,3,5,7,9]元素是否出现过元素大小 [ − 1 0 18 , 1 0 18 ] [-10^{18},10^{18}] [−1018,1018]元素数量 1 0 6 10^6 106vis 数组无法实现通过 set 可以完成。
2.6.3 注意事项
不存在下标索引
set 虽说可遍历但仅可使用迭代器进行遍历它不存在下标这一概念无法通过下标访问到数据。下面是错误用法
cout st[0] endl;元素只读
set 的迭代器取到的元素是只读的因为是 const 迭代器不可修改其值。如果要改需要先 erase 再 insert. 下面是错误用法
cout *st.begin() endl; // 正确。可读。
*st.begin() 1; // 错误不可写不可用迭代器计算下标
set 的迭代器不能像 vector 一样相减得到下标。下面是错误用法
auto it st.find(2); // 正确返回2所在位置的迭代器。
int idx it - st.begin(); // 错误不可相减得到下标。2.7 映射 map
#include map
提供对数时间的有序键值对结构。底层原理是红黑树。
映射 1 → 2 2 → 2 3 → 1 4 → 5 ⋮ \begin{matrix} 1\to2\\ 2\to2\\ 3\to1\\ 4\to5\\ \vdots \end{matrix} 1234→→→→⋮2215
性质解释mapmultimapunordered_map互异性一个键仅可以在映射中出现一次✔❌任意次✔无序性键是没有顺序的❌从小到大❌从小到大✔
2.7.1 常用方法
构造
map键类型, 值类型, 比较器 mp
键类型要储存键的数据类型值类型要储存值的数据类型比较器键比较大小使用的比较器默认为 less类型可自定义
mapint, int mp1; // int-int 的映射键从小到大
mapint, int, greaterint st2; // int-int 的映射键从大到小对于需要自定义比较器的情况涉及一些初学时容易看迷糊的语法重载小括号运算符 / lambda 表达式在此就不展开讲了。 遍历
可使用迭代器进行遍历
for (mapint, int::iterator it mp.begin(); it ! mp.end(); it)cout it-first it-second endl;基于范围的循环C 11
for (auto pr : mp)cout pr.first pr.second endl;结构化绑定 基于范围的循环C17
for (auto [key, val] : mp)cout key val endl;其他
作用用法示例增 / 改 / 查元素中括号mp[1] 2;查元素返回迭代器.find(元素)auto it mp.find(1);删除元素.erase(元素)mp.erase(2);判断元素是否存在.count(元素)mp.count(3);查看大小 / 清空 / 判空略略
增删改查时间复杂度均为 O ( log n ) O(\log n) O(logn)
2.7.2 适用情形
需要维护映射的场景可以使用输入若干字符串统计每种字符串的出现次数。(mapstring, int mp)
2.7.3 注意事项
中括号访问时默认值
如果使用中括号访问 map 时对应的键不存在那么会新增这个键并且值为默认值因此中括号会影响键的存在性。
mapchar, int mp;
cout mp.count(a) endl; // 0
mp[a]; // 即使什么都没做此时mp[a]0已经插入了
cout mp.count(a) endl; // 1
cout mp[a] endl; // 0不可用迭代器计算下标
map 的迭代器不能像 vector 一样相减得到下标。下面是错误用法
auto it mp.find(a); // 正确返回2所在位置的迭代器。
int idx it - mp.begin(); // 错误不可相减得到下标。2.8 字符串 string
#include string
顾名思义就是储存字符串的。
2.8.1 常用方法
构造
构造函数string(长度, 初值)
string s1; // 构造字符串为空
string s2 awa!; // 构造字符串并赋值awa!
string s3(10, 6); // 构造字符串通过构造函数构造为6666666666输入输出
C
string s;
cin s;
cout s;C
string s;
char buf[100];
scanf(%s, buf);
s buf;
printf(%s, s.c_str());其他
作用用法示例修改、查询指定下标字符[]s[1] a;是否相同if (s1 s2) ...字符串连接string s s1 s2;尾接字符串s awa;取子串.substr(起始下标, 子串长度)string sub s.substr(2, 10);查找字符串.find(字符串, 起始下标)int pos s.find(awa);
数值与字符串互转C11
源目的函数int / long long / float / double / long doublestringto_string()stringintstoi()stringlong longstoll()stringfloatstof()stringdoublestod()stringlong doublestold()
2.8.2 适用情形
非常好用建议直接把字符数组扔了赶快投入 string 的怀抱。
2.8.3 注意事项
尾接字符串一定要用
string 的 运算符将会在原字符串原地尾接字符串。而 了再 赋值会先生成一个临时变量在复制给 string.
通常字符串长度可以很长如果使用 字符串很容易就 TLE 了。
// 优化前: 15139ms
string s;
for (int i 0; i 5e5; i)s s a;// 优化后: 1ms (计时器显示0)
string s;
for (int i 0; i 5e5; i)s a;.substr() 方法的奇葩参数
一定要注意C string 的取子串的第一个参数是子串起点下标第二个参数是子串长度。
第二个参数不是子串终点不是子串终点要与 java 等其他语言区分开来。
.find() 方法的复杂度
该方法实现为暴力实现时间复杂度为 O ( n 2 ) O(n^2) O(n2).
不要幻想 STL 内置了个 O ( n ) O(n) O(n) 的 KMP 算法
2.9 二元组 pair
#include utility
顾名思义就是储存二元组的。
2.9.1 常用方法
构造
pair第一个值类型, 第二个值类型 pr
第一个值类型要储存的第一个值的数据类型第二个值类型要储存的第二个值的数据类型
pairint, int p1;
pairint, long long p2;
pairchar, int p3;
// ...赋值
老式
pairint, char pr make_pair(1, a);列表构造 C11
pairint, char pr {1, a};取值
直接取值
取第一个值.first取第二个值.second
pairint, char pr {1, a};
int awa pr.first;
char bwb pr.second;结构化绑定 C17
pairint, char pr {1, a};
auto [awa, bwb] pr;判同
直接用 运算符
pairint, int p1 {1, 2};
pairint, int p2 {1, 3};
if (p1 p2) { ... } // false2.9.2 适用场景
所有需要二元组的场景均可使用效率和自己定义结构体差不多。
2.9.3 注意事项
无
3 迭代器简介
3.1 迭代器是什么
不搞抽象直接举例。
对于一个 vector我们可以用下标遍历
for (int i 0; i a.size(); i)cout a[i] endl;我们同时也可以用迭代器来遍历
for (vectorint::iterator it a.begin(); it ! a.end(); it)cout *it endl;a.begin() 是一个迭代器指向的是第一个元素a.end() 是一个迭代器指向的是最后一个元素再后面一位上述迭代器具有自增运算符自增则迭代器向下一个元素移动迭代器与指针相似如果对它使用解引用运算符即 *it就能取到对应值了
3.2 为何需要迭代器
很多数据结构并不是线性的例如红黑树对于非线性数据结构下标是无意义的。无法使用下标来遍历整个数据结构。
迭代器的作用就是定义某个数据结构的遍历方式通过迭代器的增减代表遍历到的位置通过迭代器便能成功遍历非线性结构了。
例如set 的实现是红黑树我们是没法用下标来访问元素的。但是通过迭代器我们就能遍历 set 中的元素了
for (setint::iterator it st.begin(); it ! st.end(); it)cout *it endl;3.3 迭代器用法
对于 vector 容器它的迭代器功能比较完整以它举例
.begin()头迭代器.end()尾迭代器.rbegin()反向头迭代器.rend()反向尾迭代器迭代器 整型将迭代器向后移动迭代器 - 整型将迭代器向前移动迭代器 将迭代器向后移动 1 位迭代器 --将迭代器向前移动 1 位迭代器 - 迭代器两个迭代器的距离prev(it)返回 it 的前一个迭代器next(it)返回 it 的后一个迭代器
对于其他容器由于其结构特性上面的功能不一定都有例如 set 的迭代器是不能相减求距离的
3.4 常见问题
.end() 和 .rend() 指向的位置是无意义的值
对于一个长度为 10 的数组for (int i 0; i 10; i)第 10 位是不可访问的
对于一个长度为 10 的容器for (auto it a.begin(); it ! a.end(); it).end 是不可访问的
不同容器的迭代器功能可能不一样
迭代器细化的话有正向、反向、双向每个容器的迭代器支持的运算符也可能不同因此不同容器的迭代器细节很有可能是不一样的。
删除操作时需要警惕
为什么 3 没删掉
vectorint 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]为啥 RE 了
vectorint a{1, 2, 3, 4};
for (auto it a.begin(); it ! a.end(); it)if (*it 4)a.erase(it);建议如无必要别用迭代器操作容器。遍历与访问没关系 4 常用算法
4.1 内容总览
打勾的是本次将会详细讲解的其他的是算法竞赛中建议学习的不在下表列出的在比赛中基本用不到。
很多函数的功能很简单自己都能快速写出来但是使用函数可以让代码可读性变得更高这在比赛中是至关紧要的 算法库 Algorithm count() find() fill() swap() reverse() shuffle() C11 unique() sort() lower_bound() / upper_bound() max() / min() max_element() / min_element() prev_permutation() / next_permutation() 数学函数 cmath abs() exp() log() / log10() / log2() pow() sqrt() sin() / cos() / tan() asin() / acos() / atan() sinh() / cosh() / tanh() asinh() / acosh() / atanh() C11 ceil() / floor() round() C11 数值算法 numeric iota() C11 accumulate() gcd() C17 lcm() C17 伪随机数生成 random mt19937 random_device()
4.2 swap()
交换两个变量的值
用法示例
template class T
void swap( T a, T b );int a 0, b 1;
swap(a, b);
// now a 1, b 0int arr[10] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
swap(arr[4], arr[6]);
// now arr {0, 1, 2, 3, 6, 5, 4, 7, 8, 9}注意事项
这个 swap 参数是引用的不需要像 C 语言一样取地址。
4.3 sort()
使用快速排序给一个可迭代对象排序
用法示例
template class RandomIt, class Compare
void sort( RandomIt first, RandomIt last, Compare comp );默认排序从小到大
vectorint arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end());
// arr [0, 1, 1, 1, 8, 9, 9]如果要从大到小则需要传比较器进去。
vectorint arr{1, 9, 1, 9, 8, 1, 0};
sort(arr.begin(), arr.end(), greaterint());
// arr [9, 9, 8, 1, 1, 1, 0]如果需要完成特殊比较则需要手写比较器。
比较器函数返回值是 bool 类型传参是需要比较的两个元素。记我们定义的该比较操作为 ⋆ \star ⋆
若 a ⋆ b a\star b a⋆b则比较器函数应当返回 true若 a ⋆̸ b a\not\star b a⋆b则比较器函数应当返回 false
**注意**如果 a b ab ab比较器函数必须返回 false
bool cmp(pairint, int a, pairint, int b)
{if (a.second ! b.second)return a.second b.second;return a.first b.first;
}int main()
{vectorpairint, int arr{{1, 9}, {2, 9}, {8, 1}, {0, 0}};sort(arr.begin(), arr.end(), cmp);// arr [(0, 0), (8, 1), (2, 9), (1, 9)]
}4.4 lower_bound() / upper_bound()
在已升序排序的元素中应用二分查找检索指定元素返回对应元素迭代器位置。找不到则返回尾迭代器。
lower_bound(): 寻找 ≥ x \geq x ≥x 的第一个元素的位置upper_bound(): 寻找 x x x 的第一个元素的位置
怎么找 ≤ x \leq x ≤x / x x x 的第一个元素呢 x x x 的第一个元素的前一个元素如果有便是 ≤ x \leq x ≤x 的第一个元素 ≥ x \geq x ≥x 的第一个元素的前一个元素如果有便是 x x x 的第一个元素
返回的是迭代器如何转成下标索引呢减去头迭代器即可。
用法示例
template class ForwardIt, class T
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T value );vectorint arr{0, 1, 1, 1, 8, 9, 9};
vectorint::iterator it lower_bound(arr.begin(), arr.end(), 7);
int idx it - arr.begin();
// idx 4我们通常写成一行
vectorint arr{0, 1, 1, 1, 8, 9, 9};
idx lower_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx lower_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 4
idx upper_bound(arr.begin(), arr.end(), 7) - arr.begin(); // 4
idx upper_bound(arr.begin(), arr.end(), 8) - arr.begin(); // 54.5 reverse()
反转一个可迭代对象的元素顺序
用法示例
template class BidirIt
void reverse( BidirIt first, BidirIt last );vectorint arr(10);
iota(arr.begin(), arr.end(), 1);
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverse(arr.begin(), arr.end());
// 10, 9, 8, 7, 6, 5, 4, 3, 2, 14.6 max() / min()
返回最大值 / 最小值的数值
用法示例
int mx max(1, 2); // 2
int mn min(1, 2); // 1在 C11 之后可以使用列表构造语法传入一个列表这样就能一次性给多个元素找最大值而不用套娃了
// Before C11
int mx max(max(1, 2), max(3, 4)); // 4
int mn min(min(1, 2), min(3, 4)); // 1// After C11
int mx max({1, 2, 3, 4}); // 4
int mn min({1, 2, 3, 4}); // 14.7 unique()
消除数组的重复相邻元素数组长度不变但是有效数据缩短返回的是有效数据位置的结尾迭代器。
例如 [ 1 , 1 , 4 , 5 , 1 , 4 ] → [ 1 , 4 , 5 , 1 , 4 , ? ‾ ] [1,1,4,5,1,4]\to[1,4,5,1,4,\underline?] [1,1,4,5,1,4]→[1,4,5,1,4,?]下划线位置为返回的迭代器指向。
template class ForwardIt
ForwardIt unique( ForwardIt first, ForwardIt last );用法示例
单独使用 unique 并不能达成去重效果因为它只消除相邻的重复元素。但是如果序列有序那么它就能去重了。
但是它去重后序列尾部会产生一些无效数据 [ 1 , 1 , 2 , 4 , 4 , 4 , 5 ] → [ 1 , 2 , 4 , 5 , ? ‾ , ? , ? ] [1,1,2,4,4,4,5]\to[1,2,4,5,\underline?,?,?] [1,1,2,4,4,4,5]→[1,2,4,5,?,?,?]为了删掉这些无效数据我们需要结合 erase.
最终给 vector 去重的写法便是
vectorint arr{1, 2, 1, 4, 5, 4, 4};
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());4.8 数学函数
所有函数参数均支持 int / long long / float / double / long double
公式示例 f ( x ) ∣ x ∣ f(x)\lvert x\rvert f(x)∣x∣abs(-1.0) f ( x ) e x f(x)e^x f(x)exexp(2) f ( x ) ln x f(x)\ln x f(x)lnxlog(3) f ( x , y ) x y f(x,y)x^y f(x,y)xypow(2, 3) f ( x ) x f(x)\sqrt x f(x)x sqrt(2) f ( x ) ⌈ x ⌉ f(x)\lceil x\rceil f(x)⌈x⌉ceil(2.1) f ( x ) ⌊ x ⌋ f(x)\lfloor x\rfloor f(x)⌊x⌋floor(2.1) f ( x ) x f(x)\leftx\right f(x)⟨x⟩rount(2.1)
注意事项
由于浮点误差有些的数学函数的行为可能与预期不符导致 WA。如果你的操作数都是整型那么用下面的写法会更稳妥。 原文地址https://codeforces.com/blog/entry/107717 ⌊ a b ⌋ \lfloor\frac{a}{b}\rfloor ⌊ba⌋ 别用floor(1.0 * a / b)要用a / b ⌈ a b ⌉ \lceil\frac{a}{b}\rceil ⌈ba⌉ 别用ceil(1.0 * a / b)要用(a b - 1) / b ⌈ a b ⌉ ⌊ a b − 1 b ⌋ \lceil\frac{a}{b}\rceil\lfloor\frac{ab-1}{b}\rfloor ⌈ba⌉⌊bab−1⌋ ⌊ a ⌋ \lfloor\sqrt a\rfloor ⌊a ⌋ 别用(int) sqrt(a)要用二分查找 https://io.zouht.com/7.html a b a^b ab 别用pow(a, b)要用快速幂 https://io.zouht.com/18.html ⌊ log 2 a ⌋ \lfloor\log_2 a\rfloor ⌊log2a⌋ 别用log2(a)要用__lg 不规范但是这是竞赛/ bit_widthC20 可用
4.9 gcd() / lcm()
C17返回最大公因数 / 最小公倍数
int x gcd(8, 12); // 4
int y lcm(8, 12); // 24如果不是 C17但是是 GNU 编译器g那么可以用内置函数 __gcd().
当然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;
}佬~都到这里了点赞关注收藏评论一下呗你的支持永远是shuhsu最大的动力 祝大佬们心想事成码不报错
