Info
  • update at 2022-08-27 ‘重写了部分代码实例,以及补充了部分内容’
  • update at 2022-04-25 ‘关于auto和bool的一个问题’
  • update at 2022-05-21 ‘accumulate返回值类型的细节’
  • update at 2022-05-23 ‘增加了bit部分的内容’

内容未完,之后写代码过程中见到或者想到的好的技巧都会逐步添加。


使用的编译指令:

1
"g++" -std=c++17 -Wall -Ofast -DLOCAL "ac.cpp" -o "ac.exe" 

g++ 版本:

1
2
3
@Kenshin2438 ➜  ~  g++ -v
...
gcc version 11.2.0 (GCC)

尽量只使用宏:

1
2
3
using ll = long long;
#define all(a) begin(a), end(a)
#define sz(x) (int)((x).size())

参考


常见容器

  • string
  • array - vector - deque
  • map - multimap - unordered_map
  • set - multiset - unordered_set
  • stack - queue - prority_queue
  • tuple
  • bitset

支持顺序访问的容器可以用下面的办法快速枚举:

1
2
3
4
for (auto value : container) {
  // value 为容器中的元素
  // auto  为c++11加入的,可以自动推断元素类型
}

对于结构体,一定程度上可以使用tuple代替。

c++17 开始支持

两者在访问时都可以使用auto对其结构化绑定声明,语法大概如下:

1
2
3
tuple<type_1, type_2, ....> container;
// 或者 struct,按照定义变量的顺序来即可
auto [value_1, value_2, ...] : container;

上面两种可以协同使用,遍历结构体vector<tuple<...>>

但是,如果仅仅是需要结构化绑定,可以使用tie():

1
2
3
4
tuple<int, int> container;
int a, b;

tie(a, b) = container;

可以见,这种写法并非变量声明,而是赋值

关于Range-based for loop的一些问题

  • 使用for (auto val : v)确实会发生拷贝,但并不是说v中元素就一定不会改变
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n = 5;
  vector<bool> v(n, true);
  for (auto val : v) val = false;
  for (int i = 0; i < n; i++) {
    cout << (v[i] ? "true" : "false");
    cout << " \n"[i + 1 == n];
  }
  return 0;
}

/** output: 
false false false false false
**/

不过,会出现上面情况的应该也就是vector<bool>这个奇葩了。显然auto判断类型为_Bit_reference,通过下面代码可以验证:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main() {
  cout << boolalpha;
  vector<bool> v = {false};
  for (auto val : v) {
    cout << is_same<_Bit_reference, decltype(val)>::value << '\n';
  }
  return 0;
}

/** output: 
true
**/

同时,如果你使用了auto &val : v,那么你将面临下面的报错:

compile error


  • 如果想用auto自动识别变量类型的引用,但又不想出错,你应当使用auto &&val : v来代替。
  • 使用const auto &val : v来彻底避免内存拷贝以及保证元素不被修改。

迭代器 与 all()

1
#define all(a) begin(a), end(a)

c++的STL中,更常用的是迭代器,而非下标(指针),这与纯c写法有较大区别。

begin()end() 作为容器的起始迭代器和末尾的迭代器

rbegin()rend() 逆向的迭代器

用于遍历的函数如下(虽然有许多容器的迭代器重载了++--,可以直接像下标一样处理,但还是推荐):

1
2
prev(iterator) // 上一个迭代器
next(iterator) // 下一个迭代器

定义这个宏的原因是:使用算法库的函数经常需要填写迭代器范围。

下面将介绍一些比较常见的函数(如果平时码风比较偏c语言,可能就不太常见)

算法库

cpp手册 - 算法库

此处仅记录一些本人常用的部分,<algorithm>内容十分丰富,并且还在随版本更新,惟愿本文能抛砖引玉,引起读者的兴趣。


排序 std::sortlambda表达式

std::sort(),应该是一个很常见的函数,用来排序数组的时,一些偏向c的写法会使用头尾指针来确定范围,再写外部函数确定排序规则。

但是,在使用如vector等可以排序的容器时,我们一般会动态开空间,所以此时待排序的范围就是全部元素。

1
2
3
4
5
6
vector<int> a(n);
sort(all(a)); // 对全部元素排序
sort(1 + all(a)); // 对下标从 1 开始的部分排序

sort(all(a), less<int>()); // 升序 (默认)
sort(all(a), greater<int>()); // 降序

std::sort比较相似的还有std::stable_sort,后者是能够保证,相同大小的元素在排序前后的相对位置不变。

  • 检验数组是否有序:std::is_sorted()

关于 lambda 表达式 (c++11)

sort函数中,第三个参数可以为我们定义的排序规则,如果不使用lambda表达式,我们往往会把它们写在外面,然后填写函数指针。

Tip
关于lambda表达式,受篇幅限制这里无法展开,建议访问cpp手册 - lambda表达式

基础语法如下:

1
2
3
4
5
6
[ captures ] ( params ) specs requires(optional) { body }

[ 获取的变量 &表示引用,=表示传值 可以写多个变量,但一般缺省,只写& ]
( 在表达式中定义的变量 )
specs requires(optional) 一般缺省,或者写成 -> 返回值类型,如 -> int
{ 具体表达式 函数体 }

放在sort中使用的实例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
struct Node {
  int a, b;
  Node(int _a = 0, int _b = 0)
    : a(_a), b(_b) {}
};

...

sort(all(v), [&](const Node &p, const Node &q) {
  return p.a * q.b <= q.a * p.b;
});

更多的,如果关联使用<functional>,可以将外部函数写在主函数内。

  • 这里还有一个问题,那就是如何写递归函数?

使用 function 类是一种解决办法,如下面的dfs代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int V = 100;
vector G(V, vector<int>(V));

function<void (int, int)> dfs = [&](int u, int fa) {
  for (auto v : G[u]) {
    if (v == fa) continue;
    dfs(v, u);
  }
};
dfs(source, -1); // 使用方式

如果不按照function类来声明该函数,[ captures ]无法获知自己的存在,所以一个可行的方案就是,在传值的时候将自己传入。

1
2
3
4
5
6
7
auto dfs = [&](auto self, int u, int fa) {
  for (auto v : G[u]) {
    if (v == fa) continue;
    self(self, v, u);
  }
};
dfs(dfs, source, -1); // 注意调用时需要将 自己 传入

搜索相关

我们知道,对于有序容器,我们可以利用其单调性来进行二分。

进行了上面的排序操作,我们的数组(暂且这么称呼)已经变得有序,如何利用STL中写好的二分函数呢?

对于一般容器而言,二分函数的写法比较统一(以vector<int> a为例好了):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
vector<int> a { 0, 1, 2, 2, 2, 3, 4 };

// 第一个大于等于 value 的位置(迭代器)
auto it = lower_bound(all(a), value); 

// 第一个大于 value 的位置(迭代器)
auto it = upper_bound(all(a), value); 

// 同时获得上述两者 返回为 std::pair<ForwardIt, ForwardIt>
auto P = equal_range(all(a), 2);
特殊容器

对于mapset,这类使用红黑树或者其他非线性数据结构实现的容器,如果你直接按照上面的写法二分,那么时间复杂度将直接退化到$\mathcal{O}(n)$。

正确的使用方法是直接调用其内部封装好的二分函数:

1
2
set<int> S;
auto it = S.lower_bound(value);

更一般的情况是,我们只需要数组中最值。

1
2
3
4
auto it_min = min_element(all(v)); // 最小元素对应的迭代器(可以理解为下标)
auto it_max = max_element(all(v)); // 最大元素

cout << *it_min; // 用于输出

如果你需要知道是一个数组的第K大的数(比如中位数),该怎么办呢,直接排序吗?

在某些时候,我们可能连$\mathcal{O}(n\log n)$的算法也无法接受,此时可以使用均摊复杂度为$\mathcal{O}(n)$的函数nth_element()

1
2
3
4
5
6
vector<int> a {4, 5, 3, 1, 6, 2};
int k = 2;
nth_element(a.begin(), next(a.begin(), k), a.end());
for (int x : a) cout << x << ' ';

// 输出:2 1 3 4 5 6

可以见,该函数并非排序,而是将前K小的数放在最前面的K个位置,且令第K位上为第K大。

如果仅仅需要一般的查找,使用find或者find_if即可,后者搭配lambda表达式,可以按需搜索。使用时请注意复杂度,对于一般容器,该函数使用的是顺序遍历,时间复杂度为$\mathcal{O}(n)$。

此处补充一点,查找元素无果,返回的迭代器为end()。特别的,stringfind失败得到的是string::npos

计算相关

  • countcount_if

统计元素个数时可用前者 count(all(a), val) ,如果需要按满足条件来统计,使用后者再搭配上lambda表达式即可。

值得说明的一点是,mapset中的findcount函数的复杂度是$\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表达式或者重载符号+也能够对其修改。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
struct str_node {
  str s; // define str string
  str_node operator +(const str_node &oth) const {
    return str_node{this->s + " + " + oth.s};
  }
};

void example() {
  vector<str_node> a{ 
                      str_node{"abc"},
                      str_node{"123"},
                      str_node{"def"},
                      str_node{"456"},
                      str_node{"!@#"}
                   };
  str_node sum = accumulate(1 + all(a), a.front());
  cout << sum.s << endl;
}

// 输出:abc + 123 + def + 456 + !@#

使用 accumulate 值得注意的问题

先来阅读两份源码:

accumulate - cppreference.com

First version

1
2
3
4
5
6
7
8
9
template<class InputIt, class T>
constexpr // since C++20
T accumulate(InputIt first, InputIt last, T init)
{
    for (; first != last; ++first) {
        init = std::move(init) + *first; // std::move since C++20
    }
    return init;
}

Second version

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
template<class InputIt, class T, class BinaryOperation>
constexpr // since C++20
T accumulate(InputIt first, InputIt last, T init, 
             BinaryOperation op)
{
    for (; first != last; ++first) {
        init = op(std::move(init), *first); // std::move since C++20
    }
    return init;
}

可以发现,无论是哪一种,accumulate的返回值类型都不是由数组元素的类型来决定

所以,一个常犯的错误就是(此处 点名批评 感谢pbrgg提供的素材)

1
2
3
4
5
6
7
8
vector<long long> v;
...
long long sum = accumulate(all(v), 0);

// 正确的写法如下:
// long long sum = accumulate(all(v), 0LL);
// 或者
// long long sum = accumulate(1 + all(v), v.front());

问题何在呢?相信读者应该马上就能反应出来,由于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;为例):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
b.all();
b.any();
b.none();
// 检查是否所有、任一或无位被设为 true

b.count();  // 返回设置为true的位的数量
b.set();    // 将位置为 true
b.reset();  // 将位置为 false
b.flip();   // 翻转位的值

b.to_ullong();
// 转换 bitset 的内容为 unsigned long long 整数
// bitset 的首位对应数的最低位,而尾位对应最高位
// 若值不能以 unsigned long long 表示,则为 std::overflow_error

来自GCC Built-in Functions的位操作函数

官方的介绍 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
__builtin_clz()        // count leading  0s   前面0的数目
__builtin_ctz()        // count trailing 0s   后面0的数目
__builtin_popcount()   // count bit 1         比特位为1的数目

/**
(16)10 = (00000000 00000000 00000000 00010000)2
__builtin_clz      : 27
__builtin_ctz      :  4
__builtin_popcount :  1

对于 long 类型的在函数名后面加 'l'
对于 long long 类型的在后面加 'll' 如 __builtin_popcountll
*/

既然写到了gcc的内建函数,不妨也提一下其它的双下划线函数:

  • __gcd(),顾名思义,一个用于求两数最大公因数的函数。

值得注意的是,在c++17中,已经加入了gcd()函数,可以不加下划线使用。

  • __builtin_ia32_rdtsc()

rdtsc的原文大概是Read Time Stamp Counter,这个函数原本是用于测量cpu时钟的,用于竞赛大概只能生成随机数种子。所以为什么在这提呢?主要是由于我的随机数生成代码中包含这一个函数。

1
2
3
4
5
6
7
8
9
#include <random>

std::mt19937 rng(__builtin_ia32_rdtsc());
template<typename T> inline T randint(T l, T r) {
  return std::uniform_int_distribution<T>(l, r)(rng);
}
template<typename E> inline E randreal(E l, E r) {
  return std::uniform_real_distribution<E>(l, r)(rng);
}

位运算的其它操作

  • ^ 异或

对于二值集合{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)错误写法!

  1. 函数 minmax() 的返回值类型为 pair<const T &, const T &>

  2. 函数 tie(Types&... args)依次赋值

那么,如果 $a>b$,则会出现如下的情况:

1
2
3
4
tie(a, b) = minmax(a, b)

   a = (const T&) b
   b = (const T&) a // 此时,由于此处为 a 的引用,所以值已经改变

最后所有的数都变成原先的最小值!

  • rotate 旋转,放在圆(环)上理解可能会好点。
1
2
3
4
5
template< class ForwardIt >
void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last );

rotate(a.begin(), next(a.begin(), 2), a.end()); 
// a.begin() + 2, a.end() 和 a.begin(), a.begin() + 2 整体交换位置
  • 求数组中不同元素的个数
1
int num = sz(set<int>(all(a)));
  • next_permutationprev_permutation

枚举数组的所有排列,常见的写法是:

1
2
3
4
sort(all(p));
do {
  // ... 
} while (next_permutation(all(p)));
  • substr

string中的STL用得比较少,一般使用的就是substr获取子串。

1
s.substr(startlength); // length 参数缺省时表示后续直到 end()
  • cout << " \n"[i == n];

避免行末空格,原理见我的另一篇博客

std::vector 内存回收问题

CF1706D2

对于std::vector而言,pop_back()clear()resize()都不会立即回收已经使用过的内存(程序做的应该只是迭代器的移动操作,具体细节本人未作研究,建议读者自行查阅STL的相关源代码)。这大抵是为了方便后续的写入,省去再次分配空间的消耗。要做到立马回收空间,行之有效的方式是,利用std::swap()的机制,将使用的内存交换走。

1
vector<T>().swap(v);