0%

博客文章引导

Website

我的博客, 即劳振煜的知識倉儲, 也就是您当前访问的博客.

博客是基于 Hexo 的静态博客, 部署于我的 Github 上.

该博客主要用来记录我在学习以及未来工作中的所感所悟. 留作记录以便自己在未来温故或帮助到正在看博客的你.

博客的内容区别于 Github 的内容, 主要是博客将会记录完整的有体系的内容, 而 Github 上的各个仓库主要是用于记录学习笔记与实验, 自己造轮子, 学习他人的开源项目.


C++

STL

数据结构

计算机网络

操作系统

设计模式

Leetcode

Github仓库引导

我的Github, 也就是上方链接. 你可以搜索 OXygenPanda 访问.

虽然没有很多 star, 但是仍然坚持学习, 坚持记录, 坚持分享.


计算机网络课程学习 - 韩立刚老师

记录计算机网络课程学习的笔记

深入理解操作系统课程学习 - 清华大学

记录清华大学深入理解操作系统课程学习的笔记

红黑树

名称 : 红黑树

优点 :

相较AVL树来说, 平衡条件宽松, 减少了很多因插入删除节点导致的调整. 适合于插入删除频繁的情况.

AVL树适合于插入删除较少, 搜索较多的情况.

平衡条件 :

  1. 每个节点非黑即红
  2. 根节点是黑色
  3. 叶节点(NIL)是黑色 NIL : 虚拟空节点
  4. 如果一个节点是红色, 则它的两个子节点都是黑色的
  5. 从根节点触发到所有叶节点路径上, 黑色节点数量相同 (最长是最短路径的2倍 : 长边红黑相间, 短边黑色)

认识 :

平衡条件 4 和 5 限制了红黑树最长边和最短边的2倍长度关系. 本质上, 红黑树也是通过控制树高来保证平衡. 红黑树相比AVL树控制条件更弱, 因此插入删除调整的频次也会低. AVL树更适用于插入删除较少但是访问较多的情况.

快速排序

基础知识

名称 : 快速排序

性质 : 不稳定的排序算法

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 O(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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/************************************************************************
> File Name: quick_sort2.cpp
> Author: Lao Zhenyu
> Mail: LaoZhenyu_961112@163.com
> Created Time: 五 1/15 17:48:29 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void quickSort(vector<int> &arr, int left, int right){
if(left >= right) return;
int i,j,base;
base = arr[left];
i = left, j = right;
while(i < j){
while(arr[j] >= base && i < j)
j--;
while(arr[i] <= base && i < j)
i++;
if(i < j)
swap(arr[i], arr[j]);
}
arr[left] = arr[i];
arr[i] = base;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}



int main(){
vector<int> arr{1,3,2,6,5,4,9,7,8,};
quickSort(arr, 0, arr.size() - 1);
for(int n : arr){
cout << n << endl;
}
return 0;
}

归并排序

基础知识

名称 : 归并排序

性质 : 稳定的排序算法

作者 : 冯诺依曼

用途 : 分治思路的排序

复杂度 : 时间 O(nlogn) 空间 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
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
/************************************************************************
> File Name: merge_sort.cpp
> Author: Lao Zhenyu
> Mail: LaoZhenyu_961112@163.com
> Created Time: 四 1/14 20:38:22 2021
************************************************************************/

#include <iostream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
using namespace std;

void merge(vector<int> &arr, int left, int mid, int right){
vector<int> L(mid - left + 1);
vector<int> R(right - mid);
int i,j,k;
for(i = 0; i < L.size(); ++ i){
L[i] = arr[left + i];
}
for(j = 0; j < R.size(); ++ j){
R[j] = arr[mid + 1 + j];
}
i = 0;
j = 0;
k = left;
while(i < L.size() && j < R.size()){
if(L[i] >= R[j]){
arr[k] = R[j];
j++;
} else {
arr[k] = L[i];
i++;
}
k++;
}
while(i < L.size()){
arr[k] = L[i];
k++;
i++;
}
while(j < R.size()){
arr[k] = R[j];
k++;
j++;
}
}

void mergeSort(vector<int> &arr, int left, int right){
if(left < right){
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
return;
}


int main(){
vector<int> arr{1,3,2,4,5,6,9,7,8};
mergeSort(arr,0, arr.size() - 1);
for(auto n : arr){
cout << n << endl;
}
return 0;
}

AVL树

基础知识

名称 : AVL树

发明者 :

G. M. Adelson-Velsky

E.M. Landis

年代 : 1962年(58岁)

优点 :

由于对每个节点的左右子树的树高做了限制, 所以整棵树不会退化成一个链表

**学习重点 : **

  1. 平衡二叉排序树,本质上也是二叉排序树, 所以拥有二叉排序树的所有性质
  2. 平衡二叉排序树的学习重点, 在于平衡条件以及平衡调整的相关学习

性质 :

  1. 平衡条件 : | H(left) - H(right) | ≤ 1

思考 :

​ 高度为 H 的树, 所包含节点的范围是?

​ BinarySearchTree : H ≤ size ≤ 2^H - 1

​ AVLTree : low(H-2) + low(H-1) + 1 ≤ size ≤ 2^H - 1 (low(H) 是 H 高度的二叉树的最少节点数) 左边等于 1.5^H

操作SSS

AVL树 - 左旋

左旋前 左旋后 AVL树 - 右旋 右旋前 右旋后

失衡类型

h(1,2,3,4) 分别代表左孩子的左子树个高,左孩子的右子树高,右孩子的左子树高和右孩子的右子树高

LL类型:左子树的左孩子更高

满足条件 : h1 = max(h3, h4) + 2 = h2 + 1

调整方案 : K1 右旋

LR类型:左子树的右孩子更高

满足条件 : max(h2, h3) = h4 = h1

调整方案 : 小左旋, 大右旋(左孩子左旋, 根节点右旋)

RL类型:右子树的左孩子更高

调整方案 : 小右旋, 大左旋

RR类型:右子树的右孩子更高

调整方案 : K1 左旋

平衡调整策略

  1. 发生在回溯阶段的, 第一个失衡节点处
  2. 理解平衡调整策略的关键在于 : 分析清楚四种情况下, ABCD四棵子树树高的关系
  3. LL, 大右旋
  4. LR, 先小左旋, 再大右旋
  5. RL, 先小右旋, 再大左旋
  6. RR, 大左旋

代码关键点

  1. 插入和删除以后, 注意调整树高字段, 先调低的root, 再调高的tmp
  2. 引入了NIL节点, 代替了 NULL和nullptr, NULL不可访问资源, NIL是一个实际节点, 可以访问资源(h,lchild,rchild)

代码实现

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
#include <cstdio>
#include <iostream>
using namespace std;

#define L(n) (n->lchild)
#define R(n) (n->rchild)
#define H(n) (n->h)

typedef struct Node{
int key,h;
struct Node *lchild, *rchild;
}Node;

//虚拟空节点, 为红黑树做准备的节点
Node __NIL;
#define NIL (&__NIL)
__attribute__((constructor))
void init_NIL(){
NIL->key = 0, NIL->h = 0;
NIL->lchild = NIL->rchild = nullptr;
}
//优先初始化上面这一段代码


/*
* AVL树的若干操作:
* 1. 创建节点
* 2. 销毁节点
* 3. 插入
* 4. 删除
*/

Node *getNewNode(int key){
Node * tmp = (Node*)malloc(sizeof(Node));
tmp->key = key;
tmp->h = 1;
tmp->lchild = NIL, tmp->rchild = NIL;
return tmp;
}

void clear(Node * root){
if(root == NIL) return;
clear(root->lchild);
clear(root->rchild);
free(root);
return;
}

//调整高度
void update_height(Node * root){
root->h = (H(L(root)) > H(R(root)) ? H(L(root)) : H(R(root))) + 1;
}

//左旋
Node * left_rotate(Node * root){
Node * tmp = root->rchild; //新根节点
root->rchild = tmp->lchild; //新左挂旧右
tmp->lchild = root; //旧根挂新左
update_height(root);
update_height(tmp);
return tmp;
}

//右旋
Node * right_rotate(Node * root){
Node * tmp = root->lchild; //新根
root->lchild = tmp->rchild; //新右成旧左
tmp->rchild = root; //旧根成新左
update_height(root);
update_height(tmp);
return tmp;
}

//调整
Node * maintain(Node * root){
//平衡调整代码
if(abs(H(L(root)) - H(R(root))) <= 1) return root;
if(root->lchild->h > root->rchild->h) {
//LR先小左旋
if(root->lchild->lchild->h < root->lchild->rchild->h)
root->lchild = left_rotate(root->lchild);
//LL大右旋
root = right_rotate(root);
} else {
//RL先小右旋
if(root->rchild->rchild->h < root->rchild->lchild->h)
root->rchild = right_rotate(root->rchild);
//RR大左旋
root = left_rotate(root);
}
return root;
}

Node * insert(Node * root, int key){
if(root == NIL) return getNewNode(key);
if(root->key == key) return root;
if(key < root->key) root->lchild = insert(root->lchild, key);
if(key > root->key) root->rchild = insert(root->rchild, key);
update_height(root);
return maintain(root);
}

//寻找前驱节点,默认传入度为2的节点,前父节点有左子树
Node * predeccessor(Node * root){
Node * tmp = root->lchild;
while(tmp->rchild) tmp = tmp->rchild;
return tmp;
}

Node * erase(Node * root, int key){
if(root == NIL) return NIL;
if(key < root->key) {
root->lchild = erase(root->lchild, key);
} else if(key > root->key) {
root->rchild = erase(root->rchild, key);
} else { //删除当前节点
if(root->rchild == NIL || root->lchild == NIL){
Node * tmp = root->rchild != NIL ? root->rchild : root->lchild;
free(root);
return tmp;
} else { // 删除度为2的节点
Node * tmp = predeccessor(root);
root->key = tmp->key;
root->lchild = erase(root->lchild, root->key);
}
}
update_height(root);
return maintain(root);
}

void print(Node * root){
printf("(%d[%d], %d, %d)\n",
root->key, root->h,
root->lchild->key,
root->rchild->key
);
}


void output(Node * root){
if(root == NIL) return;
print(root);
output(root->lchild);
output(root->rchild);
return ;
}

int main(int argc, char ** argv){
int op, val;
Node* root = NIL;
while(~scanf("%d%d", &op, &val)){
switch(op){
case 0: root = erase(root, val); break;
case 1: root = insert(root, val); break;
}
output(root);
printf("------------\n");
}
return 0;
}

二叉排序树

基础知识

名称 : 二叉排序树, 二叉搜索树

性质 :

  1. 左子树 < 根节点
  2. 右子树 > 根节点

用途 : 解决与排名有关的检索需求

插入过程 : 根据插入节点值和根节点比较, 选择左子树或右子树继续比较, 最终放在叶子节点上

删除过程 :

  1. 删除叶子节点

    直接删除

  2. 删除度为1的节点

    把孩子交给祖父节点

  3. 删除度为2的节点

    中序遍历 : 10 17 20 28 29 30 32

    性质 : 待删除节点的前驱无右子树, 后继无左子树, 因此前驱后继一定不是度为2的节点

    将前驱或后继直接覆盖待删除节点后, 问题转换为删除叶子节点或者是度为1的节点

优化 :

  1. 删除掉处理度为0的代码逻辑,不影响代码整体功能
  2. 解决排名相关的检索需求,修改二叉搜索树的定义,增加size字段,记录每棵树的节点数目
    1. K == LS - 1 : 根节点就是排名第k的元素
    2. k <= LS : 排名第k位的元素在左子树中
    3. k > LS : $search_k(root->rchild, k - LS - 1)$
  3. 解决 top-k 问题,输出前k位的元素(找到小于第k位的所有元素)
    1. 根节点就是第k位元素, 输出左子树所有节点和根节点值
    2. 第k位元素在左子树中, 前k位元素全部在左子树中
    3. 第k位元素在右子树中, 说明左子树中的所有节点和根节点都是前k位元素
  4. 二叉排序树和快速排序的关系
    1. 二叉排序树是快速排序的逻辑结构
    2. 思考1: 快速排序算法的时间复杂度和二叉排序树建树时间复杂度之间的关系
    3. 思考2:快速选择算法和二叉排序树的关系

代码实现

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
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
using namespace std;

#define KEY(n) (n ? n->key : 0)
#define SIZE(n) (n ? n->size : 0)
#define L(n) (n ? n->lchild : 0)

typedef struct Node{
int key, size;
struct Node *lchild, *rchild;
}Node;

/*
* 二叉搜索树的若干操作:
* 1. 创建节点
* 2. 销毁节点
* 3. 查找
* 4. 插入
* 5. 删除
*/

/*
* 优化1: 将删除度为0和度为1的节点的代码合并
* 优化2: 实现查找第k位的元素
* 优化3: 实现输出前k位的元素(TOP-K)
*/

//更新树高
void update_size(Node * root){
root->size = SIZE(root->lchild) + SIZE(root->rchild) + 1;
}

//创建节点
Node * getNewNode(int key){
Node *p = (Node *)malloc(sizeof(Node));
p->key = key;
p->size = 1;
p->lchild = nullptr, p->rchild = nullptr;
return p;
}

//销毁树
void clear(Node * root){
if(root == nullptr) return;
clear(root->lchild);
clear(root->rchild);
free(root);
return;
}

//查找
int search(Node* root, int val){
if(root == nullptr) return 0;
if(root->key == val) return 1;
if(root->key > val) return search(root->lchild, val);
if(root->key < val) return search(root->rchild, val);
return 0;
}

//查找第k大的元素
int search_k(Node * root, int k){
if(root == nullptr) return -1;
if(SIZE(L(root)) == k - 1) return root->key;
if(k <= SIZE(L(root))) {
return search_k(root->lchild, k);
} else {
return search_k(root->rchild, k - SIZE(L(root)) - 1);
}
}

//插入
Node * insert(Node * root, int val){
if(root == nullptr) return getNewNode(val);
if(root->key == val) return root;
if(val < root->key) root->lchild = insert(root->lchild, val);
if(val > root->key) root->rchild = insert(root->rchild, val);
update_size(root);
return root;
}

//寻找前驱(默认父节点有左孩子)
Node * predecessor(Node * root){
Node * tmp = root->lchild;
while(tmp->rchild != nullptr) tmp = tmp->rchild;
return tmp;
}

//删除节点
Node * erase(Node * root, int val){
if(root == nullptr) return nullptr;
if(root->key > val)
root->lchild = erase(root->lchild, val);
else if(root->key < val)
root->rchild = erase(root->rchild, val);
else { //删除节点本身
//删除度为0的节点和度为1的节点操作相同
if(root->lchild == nullptr || root->rchild == nullptr){
Node * tmp = root->lchild ? root->lchild : root->rchild;
free(root);
return tmp;
} else { //删除度为2的节点
Node * tmp = predecessor(root);
root->key = tmp->key;
root->lchild = erase(root->lchild, tmp->key);
}
}
update_size(root);
return root;
}

//输出整棵树的所有节点 - 中序
void output(Node * root){
if(root == nullptr) return;
output(root->lchild);
printf("[%d, %d, %d, size : %d]\n",KEY(root),KEY(root->lchild),KEY(root->rchild),SIZE(root));
output(root->rchild);
return;
}

//输出前k个节点
void output_k(Node *root, int k){
if(k == 0 || root == nullptr) return;
if(k <= SIZE(L(root))){
output_k(root->lchild, k);
} else {
output(root->lchild);
printf("[%d, %d, %d, size : %d]\n",KEY(root),KEY(root->lchild),KEY(root->rchild),SIZE(root));
output_k(root->rchild, k - SIZE(L(root)) - 1);
}
return;
}


int main(int argc, char ** argv){

int op, val;

/* op :
* 0 查找
* 1 插入
* 2 删除
* 3 查找第k位的元素
* 4 输出前k位的元素
*/
Node * root = nullptr;
while(~scanf("%d%d", &op, &val)){
switch(op){
case 0: printf("search %d, result : %d\n", val, search(root, val)); break;
case 1: root = insert(root, val); break;
case 2: root = erase(root, val); break;
case 3: printf("search k %d, result : %d\n",val, search_k(root, val)); break;
case 4: {
printf("output top-%d elements\n",val);
output_k(root, val);
printf("----------------\n");
} break;
}
if(op != 0 && op != 4){
output(root);
printf("----------------\n");
}
}

return 0;
}

内存管理

Website

内存管理是一个很深刻的话题, 对于初学者来说, 内存管理看不到摸不着, 我们常使用 new / delete 来管理我们的堆内存. 仅此而已.

本文记录了侯捷老师内存管理课程的学习笔记以及部分自己写的代码.

目的是了解C++如何进行内存管理, 剖析源码, 能够设计自己的内存池.

C++中内存管理工具

分配 释放 类型 是否可以重载
malloc() free() C函数 不可以
new delete C++表达式 不可以
::operator new() ::operator delete() C++函数 可以
allocator<T>::allocate() allocator<T>::deallocate() C++标准库 可自由设计并搭配容器

用法示例

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
void* p1 = malloc(512); //512 bytes
free(p1);

complex<int>* p2 = new complex<int>; //one object
delete p2;

void* p3 = ::operator new(512); //512 bytes
::operator delete(p3);

#ifdef __GUNC__ //GNUC 2.9

void* p4 = alloc::allocate(512);
alloc::deallocate(p4,512); //得记得当初申请了多少的内存,比较适用于容器

#endif

/*************************/
#ifdef __GNUC__ //GNUC 4.9

//allocate() 和 deallocate() 是 non-static 必须由 object 调用
void* p4 = allocator<int>().allocate(7); //分配7个int的内存大小
allocator<int>().deallocate((int*)p4, 7);

//allocate() 和 deallocate() 是 non-static 必须由 object 调用
void* p5 = __gnu_cxx::__pool_alloc<int>().allocate(9); //分配9个int的内存大小
__gnu_cxx::__pool_alloc<int>().deallocate((int*)p5, 9);

#endif

new 运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
Complex* pc = new Complex(1,2);

编译器转换→

Complex *pc;
try{
void* mem = operator new(sizeof(Complex)); //allocate
pc = static_cast<Complex*>(mem); //cast
pc->Complex::Complex(1,2); //construct
//只有编译器才能够像上式直接调用 ctor
} catch (std::bad_alloc) {
//allocate 失败, 不执行 ctor
}

operator new() vc98默认版本

1
2
3
4
5
6
7
8
9
10
11
12
void * operator new(size_t size, const std::nothrow t&) _THROW0()
{ //try to allocate size bytes
void *p;
while((p == malloc(size)) == 0){
//buy more memory or return null pointer
_TRY_BEGIN
if(_callnewh(size) == 0) break;
_CATCH(std::bad_alloc) return 0;
_CATCH_END
}
return (p);
}

delete 运算符

1
2
3
4
5
6
7
8
Complex* pc = new Complex(1,2);
...
delete pc;

编译器转换->

pc->~Complex(); //先析构
operator delete(pc); //然后释放内存

operator delete() vc98默认版本

1
2
3
4
void __cdecl operator delete(void * p) _THROW0()
{ //free an allocated object
free(p);
}

array new / array delete

1
2
3
4
Complex * pca = new Complex[3];
//触发三次ctor
...
delete [] pca; //触发三次dtor

内存分配的时候, 头部会有 cookie 方便回收.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int * pi = new int[10];
delete pi;

vc6 : cookie
61h(记录大小是60字节,1表示使用了这一块)
Debugger Header(32 Bytes)
int
int
int
...
int
no man land
Pad(12 Bytes)
61h

placement new

1
new (p)

允许我们在已经申请的堆内存上, 构建一个对象.

placement new 没有对应的 placement delete, 因为 placement new操作并没有分配内存.

1
2
3
4
5
6
7
8
9
10
11
12
13
char * buf = new char[sizeof(Complex)*3];
Complex * pc = new (buf) Complex(1,2);
...
delete [] buf;

编译器->

Complex * pc;
try {
void * mem = operator new(sizeof(Complex), buf); //实际上不操作
pc = static_cast<Complex*>(mem); //cast
pc->Complex::Complex(1,2); //construct
}

C++应用程序分配内存的途径

应用程序

1
2
3
4
5
6
7
8
9
10
Foo *p = new Foo(x);
delete p;

编译器->不可以改变不可以重载

Foo *p = (Foo*)operator new(sizeof(Foo));
new (p) Foo(x);

p->~Foo();
operator delete(x);

operator new / operator delete

1
2
3
4
5
6
7
Foo *p = (Foo*)operator new(sizeof(Foo));
调用 -> ::operator new(size_t);
调用 -> malloc(size_t);

operator delete(x);
调用 -> ::operator delete(void*);
调用 -> free(void*);

在类中重载 operator newoperator delete

1
2
3
4
5
Foo *p = (Foo*)operator new(sizeof(Foo));
重载 Foo::operator new(size_t); -> 调用 ::operator new(size_t);

operator delete(x);
重载 Foo::operator delete(void*); -> 调用 ::operator delete(void*);

C++容器分配内存的途径

容器

1
2
3
4
5
T *p = allocate();
construct();

destroy();
deallocate(p);

分配器

1
2
3
allocate();
deallocate();
调用 -> ::operator new or ::operator delete

重载 ::operator new / ::operator delete

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
void * myAlloc(size_t size){
return malloc(size);
}

void myFree(void * ptr){
return free(ptr);
}

inline void * operator new(size_t size){
cout << "global new()" << endl;
return myAlloc(size);
}

inline void * operator new[](size_t size){
cout << "global new[]" << endl;
return myAlloc(size);
}

inline void operator delete(void * ptr){
cout << "global delete()" << endl;
myFree(ptr);
}

inline void operator delete[](void * ptr){
cout << "global delete[]" << endl;
myFree(ptr);
}

重载 operator new / operator delete

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Foo {
public:
/*重载这两个函数应该是 static, 编译器默认*/
void * operator new(size_t);
void operator delete(void *, size_t); //第二参数 optional
};

Foo *p = new Foo;
编译器->
try {
void * mem = operator new(sizeof(Foo)); //此处调用类中重载的 operator new
p = static_cast<Foo*>(mem);
p->Foo::Foo(1,2);
}

delete p; //使用 ::delete p; 可以绕过重载的 operator delete
编译器->
p->~Foo();
operator delete(p); //此处调用类中重载的 operator delete

重载 placement new / placement delete

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
class Foo {

/* 1,2默认版本; 3,4重载版本;*/

void * operator new(size_t size){ // 调用 new Foo
return malloc(size);
}

void * operator new(size_t size, void * start){ // 调用 new (&) Foo
return start;
}

void * operator new(size_t size, long extra){ // 调用 new (100) Foo
return malloc(size + extra);
}

void * operator new(size_t size, long extra, char init){ //调用 new(100,'a') Foo
return malloc(size + extra);
}

/*
** placement new 重载时, 第一参数必须为 size_t
** 否则, [Error] 'operator new' takes type 'size_t'(unsigned int)
** as first parameter
*/

/*
** placement delete 重载时, 不会被 delete 调用
** 除非 new 的时候抛出异常, 才会去调用对应的重载的 operator delete()
*/
};