Modern C++

Grammar

std::ranges

std::ranges 库的核心思想是让算法直接操作容器（而非迭代器对），并支持管道式（pipeline）链式调用。

对比以前的迭代器使用方式：

1
2
3
4
5
6
7

// 找到指定元素
std::sort(v.begin(), v.end());
auto it = std::find(v.begin(), v.end(), 4);

// std::ranges
std::ranges::sort(v);
auto it = std::ranges::find(v, 4);

以下是一些std::ranges的常用方式：

转换：

  • std::transform

过滤：

  • std::filter

排序：

  • std::sort

查找：

  • std::find

    遍历：

  • for_each

    1
2
3

    // 将数组内所有元素置0
std::vector<int> matrix{0, 1, 0, 2, 3};
std::ranges::for_each(matrix, [](auto& value) { value = 0; });

判断是否存在满足条件的元素：

  • contains
    1
2
3

    // 检查是否包含0元素
std::vector<int> matrix{0, 1, 0, 2, 3};
bool hasZero = std::ranges::contains(matrix, 0);
  • any_of
    1
2
3
4
5

    // 检查是否包含0元素
std::vector<int> matrix{0, 1, 0, 2, 3};
bool hasZero = std::ranges::any_of(matrix, [](auto& value) -> bool {
    return value == 0 
});

其他：

  • take

std::filesystem

容器小tips

大小根堆

std::priority_queue为标准库自带的大根堆，默认为：std::priority_queue<T, std::vector<T>, std::less<>>，自定义排序版的堆为：

1
2
3
4

auto cmp = [](const T left, const T right) {
    return left > right;  // 小根堆，与排序相反，比较返回true时默认left节点下沉
};
std::priority_queue<T, std::vector<T>, decltype(cmp)> heap;

std::priority_queue本身为对<algorithm>中make_heap、push_heap、pop_heap、is_heap等方法的封装，所以第二个模板参数需要提供支持随机访问的容器：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

vector<int> vec = {3, 1, 5, 2};
// 构建大根堆
make_heap(vec.begin(), vec.end());
// 插入新元素
vec.push_back(6);
push_heap(vec.begin(), vec.end());
// 弹出堆顶
pop_heap(vec.begin(), vec.end());
vec.pop_back();
// ...

基于vector手动实现堆排序：

1

// TODO

Container/Tool Class

std::string

  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
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251

#include <cstring>
#include <iostream>
#include <algorithm>
#include <stdexcept>

class MyString {
public:
	using iterator = char*;
	using const_iterator = const char*;
	static const size_t npos = static_cast<size_t>(-1);

	MyString()
		: m_data(new char[1])
		, m_size(0)
		, m_capacity(0)
	{
		m_data[0] = '\0';
	}

	MyString(const char* str)
	{
		if (str == nullptr) 
		{
			m_size = 0;
			m_capacity = 0;
			m_data = new char[1];
			m_data[0] = '\0';
		}
		else
		{
			m_size = std::strlen(str);
			m_capacity = m_size;
			m_data = new char[m_capacity + 1];
			std::memcpy(m_data, str, m_size + 1);
		}
	}

	MyString(size_t count, char ch)
		: m_data(new char[count + 1])
		, m_size(count)
		, m_capacity(count)
	{
		std::memset(m_data, ch, count);
		m_data[m_size] = '\0';
	}

	~MyString()
	{
		delete[] m_data;
	}

	// 拷贝构造
	MyString(const MyString& other)
		: m_data(new char[other.m_size + 1])
		, m_size(other.m_size)
		, m_capacity(other.m_size)
	{
		std::memcpy(m_data, other.m_data, m_size + 1);
	}

	// 移动构造
	MyString(MyString&& other) noexcept
		: m_data(other.m_data)
		, m_size(other.m_size)
		, m_capacity(other.m_capacity)
	{
		other.m_data = new char[1];
		other.m_data[0] = '\0';
		other.m_size = 0;
		other.m_capacity = 0;
	}

	MyString& operator=(MyString other) noexcept
	{
		swap(other);
		return *this;
	}

	// 容量相关
	size_t size()     const noexcept { return m_size; }
	size_t length()   const noexcept { return m_size; }
	size_t capacity() const noexcept { return m_capacity; }
	bool   empty()    const noexcept { return m_size == 0; }

	// c_str()
	const char* c_str()  const noexcept { return m_data; }
	const char* data()   const noexcept { return m_data; }

	// 预分配容量
	void reserve(size_t newCap)
	{
		if (newCap <= m_capacity) return;

		char* newData = new char[newCap + 1];
		std::memcpy(newData, m_data, m_size + 1);
		delete[] m_data;
		m_data = newData;
		m_capacity = newCap;
	}

	void clear() noexcept
	{
		m_size = 0;
		m_data[0] = '\0';
	}

	// operator[]
	char& operator[](size_t pos) { return m_data[pos]; }
	const char& operator[](size_t pos) const { return m_data[pos]; }

	// at() 做越界检查，抛 std::out_of_range
	char& at(size_t pos)
	{
		if (pos >= m_size) throw std::out_of_range("MyString::at");
		return m_data[pos];
	}
	const char& at(size_t pos) const
	{
		if (pos >= m_size) throw std::out_of_range("MyString::at");
		return m_data[pos];
	}

	char& front() { return m_data[0]; }
	const char& front() const { return m_data[0]; }
	char& back() { return m_data[m_size - 1]; }
	const char& back()  const { return m_data[m_size - 1]; }
	
	// 修改
	MyString& operator+=(const MyString& rhs)
	{
		append(rhs.m_data, rhs.m_size);
		return *this;
	}

	MyString& operator+=(const char* str)
	{
		append(str, std::strlen(str));
		return *this;
	}

	MyString& operator+=(char ch)
	{
		push_back(ch);
		return *this;
	}

	// 2 倍扩容
	void push_back(char ch)
	{
		if (m_size == m_capacity) {
			reserve(m_capacity == 0 ? 1 : m_capacity * 2);
		}
		m_data[m_size++] = ch;
		m_data[m_size] = '\0';
	}

	void pop_back()
	{
		if (m_size > 0) {
			m_data[--m_size] = '\0';
		}
	}

	size_t find(const char* target, size_t pos = 0) const
	{
		if (pos > m_size) return npos;
		const char* found = std::strstr(m_data + pos, target);
		return found ? static_cast<size_t>(found - m_data) : npos;
	}

	size_t find(char ch, size_t pos = 0) const
	{
		for (size_t i = pos; i < m_size; ++i) {
			if (m_data[i] == ch) return i;
		}
		return npos;
	}

	size_t find(const MyString& str, size_t pos = 0) const
	{
		return find(str.m_data, pos);
	}

	MyString substr(size_t pos = 0, size_t count = npos) const
	{
		if (pos > m_size) throw std::out_of_range("MyString::substr");
		size_t len = std::min(count, m_size - pos);
		MyString result;
		result.reserve(len);
		result.m_size = len;
		std::memcpy(result.m_data, m_data + pos, len);
		result.m_data[len] = '\0';
		return result;
	}

	void swap(MyString& other) noexcept
	{
		std::swap(m_data, other.m_data);
		std::swap(m_size, other.m_size);
		std::swap(m_capacity, other.m_capacity);
	}

	int compare(const MyString& other) const noexcept
	{
		return std::strcmp(m_data, other.m_data);
	}

	iterator       begin()        noexcept { return m_data; }
	iterator       end()          noexcept { return m_data + m_size; }
	const_iterator begin()  const noexcept { return m_data; }
	const_iterator end()    const noexcept { return m_data + m_size; }
	const_iterator cbegin() const noexcept { return m_data; }
	const_iterator cend()   const noexcept { return m_data + m_size; }

	// operator+
	friend MyString operator+(const MyString& lhs, const MyString& rhs)
	{
		MyString result;
		result.reserve(lhs.m_size + rhs.m_size);
		result.append(lhs.m_data, lhs.m_size);
		result.append(rhs.m_data, rhs.m_size);
		return result;
	}

	// 比较运算符：先比 size 做短路优化
	friend bool operator==(const MyString& a, const MyString& b) noexcept
	{
		return a.m_size == b.m_size && std::memcmp(a.m_data, b.m_data, a.m_size) == 0;
	}
	friend bool operator!=(const MyString& a, const MyString& b) noexcept { return !(a == b); }
	friend bool operator< (const MyString& a, const MyString& b) noexcept { return a.compare(b) < 0; }
	friend bool operator<=(const MyString& a, const MyString& b) noexcept { return a.compare(b) <= 0; }
	friend bool operator> (const MyString& a, const MyString& b) noexcept { return a.compare(b) > 0; }
	friend bool operator>=(const MyString& a, const MyString& b) noexcept { return a.compare(b) >= 0; }

private:
	// 追加 len 个字符到末尾
	void append(const char* str, size_t len)
	{
		if (m_size + len > m_capacity) {
			reserve(std::max(m_capacity * 2, m_size + len));
		}
		std::memcpy(m_data + m_size, str, len);
		m_size += len;
		m_data[m_size] = '\0';
	}

	char* m_data;
	size_t m_size;
	size_t m_capacity;
};
一些小细节

比较运算符

关于比较运算符的重载，C++20提供了更高效的 <=> 运算符重载，可以更高效的重载比较运算符，所以上面的代码可以修改为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <compare>
// ...
friend bool operator==(const MyString& a, const MyString& b) noexcept
{
    return a.m_size == b.m_size && std::memcmp(a.m_data, b.m_data, a.m_size) == 0;
}

friend std::strong_ordering operator<=>(const MyString& a, const MyString& b) noexcept
{
    int result = std::strcmp(a.m_data, b.m_data);
    if (result < 0) return std::strong_ordering::less;
    if (result > 0) return std::strong_ordering::greater;
    return std::strong_ordering::equal;
}

对于比较结果，C++20提供了三种不同强度的类型：

1
2
3

std::strong_ordering	// ：强排序，equal时两个值完全相同，可以相互替换（枚举、字符串、Point值类型等）
std::weak_ordering		// ：弱排序，equal时两个值不一定完全相同，仅仅在判断时表示相同
std::partial_ordering   // ：部分排序，相比于weak_ordering，还多了一个 unordered 状态，表示两个值无法比较大小

友元

C++ 中有三种友元形式：友元函数、友元类、友元成员函数：

友元函数

类内定义的友元函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Object {
public:
	Object(size_t size) : m_size(size) {}
    // 在类体内部直接定义
    friend bool operator==(const Object& a, const Object& b) noexcept
    {
        return a.m_size == b.m_size;
    }
private:
    size_t m_size;
};

这种定义方式会使得函数在全局命名空间不可见，只有当参数中包含Object类时，才会在Object的命名空间中查找该函数。对于Object(2) == 2 和 2 == Object(2)，如果没有friend，后者会编译失败（在C++20之前）。

C++20之后引入了新的 == 运算符规则，允许编译器翻转运算符两边的内容）。

普通友元函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Object {
public:
	Object(size_t size) : m_size(size) {}
	friend bool operator==(const Object& a, const Object& b) noexcept;  // 声明
private:
    size_t m_size;
};

// 在类外部定义
friend bool operator==(const Object& a, const Object& b) noexcept
{
    return a.m_size == b.m_size;
}

适用于同时需要访问两个类的私有成员的场景。

友元类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Object {
public:
	Object(size_t size) : m_size(size) {}
	friend class OtherClass;
private:
    size_t m_size;
};

class OtherClass {
public:
    void print(const Object& obj) {
        std::cout << obj.m_size << std::endl;  // 可以访问对方的私有成员，且单向访问
    }
};

友元成员函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class B; // 前向声明

class A {
public:
    void inspect(const B& b);  // 需要访问 B 的私有成员
};

class B {
    friend void A::inspect(const B& b);  // 只授权 A 的这一个函数
private:
    int m_secret = 42;
};

void A::inspect(const B& b) {
    std::cout << b.m_secret;  // 可以访问对方的私有成员，且单向访问
}

std::vector

堆、栈

std::map

线程池

无锁队列

Algorithm Template

排序

快速排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 快速排序
int _Partition(std::vector<int>& arr, int first, int last)
{
	if (first == last) return first;

	int posVal = arr[last];
	int i = first;
	for (int j = first; j < last; j++)
	{
		if (arr[j] < posVal)
			std::swap(arr[i++], arr[j]);
	}
	std::swap(arr[i], arr[last]);
	return i;
}

void QuickSort(std::vector<int>& arr, int first, int last)
{
	if (first >= last) return;
	int pos = _Partition(arr, first, last);
	QuickSort(arr, first, pos - 1);
	QuickSort(arr, pos + 1, last);
}

时间复杂度：

对于理想待排序数组，即每次都能正好平均分原始数组时，树的递归深度（即“循环次数”）为：将数组长度N除以2直到长度为1或0的次数，即：N/2^x = 1，x = log2N。对于每一层树的处理，所有节点长度总是N，所以最终复杂度为：O(NlogN)。

对于最坏情况，即每次拆分数组都只能将原始数组分成0和n - 1的两个子数组，此时循环次数会退化回N，时间复杂度也来到最差情况：O(N^2)

对于std::sort，内部在选基准点时会选取前、中、后三个基准点，并取居中的数作为基准以避免极端情况，当递归次数过多时也会退化为“堆排序”。

快速排序的优势在于：每次处理子数组都是顺序处理，CPU友好，并且空间复杂度为递归深度O(logN)，且没有资源拷贝开销。

Partition

上面的快排的Partition实现采用了快慢指针法，代码实现精简，但是可以注意到，对于近乎有序的数组，比如：

1

std::vector<int> arr{1, 2, 3, 4, 5, 6, 7};

在初次排序时，需要swap七次才能将数字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
27

int _Partition2(std::vector<int>& arr, int first, int last)
{
	int pivot = arr[last];
	int left = first;
	int right = last - 1;
	while (true)
	{
		while (left <= right && arr[left] < pivot) {
			left++;
		}

		while (left <= right && arr[right] >= pivot) {
			right--;
		}

		if (left >= right) {
			break;
		}

		std::swap(arr[left], arr[right]);
		left++;
		right--;
	}

	std::swap(arr[left], arr[last]);
	return left;
}

这种算法可以尽量避免不必要的交换，一定程度上提高排序的速度，毕竟Partition的目的只是分区。

如果要支持迭代器类型，可以将参数做如下修改：

 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

template <typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
RandomIt partition(RandomIt first, RandomIt last, Compare comp = Compare{}) {
	if (first == last) return first;

	auto pivot_it = std::prev(last);
	auto& pivot_val = *pivot_it;
	auto store = first;

	for (auto it = first; it != pivot_it; ++it) {
		if (comp(*it, pivot_val)) {
			std::swap(*it, *store);
			++store;
		}
	}
	std::swap(*store, *pivot_it);
	return store;
}

template <typename RandomIt, typename Compare = std::less<typename std::iterator_traits<RandomIt>::value_type>>
void quick_sort(RandomIt first, RandomIt last, Compare comp = Compare{}) {
	if (std::distance(first, last) <= 1) return;

	auto pivot_pos = ::partition(first, last, comp);
	quick_sort(first, pivot_pos, comp);
	quick_sort(std::next(pivot_pos), last, comp);
}

这里的RandomIt可以换成C++20的std::random_access_iterator，以限制迭代器为随机访问迭代器，否则当传入的迭代器类型为双向迭代器时，std::distance复杂度会退化成O(n)，通过while (++it)来前进计算距离。

同时对于一长串的迭代器类型萃取，c++14提供了透明比较器 std::less<>，可以在进行比较时根据传入的参数来生成相应的实例化代码，区别在于前者仅支持相同类型的 ‘<’ 比较。

归并排序

 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

void _MergeRecursive(std::vector<int>& arr, std::vector<int>& temp, int first, int mid, int last)
{
	int tempIndex = first;
	int i = first, j = mid + 1;
	while (i <= mid && j <= last)
	{
		if (arr[i] <= arr[j])
			temp[tempIndex++] = arr[i++];
		else
			temp[tempIndex++] = arr[j++];
	}
	while (i <= mid) temp[tempIndex++] = arr[i++];
	while (j <= last) temp[tempIndex++] = arr[j++];

	for (int k = first; k <= last; k++)
		arr[k] = temp[k];
}

void MergeSortImpl(std::vector<int>& arr, std::vector<int>& temp, int first, int last)
{
	if (first >= last) return;
	int mid = first + (last - first) / 2;
	MergeSortImpl(arr, temp, first, mid);
	MergeSortImpl(arr, temp, mid + 1, last);
	_MergeRecursive(arr, temp, first, mid, last);
}

void MergeSort(std::vector<int>& arr, int first, int last)
{
	std::vector<int> temp(arr);  // 复用数组
	MergeSortImpl(arr, temp, first, last);
}

并查集

Trie 树

LRU

 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
44

// LRU
class LRUCache {
	using ListNode = std::pair<int, int>;
public:
	LRUCache(int capacity) :cap(capacity) {}

	int get(int key) {
		int value = -1;
		if (map.find(key) != map.end()) 
		{
			value = map[key]->second;
			lists.splice(lists.begin(), lists, map[key]);
			map[key] = lists.begin();
		}
		return value;
	}

	void put(int key, int value) {
		if (map.find(key) != map.end())
		{
			map[key]->second = value;
			lists.splice(lists.begin(), lists, map[key]);
			map[key] = lists.begin();
		}
		else
		{
			lists.push_front({key, value});
			if (lists.size() > cap)
			{
				auto it = lists.back();
				map.erase(it.first);
				lists.pop_back();
			}
			map[key] = lists.begin();
		}
	}

private:
	int cap;
	std::list<ListNode> lists;
	std::unordered_map<int, std::list<ListNode>::iterator> map;
};

// TODO LRU-K

二叉平衡树

Qt

OpenGL

杂项记录

glBufferData

glBufferData是用来向GPU申请缓存的函数：

1
2
3
4
5
6

void glBufferData(
    GLenum target,
    GLsizeiptr size,
    const void *data,
    GLenum usage
);

其中target不同，用处不同：

target含义
GL_ARRAY_BUFFER顶点数据
GL_ELEMENT_ARRAY_BUFFER索引数据
GL_UNIFORM_BUFFERuniform 数据
GL_SHADER_STORAGE_BUFFER计算数据
GL_PIXEL_UNPACK_BUFFER纹理上传

针对data参数，传入非空时会将数据从CPU copy到 GPU，传NULL时会等待glBufferSubData或glMapBuffer写数据（与usage参数无关）。

最后一个usage参数不会改变 API 行为，其作用是调整OpenGL驱动对GPU缓存的优化策略：

usage含义
GL_STATIC_DRAW数据几乎不变
GL_DYNAMIC_DRAW会偶尔修改
GL_STREAM_DRAW每帧更新

所以，对于GL_STATIC_DRAW，也可以在申请缓存时将data字段传NULL，但是会导致每次调用glBufferSubData时消耗增加。

glBufferSubData 与 glMapBuffer

  • glBufferSubData

    当glBufferData 的数据部分传空时需要使用glBufferSubData进一步动态更新数据：

    1
2

    glBindBuffer(GL_ARRAY_BUFFER, vbo);
glBufferSubData(GL_ARRAY_BUFFER, 0, size, data);

    这里会存在一个pipeline stall(或CPU stall)，即GPU流水线上堆积了任务，正在使用该缓存，但是此时CPU又要进行写入，这就会造成CPU的等待，可以通过buffer orphaning(缓存孤立)来缓解这种停顿现象：

    1
2
3

    glBindBuffer(GL_ARRAY_BUFFER, vbo);
glBufferData(GL_ARRAY_BUFFER, size, NULL, GL_DYNAMIC_DRAW);
glBufferSubData(GL_ARRAY_BUFFER, 0, size, data);

  • glMapBuffer

    1
2
3
4

    glBindBuffer(GL_ARRAY_BUFFER, vbo);
void* ptr = glMapBuffer(GL_ARRAY_BUFFER, GL_WRITE_ONLY);
// use ptr to copy data
glUnmapBuffer(GL_ARRAY_BUFFER);

    可以直接将数据从文件拷贝到共享buffer，减少拷贝？（是否可以类比于Linux下的mmap？）

    glMapBuffer 与 glBufferSubData，返回 ·SteveStreeting.com 有博客提到在大数据量的情况下glMapBuffer性能高于glBufferSubData，并且存在一个阈值。

glEnableVertexAttribArray 和 glVertexAttribPointer

glDrawElements 和 glDrawArrays

场景问题