【学习笔记】C++ 标准模板库 2 - 函数篇
2022/1/6 9:34:09
本文主要是介绍【学习笔记】C++ 标准模板库 2 - 函数篇,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
零、前言
就这篇啊,现在是 2022/1/6 00:54,我在写这句话。
本来说函数篇应该去年就写完了,但是我老鸽子了,到今年才开始写。
参考资料:
- cppreference
- 百度百科
- 必应词典
在这里表示感谢。
行吧,正片开始。
一、sort 和 stable_sort
所在头文件:<algorithm>
。
1. 是什么
看这个名字就知道是干什么用的。
sort
US:[sɔrt];UK:[sɔː(r)t]
n. 排序;分类;种类;类别
v. 整理;把……分类;妥善处理;安排妥当
排序昂,排序。
关于这个东西的原理,好家伙我也不知道,笑死根本看不懂,感兴趣的直接搜吧。
sort
和 stable_sort
的区别在于,stable_sort
可以保证相等元素的相对位置不变。
2. 为什么
废话文学奖,因为可以排序,只要一行。
方便也快,时间复杂度如下:
Complexity
\(O(N\cdot\log(N))\), where
N = std::distance(first, last)
comparisons on average. (until C++11)
\(O(N\cdot\log(N))\), whereN = std::distance(first, last)
comparisons. (since C++11)
来自 cppreference - std::sort。
注意这个“since C++11”,根据 CCF - 关于NOI系列活动中编程语言使用限制的补充说明 第一条:
除题面有明确要求外,C++程序编译默认采用的语言标准为C++14
所以在 NOI 系列比赛中,时间复杂度 \(O(n\log n)\),大家放心使用。
3. 怎么做
这个东西要怎么用呢。
sort(begin, end, compare)
stable_sort(begin, end, compare)
用于一个连续的区间,从 begin
这个地址开始,到 end
这个地址结束。排序方法为 compare
。
compare
这个东西同 priority_queue,这里就不多说了。
或者重载运算符 <
,也在 priority_queue。
对于 C++ 本身有的,或者重载运算符 <
的数据类型,compare
可以不写。
主要是这个 begin
和 end
,是左闭右开的,这个需要注意。
二、lower_bound 和 upper_bound
所在头文件:<algorithm>
。
1. 是什么
这两个东西要一起说。
lower_bound
和 upper_bound
是二分查找,可以在 \(O(n\log n)\) 的时间内查找一个元素。
lower_bound
找大于等于。
upper_bound
找大于。
就是二分查找。
2. 为什么
因为懒,好写,所以用。
3. 怎么做
咋用?
lower_bound(begin, end, value, compare)
upper_bound(begin, end, value, compare)
同 sort - 怎么做,value
是判断相不相等。
对于 C++ 本身有的,或者重载运算符 <
的数据类型,compare
可以不写。
找到了,返回那个数的地址。
没找到,返回 end
。
左闭右开。
三、max 和 min
所在头文件:<algorithm>
。
1. 是什么
如其名。
maximum
US:[ˈmæksɪməm];UK:['mæksɪməm]
n. 最大限度;最大量;最高限度
adj. 最高的;最多的;最大极限的
minimum
US:[ˈmɪnɪməm];UK:['mɪnɪməm]
n. 最低限度;最小值;最少量;极小量
adj. 最低的;最小的;最低限度的
2. 为什么
同前。
3. 怎么做
max(A, B, compare)
min(A, B, compare)
对于 C++ 本身有的,或者重载运算符 <
的数据类型,compare
可以不写当且仅当A
和 B
的数据类型相同。
返回当中满足最大 / 最小的那一个。
四、swap
所在头文件:<algorithm>
。
1. 是什么
swap
US:[swɑp];UK:[swɒp]
v. 换;掉换;交换;替换
n. 〈非正式〉交换;〈非正式〉交换物;【商】互换信贷
交换。
2. 为什么
主要是因为这个东西可以适用于任何类型。
3. 怎么做
swap(A, B)
注意传入的是两个变量,使用引用。
template< class T > void swap( T& a, T& b );(until C++11)
这是 cppreference - swap 上,“until C++11” swap
的声明,后面的也差不多,很明显地看到有 &
引用符号,所以我们只能传入变量而不是变量的地址。
五、nth_element
所在头文件:<algorithm>
。
1. 是什么
可以看到 洛谷 - P1923 【深基9.例4】求第 k 小的数 里面有这样一句话:
请尽量不要使用
nth_element
来写本题,因为本题的重点在于练习分治算法。
很明显地,我们就可以知道,nth_element
用来求第 \(k\) 小的数。
2. 为什么
我们平时所写的分治算法求第 \(k\) 小的数,时间复杂度是平均 \(O(n)\) 的,但是并没有达到 \(O(n)\)。
而 nth_element
达到了 \(O(n)\) 效率更高了。
3. 怎么做
nth_element(begin, nth, end, compare)
注意一下,这里都是地址,左闭右开。
nth_element
会使得 nth
上的元素为应该在的 nth
上的元素,但是除了那个数,其他数的顺序会乱。
对于 C++ 本身有的,或者重载运算符 <
的数据类型,compare
可以不写。
六、find
所在头文件:<algorithm>
。
不想写了。
七、fill
不想写了。
八、is_permutation、next_permutation 和 prev_permutation
真不想写了。
九、is_heap、make_heap、push_heap 和 pop_heap
真的不想写了。
十、random_shuffle
我是真的不想写了。
这篇关于【学习笔记】C++ 标准模板库 2 - 函数篇的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升