- update at 2022-08-27 ‘重写了部分代码实例,以及补充了部分内容’
- update at 2022-04-25 ‘关于auto和bool的一个问题’
- update at 2022-05-21 ‘accumulate返回值类型的细节’
- update at 2022-05-23 ‘增加了bit部分的内容’
内容未完,之后写代码过程中见到或者想到的好的技巧都会逐步添加。
使用的编译指令:
|
|
g++
版本:
|
|
尽量只使用宏:
|
|
参考
常见容器
string
array
-vector
-deque
map
-multimap
-unordered_map
set
-multiset
-unordered_set
stack
-queue
-prority_queue
tuple
bitset
支持顺序访问的容器可以用下面的办法快速枚举:
|
|
对于结构体,一定程度上可以使用tuple
代替。
两者在访问时都可以使用auto
对其结构化绑定声明,语法大概如下:
|
|
上面两种可以协同使用,遍历结构体vector<tuple<...>>
但是,如果仅仅是需要结构化绑定,可以使用tie()
:
|
|
可以见,这种写法并非变量声明,而是赋值。
关于Range-based for loop
的一些问题
- 使用
for (auto val : v)
确实会发生拷贝,但并不是说v
中元素就一定不会改变
|
|
不过,会出现上面情况的应该也就是vector<bool>
这个奇葩了。显然auto
判断类型为_Bit_reference
,通过下面代码可以验证:
|
|
同时,如果你使用了auto &val : v
,那么你将面临下面的报错:
- 如果想用
auto
自动识别变量类型的引用,但又不想出错,你应当使用auto &&val : v
来代替。 - 使用
const auto &val : v
来彻底避免内存拷贝以及保证元素不被修改。
迭代器 与 all()
宏
|
|
在c++
的STL中,更常用的是迭代器,而非下标(指针),这与纯c
写法有较大区别。
begin()
,end()
作为容器的起始迭代器和末尾的迭代器
rbegin()
,rend()
逆向的迭代器
用于遍历的函数如下(虽然有许多容器的迭代器重载了++
和--
,可以直接像下标一样处理,但还是推荐):
|
|
定义这个宏的原因是:使用算法库的函数经常需要填写迭代器范围。
下面将介绍一些比较常见的函数(如果平时码风比较偏c
语言,可能就不太常见)
算法库
此处仅记录一些本人常用的部分,<algorithm>
内容十分丰富,并且还在随版本更新,惟愿本文能抛砖引玉,引起读者的兴趣。
排序 std::sort
与 lambda
表达式
std::sort()
,应该是一个很常见的函数,用来排序数组的时,一些偏向c
的写法会使用头尾指针来确定范围,再写外部函数确定排序规则。
但是,在使用如vector
等可以排序的容器时,我们一般会动态开空间,所以此时待排序的范围就是全部元素。
|
|
与std::sort
比较相似的还有std::stable_sort
,后者是能够保证,相同大小的元素在排序前后的相对位置不变。
- 检验数组是否有序:
std::is_sorted()
关于 lambda
表达式 (c++11
)
在sort
函数中,第三个参数可以为我们定义的排序规则,如果不使用lambda
表达式,我们往往会把它们写在外面,然后填写函数指针。
lambda
表达式,受篇幅限制这里无法展开,建议访问cpp手册 - lambda表达式。基础语法如下:
|
|
放在sort
中使用的实例:
|
|
更多的,如果关联使用<functional>
,可以将外部函数写在主函数内。
- 这里还有一个问题,那就是如何写递归函数?
使用 function
类是一种解决办法,如下面的dfs
代码:
|
|
如果不按照function
类来声明该函数,[ captures ]
无法获知自己的存在,所以一个可行的方案就是,在传值的时候将自己传入。
|
|
搜索相关
我们知道,对于有序容器,我们可以利用其单调性来进行二分。
进行了上面的排序操作,我们的数组(暂且这么称呼)已经变得有序,如何利用STL
中写好的二分函数呢?
对于一般容器而言,二分函数的写法比较统一(以vector<int> a
为例好了):
|
|
对于map
,set
,这类使用红黑树或者其他非线性数据结构实现的容器,如果你直接按照上面的写法二分,那么时间复杂度将直接退化到$\mathcal{O}(n)$。
正确的使用方法是直接调用其内部封装好的二分函数:
|
|
更一般的情况是,我们只需要数组中最值。
|
|
如果你需要知道是一个数组的第K
大的数(比如中位数),该怎么办呢,直接排序吗?
在某些时候,我们可能连$\mathcal{O}(n\log n)$的算法也无法接受,此时可以使用均摊复杂度为$\mathcal{O}(n)$的函数nth_element()
|
|
可以见,该函数并非排序,而是将前K
小的数放在最前面的K
个位置,且令第K
位上为第K
大。
如果仅仅需要一般的查找,使用find
或者find_if
即可,后者搭配lambda
表达式,可以按需搜索。使用时请注意复杂度,对于一般容器,该函数使用的是顺序遍历,时间复杂度为$\mathcal{O}(n)$。
此处补充一点,查找元素无果,返回的迭代器为end()
。特别的,string
中find
失败得到的是string::npos
。
计算相关
count
和count_if
统计元素个数时可用前者 count(all(a), val)
,如果需要按满足条件来统计,使用后者再搭配上lambda
表达式即可。
值得说明的一点是,map
和set
中的find
和count
函数的复杂度是$\mathcal{O}(\log n)$,可以放心使用。
all_of
any_of
none_of
顾名思义,对于一个范围,判断满足条件(一般用lambda
表达式写)的集合与全集的关系。
partial_sum
前缀和函数,partial_sum(all(a), begin(b))
,此处的 b
需要先开够空间。
类似的还有前向差分函数。
accumulate
比较常见的要求是对数组求和,我们直接利用accumulate(all(a), 0)
即可,但是该函数还有许多值得探究的部分(参考链接)。
其参数中,求和并非恒定不变,使用lambda
表达式或者重载符号+
也能够对其修改。
|
|
使用 accumulate
值得注意的问题
先来阅读两份源码:
First version
|
|
Second version
|
|
可以发现,无论是哪一种,accumulate
的返回值类型都不是由数组元素的类型来决定。
所以,一个常犯的错误就是(此处 点名批评 感谢pbrgg提供的素材)
|
|
问题何在呢?相信读者应该马上就能反应出来,由于0
的类型为int
在求和的过程种结果已经溢出。
Bit相关
这部分主要和c++20
标准库头文件<bit>
相关,但是考虑到现在许多的编译器还未能完全支持c++20
,因此在后面加入了一部分来自GCC Built-in Functions
的位操作函数。
c++20 <bit>
常用的函数
has_single_bit
检查一个数是否为二的整数次幂bit_ceil
寻找不小于给定值的最小的二的整数次幂bit_floor
寻找不大于给定值的最大的二的整数次幂countl_zero
从最高位起计量连续的0
位的数量countl_one
从最高位起计量连续的1
位的数量countr_zero
从最低位起计量连续的0
位的数量countr_one
从最低位起计量连续的1
位的数量popcount
计量无符号整数中为1
的位的数量
bitset
容器
补充一个不怎么常用的容器,bitset
本质上就是一个01
序列。
其占用内存很小并且也重载了位操作(&
, |
, >>
, <<
等)因此有时也用于卡常数。
常用的操作大致如下(以bitset<N> b;
为例):
|
|
来自GCC Built-in Functions
的位操作函数
官方的介绍 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
|
|
既然写到了gcc的内建函数,不妨也提一下其它的双下划线函数:
__gcd()
,顾名思义,一个用于求两数最大公因数的函数。
值得注意的是,在c++17
中,已经加入了gcd()
函数,可以不加下划线使用。
__builtin_ia32_rdtsc()
rdtsc
的原文大概是Read Time Stamp Counter
,这个函数原本是用于测量cpu时钟的,用于竞赛大概只能生成随机数种子。所以为什么在这提呢?主要是由于我的随机数生成代码中包含这一个函数。
|
|
位运算的其它操作
^
异或
对于二值集合{a, b}
,如何找到不同与x的另一个数呢?,直接if-else
判断当然可以,但没必要。最快的写法利用相同数的异或为0
,同时任何数与0
异或都等于它本身这两个所有人熟知的性质,写成x ^ a ^ b
就可以了。
- 二进制枚举
主要是在dfs
由数组确定的集合时用到,当然直接写dfs
也是可行的,甚至更快。(但,私以为二进制枚举最优雅)
- 取模$2^k$
等价为 &
上 $2^k-1$。用法大概是,最后 &
一下就行(大概。
注意,$2^{32}-1$需要int64_t
。此时用uint32_t
自然可以,但是会比int32_t
慢。
杂项 与 写法上的技巧
iota(all(a), val)
从val
开始递增地赋值,赋值后地数组为 { val, val + 1, ... }
。
十分适合用来写并查集的初始化(当然,还有不同的写法是初始化成-1)。
auto [min_val, max_val] = minmax(a, b)
同时获得两数的最大值和最小值,啥用没用 实际使用很少。
低版本建议的写法是 tie(min_val, max_val) = minmax(a, b)
,需要先声明变量。
tie(a, b) = minmax(a, b)
为错误写法!
函数
minmax()
的返回值类型为pair<const T &, const T &>
。函数
tie(Types&... args)
会依次赋值。
那么,如果 $a>b$,则会出现如下的情况:
|
|
最后所有的数都变成原先的最小值!
rotate
旋转,放在圆(环)上理解可能会好点。
|
|
- 求数组中不同元素的个数
|
|
next_permutation
和prev_permutation
枚举数组的所有排列,常见的写法是:
|
|
substr
string
中的STL
用得比较少,一般使用的就是substr
获取子串。
|
|
cout << " \n"[i == n];
避免行末空格,原理见我的另一篇博客。
std::vector
内存回收问题
对于std::vector
而言,pop_back()
,clear()
,resize()
都不会立即回收已经使用过的内存(程序做的应该只是迭代器的移动操作,具体细节本人未作研究,建议读者自行查阅STL
的相关源代码)。这大抵是为了方便后续的写入,省去再次分配空间的消耗。要做到立马回收空间,行之有效的方式是,利用std::swap()
的机制,将使用的内存交换走。
|
|