cpp snippets

(Updated: )
(35 mins to read)

std::monostate用于模拟空值的状态（就是一个空的结构体）。

std::variant会默认调用第一个类型的默认构造函数，如果第一个类型没有默认构造函数，就会编译错误。

在从一种状态转换到另一种状态时出现异常会罕见的变为valueless_by_exception，并且在index()时会返回variant_npos。

1
2
3
4
5
6
7
8
9
10
template< class T >
constexpr const T& clamp( const T& v, const T& lo, const T& hi );
// if v < lo return lo
// else if v > hi return hi
// else return v
// 如果lo大于hi，是未定义行为

template< class T >
constexpr T midpoint( T a, T b ) noexcept;
// 在a+b为奇数时，向a取整

std::piecewise_construct是空结构体std::piecewise_construct_t的一个实例，用于对一个std::pair的构造进行消歧。

使用std::piecewise_construct，会对pair的first和second分别进行原地构造；否则会先生成两个临时对象，再进行拷贝构造。

1
2
std::map<int, big> map;
map.emplace(std::piecewise_construct, /*key*/std::forward_as_tuple(1), /*value*/std::forward_as_tuple(2,3));

实际原理就是pair有一个特化的构造函数，piecewise_construct就是起到一个标签作用。

1
2
3
4
template< class... Args1, class... Args2 >
pair( std::piecewise_construct_t,
      std::tuple<Args1...> first_args,
      std::tuple<Args2...> second_args );

vector的特化

  • SmallVector：在size小于某个阈值时，使用对象内置的栈上分配的buffer存储，而在大于阈值后再转为动态分配。std::string也有类似的优化，在比较短时使用char [N]来存储。

  • FixedCapacityVector：类似于array，但是初始容量为0，在增加和删除元素时进行构造和析构，array则在实例化时就要对所有元素进行初始化。在增加元素超过固定的容量时报错。

  • PODVector: vector在扩容时会对元素进行默认初始化，但有时候我们希望省略这个步骤，比如我们只是想resize一个足够大的buffer用来read。

    解决方案：可以包装一个构造函数为空的类。（另见https://stackoverflow.com/a/61346609和https://www.bilibili.com/video/BV1gu411m7kN的1:24:00处）

std::weak_ptr

指向一个由shared_ptr管理的对象，但不实际拥有它，也就不会影响引用计数。

expired()检查对应的对象是否已被消除。

lock()创建一个实际拥有对应对象的shared_ptr。

用于解决循环引用（引用计数永远不为0导致内存泄露），悬挂空指针（可以利用expired判断对象是否还存在，如果存在，再用lock来操作该对象）。

std::enable_shared_from_this

用于在类内拿到this的shared_ptr对象（有一个用处时用在回调函数中以使对象保活）。

对于指向同一个对象的多个shared_ptr，只能有一个是通过持有对象的指针构造的，其余的都是通过这个shared_ptr构造的。

而如果在类内使用auto local = std::make_shared(this);，就又产生了一个独立的shared_ptr。

正确的做法是: public std::enable_shared_from_this<T>，然后在类内使用shared_from_this()。

原理：利用了CRTP和weak_ptr。在shared_ptr的传入指针（T* ptr）的构造函数中，会判断T是不是继承自enable_shared_from_this<T>，如果是就将enable_shared_from_this<T>中的weak_ptr成员指向自身。这样每次shared_from_this()只需要调用该weak_ptr成员的lock()来得到一个共享的shared_ptr了。

在调用shared_from_this()之前，必须得有一个shared_ptr了，否则weak_ptr还没有被初始化。因此最好的方法是去掉该类的构造函数，只暴露一个工厂函数（create），返回一个独立的shared_ptr。

在具体实现上，shared_ptr和weak_ptr都会包含一个指向堆上的引用计数控制块信息的指针，该引用计数控制块不仅包含引用计数、弱引用计数，还包含一个原始指针。即原始指针会存两遍，这也是一个容易被忽略的开销。

1
2
3
4
std::numeric_limits<T>::min();
std::numeric_limits<T>::lowest();
// 对于浮点数，min返回的是以标准形式表示的最小正浮点数，最小表示值应使用lowest
std::numeric_limits<T>::infinity();

deque

std::deque的实现是一个块状数组，每个块有固定的大小block_size（8或16），每次随机访问需要先算出块(index / block_size)，再找到块内偏移（index % block_size）。显然不同块的存储可能不连续。这样的好处是在不断push_back扩容时不需要移动数据，因此可以更快，且迭代器不会失效。

仅供参考：相比std::vector，迭代器在扩容时不会失效；相比std::list，缓存更友好；相比std::array，可以动态扩容。因此可以作为全局的内存池使用（见https://codeforces.com/blog/entry/60321）。

stack和queue的底层默认是deque（只是禁用了某些接口）。

template<class T, class Container = std::deque<T>> class stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
stack<elem*> recycleBin;
deque<elem> elemCache;

elem *fetchElement() {
  if (!recycleBin.empty()) {
    elem *temp = recycleBin.top();
    recycleBin.pop();
    return temp;
  }
  elemCache.push_back(elem());
  return &elemCache.back();
}

void deleteElement(elem *e) {
  recycleBin.push(e);
}

veque的实现方式就是在前面也有一段预留的buffer，即底层的buffer分成[front][data][back]三部分。类似地，在push_front时，如果没有空间，就对[front]进行扩容，也可以选择shift_back，需要对front和back的buffer进行平衡。front和data的边界用一个额外的变量offset指示，data和back的边界是size

ring_buffer

环形缓冲区，或环形队列。容量是固定的。

每次读取数据返回的是当前最老的数据。

需要一个头指针（写索引）、尾指针（读索引）。由于可能出现缓冲区满发生覆盖的情况，判断当前是空还是满是重点。

  1. 可以用一个size变量记录当前的大小。
  2. 留空一个位置，这样满的时候就是max_size - 1。
  3. RT-Thread使用的是镜像指示位。每个索引的范围是[0, 2 * max_size - 1]，真实指针需要% max_size。同时为了效率，还用两个bool变量指示索引在逻辑地址空间（[0, max_size - 1]）还是镜像逻辑地址空间（[max_size, 2 * max_size - 1]）。
  4. Linux2.6对镜像指示位进行了扩展，索引范围是[0, 2^32 - 1]，也就是让其自然溢出。本质上让索引能大于等于max_size，就可以通过差值等于max_size来判断满了，但这就强制要求max_size是2的幂次。

要求ring_buffer的max_size为2的幂次会方便一些，取模可以用& (max_size - 1)。

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
// RT_Thread
struct rt_ringbuffer
{
  rt_uint8_t *buffer_ptr;
  rt_uint16_t read_mirror : 1;
  rt_uint16_t read_index : 15;
  rt_uint16_t write_mirror : 1;
  rt_uint16_t write_index : 15;
  rt_int16_t buffer_size;
};
// Linux2.6
struct kfifo {
  unsigned char *buffer; /* the buffer holding the data */
  unsigned int size; /* the size of the allocated buffer */
  unsigned int in; /* data is added at offset (in % size) */
  unsigned int out; /* data is extracted from off. (out % size) */
  spinlock_t *lock; /* protects concurrent modifications */
};
// Linux5.17
struct __kfifo {
  unsigned int in;
  unsigned int out;
  unsigned int mask; // max_size - 1
  unsigned int esize;
  void  *data;
};

hyperloglog

估计一个很大的集合的基数。

基本思想：如果一个均匀分布的随机数集合中二进制前导零个数最大为$n$，则估计集合大小为$2^n$。

对每个数进行hash（hash得到的值就可以认为构成一个均匀分布的随机数集合），高14位作为桶编号，低50位在每个桶内统计前导零个数的最大值，最后对所有桶求加权平均。

ordered map

这里的order指的是保持插入时的顺序，对ordered map进行迭代会遵循插入的顺序。显然std::map和std::unordered_map都不满足要求。

实现方式：

  1. list存迭代器，map维护键值对
1
2
std::unordered_map<K, V> map;
std::list<decltype(map.begin())> order;
  1. 一个deque/vector values维护value序列，另一个vector buckets维护桶序列，每个桶包含一个key的hash值以及其value在values中的下标（也就是一个map）。

tsl::ordered_map

有更快的插入和遍历速度，但是保持有序的删除是$O(N)$的。

  1. python3.6后的字典就是有序的。vector<pair<K,V>> entries存键值对，另一个vector indices存下标。每次查找，对键哈希找到在indices中的位置，然后得到在entries中的位置。

显然删除也是$O(N)$的，但实际用了懒惰标记，在删除个数达到一定阈值时，再统一进行一次删除。

placement new

A* a = new(buf) A，自己指定位置（给定buf，既可以是已分配的堆上空间，也可以是栈上的），然后调用对象的构造函数进行构造。

但注意用完对象后需要显示调用析构函数a.~A()。

类似于内存池，对内存复用。

还有一种情况是创建一个构造函数有参数的类数组，可以先申请空间，然后对每一项利用placement new构造对应的对象（这其实就是vector的做法）。

algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
std::iota(a.begin(), a.end(), 0) // range(0, n)
std::fill(a.begin(), a.end(), value)
std::adjacent_difference(in.begin(), in.end(), out.begin()); // 差分，out可以等于in
std::partial_sum(in.begin(), in.end(), out.begin()) // 前缀和
std::partial_sort(a.begin(), a.begin() + k, a.end()) // 使得前k个位置包含k个最小的元素 O(n\log k)
bool std::lexigraphical_compare(a.begin(), a.end(), b.begin(), b.end()) // O(n)
bool std::is_sorted(a.begin(), a.end())
iterator std::min/max_element(a.begin(), a.end())
bool std::binary_search(a.begin(), a.end(), target) // O(log n)
T std::accumulate(a.begin(), a.end(), 0LL); // 求区间和，注意返回类型和最后一个参数的类型相同
bool std::any/all/none_of(a.begin(), a.end(), func);
std::for_each(a.begin(), a.end(), func); // 很多时候可能不如range-based for
int std::count(a.begin(), a.end(), value);
std::nth_element(a.begin(), a.begin() + k, a.end()); // 第k + 1大将位于a[k]，且前面的都不小于后面的 O(n)
std::merge(in1.begin(), in1.end(), in2.begin(), in2.end(), out.begin()) // 归并排序， out和in不能有重叠
std::rotate(a.begin(), a.begin() + k, a.end()) // a[k]成为第一个元素
bool std::is_permutation(a.begin(), a.end(), b.begin()) // a是否是b的一个排列 O(n^2) 排序比较即可

std::end(container)[-1]像python一样得到最后一个元素

ssize(v)返回有符号类型的大小

std::byte

enum class byte : unsigned char {};

char/signed char/unsigned char被用于表示字节、字符以及执行计算。引入std::byte，专门让其用于表示一个字节的内容，只能进行位运算和比较运算，以提高程序的安全性和可读性。

注意：一个字节通常是8个比特，但也可能更多（如16比特），确切数值定义在CHAR_BIT中。

std::call_once

1
2
template< class Callable, class... Args >
void call_once( std::once_flag& flag, Callable&& f, Args&&... args );`

确保一个函数只会被正常调用一次（如果调用时发生了异常，则不算正常调用）。用于全局变量的按需初始化一级单例模式。

std::once_flag是专门用于std::call_once的一个结构体标记。

1
2
3
4
5
Singleton& Singleton::get() {
    static std::once_flag flag;
    std::call_once(flag, [&](){ instance.reset(new SingletonDataBase()); });
    return instance.get_interface()
}

std::using

typedef可以通过声明+右左法则来理解，类型别名位于声明语句中变量名和函数名所在的位置。在C语言中与static、register等同属于storage class specifiers，即存储类型说明符。

std::using中类型别名永远位于等号左侧，而typedef则会混杂在里面。

1
2
typedef int(*func_ptr)(int, double);
using func_ptr1 = int(*)(int, double);

在右左法则中，我们会从未定义的变量名开始从右向左螺旋解释类型，但是在C++中，有些类型（模板、别名）是不包含名称的，这被称作type-id，这时应该从最左侧的最内层括号开始（当然C语言其实也是这样，只是有些人会从未定义变量开始，但在这里就不适用了）。

std::using还可以用于模板别名。

类成员函数指针

1
2
3
4
5
void (A::*fp)(int) = &(A::f);
void (*gp)(int) = A::g;
A a;
a.*fp(1);
gp(1);

静态成员函数和普通的函数一样。而非静态成员函数在声明时需要附加类名称（A::），并且在调用时传入对象（a.），而且&和*不能省略。

虚函数的指针值是一个偏移量，而不是实际地址。

函数级try catch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class D {
    D(int x) try : x_(x) {

    } catch(...) {

    }
};

int f(int n = 2) try {
    ++n; // increments the function parameter
    throw n;
} catch(...)
{
    ++n; // n is in scope and still refers to the function parameter
    assert(n == 4);
    return n;
}

这个try块包裹了函数体（对于构造函数，还可以包裹成员初始化），但不包括函数参数的赋值。

特别地，对于构造函数上的try catch，如果发生异常，虽然会执行catch块，但由于对象构造失败，唯一能做的就是重新抛出一次异常。因此构造函数上的try catch的作用仅仅是清理或者抛出另一个异常，它并不能阻止异常的传播。

类模板参数推导

C++17起有CTAD，此时不必写出模板参数列表，编译器会根据上下文进行推导（有点类似rust）。

所以可以写出下面的简化代码：

1
2
3
std::pair p(2, 4.5); // std::pair<int, double>
std::vector dp(N, std::vector<int>(M)); // 多维vector的声明会方便很多
std::lock_guard(mutex); // std::lock_guard(std::mutex) 函数也是可以的

推导指示

用于指示编译器如何正确推导模板参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename T, typename U>
struct Pair
{
    T first{};
    U second{};
};

// Here's a deduction guide for our Pair (needed in C++17)
// Pair objects initialized with arguments of type T and U should deduce to Pair<T, U>
template <typename T, typename U>
Pair(T, U) -> Pair<T, U>;

int main()
{
    Pair<int, int> p1{ 1, 2 }; // explicitly specify class template Pair<int, int> (C++11 onward)
    Pair p2{ 1, 2 };           // CTAD used to deduce Pair<int, int> from the initializers (C++17)

    return 0;
}

Y Combinator

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html

C++不支持递归的lambda，只能通过std::function解决。

1
2
3
auto gcd = std::y_combinator([](auto gcd, int a, int b) -> int {
    return b == 0 ? a : gcd(b, a % b);
});

一种示例实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <functional>
#include <utility>
namespace std {
template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
} // namespace std

new int[0]

这被允许，但是返回的指针没有意义，对其解引用是未定义行为，但是你仍然需要使用delete[]（没有规定应该怎么实现，但猜测会像非零值时一样再前面有一块meta data，并不会特殊处理）。

这是为了和malloc一致，不过malloc(0)会返回NULL，而new int[0]不一定。

和free(NULL)类似，delete nullptr什么也不会做，是合法行为。

std::clog

除了常见的std::cout和std::cerr外，还有std::clog，它也输出到stderr中。区别是std::cerr不像其它两个那样会缓冲。

std::string c_str() vs. data()

在C++11之后，std::string和C风格字符串一样，会额外存储一个’\0’作为null terminate。因此，c_str()和data()都保证返回的是null terminate的字符数组，它们的行为一样。

在C++17之后，data()有const和非const的重载，而c_str()一定返回const。

三向比较

C++20之前可以重载<、>、<=、>=、==、!=这6种比较运算符。

一般会遵循以下原则：

  • 同类型用成员函数实现
  • 不同类型用非成员函数实现
  • 优先实现>、<、==
  • 其余的用以上三种实现

默认比较

1
auto operator<=>(const Point&) const = default;

编译器会按固定的规则生成所有的6种比较运算符。

自定义比较

<=>的返回类型有三种：

  • std::strong_ordering：必须严格比较所有成员，但是可以按不同的顺序。严格的意思是说，如果a==b，则f(a)==f(b)，其中f是任意只读函数
  • std::weak_ordering：必须比较所有成员，但是可以按不同的顺序。可以是不严格的，比如字符串可以按照大小写不敏感的方式比较。
  • std::partial_ordering：允许只比较部分成员，可以按不同的顺序，也可以是不严格的。

如果类包含容器类型，应该再写一个默认的等于运算符，因为三向比较生成的会比较容器中的每一个元素，而等于运算符生成的会优先比较容器的大小，性能会更好。

1
bool operator==(const Point&) const = default;

format

用法类似Python3的fstring：std::format("Hello {}", world_str)。

std::format相比于sprintf和std::stringstream的优势是速度更快，更安全（不需要写具体的格式控制符，用大括号即可），在浮点数精度方面也更优。

不过自定义类型要想使用std::format还是比较麻烦的，需要写一个特化的std::formatter<T>，实现其中的parse函数和format函数。

此外，std::format_to将结果写入到一个迭代器中，用于追加写，std::format_to_n限制最多写入n个字符，std::formatted_size则返回构成的字符串的大小。

1
2
3
4
5
6
7
8
9
10
template< class... Args >
std::string format( std::format_string<Args...> fmt, Args&&... args );
template< class OutputIt, class... Args >
OutputIt format_to( OutputIt out, std::format_string<Args...> fmt, Args&&... args );
template< class OutputIt, class... Args >
std::format_to_n_result<OutputIt>
    format_to_n( OutputIt out, std::iter_difference_t<OutputIt> n,
                 std::format_string<Args...> fmt, Args&&... args );
template< class... Args >
std::size_t formatted_size( std::format_string<Args...> fmt, Args&&... args );

optional

  • std::make_optional()
  • *, has_value()
  • ->, value()
  • value_or(default_value)：为空就返回传入的default_value
  • reset()：如果有value，就销毁包含的value（这和={},=std::nullopt没什么区别）
  • emplace()：optional也有emplace函数，在原地构造

STL的实现是一块aligned storage再加一个单独的bool标记，但由于内存对齐的原因，sizeof(optional<double>) == 16，sizeof(optional<int>) == 8。

tiny-optional使用不会出现的位模式来标记nullopt状态，比如bool类型一般为1个字节，但事实上只需要1个比特即可表达true/false，因此完全可以利用其它的7个字节，而不需要一个额外的bool标记。

extern “C”

C++有函数重载、命名空间、模板等，因此需要对名称进行mangle，而C语言不会。

使用extern "C"表明符号不会被mangle，从而能够与C文件链接，实现在C文件中调用C++函数以及在C++文件中调用C函数。显然，在extern "C"就不能使用C++那些必须mangle的功能了。

1
2
3
4
5
6
7
8
extern "C" int a;
extern "C" double b;
extern "C" char c;
extern "C" {
    int a;
    double b;
    char c;
}

extern "C" {...}作用到其中所有具有外部链接的函数和变量上。

注意，不带大括号时，extern直接作用到后续的语句上，因此这只是一个声明。而在带大括号时，则是声明加定义，除非写成extern "C" { extern int a; }。当然，这个细微差别仅在定义变量时存在，而在更常见的定义函数时不存在。

除了static，在C++中const变量也会变成内部链接。

std::jthread

jthread即joining thread，不同于std::thread，std::jthread会在析构时自动调用join，而std::thread在析构时调用std::terminate。此外，还可以请求jthread暂停执行，以对线程执行进行额外控制（通过std::stop_token.stop_requested()和jthread.request_stop()）。

重载&&和||

注意重载与运算和或运算会丧失掉原生的短路性质。

原因其实也很简单，因为重载是一个函数，A && B等价于A.operator&&(B)，B是一个函数参数；函数参数必须先求值才能进入函数中。所以无法实现短路性质（在C#中要求用户定义两个函数才能实现短路，本质上需要一种表达懒惰求值的方式，这是C++没有的）。

一种更好的方式是近实现bool operator。

clear()

众所周知，clear只是把size改为了0，而capacity保持不变。但是该操作的复杂度其实是$O(n)$的，而不是$O(1)$的，因为它需要对每个元素调用析构函数。类比delete[]，不过显然trivial destruct的元素是可以优化为$O(1)$的。

extract()

在STL中，关联容器的key都是const的，无法修改。可以利用extract加insert实现对key的修改：

extract返回一个node handle，这是一个仅可移动的对象。（注意和erase是不一样的，erase返回下一个迭代器，而extract返回拥有被删除对象的一个node handle，这么做可以避免拷贝）

1
2
3
4
map<int, string> m{{1, "mango"}, {2, "papaya"}, {3, "guava"}};
auto nh = m.extract(2);  // m == {{1, "mango"}, {3, "guava"}}
nh.key() = 4;
m.insert(move(nh));

merge()

顾名思义，就是合并两个容器。

std::aligned_storage

可以存储任何大小至多为Len，内存对齐为Align的因子的对象。

1
2
3
4
5
6
template<std::size_t Len, std::size_t Align = /* default alignment not implemented */>
struct aligned_storage {
    struct type { // possible implementation
        alignas(Align) unsigned char data[Len];
    };
};

std::this_thread::sleep_for()

该函数的兼容性比sleep更好，底层可能是用nanosleep来实现的，也就意味着时间精度会更高。

std::push_heap/std::pop_heap

priority_queue就是对这几个函数的包装。

1
2
3
4
5
6
7
// [first, last)构成一个大顶堆，所以pq默认也是大顶堆（默认是less比较）
template< class RandomIt >
void make_heap( RandomIt first, RandomIt last );
template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last ); // 将堆顶移至末尾

std::exchange

1
2
std::exchange(a, b); // 将b赋值给a，并返回原来的a，a++等价于std::exchange(a,1)
// 注：后置自增因为需要返回原来的值，所以需要额外的一个临时变量，因此会比前置自增慢。不过现代编译器必然都进行了优化。