C++ 巩固基础之三

发表于 阅读次数： 评论数： 本文字数： 2.6k 阅读时长 ≈ 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
#include <iostream>

using namespace std;

class CComplex {

public:
    CComplex(int r = 0, int i = 0) : mreal(r), mimage(i) {

    }

    // 在局部作用域加法运算符的重载函数
    // 这里不能返回引用，因为在栈上分配内存空间的对象，随着函数的运行结束，内存空间会自动释放
    CComplex operator+(const CComplex &other) {
        return CComplex(this->mreal + other.mreal, this->mimage + other.mimage);
    }

    // 利用友元函数实现加法运算符的重载
    friend CComplex operator+(const CComplex &left, const CComplex &right);

    // 利用友元函数实现左移运算符的重载
    // 左移运算符的重载只能使用友元函数来实现
    friend ostream &operator<<(ostream &out, const CComplex &c);

    void print() {
        cout << "mreal: " << mreal << ", mimage: " << mimage << endl;
    }

private:
    int mreal;
    int mimage;

};

// 在全局作用域实现加法运算符的重载
CComplex operator+(const CComplex &left, const CComplex &right) {
    return CComplex(left.mreal + right.mreal, left.mimage + right.mimage);
}

// 在全局作用域实现左移运算符的重载
ostream &operator<<(ostream &out, const CComplex &c) {
    out << "mreal: " << c.mreal << ", mimage: " << c.mimage << endl;
    return out;
}

int main() {
    CComplex c1(10, 10);
    CComplex c2(20, 20);

    CComplex c3 = c1 + c2;       // 相当于 CComplex c3 = c1.operator+(c2);
    c3.print();

    CComplex c4 = c1 + 20;      // 默认可以正常编译运行，会自动调用 CComplex(int r = 0, int i = 0) 构造函数，然后再执行加法运算
    c4.print();

    // 编译器做对象运算的时候，会调用对象的运算符重载函数（优先调用成员方法）；如果没有成员方法，就会在全局作用域找合适的运算符重载函数。
    CComplex c5 = 30 + c1;      // 默认不可以正常编译运行，除非是在全局作用域实现加法运算符的重载
    c5.print();

    cout << c1 << endl;     // 左移运算符的重载

    return 0;
}

程序执行后的输出结果：

1
2
3
4
mreal: 30, mimage: 30
mreal: 30, mimage: 10
mreal: 40, mimage: 10
mreal: 10, mimage: 10

一元运算符的重载

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
#include <iostream>

using namespace std;

class CComplex {

public:
    CComplex(int r = 0, int i = 0) : mreal(r), mimage(i) {

    }

    // "前置++" 运算符的重载
    CComplex &operator++() {
        this->mreal++;
        this->mimage++;
        return *this;
    }

    // "后置++" 运算符的重载
    // 使用占位参数进行函数重载，是为了解决与 "前置++" 类成员函数冲突的问题
    CComplex operator++(int) {
        return CComplex(this->mreal++, this->mimage++);
    }

    void print() {
        cout << "mreal: " << mreal << ", mimage: " << mimage << endl;
    }

private:
    int mreal;
    int mimage;

};

int main() {
    CComplex c1(10, 10);

    // 前置++
    CComplex c2(20, 20);
    c2 = ++c1;
    c1.print();     // 11 11
    c2.print();     // 11 11

    // 后置++
    CComplex c3(30, 30);
    c3 = c1++;
    c1.print();     // 12 12
    c3.print();     // 11 11

    return 0;
}

程序执行后的输出结果：

1
2
3
4
mreal: 11, mimage: 11
mreal: 11, mimage: 11
mreal: 12, mimage: 12
mreal: 11, mimage: 11

模拟实现字符串类

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
#include <iostream>
#include <cstring>

using namespace std;

class MyString {

public:
    // 构造函数
    MyString(const char *p = nullptr) {
        if (p != nullptr) {
            _pstr = new char[strlen(p) + 1];
            strcpy(_pstr, p);
        } else {
            _pstr = new char[1];
            *_pstr = '\0';
        }
    }

    // 析构函数
    ~MyString() {
        delete[] _pstr;
        _pstr = nullptr;
    }

    // 拷贝构造函数
    MyString(const MyString &str) {
        // 深拷贝
        _pstr = new char[strlen(str._pstr) + 1];
        strcpy(_pstr, str._pstr);
    }

    // 赋值运算符重载
    MyString &operator=(const MyString &str) {
        // 防止自赋值
        if (this == &str) {
            return *this;
        }

        // 释放原来的内存空间
        delete[] _pstr;

        // 深拷贝
        _pstr = new char(strlen(str._pstr) + 1);
        strcpy(_pstr, str._pstr);

        return *this;
    }

    // 加法运算符重载
    friend MyString operator+(const MyString &str1, const MyString &str2);

    // 左移运算符重载
    friend ostream &operator<<(ostream &out, const MyString &str);

    // 大于运算符重载
    bool operator>(const MyString &str) const {
        return strcmp(_pstr, str._pstr) > 0;
    }

    // 小于运算符重载
    bool operator<(const MyString &str) const {
        return strcmp(_pstr, str._pstr) < 0;
    }

    // 双等号运算符重载
    bool operator==(const MyString &str) const {
        return strcmp(_pstr, str._pstr) == 0;
    }

    // 中括号运算符重载（读写）
    char &operator[](int index) {
        return _pstr[index];
    }

    // 中括号运算符重载（只读）
    const char &operator[](int index) const {
        return _pstr[index];
    }

    // 返回字符串自身
    const char *c_str() const {
        return _pstr;
    }

    // 获取字符串长度
    long length() const {
        long length = strlen(_pstr);

        // 空字符串
        if (0 == length) {
            return 0;
        }

        // 以 '\0' 结尾的字符串
        if (_pstr[length] == '\0') {
            return length;
        }

        // 不以 '\0' 结尾的字符串
        return length + 1;
    }

private:
    char *_pstr;
};

MyString operator+(const MyString &str1, const MyString &str2) {
    MyString tmpStr;
    tmpStr._pstr = new char[strlen(str1._pstr) + strlen(str2._pstr) + 1];
    strcpy(tmpStr._pstr, str1._pstr);
    strcat(tmpStr._pstr, str2._pstr);
    return tmpStr;
}

ostream &operator<<(ostream &out, const MyString &str) {
    out << str._pstr;
    return out;
}

int main() {
    // 调用构造函数
    MyString str1("abcde");
    cout << str1 << endl;

    // 调用构造函数
    MyString str2 = "fghij";
    cout << str2 << endl;

    // 调用拷贝构造函数
    MyString str3 = str2;
    cout << str3 << endl;

    // 赋值运算符重载
    str3 = str1;
    cout << str3 << endl;

    // 加法运算符重载
    MyString str4 = str1 + str2;
    cout << str4 << endl;

    // 大于运算符重载
    bool result1 = str1 > str2;
    cout << (result1 ? "true" : "false") << endl;

    // 小于运算符重载
    bool result2 = str1 < str2;
    cout << (result2 ? "true" : "false") << endl;

    // 双等号运算符重载
    str1 = str2;
    bool result3 = str1 == str2;
    cout << (result3 ? "true" : "false") << endl;

    // 中括号运算符重载
    MyString str5("hello");
    str5[4] = 'k';
    cout << "str5[3] = " << str5[4] << endl;

    // 获取字符串长度
    MyString str6("world");
    cout << "str6.length = " << str6.length() << endl;

    // 返回字符串自身
    const char *tmpstr = str6.c_str();
    cout << tmpstr << endl;

    return 0;
}

程序执行后的输出结果：

1
2
3
4
5
6
7
8
9
10
11
abcde
fghij
fghij
abcde
abcdefghij
false
true
true
str5[3] = k
str6.length = 5
world

迭代器的实现

迭代器的介绍

  • 迭代器的功能是：提供一种统一的方式来透明地遍历容器。
  • 泛型算法参数接收的都是选代器。
  • 在泛型算法中，通常都有一个可以统一地遍历所有容器的元素的迭代器。

模拟实现字符串类的迭代器

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
#include <iostream>
#include <cstring>

using namespace std;


class MyString {

public:
    // 构造函数
    MyString(const char *p = nullptr) {
        if (p != nullptr) {
            _pstr = new char[strlen(p) + 1];
            strcpy(_pstr, p);
        } else {
            _pstr = new char[1];
            *_pstr = '\0';
        }
    }

    // 析构函数
    ~MyString() {
        delete[] _pstr;
        _pstr = nullptr;
    }

    // 拷贝构造函数
    MyString(const MyString &str) {
        // 深拷贝
        _pstr = new char[strlen(str._pstr) + 1];
        strcpy(_pstr, str._pstr);
    }

    // 赋值运算符重载
    MyString &operator=(const MyString &str) {
        // 防止自赋值
        if (this == &str) {
            return *this;
        }

        // 释放原来的内存空间
        delete[] _pstr;

        // 深拷贝
        _pstr = new char(strlen(str._pstr) + 1);
        strcpy(_pstr, str._pstr);

        return *this;
    }

    // 加法运算符重载
    friend MyString operator+(const MyString &str1, const MyString &str2);

    // 左移运算符重载
    friend ostream &operator<<(ostream &out, const MyString &str);

    // 大于运算符重载
    bool operator>(const MyString &str) const {
        return strcmp(_pstr, str._pstr) > 0;
    }

    // 小于运算符重载
    bool operator<(const MyString &str) const {
        return strcmp(_pstr, str._pstr) < 0;
    }

    // 双等号运算符重载
    bool operator==(const MyString &str) const {
        return strcmp(_pstr, str._pstr) == 0;
    }

    // 中括号运算符重载（读写）
    char &operator[](int index) {
        return _pstr[index];
    }

    // 中括号运算符重载（只读）
    const char &operator[](int index) const {
        return _pstr[index];
    }

    // 返回字符串自身
    const char *c_str() const {
        return _pstr;
    }

    // 获取字符串长度
    long length() const {
        long length = strlen(_pstr);

        // 空字符串
        if (0 == length) {
            return 0;
        }

        // 以 '\0' 结尾的字符串
        if (_pstr[length] == '\0') {
            return length;
        }

        // 不以 '\0' 结尾的字符串
        return length + 1;
    }

    // 迭代器
    class iterator {
    public:
        iterator(char *p = nullptr) : _p(p) {

        }

        // 重载不等于运算符
        bool operator!=(const iterator &other) const {
            return _p != other._p;
        }

        // 重载前置 ++ 运算符
        iterator &operator++() {
            _p++;
            return *this;
        }

        // 重载后置 ++ 运算符
        iterator operator++(int) {
            return iterator(_p++);
        }

        // 解引用运算符重载
        char &operator*() const {
            return *_p;
        }

    private:
        char *_p;
    };

    // 返回的是容器底层首元素的迭代器的表示
    iterator begin() {
        return iterator(_pstr);
    }

    // 返回的是容器末尾元素后继位置的迭代器的表示
    iterator end() {
        return iterator(_pstr + length());
    }

private:
    char *_pstr;
};

MyString operator+(const MyString &str1, const MyString &str2) {
    MyString tmpStr;
    tmpStr._pstr = new char[strlen(str1._pstr) + strlen(str2._pstr) + 1];
    strcpy(tmpStr._pstr, str1._pstr);
    strcat(tmpStr._pstr, str2._pstr);
    return tmpStr;
}

ostream &operator<<(ostream &out, const MyString &str) {
    out << str._pstr;
    return out;
}

void test01() {
    MyString str1 = "Hello World";
    // 使用迭代器遍历字符串
    for (MyString::iterator it = str1.begin(); it != str1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void test02() {
    MyString str2 = "Golang";
    // 使用 For 循环遍历字符串，会自动调用字符串类的 begin() 和 end() 函数
    for (char ch: str2) {
        cout << ch << " ";
    }
    cout << endl;
}

int main() {
    test01();
    test02();
    return 0;
}

程序执行后的输出结果：

1
2
H e l l o   W o r l d 
G o l a n g

模拟实现 vector 容器的迭代器

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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include <iostream>
#include <cstring>

using namespace std;

// 类模板
template<typename T>
// 空间配置器（负责内存开辟、内存释放、对象构造、对象析构）
struct Allocator {

    // 数组的内存开辟
    T *allocate(size_t size) {
        return (T *) malloc(sizeof(T) * size);
    }

    // 数组的内存释放
    void deallocate(void *p) {
        free(p);
    }

    // 对象构造
    void construct(T *p, const T &val) {
        // 在指定的内存上构造对象（定位 new）
        new(p)T(val);
    }

    // 对象析构
    void destroy(T *p) {
        // ~T() 代表了 T 类型对象的析构函数
        p->~T();
    }

};

// 类模板
template<typename T, typename Alloc = Allocator<T>>
// 向量容器
class Vector {

public:
    // 构造函数
    Vector(int size = 10) {
        // 开辟数组的内存空间
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }

    // 析构函数（先析构容器内的有效元素，然后再释放 _first 指针指向的堆内存）
    ~Vector() {
        // 析构容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放堆上的数组内存
        _allocator.deallocate(_first);
        _first = _last = _end = nullptr;
    }

    // 拷贝构造函数
    Vector(const Vector<T> &v) {
        // 容器的总大小
        int size = v._end - v._first;
        // 有效元素的个数
        int length = v._last - v._first;

        // 开辟数组的内存空间
        _first = _allocator.allocate(size);

        // 在指定的内存空间中构造对象
        for (int i = 0; i < length; i++) {
            _allocator.construct(_first + i, v._first[i]);
        }
        _last = _first + length;
        _end = _first + size;
    }

    // 赋值运算符重载
    Vector<T> &operator=(const Vector<T> &v) {
        if (this == v) {
            return *this;
        }

        // 析构容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放堆上的数组内存
        _allocator.deallocate(_first);

        // 容器的总大小
        int size = v._end - v._first;
        // 有效元素的个数
        int length = v._last - v._first;

        // 开辟数组的内存空间
        _first = _allocator.allocate(size);

        // 在指定的内存空间中构造对象
        for (int i = 0; i < length; i++) {
            _allocator.construct(_first + i, v._first[i]);
        }
        _last = _first + length;
        _end = _first + size;

        return *this;
    }

    // 往容器尾部添加元素
    void push_back(const T &val) {
        if (full()) {
            resize();
        }
        // 在指定的内存空间中构造对象
        _allocator.construct(_last, val);
        _last++;
    }

    // 从容器尾部删除元素（需要将对象的析构和内存释放分开处理）
    void pop_back() {
        if (!empty()) {
            _last--;
            // 在指定的内存空间中析构对象
            _allocator.destroy(_last);
        }
    }

    // 返回容器尾部的元素
    T back() const {
        if (empty()) {
            throw "Vector is empty!";
        }
        return *(_last - 1);
    }

    // 容器是否满了
    bool full() const {
        return _last == _end;
    }

    // 容器是否为空
    bool empty() const {
        return _first == _last;
    }

    // 返回有效元素的个数
    int size() const {
        return _last - _first;
    }

    // 重载中括号运算符
    T &operator[](int index) {
        if (index < 0 || index >= size()) {
            throw "OutOfRangeException";
        }
        return _first[index];
    }

    // 迭代器
    class iterator {

    public:
        iterator(T *p = nullptr) : _ptr(p) {

        }

        // 重载不等于运算符
        bool operator!=(const iterator &other) const {
            return _ptr != other._ptr;
        }

        // 重载前置 ++ 运算符
        iterator &operator++() {
            _ptr++;
            return *this;
        }

        // 重载后置 ++ 运算符
        iterator operator++(int) {
            return iterator(_ptr++);
        }

        // 解引用运算符重载
        T &operator*() const {
            return *_ptr;
        }

    private:
        T *_ptr;
    };

    // 返回的是容器底层首元素的迭代器的表示
    iterator begin() {
        return iterator(_first);
    }

    // 返回的是容器末尾元素后继位置的迭代器的表示
    iterator end() {
        return iterator(_last);
    }

private:
    T *_first;  // 指向数组起始的位置
    T *_last;   // 指向数组中有效元素的后继位置
    T *_end;    // 指向数组空间的后继位置
    Alloc _allocator;   // 定义容器空间配置器的对象

    // 扩容操作
    void resize() {
        int size = _end - _first;
        // 开辟数组的内存空间
        T *_ptemp = _allocator.allocate(size * 2);
        // 在指定的内存空间中构造对象
        for (int i = 0; i < size; i++) {
            _allocator.construct(_ptemp + i, _first[i]);
        }

        // 析构原来容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放原来的数组内存
        _allocator.deallocate(_first);

        _first = _ptemp;
        _last = _first + size;
        _end = _first + size * 2;
    }
};

class Person {

public:
    Person() {
        cout << "call Person()" << endl;
    }

    Person(const Person &p) {
        cout << "call Person(const Person &p)" << endl;
    }

    ~Person() {
        cout << "call ~Person()" << endl;
    }

};

void test01() {
    cout << "============ test01() ============" << endl;

    Vector<int> v;
    for (int i = 0; i < 20; i++) {
        int val = random() % 100;
        v.push_back(val);
    }

    // 使用中括号取值
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;

    cout << "size: " << v.size() << endl;
    cout << "full: " << (v.full() ? "true" : " false") << endl;
    cout << "empty: " << (v.empty() ? "true" : " false") << endl;

    while (!v.empty()) {
        cout << v.back() << " ";
        v.pop_back();
    }
    cout << endl;
}

void test02() {
    cout << "============ test02() ============" << endl;

    // 往容器插入元素
    Vector<int> v;
    for (int i = 0; i < 20; i++) {
        int val = random() % 100;
        v.push_back(val);
        cout << val << " ";
    }
    cout << endl;

    // 使用迭代器变遍历容器
    for (Vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 使用 For 循环遍历容器，会自动调用容器类的 begin() 和 end() 函数
    for (int item : v) {
        cout << item << " ";
    }
    cout << endl;
}

int main() {
    // 设置随机数种子
    srand(time(nullptr));

    test01();
    test02();
    return 0;
}

程序执行后的输出结果：

1
2
3
4
5
6
7
8
9
10
============ test01() ============
99 75 54 4 58 27 46 64 65 99 85 32 85 0 27 36 56 10 59 8 
size: 20
full: true
empty:  false
8 59 10 56 36 27 0 85 32 85 99 65 64 46 27 58 4 54 75 99 
============ test02() ============
75 51 32 20 28 23 4 55 76 61 78 75 88 84 31 46 11 30 62 29 
75 51 32 20 28 23 4 55 76 61 78 75 88 84 31 46 11 30 62 29 
75 51 32 20 28 23 4 55 76 61 78 75 88 84 31 46 11 30 62 29

模拟重现迭代器的失效问题

迭代器失效问题的发生

  • 第一种迭代器失效的情况（容器删除元素），以下代码会异常终止运行
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
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v;
    for (int i = 0; i < 20; i++) {
        v.push_back(random() % 100 + 1);
    }

    // 将容器中的所有偶数删除掉
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            // 迭代器失效的问题：第一次调用 erase() 函数以后，迭代器 it 就已经失效了
            // 当容器调用 erase() 函数后，当前删除位置到容器尾元素的所有的选代器将全部失效，但是首元素到当前删除位置的所有的迭代器依旧是生效的
            v.erase(it);
        }
    }

    return 0;
}
  • 第二种迭代器失效的情况（容器插入元素），以下代码会异常终止运行
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 <vector>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v;
    for (int i = 0; i < 20; i++) {
        v.push_back(random() % 100 + 1);
    }

    // 给容器中所有的偶数前面添加一个小于该偶数的数字
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            // 迭代器失效的问题：第一次调用 insert() 函数以后，迭代器 it 就已经失效了
            // 当容器调用 insert() 函数后，当前插入位置到容器尾元素的所有的选代器将全部失效，但是首元素到当前插入位置的所有的迭代器依旧是生效的
            // 一旦 insert() 函数的插入操作引起扩容，那么原来容器从首元素到尾元素的所有的选代器将全部失效
            v.insert(it, *it - 1);
        }
    }

    return 0;
}
  • 第三种迭代器失效的情况（容器触发扩容），当容器扩容后，原容器从首元素到尾元素的所有的选代器将全部失效。

迭代器失效问题的解决

解决方案介绍

温馨提示

解决迭代器失效的问题，最关键是对插入点 / 删除点的迭代器执行更新操作。

  • 第一种迭代器失效的情况（容器删除元素），以下代码可以正常运行
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 <vector>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v;
    for (int i = 0; i < 20; i++) {
        v.push_back(random() % 100 + 1);
    }

    // 将容器中的所有偶数删除掉
    for (vector<int>::iterator it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            // 更新迭代器
            it = v.erase(it);
        } else {
            ++it;
        }
    }

    return 0;
}
  • 第二种迭代器失效的情况（容器插入元素），以下代码可以正常运行
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
#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> v;
    for (int i = 0; i < 20; i++) {
        v.push_back(random() % 100 + 1);
    }

    // 给容器中所有的偶数前面添加一个小于该偶数的数字
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            // 更新迭代器
            it = v.insert(it, *it - 1);
            ++it;
        }
    }

    return 0;
}
底层实现原理

为了解决迭代器失效的问题，可以在容器内部维护一个专门用于存放迭代器的单向链表数据结构，当往容器插入 / 删除元素时，对迭代器的单向链表进行维护。值得一提的是，以下代码是在 上面的案例代码 的基础上改造而来，实现了 vector 容器的插入（暂时不考虑容器扩容）和删除操作。

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
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
#include <iostream>
#include <cstring>

using namespace std;

// 类模板
template<typename T>
// 空间配置器（负责内存开辟、内存释放、对象构造、对象析构）
struct Allocator {

    // 数组的内存开辟
    T *allocate(size_t size) {
        return (T *) malloc(sizeof(T) * size);
    }

    // 数组的内存释放
    void deallocate(void *p) {
        free(p);
    }

    // 对象构造
    void construct(T *p, const T &val) {
        // 在指定的内存上构造对象（定位 new）
        new(p)T(val);
    }

    // 对象析构
    void destroy(T *p) {
        // ~T() 代表了 T 类型对象的析构函数
        p->~T();
    }

};

// 类模板
template<typename T, typename Alloc = Allocator<T>>
// 向量容器
class Vector {

public:
    // 构造函数
    Vector(int size = 10) {
        // 开辟数组的内存空间
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }

    // 析构函数（先析构容器内的有效元素，然后再释放 _first 指针指向的堆内存）
    ~Vector() {
        // 析构容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放堆上的数组内存
        _allocator.deallocate(_first);
        _first = _last = _end = nullptr;
    }

    // 拷贝构造函数
    Vector(const Vector<T> &v) {
        // 容器的总大小
        int size = v._end - v._first;
        // 有效元素的个数
        int length = v._last - v._first;

        // 开辟数组的内存空间
        _first = _allocator.allocate(size);

        // 在指定的内存空间中构造对象
        for (int i = 0; i < length; i++) {
            _allocator.construct(_first + i, v._first[i]);
        }
        _last = _first + length;
        _end = _first + size;
    }

    // 赋值运算符重载
    Vector<T> &operator=(const Vector<T> &v) {
        if (this == v) {
            return *this;
        }

        // 析构容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放堆上的数组内存
        _allocator.deallocate(_first);

        // 容器的总大小
        int size = v._end - v._first;
        // 有效元素的个数
        int length = v._last - v._first;

        // 开辟数组的内存空间
        _first = _allocator.allocate(size);

        // 在指定的内存空间中构造对象
        for (int i = 0; i < length; i++) {
            _allocator.construct(_first + i, v._first[i]);
        }
        _last = _first + length;
        _end = _first + size;

        return *this;
    }

    // 往容器尾部添加元素
    void push_back(const T &val) {
        if (full()) {
            resize();
        }
        // 在指定的内存空间中构造对象
        _allocator.construct(_last, val);
        _last++;
    }

    // 从容器尾部删除元素（需要将对象的析构和内存释放分开处理）
    void pop_back() {
        if (!empty()) {
            verify(_last - 1, _last - 1);
            _last--;
            // 在指定的内存空间中析构对象
            _allocator.destroy(_last);
        }
    }

    // 返回容器尾部的元素
    T back() const {
        if (empty()) {
            throw "Vector is empty!";
        }
        return *(_last - 1);
    }

    // 容器是否满了
    bool full() const {
        return _last == _end;
    }

    // 容器是否为空
    bool empty() const {
        return _first == _last;
    }

    // 返回有效元素的个数
    int size() const {
        return _last - _first;
    }

    // 重载中括号运算符
    T &operator[](int index) {
        if (index < 0 || index >= size()) {
            throw "OutOfRangeException";
        }
        return _first[index];
    }

    // 迭代器
    class iterator {

    public:

        friend class Vector<T, Alloc>;

        iterator(Vector<T, Alloc> *pvec = nullptr, T *p = nullptr) : _pVec(pvec), _ptr(p) {
            // 维护迭代器的单向链表结构
            Iterator_Base *itb = new Iterator_Base(this, _pVec->_head._next);
            _pVec->_head._next = itb;
        }

        // 重载不等于运算符
        bool operator!=(const iterator &other) const {
            // 判断迭代器指向的容器是不是同一个
            if (_pVec == nullptr || _pVec != other._pVec) {
                throw "Iterator incompatable!";
            }
            return _ptr != other._ptr;
        }

        // 重载前置 ++ 运算符
        iterator &operator++() {
            // 检测迭代器的有效性
            if (_pVec == nullptr) {
                throw "Iterator invalid!";
            }
            _ptr++;
            return *this;
        }

        // 重载后置 ++ 运算符
        iterator operator++(int) {
            // 检测迭代器的有效性
            if (_pVec == nullptr) {
                throw "Iterator invalid!";
            }
            return iterator(_ptr++);
        }

        // 解引用运算符重载
        T &operator*() const {
            // 检测迭代器的有效性
            if (_pVec == nullptr) {
                throw "Iterator invalid!";
            }
            return *_ptr;
        }

    private:
        T *_ptr;
        Vector<T, Alloc> *_pVec; // 当前迭代器是哪个容器的对象
    };

    // 返回的是容器底层首元素的迭代器的表示
    iterator begin() {
        return iterator(this, _first);
    }

    // 返回的是容器末尾元素后继位置的迭代器的表示
    iterator end() {
        return iterator(this, _last);
    }

    // 通过迭代器往容器插入元素
    // 这里暂时不考虑容器扩容，也不考虑 it._prt 的指针合法性
    iterator insert(iterator it, const T &val) {
        verify(it._ptr - 1, _last);

        // 重新分配数组的内存空间，并往右边移动数组元素
        T *p = _last;
        while (p > it._ptr) {
            _allocator.construct(p, *(p - 1));
            _allocator.destroy(p - 1);
            p--;
        }
        _allocator.construct(p, val);

        _last++;
        return iterator(this, p);
    }

    // 通过迭代器往容器删除元素
    iterator erase(iterator it) {
        verify(it._ptr - 1, _last);

        // 重新分配数组的内存空间，并往左边移动数组元素
        T *p = it._ptr;
        while (p < _last - 1) {
            _allocator.destroy(p);
            _allocator.construct(p, *(p + 1));
            p++;
        }
        _allocator.destroy(p);

        _last--;
        return iterator(this, it._ptr);
    }

private:
    T *_first;  // 指向数组起始的位置
    T *_last;   // 指向数组中有效元素的后继位置
    T *_end;    // 指向数组空间的后继位置
    Alloc _allocator;   // 定义容器空间配置器的对象

    // 迭代器的单向链表结构
    struct Iterator_Base {
        Iterator_Base(iterator *cur = nullptr, Iterator_Base *next = nullptr) : _cur(cur), _next(next) {

        }

        iterator *_cur;
        Iterator_Base *_next;
    };

    Iterator_Base _head;

    // 扩容操作
    void resize() {
        int size = _end - _first;
        // 开辟数组的内存空间
        T *_ptemp = _allocator.allocate(size * 2);
        // 在指定的内存空间中构造对象
        for (int i = 0; i < size; i++) {
            _allocator.construct(_ptemp + i, _first[i]);
        }

        // 析构原来容器内的有效元素
        for (T *p = _first; p != _last; p++) {
            _allocator.destroy(p);
        }

        // 释放原来的数组内存
        _allocator.deallocate(_first);

        _first = _ptemp;
        _last = _first + size;
        _end = _first + size * 2;
    }

    // 维护迭代器的单向链表
    void verify(T *start, T *end) {
        Iterator_Base *cur = &this->_head;
        Iterator_Base *next = this->_head._next;
        while (next != nullptr) {
            if (next->_cur->_ptr >= start && next->_cur->_ptr <= end) {
                // 迭代器失效，将迭代器持有的容器指针置为空
                next->_cur->_pVec = nullptr;
                // 在迭代器链表中，删除当前迭代器节点，并继续判断后面的迭代器节点是否失效
                cur->_next = next->_next;
                delete next;
                next = cur->_next;
            } else {
                next = next->_next;
            }
        }
    }

};

class Person {

public:
    Person() {
        cout << "call Person()" << endl;
    }

    Person(const Person &p) {
        cout << "call Person(const Person &p)" << endl;
    }

    ~Person() {
        cout << "call ~Person()" << endl;
    }

};

void test01() {
    cout << "============ test01() ============" << endl;

    // 往容器插入元素
    Vector<int> v(100);
    for (int i = 0; i < 20; i++) {
        int val = random() % 100;
        v.push_back(val);
        cout << val << " ";
    }
    cout << endl;

    // 将容器中的所有偶数删除掉
    for (Vector<int>::iterator it = v.begin(); it != v.end();) {
        if (*it % 2 == 0) {
            // 更新迭代器
            it = v.erase(it);
        } else {
            ++it;
        }
    }

    // 使用 For 循环遍历容器，会自动调用容器类的 begin() 和 end() 函数
    for (int item : v) {
        cout << item << " ";
    }
    cout << endl;
}

void test02() {
    cout << "============ test02() ============" << endl;

    // 往容器插入元素
    Vector<int> v(100);
    for (int i = 0; i < 20; i++) {
        int val = random() % 100;
        v.push_back(val);
        cout << val << " ";
    }
    cout << endl;

    // 给容器中所有的偶数前面添加一个小于该偶数的数字
    for (Vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            // 更新迭代器
            it = v.insert(it, *it - 1);
            ++it;
        }
    }

    // 使用 For 循环遍历容器，会自动调用容器类的 begin() 和 end() 函数
    for (int item : v) {
        cout << item << " ";
    }
    cout << endl;
}

int main() {
    // 设置随机数种子
    srand(time(nullptr));

    test01();
    test02();

    return 0;
}

程序执行后的输出结果：

1
2
3
4
5
6
============ test01() ============
93 95 0 33 65 6 15 50 94 2 21 16 36 0 7 3 43 59 25 60 
93 95 33 65 15 21 7 3 43 59 25 
============ test02() ============
67 86 10 44 87 27 47 53 79 60 66 24 7 67 58 24 25 73 27 19 
67 85 86 9 10 43 44 87 27 47 53 79 59 60 65 66 23 24 7 67 57 58 23 24 25 73 27 19

new 与 delete

malloc 与 new 的区别

malloc 和 new 都用于在 C++ 中动态分配内存空间，但它们之间有本质的区别。

  • 语法和用途
区别点mallocnew
语法void* ptr = malloc(size);Type* ptr = new Type;
功能仅按字节分配内存空间，不会调用构造函数。按类型分配内存并调用对象的构造函数。
返回值返回 void*，需要显式转换为目标类型指针。返回指定类型的指针，无需显式转换。
  • 初始化
区别点mallocnew
默认值分配的内存未初始化，包含垃圾值。基本类型未初始化，但类对象会调用构造函数进行初始化。
支持类型通常适用于基本数据类型和简单内存块分配。适用于类和复杂类型，支持构造函数调用。
  • 释放内存
区别点mallocnew
释放方法使用 free(ptr); 释放内存。使用 delete ptr; 释放内存，并调用析构函数（如果有）。
析构函数调用不会调用对象的析构函数。自动调用对象的析构函数，进行清理操作。
  • 性能和类型安全
区别点mallocnew
类型安全无类型安全，需手动进行类型转换。类型安全，无需手动类型转换。
性能较低级，效率略高（无构造函数调用的情况下）。高级，功能更强，但可能稍慢（有构造函数调用时）。
  • 支持数组分配
区别点mallocnew
数组分配手动计算所需字节数并分配：int* arr = (int*) malloc(n * sizeof(int));使用 new[]：int* arr = new int[n];
释放数组释放数组时，需用 free(arr);必须使用 delete[] arr;，否则可能导致内存泄漏或未调用析构函数。
  • 异常处理
区别点mallocnew
失败行为分配失败返回 NULL，需要手动检查返回值。分配失败抛出 std::bad_alloc 异常（除非使用 new (std::nothrow)）。

适用场景

  • 使用 malloc：适合兼容 C 代码、分配简单内存块、不需要调用构造函数或析构函数的场景。
  • 使用 new：适合 C++ 风格编程，需要调用构造和析构功能的场景，推荐在现代 C++ 中优先使用。

温馨提示

  • 在现代 C++ 中，推荐使用智能指针（如 std::unique_ptr 和 std::shared_ptr） 或 std::vector 等容器，减少手动管理内存的风险。

free 和 delete 的区别

free 和 delete 都用于释放动态分配的内存空间，但它们之间有本质的区别。

  • 语法和用途
区别点freedelete
语法free(ptr);delete ptr; 或 delete[] ptr;
适用对象与 malloc 和 calloc 搭配使用的内存。与 new 或 new[] 分配的内存。
用途释放动态分配的内存，不关心类型和构造函数。释放动态分配的内存，同时调用析构函数（如果有）。
  • 析构函数调用
区别点freedelete
析构函数调用不会调用析构函数，只释放内存。自动调用对象的析构函数，完成清理操作后释放内存。
  • 数组支持
区别点freedelete
数组释放没有专门的数组释放机制，需明确释放首地址。对于数组，需要使用 delete[] 来正确释放并调用析构函数。
  • 异常处理
区别点freedelete
内存管理手动管理，不与异常处理直接相关。更安全，若内存释放过程中发生异常，析构函数可以处理。
  • 性能差异
区别点freedelete
性能开销较低，不会进行类型检查或调用析构函数。较高，涉及类型检查和析构函数调用。
  • 用法不当的后果
区别点freedelete
用法不当释放 new 分配的内存可能会导致未定义行为。释放 malloc 分配的内存可能会导致未定义行为。
未使用正确的形式不会自动检测类型或数组。使用 delete 而非 delete[] 释放数组，可能会导致部分内存泄漏或析构函数未调用。

特别注意

  • 对数组使用 new[] 分配内存时，必须用 delete[] 释放内存。
  • free 和 delete 不能混用。malloc 分配的内存必须用 free 释放内存；new 分配的内存必须用 delete 释放内存。

温馨提示

  • 在现代 C++ 中，推荐使用智能指针（如 std::unique_ptr 和 std::shared_ptr） 或 std::vector 等容器，减少手动管理内存的风险。

重载 new 和 delete 运算符

当 C++ 内置的 new 和 delete 运算符不能满足业务需求时（比如需要实现自定义的内存池，或者需要检测内存泄漏），可以通过运算符重载来改变 new 和 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
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
#include <iostream>

using namespace std;

// 重写 new 运算符，先调用 operator new 开辟内存空间，然后再调用对象的构造函数（初始化）
void *operator new(size_t size) {
    void *ptr = malloc(size);
    if (ptr == nullptr) {
        throw bad_alloc();
    }
    cout << "operator new address: " << ptr << endl;
    return ptr;
}

// 重写 delete 运算符，先调用 ptr 指向对象的析构函数，然后再调用 operator delete 释放内存空间
void operator delete(void *ptr) {
    if (ptr != nullptr) {
        free(ptr);
        cout << "operator delete address: " << ptr << endl;
    }
}

// 重写 new[] 运算符，先调用 operator new[] 开辟内存空间，然后再调用对象的构造函数（初始化）
void *operator new[](size_t size) {
    void *ptr = malloc(size);
    if (ptr == nullptr) {
        throw bad_alloc();
    }
    cout << "operator new[] address: " << ptr << endl;
    return ptr;
}

// 重写 delete[] 运算符，先调用 ptr 指向对象的析构函数，然后再调用 operator delete[] 释放内存空间
void operator delete[](void *ptr) {
    if (ptr != nullptr) {
        free(ptr);
        cout << "operator delete[] address: " << ptr << endl;
    }
}

class Test {
public:
    Test(int data = 10) : _data(data) {
        cout << "Test()" << endl;
    }

    ~Test() {
        cout << "~Test()" << endl;
    }

private:
    int _data;
};

void test01() {
    cout << "============ test01() ============" << endl;
    try {
        // 调用重载后的 new 和 delete 运算符
        int *p = new int;
        delete p;
    } catch (const bad_alloc &exception) {
        cerr << exception.what() << endl;
    }
}

void test02() {
    cout << "============ test02() ============" << endl;
    try {
        // 调用重载后的 new[] 和 delete[] 运算符
        int *p = new int[10];
        delete[] p;
    } catch (const bad_alloc &exception) {
        cerr << exception.what() << endl;
    }
}

void test03() {
    cout << "============ test03() ============" << endl;
    try {
        // 调用重载后的 new 和 delete 运算符
        Test *t = new Test(5);
        delete t;
    } catch (const bad_alloc &exception) {
        cerr << exception.what() << endl;
    }
}

void test04() {
    cout << "============ test04() ============" << endl;
    try {
        // 调用重载后的 new[] 和 delete[] 运算符
        Test *t = new Test[2]();
        delete[] t;
    } catch (const bad_alloc &exception) {
        cerr << exception.what() << endl;
    }
}

int main() {
    test01();
    test02();
    test03();
    test04();
    return 0;
}

程序执行后的输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
============ test01() ============
operator new address: 0x232fc20
operator delete address: 0x232fc20
============ test02() ============
operator new[] address: 0x232fc40
operator delete[] address: 0x232fc40
============ test03() ============
operator new address: 0x232fc20
Test()
~Test()
operator delete address: 0x232fc20
============ test04() ============
operator new[] address: 0x232fc20
Test()
Test()
~Test()
~Test()
operator delete[] address: 0x232fc20

通过运算符重载实现对象池

这里将通过重载 new 和 delete 运算符来实现对象池，这样就可以避免为特定对象（如下面的 QueueItem）频繁开辟和释放内存空间，从而提高程序的运行效率。

C++ 的各种池对象

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
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
#include <iostream>
#include <stdexcept>

using namespace std;

template<typename T>
class Queue {

public:
    Queue() {
        cout << "Queue()" << endl;
        _size = 0;
        _front = _rear = new QueueItem();
    }

    ~Queue() {
        cout << "~Queue()" << endl;
        while (_front != nullptr) {
            QueueItem *next = _front->_next;
            delete _front;
            _front = next;
        }
    }

    // 入队操作（插入尾节点）
    void push(const T &value) {
        QueueItem *item = new QueueItem(value);
        _rear->_next = item;
        _rear = item;
        _size++;
    }

    // 出队操作（移除头节点）
    void pop() {
        if (empty()) {
            throw runtime_error("Queue is empty, cannot pop");
        }

        QueueItem *first = _front->_next;
        _front->_next = first->_next;
        if (_front->_next == nullptr) {
            _rear = _front;
        }
        delete first;
        _size--;
    }

    // 返回头节点
    T front() const {
        if (empty()) {
            throw runtime_error("Queue is empty");
        }
        return _front->_next->_data;
    }

    // 队列是否为空
    bool empty() const {
        return _front == _rear;
    }

    // 获取队列的大小
    size_t size() {
        return _size;
    }

private:
    // 队列元素
    struct QueueItem {
        QueueItem(T data = T()) : _data(data), _next(nullptr) {

        };

        // 自定义 QueueItem 对象的内存开辟
        void *operator new(size_t size) {
            if (_itemPool == nullptr) {
                // 初始化对象池
                _itemPool = (QueueItem *) new char[sizeof(QueueItem) * ITEM_POOL_SIZE];
                QueueItem *p = _itemPool;
                for (; p < _itemPool + ITEM_POOL_SIZE - 1; ++p) {
                    p->_next = p + 1;
                }
                // 处理最后一个节点
                p->_next = nullptr;
            }

            QueueItem *ptr = _itemPool;
            _itemPool = _itemPool->_next;
            return ptr;
        }

        // 自定义 QueueItem 对象的内存释放
        void operator delete(void *ptr) {
            // 归还给对象池
            QueueItem *p = (QueueItem *) ptr;
            p->_next = _itemPool;
            _itemPool = p;
        }

        T _data;                                    // 当前节点的数据
        QueueItem *_next;                           // 下一个节点
        static QueueItem *_itemPool;                // 指向对象池中未使用的第一节点
        static const int ITEM_POOL_SIZE = 10000;    // 对象池的大小
    };

    QueueItem *_front;  // 头结点，是一个虚拟节点，用于简化队列操作（如插入和删除）
    QueueItem *_rear;   // 尾节点，是一个真实节点，始终指向队列的最后一个有效节点，或者在队列为空时指向虚拟头节点
    int _size;          // 队列的大小

};

template<typename T>
typename Queue<T>::QueueItem *Queue<T>::QueueItem::_itemPool = nullptr;

void test01() {
    cout << "============ test01() ============" << endl;

    Queue<int> queue;

    for (int i = 0; i < 10; i++) {
        int value = random() % 100 + 1;
        queue.push(value);
        cout << value << " ";
    }
    cout << endl << "size = " << queue.size() << endl;

    while (!queue.empty()) {
        cout << queue.front() << " ";
        queue.pop();
    }
    cout << endl << "size = " << queue.size() << endl;
}

void test02() {
    cout << "============ test02() ============" << endl;

    Queue<int> queue;

    // 如果这里不使用对象池，那么就会频繁开辟和释放对象的内存空间，导致性能消耗比较严重
    for (int i = 0; i < 1000; i++) {
        int value = random() % 100 + 1;
        queue.push(value);
        queue.pop();
    }

    cout << (queue.empty() ? "empty" : "not empty") << endl;
}

int main() {
    // 设置随机种子
    srand(time(nullptr));

    test01();
    test02();

    return 0;
}

程序执行后的输出结果：

1
2
3
4
5
6
7
8
9
10
11
============ test01() ============
Queue()
60 32 73 100 26 31 94 6 47 60 
size = 10
60 32 73 100 26 31 94 6 47 60 
size = 0
~Queue()
============ test02() ============
Queue()
empty
~Queue()