【学习笔记】C++ 标准模板库 2 - 函数篇

零、前言

就这篇啊,现在是 2022/1/6 00:54,我在写这句话。

本来说函数篇应该去年就写完了,但是我老鸽子了,到今年才开始写。

参考资料:

  1. cppreference
  2. 百度百科
  3. 必应词典

在这里表示感谢。

行吧,正片开始。

一、sort 和 stable_sort

所在头文件:<algorithm>

1. 是什么

看这个名字就知道是干什么用的。

sort
US:[sɔrt];UK:[sɔː(r)t]
n. 排序;分类;种类;类别
v. 整理;把……分类;妥善处理;安排妥当

排序昂,排序。

关于这个东西的原理,好家伙我也不知道,笑死根本看不懂,感兴趣的直接搜吧。

sortstable_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))\), where N = 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 可以不写。

主要是这个 beginend,是左闭右开的,这个需要注意。

二、lower_bound 和 upper_bound

所在头文件:<algorithm>

1. 是什么

这两个东西要一起说。

lower_boundupper_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 可以不写当且仅当AB 的数据类型相同。

返回当中满足最大 / 最小的那一个。

四、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

我是真的不想写了。

上一篇:前端3+1(Day2)


下一篇:用户注册功能实现