cpp2
cpp八股2
实现三个智能指针
首先是 UniquePtr，它是独占式的智能指针，不能被复制，只能被移动。
1 | template<typename T> |
在C++03中引入了一个 std::auto_ptr，它的思想也是将资源独占。但是它的实现内允许使用复制构造函数和复制赋值运算符，这会导致一些问题，例如在函数传参时会发生资源的转移，导致原来的指针变成空指针。以及它和STL容器结合会产生一堆未定义行为，例如一个 std::vector 存 std::auto_ptr ，如果使用 reserve 或者扩容触发内存重新分配，会导致可能一部分 std::auto_ptr 为空。
后续C++11引入了右值引用和移动语义的概念，这十分符合资源独占的需求，因此 std::auto_ptr 被废弃了，取而代之的是 std::unique_ptr。
然后是 SharedPtr，它是共享式的智能指针，允许多个指针共享同一个资源，通过引用计数来管理资源的生命周期。
前面的文章已经给了一个实现，但是我们这里由于要同时实现 WeakPtr ，而如果将进行引用计数特化为另一个类 ControlBlock 的话，那么 SharedPtr 和 WeakPtr 就能够共享这个 ControlBlock，实现会更加自然：
1 | template<typename T> |
面试的时候如果被问到智能指针的实现细节，我会将 UniquePtr 单独拎出来讲，它的Big Five中的拷贝构造和拷贝赋值直接删除掉，移动构造和移动赋值实现资源转移，析构函数负责释放资源。可以提一下 std::auto_ptr 的问题，以及为什么被废弃了。然后讲 SharedPtr 和 WeakPtr 的实现细节，重点讲解 ControlBlock 的设计，俩智能指针的Big Five怎么写，以及如何通过引用计数来管理资源的生命周期。
也可以稍微提一提RAII相关的东西。
排序算法
冒泡排序：通过交换相邻元素，每次迭代将最大的元素“冒泡”到数组的末尾。时间复杂度为O(n^2)，空间复杂度为O(1)。
1 | void BuddleSort(std::vector<int>& arr) |
插入排序：前后分为已排序和未排序两部分，每次从未排序部分取一个元素，插入到已排序部分的正确位置。时间复杂度为O(n^2)，空间复杂度为O(1)。
1 | void InsertionSort(std::vector<int>& arr) |
选择排序：一直选择未排序部分里最小的元素，放到已排序部分的末尾。时间复杂度为O(n^2)，空间复杂度为O(1)。
1 | void SelectionSort(std::vector<int>& arr) |
快速排序：使用 Partition 函数将数组分成两部分，一部分小于基准值，另一部分大于基准值，然后递归地对两部分进行排序。平均时间复杂度为O(n log n)，最坏情况为O(n^2)，空间复杂度为O(log n)（递归栈空间）。
1 | size_t Partition(std::vector<int>& arr, size_t l, size_t r) |
堆排序：将数组原地建堆，然后不断将堆顶元素与末尾元素交换，并调整堆。时间复杂度为O(n log n)，空间复杂度为O(1)。
1 | void Heapify(std::vector<int>& arr, size_t n, size_t i) |
注意建堆本身是O(n)的。
归并排序：可以写成递归或迭代两种形式，主要的idea是二路有序数组的合并。时间复杂度为O(n log n)，空间复杂度为O(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
27
28
29
30
31void MergeSortRecursive(std::vector<int>& arr, size_t l, size_t r)
{
if(l >= r)
{
return;
}
size_t mid = l + (r - l) / 2;
MergeSortRecursive(arr, l, mid);
MergeSortRecursive(arr, mid + 1, r);
std::vector<int> tmp(r-l+1);
size_t i{l}, j{mid+1}, k{};
while(i <= mid && j <= r)
{
if(arr[i] <= arr[j]) // 注意这里是 <=，保持稳定性
{
tmp[k++] = arr[i++];
}
else
{
tmp[k++] = arr[j++];
}
}
while(i <= mid) tmp[k++] = arr[i++];
while(j <= r) tmp[k++] = arr[j++];
for(size_t idx = 0; idx < tmp.size(); ++idx)
{
arr[l + idx] = tmp[idx];
}
}
迭代： 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
36void MergeSortIterative(std::vector<int>& arr)
{
size_t n = arr.size();
if (n < 2)
{
return;
}
std::vector<int> tmp(n);
for (size_t width = 1; width < n; width *= 2)
{
for(size_t i = 0; i < n; i += width * 2)
{
size_t l = i;
size_t mid = std::min(i + width, n);
size_t r = std::min(i + width * 2, n);
size_t p = l, q = mid;
size_t k = l;
while(p < mid && q < r)
{
if(arr[p] <= arr[q])
{
tmp[k++] = arr[p++];
}
else
{
tmp[k++] = arr[q++];
}
}
while(p < mid) tmp[k++] = arr[p++];
while(q < r) tmp[k++] = arr[q++];
}
arr.swap(tmp);
}
}
基数排序：对每个位做桶排序，在低关键字有序的基础上对高关键字进行排序。时间复杂度为O(d*(n+b))，其中d是数字的位数，b是基数（例如10）。空间复杂度为O(n+b)。
1 | void RadixSortLSD(std::vector<int>& arr) |
排序稳定性：稳定指相同元素在排序后相对位置不变。冒泡、插入、归并和基数排序是稳定的，而选择、快速和堆排序是不稳定的。
选择排序不稳定是因为在交换最值和当前值的时候，当前值的与其它相同的值的相对位置可能会发生改变。快速排序不稳定是因为在分区过程中，元素的相对位置可能会被改变（和选择排序一样有大范围的 swap ）。堆排序不稳定是因为在调整堆的过程中，元素的相对位置可能会被改变。
手写堆
主要操作为 SiftUp 和 SiftDown ，按照堆的性质实现即可： 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
85template<typename T>
class MaxHeap {
public:
MaxHeap() = default;
MaxHeap(const std::vector<T>& elements) {
heap = elements;
// O(n) 建堆
for(int i = heap.size() / 2 - 1; i >= 0; --i)
SiftDown(i);
}
void Insert(const T& value) {
heap.push_back(value);
SiftUp(heap.size() - 1);
}
const T& Top() const {
if(heap.empty())
throw std::runtime_error("Heap is empty");
return heap[0];
}
void Pop() {
if(heap.empty())
throw std::runtime_error("Heap is empty");
heap[0] = heap.back();
heap.pop_back();
if(!heap.empty())
SiftDown(0);
}
void EraseAt(size_t idx) {
if(idx >= heap.size())
throw std::out_of_range("Index out of range");
size_t last = heap.size() - 1;
if(idx != last)
std::swap(heap[idx], heap[last]);
heap.pop_back();
if(idx >= heap.size())
return;
if(idx > 0 && heap[idx] > heap[(idx - 1) / 2])
SiftUp(idx);
else
SiftDown(idx);
}
size_t Size() const {
return heap.size();
}
bool Empty() const {
return heap.empty();
}
private:
std::vector<T> heap;
void SiftDown(size_t idx)
{
size_t n = heap.size();
while(true)
{
size_t left = idx * 2 + 1;
size_t right = idx * 2 + 2;
size_t largest = idx;
if(left < n && heap[left] > heap[largest])
largest = left;
if(right < n && heap[right] > heap[largest])
largest = right;
if(largest == idx)
break;
std::swap(heap[idx], heap[largest]);
idx = largest;
}
}
void SiftUp(size_t idx)
{
while(idx > 0)
{
size_t parent = (idx - 1) / 2;
if(heap[idx] > heap[parent])
{
std::swap(heap[idx], heap[parent]);
idx = parent;
}
else
break;
}
}
};
Placement new
所谓的定位放置new，它只在给定地址上执行构造函数。后面给出例子讲明。
Forwarding Reference
Forwarding Reference（万能引用）是C++11 引入的特殊引用形式（仅 T&&/auto&& ），在「类型推导」场景下，可根据绑定的实参值类别（左值 / 右值），通过「引用折叠」自动实例化为左值引用（绑定左值时）或右值引用（绑定右值时），从而兼容左值和右值。
1 | template<typename T> |
它会实例化以下两种版本：
1 | void testForward(int && v){} // case 1 |
std::remove_reference
这个东西我单独拿出来讲讲，在 std::move 和 std::forward 中你能看到这玩意。MSVC的实现如下： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20_EXPORT_STD template <class _Ty>
struct remove_reference {
using type = _Ty;
using _Const_thru_ref_type = const _Ty;
};
template <class _Ty>
struct remove_reference<_Ty&> {
using type = _Ty;
using _Const_thru_ref_type = const _Ty&;
};
template <class _Ty>
struct remove_reference<_Ty&&> {
using type = _Ty;
using _Const_thru_ref_type = const _Ty&&;
};
_EXPORT_STD template <class _Ty>
using remove_reference_t = typename remove_reference<_Ty>::type;
这个东西事实上非常简单，它用到了类模板的偏特化（对于左值引用和右值引用分别做了特化），它的作用是去掉类型中的引用部分，得到一个纯粹的类型。对于 T& 和 T&& 都会得到 T，而对于非引用类型则保持不变。
std::move
1 | _EXPORT_STD template <class _Ty> |
要理解这个看似很简单的函数，我们需要对Type和Value Category有一个清晰的认识。
相信你看到上面这个 std::move 的实现，有这么一个疑问，为什么 int&& x=5 中的 x 作为一个右值引用，它是个左值。而 static_cast<int&&>(x) 和前面的 x 一样都是 int&& ，但是个右值？
这是因为 int&& 是 Type，而同一个Type，可能有不同的Value Category。对于右值引用 x ，它可以进行取地址操作。而经过 static_cast 变换后得到的是一个表达式，它不能进行取地址，因此它是一个右值。
因此我们可以理解 std::move 的核心原理：通过 static_cast 生成一个 无名的右值引用类型表达式。
std::forward
MSVC的实现如下：
1 | _EXPORT_STD template <class _Ty> |
可以看到 forward 重载了左值和右值两个版本。主要用的都是第一个版本。第二个版本主要用于防止某些sb将右值通过 std::forward 转发成左值的情况。
我们先探讨 std::forward 的应用场景。前面我们讲过Forwarding Reference，那么当函数通过Forwarding Reference接受参数，这时候编译器是不知道其值类别（Value Category，即左值还是右值）的。如果我们将该参数转发给另一个函数，且要通过其值类别正确地调用其左值或右值的重载版本，那么就需要 std::forward 来保持参数的值类别。后面我们会以 std::vector 的 emplace_back 为例来说明。
首先C++规定使用 std::forward 时需要显式指定模板参数。这个参数直接决定了转发后得到的是左值还是右值。int & 这种左值引用类型会导致转发后得到一个左值，而 int 或者 int&& 这种类型会导致转发后得到一个右值。
我写了一个测试程序： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void print(int&& x)
{
std::cout << "rvalue " << x << std::endl;
}
void print(int& x)
{
std::cout << "lvalue " << x << std::endl;
}
int main() {
int x = 10;
print(std::forward<int>(10)); // rvalue 10
print(std::forward<int&>(x)); // lvalue 10
print(std::forward<int>(x)); // rvalue 10，虽然x是个左值，但是我们通过std::forward<int>将它转发成了一个右值
//print(std::forward<int&>(10)); // 右值不能通过std::forward转换为左值，重载2的static_assert会触发，编译错误
return 0;
}
可以单方面认为 std::forward 包含了 std::move 的功能。但是首先 std::forward 需要显示指名模板参数，其次语义不符合，在特定情况下还是使用可读性比较好的 std::move 来表达转移语义比较好。
完美转发
纯纯的误区：完美转发就是
std::forward。这种要是面试答了直接就露馅了。
所谓的完美转发指的是一种需求：在模板函数中，通过Forwarding Reference即万能引用接受任意Value Category的参数，并将该参数转发给另一个函数时，能够完全保留其Value Category。
因此，完美转发=Forwarding Reference + std::forward （或许再加个引用折叠）。
我们来看一个例子，即 std::vector 的 emplace_back 的实现。
首先看MSVC中 push_back 和 emplace_back 的实现：
1 | template <class... _Valty> |
可以看到 push_back 有两个版本，一个接受左值，一个接收右值。二者都不是函数模板。
而 emplace_back 是一个函数模板，参数是万能引用的不定长参数列。其内部调用了 _Emplace_one_at_back 。我们重点看一下 _Emplace_back_with_unused_capacity ，它是 _Emplace_one_at_back 的一个分支，专门处理有剩余容量的情况：
1 | template <class... _Valty> |
根据条件编译区分构造是否可能抛异常来选择不同的构造方式。无论哪种方式，核心都是通过 std::forward 来完美转发参数，以保持参数的值类别，从而正确调用对应的构造函数。对于 Construct_in_place 来说，其内部采用了 Placement new 来在指定内存位置构造对象： 1
2
3
4
5
6
7
8
9
10
11
12template <class _Ty, class... _Types>
_CONSTEXPR20 void _Construct_in_place(_Ty& _Obj, _Types&&... _Args)
noexcept(is_nothrow_constructible_v<_Ty, _Types...>) {
if (_STD is_constant_evaluated()) {
_STD construct_at(_STD addressof(_Obj), _STD forward<_Types>(_Args)...);
} else
{
::new (static_cast<void*>(_STD addressof(_Obj))) _Ty(_STD forward<_Types>(_Args)...);
}
}
这里我们回答一下 push_back 和 emplace_back 的区别：emplace_back 除了支持 copy 和 move构造外，还支持直接构造。如果类型不支持move构造，并且copy构造代价比较大的时候，使用 emplace_back 可以获得更多性能。然而在某些特定情况下，使用 emplace_back 可能导致函数模板创建过多，例如频繁转发 const char(&)[] 这种类型的字符串字面量时，会导致每次调用 emplace_back 都实例化一个新的函数模板版本，从而增加编译时间和代码体积。此时如果直接使用 push_back 来传递字符串字面量，虽然会有一次额外的复制，但可以避免过多的函数模板实例化。
二者传递参数都使用了完美转发，用来匹配正确的构造函数重载版本。
内存池
我们知道，在STL中有一个经典的内存管理策略，叫做二级配置器。第一级处理大内存块（通常>=128字节）的分配和释放，直接调用操作系统的内存分配函数（如 malloc 和 free ）。第二级处理小内存块（<128字节）的分配和释放，使用一个叫做内存池+自由链表的机制来管理这些小块内存。
内存池的作用有两点：减少系统调用+减少外部碎片。
我们来简单复刻一下STL的空闲链表和内存池，大部分都是vibe的： 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// ===================== 核心常量定义 =====================
const size_t __ALIGN = 8; // 8字节对齐
const size_t __MAX_BYTES = 128; // 小内存阈值：<128字节用内存池，≥128用malloc
const size_t __NFREELISTS = __MAX_BYTES / __ALIGN; // 16个自由链表（8~128字节）
const size_t __NOBJS = 20; // 内存池每次批量申请20个块
// ===================== 自由链表节点 =====================
// 共用体：节省空间，要么存链表指针，要么存用户数据
union FreeNode
{
FreeNode* next; // 指向下一个空闲块的指针（链表用）
char data[1]; // 用户实际使用的内存（仅占位）
};
// ===================== 内存分配器核心类 =====================
class STLAllocator
{
private:
static FreeNode* free_list[__NFREELISTS];
static char* start_free;
static char* end_free;
// 神奇位运算
static size_t round_up(size_t bytes)
{
return (bytes + __ALIGN - 1) & ~(__ALIGN - 1);
}
static size_t free_list_index(size_t bytes)
{
return (round_up(bytes) / __ALIGN) - 1;
}
// 核心函数：内存池扩容 + 填充自由链表
static void* refill(size_t size)
{
// step1: 计算要申请的总字节数（20个size大小的块）
size_t nobjs = __NOBJS;
char* chunk = (char*)malloc(size * nobjs); // 批量申请大块内存
if (!chunk)
{
std::cerr << "内存池扩容失败！" << std::endl;
return nullptr;
}
// step2: 更新内存池指针（标记未拆分区域）
start_free = chunk;
end_free = chunk + size * nobjs;
// step3: 找到对应size的自由链表
size_t index = free_list_index(size); // 比如size=8→index=0
FreeNode*& my_free_list = free_list[index]; // 对应自由链表的头指针
// step4: 将大块内存拆分成size大小的块，串成自由链表
FreeNode* free_list_head = (FreeNode*)chunk; // 第一个块（返回给用户）
my_free_list = (FreeNode*)(chunk + size); // 第二个块作为自由链表的新头
FreeNode* curr = my_free_list; // 从第二个块开始串
// 拆分剩余18个块（总共20个：1个返回+19个挂链表）
for (size_t i = 2; i < nobjs; ++i)
{
curr->next = (FreeNode*)(chunk + i * size);
curr = curr->next;
}
curr->next = nullptr; // 链表尾
// step5: 返回第一个块给用户，剩余19个块已挂到自由链表
return free_list_head;
}
public:
static void* allocate(size_t bytes)
{
if (bytes == 0)
return nullptr;
// 情况1：大内存（≥128字节）→ 直接调用malloc
if (bytes >= __MAX_BYTES)
{
std::cout << "[大内存] 分配 " << bytes << " 字节 → 调用malloc" << std::endl;
return malloc(bytes);
}
// 情况2：小内存（<128字节）→ 走自由链表+内存池
size_t align_bytes = round_up(bytes); // 8字节对齐
size_t index = free_list_index(bytes); // 找到对应自由链表
FreeNode*& my_free_list = free_list[index]; // 对应链表的头指针
if(my_free_list)
{
std::cout << "[小内存] 分配 " << bytes << " 字节（对齐后" << align_bytes << "）→ 从自由链表取" << std::endl;
FreeNode* result = my_free_list;
my_free_list = result->next;
return result;
}
std::cout << "[小内存] 分配 " << bytes << " 字节 → 自由链表空，内存池扩容" << std::endl;
return refill(align_bytes);
}
// ===================== 对外接口：释放内存 =====================
static void deallocate(void* p, size_t bytes)
{
if (!p)
return;
// 情况1：大内存 → 直接调用free
if (bytes >= __MAX_BYTES)
{
std::cout << "[大内存] 释放 " << bytes << " 字节 → 调用free" << std::endl;
free(p);
return;
}
// 情况2：小内存 → 插回对应自由链表
size_t align_bytes = round_up(bytes);
size_t index = free_list_index(bytes);
FreeNode*& my_free_list = free_list[index];
std::cout << "[小内存] 释放 " << bytes << " 字节（对齐后" << align_bytes << "）→ 插回自由链表" << std::endl;
FreeNode* node = (FreeNode*)p;
node->next = my_free_list; // 头插：将块插回链表头部
my_free_list = node;
}
};
// ===================== 静态成员初始化 =====================
FreeNode* STLAllocator::free_list[__NFREELISTS] = {nullptr};
char* STLAllocator::start_free = nullptr;
char* STLAllocator::end_free = nullptr;