C++ 学习笔记

最后更新于：2022年6月25日 下午

跟同事 WZ 讨论了一些 C++ 特征之后，觉得 C++17 并没有掌握的那么好，于是重新去翻了一遍 《C++17 入门经典》第五版（这书确实太入门了，已经将《Effienct Modern C++》放进 ToDo 列表，已看完，看的时候书中内容基本之前都了解），多学学 ANSI C 和 C99(多了 for 中定义，双杠注释，变长数组（无意义），复数)，不优先学 C11（你都用 C11 了干嘛不用 C++），除非你要做多线程然后只能用 C，这有意义吗？ C99 也可以用 pthread 搞呀

没有必要关心你自己不用的特征！但是用的就一定要搞清楚。

等到 Codeforces 支持 C++20 后开始学习 C++2x，十分期待 C++23 和 C++26。 我猜应该等到 C++23 出来之后 Codeforces 才会添加 C++2x（已出 但是没有学的动力，静等 C++23 网络库的加入）。

后来我知道语言能做到跨平台是因为语言或者标准库帮你用类似宏的方式做了，没有的部分我们也可以手动做

文件拓展名（只是约定，其实文件名想怎么取都行）

  • .h: C/C++ 头文件
  • .hpp: 有模板的带实现的 C++ 的头文件
  • .c, cpp: 分别是 C, C++ 实现文件
  • .cc: 既可以用是 c 也可以是 c++ 的混合实现文件
  • .m: objective-C 的实现文件
  • .mm: objective-C 和 C++ 的混合实现文件

C 是面向机器编程，C++ 是面向编译器编程

头文件原则

以前我以为应该让头文件包含越少越好，甚至要用工具来简化所有多余的头文件，这是十分错误的做法

正确的做法：自身的头文件不应该依赖包含的头文件，你要啥就 include 啥，不要的就不 include，能放在 .cpp 就不要放在 .h。这样看上去更合理，并且你包含的头文件修改时，自己不必修改

C++ 之坑总结

了解一门语言的痛点，比了解一门语言的优势更为重要 ### std::vector<bool> 并不是 bool 的数组

避免使用 vector<bool>，推荐使用 bitset<N>

（更省内存，O2 优化后特别快！，但是注意不能开特别大的局部变量，太大就开全局变量，注意 bitset 是从后往前记的） 简单的说就是它并未实际保存一个 bool, 而是用位域的概念进行了封装

所以你在实际应用的时候可能会发生一些你意料之外的问题

整型提升

1
2
uint16_t a = 1, b = 2;
auto c = a - b // c 的类型竟然是 int

vector 引用

1
2
3
4
std::vector<std::vector<int>> a{{1, 2}, {3, 4, 5}};
auto &b = a[1];
a.emplace_back(std::vector<int>{6}); // no copy here
std::cout << b.size() << '\n'; // b.size() = 0

用引用的时候要相当小心

常引用的值可以改变

1
2
3
4
int x = 2;
const auto &y = x; // 只是说 y 指向的值不能由 y 来变罢了
x = 3; // 此时 y 的值也改变了
std::cout << y << '\n';

当然这就可以给出：单例的神仙用法，具体见 poly 中的用法

C 类型的数组并不会做安全的检测

这其实也是取舍问题，如果做了检测，必然会带了性能的降低。只是 C 更想要性能，然后安全检测可以交给应用程序，或者其他包装的库，例如 std::array, std::vector

编辑器/编译器/IDE

VScode 查看代码管理代码还是特别好的，但是 debug 还是选择各个平台对应的 IDE 较好，特别是 Xcode 除了 debug 还有一些性能工具真的难用的一 p， VS 也是！

VScode

Xcode

数值范围

double 会出现大数吃小数（这个涉及 double 的二进制表达，加减的时候要向大的数对齐），一旦超过了 DBL_MAX，那就变成 inf，inf 的运算规则跟数学的一致。inf - inf = nan 跟 1/0 = nan 一致都是未定义数。（他们都有自己特殊的二进制表示，且 nan == nan 返回值为 false）

INT_MAX, INT64_MAX, DBL_MAX 等都是常见的常数，当然也可以用 std::numeric_limits<T>::max() 或 std::numeric_limits<T>::min()

引用

指针 VS 引用

引用安全不用管回收，应该尽量使用引用

指针是一个非常重要的东西，它可以做四则运算相当灵活，而且有空指针却没有空引用

void*, shared_ptr<void>, std::any

  • void* 可以理解为单位长度为 0 的指针
  • 库无法复制 void* 指向的对象，因为不知道类型
  • shared_ptr 能释放内存，但是依然解决不了上面的类型安全问题
  • C++17 才有的 any 有一说一相当牛，可看 C++ reference 的实例

指向 const 的指针 p, const 指针 q 和 指向 const 的 const 指针 pq

1
2
3
4
5
6
7
8
const int i = 0;
const int j = 1;
const int *p {&i};
*p = &j;
int k = 0;
int * const q {&k};
*q = 1;
const int * const pq{&j};

std::ref 和 std::cref

这两个在多线程中尤为重要

左值，右值，右值引用

  • 单个变量的表达式必然是左值，用户返回的引用表达式也是左值，不是左值的表达值就是右值。
  • 右值引用可以延长右值的生命周期，但是它出现的作用是为了减少 copy 操作，如果你没有这个需求完全不用理会这个概念。
  • std::move 是将左值转换成右值引用，std::forward 则是原封不动的保持数据的类型（这是因为一个右值引用放在表达式的右边还是一个左值，要想它保持右值，就可以用 std::forward
  • 右值引用就是引用，它可以修改对应的值，可以转移所有权限
  • std::move 和 std::forward 在运行期都不做任何事情
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
using LL = long long;

class A{
  std::vector<int>&& a_;
 public:
  A(std::vector<int> &&a) : a_(std::forward<std::vector<int>>(a)) {
    a_.pop_back();
  }
  int size() {
    return a_.size();
  }
};
// 根据情况换成 bool
A solve() {
  std::vector<int> x{1, 3, 2, 5, 6};
  A y(std::move(x));
  cerr(y.size());
  cerr(x.size()); // x 因为 y 而改变了
  x.pop_back();
  cerr(y.size()); // y 也因为 x 改变了
  return y;
}

int main() {
  //freopen("in", "r", stdin);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  cerr(xxx);
  int cas = 1;
  // std::cin >> cas; // 根据情况注释掉
  while (cas--) {
    auto z = solve(); // 随着 solve() 中 x 被释放 y.a 也跟着消失了
    cerr(z.size());   // 答案为非合理值
  }
  return 0;
}

参考：https://www.cnblogs.com/guxuanqing/p/6594857.html(以及我在此篇的评论)

C++11 标准中规定，通常情况下右值引用形式的参数只能接收右值，不能接收左值。

但对于函数模板中使用右值引用语法定义的参数来说，它不再遵守这一规定，既可以接收右值，也可以接收左值（此时的右值引用又被称为"万能引用"）。

在函数模板中:

当实参为左值或者左值引用（A&）时， T&& 将转变为 A&（A& && = A&）； 当实参为右值或者右值引用（A&&）时，T&& 将转变为 A&&（A&& && = A&&）。 在实现完美转发时，只要函数模板的参数类型为 T&&，则 C++ 可以自行准确地判定出实际传入的实参是左值还是右值。

此时使用 std::forward<T> 就相当有价值了，以上部分来自：https://blog.csdn.net/lvwx369/article/details/118405626

可变参数

新版本：关于 可选参数 即参数带默认值（本质是添加一个函数，且是非 virtual 的！）

  1. 接口一般不推荐带可选参数，这是因为接口可选参数，那么所有实现都要有可选参数(否则实现类无法单独使用默认参数)，要小心不同参数可能参数不一致，此时是特别危险的，因为编译器添加的函数是非 virtual 的。
  2. 接口无可选参数，实现带可选参数，可行不推荐，因为不够优雅且应用不广泛：我们一般用接口的指针搞，缺失参数将会无法通过编译
  3. 如果可选参数是指针，默认参数是 nullptr 也可以让接口是可选参数，也不是不行

添加缺省参数的步骤 1. 直接添加参数，解决编译问题（让编译器帮助自己，防止遗漏自己想要改的内容） 2. 把默认值加上，使用默认值的回退不用修改

weak_ptr

1
2
auto sharedPtr = weakptr_.lock();
if (!sharedPtr) return;

确实是一个优雅的做法！这样如果这个 ptr 无效了那就啥也不做，当前有效就让它在这个区域一直有效！

模版类型萃取

模版添加了功能，但是有时我们的模版仅对一些特定类型正确，此时类型萃取提前告知用户这是错误的用法，确实不错

链接错误（总结）

  • 类中有 static 变量，但没有 inline
  • 多线程中有 static 变量，没有再类外面申明一下
  • 编译的时候 symbol 有两个

参数传入

void f(D x), void f(const D &x) 都可以接受全部参数类型（这是历史原因），但是两个不能同时出现！但是纯左值，纯右值的方式，就是根据自己的需要组合（不想说的太细，很繁琐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class D {
 public:
  static inline int cnt = 0;
  int a;
  D() {a = 0; }
  void print() const {
    std::cout << a << '\n';
  }
  ~D() {
    ++cnt;
  }
  D operator+() {
    D y(*this);
    ++y.a;
    return y;
  }
};

void f(D x) {
  x.print();
  std::cout << "f(D x)" << '\n';
}

int main () {
  { // complie error
    D x;
    x.a = 2;
    f(x);
    cerr(D::cnt);
    f(std::move(x));  // 这里为什么不被优化呢？
    cerr(D::cnt);
    f(+x);           //
    cerr(D::cnt);
    f(D());
    cerr(D::cnt);
  }
  cerr(D::cnt);
}

其实这本质就是一个需求问题，C++11 之前，你有时想穿进常引用，但是有时传入的是一个临时值，这都可以满足条件，但是如果你想传一个非临时的值，但是它在内部又回被修改，但你知道之后不会用它你应该怎么办？右值引用就是来解决这个问题的

C++ 类

权限问题，public, protected, private 要根据需求来。

其实 private 的变量是最让人喜欢的，因为它一来防止了别人瞎搞，二来如果你有代码修改，那么只用关心类中的更改，但是你要修改一个 public 的那问题就大了，特别是如果你这个是给别人提供 API，那这个就更不可能修改了

类的构造函数

用 Node(const int &A) 这种写法可以自动进行转化。但是又多个时候也要写反推回去的版本。

类用同类初始化和类等号运算符有本质的区别（虽然他们很多时候行为一致）

从 C++11 之后类构造函数可以设置默认值

有时我们不想隐式类型转换带来不可预期的问题，可以使用 explict 关键字

mutable 成员

multable 成员指出，即使是 const 对象，它的 mutable 成员也是可以被修改的（例如计数的）

虚函数 virtual, 重载 overide，不再允许子类重载 final

虚函数直白的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

class A {
 public:
  virtual void print() {
  // void print() {
    std::cout << "A" << std::endl;
  }
  void printS() {
    print();
  }
};
class B : public A {
 public:
  void print() {
    std::cout << "B" << std::endl;
  }
};

int main() {
  //freopen("in", "r", stdin);
  std::cin.tie(nullptr)->sync_with_stdio(false);
  A a;
  B b;
  A *p1 = &a;
  A *p2 = &b;
  B *p3 = &b;
  p1->print();
  p2->print();
  p3->print();
  p1->printS();
  p2->printS();
  p3->print();
  return 0;
}

A 的 print 函数前加 virtual 和不加有很大的不同

假设基类 的 A 函数需要调用 B 函数，而子类有对 B 进行覆盖。那么子类在调用（从基类继承的） A 函数时，并不会调用子类的 B 函数，而是调用基类的 B 函数。如果像 A 函数调用的是子类中的 B 函数，那么只需在 A 函数前加 virtual 关键字即可，此时最好在子类的函数中添加一个 overide 关键字，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// Box.hpp
#ifndef BOX_HPP
#define BOX_HPP
#include <bits/stdc++.h>
class Box {
  double x = 2;
 protected:
  double length {1.0};
  double width {1.0};
  double height {1.0};
 public:
  Box() = default;
  Box(double lv, double wv, double hv) : length {lv}, width {wv}, height {hv} {}
  // Function to show the volume of an object
  void showVolume() const { std::cout << "Box usable volume is " << volume() << std::endl; }
  // Function to calculate the volume of a Box object
  virtual double volume() const { return length * width * height; }
};

#endif

// Package.hpp
#ifndef PACKAGE_H
#define PACKAGE_H
#include "Box.hpp"
class Package : public Box {
 public:
  // Constructor
  Package(double lv, double wv, double hv) : Box {lv, wv, hv} {}
  // Function to calculate volume of a ToughPack allowing 15% for packing
  double volume() const override { return 0.85 * length * width * height; }
};
#endif

// main.cpp
#include "Box.hpp" // For the Box class
#include "Package.hpp" // For the ToughPack class
int main() {
  Box box {20.0, 30.0, 40.0}; // Define a box
  Package hardcase {20.0, 30.0, 40.0}; // Declare tough box - same size
  box.showVolume(); // Display volume of base box
  hardcase.showVolume(); // Display volume of derived box
}

虚函数一般用来作为接口，是特别有用的

混合特征

Mixin

利用可变参数模版和 C++ 多继承来把一些不相关的功能做成一个类

constexpr 用编译时间换运行时间

好处：安全，加密； 坏处：延长了编译时间。看以后的发展了。

替代解决方案：预处理得到文件，然后读取文件（容易有安全问题，另外要考虑独写效率）

optional 有三个顾名思义的函数：have_value, value, value_or

如果无值时调用 value，那么会 RE，这是件好事。 ### reserve 是个好东西，多注意内存相关

std::vector<T> 有三个重要的 "指针"：begin(), end() 和一个确定占用空间的（对应着 capacity 函数)。然后扩容是按照初始容量倍增的。然后 pop_back(), clear() 这些都不会影响到 capacity()（它只会被 reserve 和 扩容影响）

vector::at

at 会做边界检测，而 [] 默认不会，但是可以在编译中加如下参数做边界检测。例如我可以如下编译

1
g++ main.cpp -O2 -std=c++17 -D_GLIBCXX_DEBUG -o main

gcc 与 g++的区别

gnu libstdc++

boost

BOOST_DISABLE_ASSERTS -- disable asserts in the boost library.

Microsoft

gcc 内建的一些好用的函数

下面函数后加 ll 就可以得到 unsigned long long 对应的版本。应该尽量避免这样写，因为如果公司需要用 clang 你还要迁移

1
2
3
4
5
6
7
8
9
using uint = unsigned int;
__builtin_clz(uint n);           // 返回n的二进制前置0的个数（有汇编支持）
__builtin_clrsb (int x);         // 返回冗余位个数
__builtin_ctz(uint n);           // 返回n的二进制后置0的个数
__builtin_ffs(int n) = __builtin_ctz(uint n) + 1;  // 返回n的二进制从后往前第一次出现1的位置
__builtin_popcount(uint n);      // 返回n的二进制1的个数，以上函数仅在GCC中有
int __builtin_parity(uint n);    // 返回n的二进制1的个数奇偶性
std::__lg(int n);                //  返回log2(n)的整数部分
lowbit(uint n) = n & -n;         //  返回使得最大的2^i|n // 这个不是内建的

参考 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html，其中 __builtin_clz, __builtin_clrsb, __builtin_ctz, __builtin_ffs, std::__lg 可认为有内置汇编语言支持，__builtin_popcount 有更快的实现，而 __builtin_parity 我尝试了各种写法都无法超过内建的，不知道它怎么写的

智能指针

一般根据需求使用 unique_ptr<T> 或 shared_ptr<T>

weak_ptr<T> 可以理解为 shared_ptr<T> 的引用，可以解决 shared_ptr<T> 的循环引用导致无法释放内存的问题。

unique_ptr<T> 可以通过 std::move 转移所有权；shared_ptr<T> 可以通过 reset 释放或者指向其他内存（谨慎使用 release，最好别用）

智能指针唯一的劣势：无法进行四则运算

free store VS heap

简单的说，用户申请内存在 heap 上，这是 C 原有的，C++ 兼容了这一点，当然 C++ new 是在 free store 上的（这是一个抽象的概念），但是主流编译器实现的都是基于 C 的 malloc，因此其实也是在 heap 上的。但是用户可以重载 new/delete 使得它们不在 heap 上

烫烫烫烫烫 的原因

0xCCCCCCCC -858993460: https://blog.csdn.net/huijiaaa1/article/details/89361230

lambda 函数做计数器

C++ 代码注入

volatile 关键字

特别重要的特征，在跟操作系统，硬件交互或者多线程的编程中尤为重要

A volatile specifier is a hint to a compiler that an object may change its value in ways not specified by the language so that aggressive optimizations must be avoided.

当使用并发时使用 std::atomic，对特定内存才使用（要接触硬件）时使用 volatile

extern 关键字

可变参数模版

参考：https://www.cnblogs.com/yyxt/p/4204933.html

完全 C++ 风格示例（可以不用 va_start, va_args, va_end, va_list 这一套了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
using LL = long long;

template <typename... Ts>
void foo_print(Ts... args) {
  ((std::cout << args << ' '), ...);
}

template <typename... Ts>
int foo_sum(Ts... args) {
  std::cout << sizeof...(args) << std::endl;
  return ((args) + ...);
}

int main() {
  std::cout << std::boolalpha;
  foo_print(1, 3.14f); // 1 3.14
  foo_print("Foo", 'b', true, nullptr); // Foo b true nullptr
  std::cout << foo_sum(1, 3, 2, 5) << '\n';
}

参考：https://en.wikipedia.org/wiki/Variadic_function#Variadic_functions_in_C.2C_Objective-C.2C_C.2B.2B.2C_and_D

宏编程

有时候一些平台相关的代码，或者一些预处理必然需要用的宏，但是有时一句话很长为此可以在后面加入 \ 来换行

  • #if, #define #has_include 等等，可以把 # 全部放在第一列，这样看上去就跟普通 if else 一样（看 stl 的实现可以看到这样的技巧）
  • #x 表示 \(x\) 的字符串，x##y 表示将 \(x\), \(y\) 这两个字符串拼接起来

g++ -dM -E main.cpp 查看全部宏(main.cpp 内容可以为空) gcc, clang 用法一样，其它未求证

常用算法简化编程实例

最小最大值

min, max, minmax 都是参数个数为 2，返回的是值。所以不举例了，注意到 minmax 返回的是 pair

min_element,max_element,minmax_element 参数都是 vector，且返回的是索引。

1
2
3
4
5
std::cout << *max_element(a.begin(), a.end()) << std::endl;
auto lr = minmax_element(a.begin(), a.end()); //不能取*,因为返回的是pair类型
std::cout << *lr.first << " " << *lr.second << std::endl;
auto[l, r] = minmax_element(a.begin(), a.end()); //自动解析也行
std::cout << *l < " " << *r << std::endl;

累积运算 accumulate （长没关系，有代码补全）

1
2
3
4
5
6
7
8
9
std::vector<int> a{1, 3, 2, 4};
std::cout << accumulate(a.begin(), a.end(), 0) << std::endl; //默认累和
std::cout << accumulate(a.begin(), a.end(), 0, std::plus<int>()) << std::endl; //可选加减乘除
std::cout << accumulate(a.begin(), a.end(), 0, std::minus<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::multiplies<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::divides<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 0, [](auto & x, auto & y) {
  return 3 * x + y;
}) << std::endl;

排序

sort 的时候不能出现 \(a < b\) 且 \(b < a\) 同时出现的情况 stable_sort 是稳定排序，即不改变原有相互不小于的元素的相对位置

1
2
3
4
5
6
7
8
9
10
std::sort(a.begin(), a.end()); // 默认从小到大排序
std::sort(a.begin(), a.end(), std::less<int>()); // 手动从小到大排序（不一定是int，具体问题具体修改）
std::sort(a.rbegin(), a.end()); // 从大到小排序
std::sort(a.begin(), a.end(), std::greater<int>()); // 从大到小排序
//对于 tuple 和 pair 大小关系都是从按照字典序比较的
std::sort(a.begin(), a.end(), [](int & x, int & y) {
  return (x ^ 4) < (y ^ 4); // 位运算的优先级好低呀
});
for (auto & x: a) std::cout << x << " ";
std::cout << std::endl;

std::tuple_size<decltype(tupleExample)>::value; 可以获得 tuple 是多少维的。其中 decltype 代表 declare type 即声明类型。

集合交并运算

1
2
3
4
5
6
7
std::set<int> x{1, 2, 3};
std::set<int> y{2, 3, 5};
std::set<int> t;
std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::inserter(t, t.begin()));
// 若x,y,t是vector等有push_back 的容器，就可以使用
// set_intersection(x.begin(),x.end(),y.begin(),y.end(),back_inserter(t));
// set_union,set_difference,set_symmetric_difference 等同理

优先使用 unorder_set

lambda 表达式递归写法

1
2
3
4
5
6
7
8
9
std::function<int(int, int)> gcd = [ & ](int a, int b) -> int { // 注意最前面不能用auto
  return b ? gcd(b, a % b) : a;
};
std::cout << gcd(102, 210) << std::endl;
std::cout << std::__gcd(102, 210) << std::endl;
// 也可以这么写，但是调用的时候要使用  gcd(gcd, a, b) 不如上面来的方便
auto gcd = [&](const auto& self, int a, int b) {
  return b ? self(self, b, a % b) : a;
};

注意全局变量和全局函数，即使 lambda 列表为空，也能访问它们 注意 lambda 列表中如果是传值，那么默认不会修改，要修改可以加 mutable, 注意一旦传值就是另一个副本了，即此时原来的值改变不会影响 lambda 列表中的值（见下面例子）。

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
  int x = 0;
  auto f = [x]() mutable -> int {
    return --x;
  };
  auto g = [x]() -> int {
    return x;
  };
  ++x; // x 再次改变不会影响 f 和 g 中的 x
  cerr(f()); // -1
  cerr(g()); // 0
}

我们为了性能一般会优先选择传引用，但是默认不支持传 const 引用，此时可以用 C++17 中的 as_cost 的做法(当然了 const 引用你也可以直接写 引用，毕竟 const 只是编译器帮助自己检查罢了，对于机器来说并无区别)

普通函数转 lambda 函数（利用 std::bind)

std::placeholders::_1, std::placeholders::_2, ..., std::placeholders::_N，貌似很有用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <functional>

void Print(int i, int x){
  std::cout << 2 * i + x << '\n';
}

class A{
 public:
  void Print(int i, int x) {
    std::cout << 1LL * i * x << '\n';
  }
};

int main () {
  std::function<void(int, int)> f = &Print;
  f(2, 3); // 7
  std::function<void(int)> g = std::bind(Print, std::placeholders::_1, 3);
  g(4);    // 11
  std::function<void(int)> h = std::bind(Print, 3, std::placeholders::_1);
  h(5);    // 11
  A x;
  std::function<void(int)> i = std::bind(&A::Print, &x, 3, std::placeholders::_1);
  i(6);    // 18
  return 0;
}

官方示例：https://en.cppreference.com/w/cpp/utility/functional/bind

容器简介

  • array, vector, deque, list（双向链表）, forward_list（单向链表）都是顺序容器。
  • set, map 是关联容器。
  • unordered_map 和 unordered_set 是无序关联容器
  • stack，queue，priority_queue 严格说不是容器，而是容器适配器（默认使用 deque，可以自己换成 vector）

优先队列 priority_queue

  • std::priority_queue<int> 是默认最大堆，即头部是最大值。

  • 最小堆可以用 std::priority_queue<int, std::vector<int>, std::greater<>>。

  • 如果一般化地情况，std::priority_queue<Node> 其中 Node 中要定义小于号，然后也是最大堆。例如 Node 可以是 std::pair<int, int>

    1
    2
    3
    4
    5
    6
    7
    struct Node {
      int x, y;
      Node(int _x, int _y) : x(_x), y(_y) {}
      bool operator< (const Node &A) const {
        return x * A.y < y * A.x;
      }
    };

  • 另一种方式（cmp 中出现的 lambda 函数必须是全局变量），例如对 pii = std::pair<int, int> 的

    1
    2
    3
    4
    5
    6
    class cmp {
     public:
      bool operator() (const pii &lhs, const pii &rhs) const {
        return lhs.first * rhs.second < rhs.second * rhs.first;
      }
    };

注意优先队列不能随机访问和自然遍历 0.0

注意 map 和 unordered_map 的数据污染问题

map 中支持 mp[i] 的直接调用（即使没有数据 i，此时默认返回 0），但是次调用会污染了数据，即此时无论 mp 中是否有元素 i, i 都被添加到 mp 中。此时调用迭代器，i 就会出现了，这里需要特别注意。

unordered_map 同理。

pb_ds

过题的实例代码：gym 103076I

大数库

GMP

谁说 GMP 好用的，出来挨打！已经抛弃

Ubuntu 20.04 好像内置安装了 GMP，如果没安装可以使用 sudo apt install libgmp-dev 安装（可能需要安装 m4) 使用的时候 #include <gmpxx.h> 就好了（带 xx 表示 C++ 使用，不带表示 C 使用），不过它真的难用

NTL：专攻数论，以后再学吧

NTL 才是正确的选择，但是它的高效是需要借助 GMP 的

Boost：最终选择

Boost 是激进的 STL，STL 是保守的 Boost

一键安装：sudo apt install libboost-all-dev，正确用法：

1
2
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;

win10 下 WSL ubuntu20.04 真香。全所未有的方便！ win10 下 还可以用 MSYS2 安装

网络编程之 asio

很依赖 boost，将于 C++23 加入 STL

学习资料：官方库，基于 asio 的 C++ 网络编程