容器类
本节阅读量:
在现实生活中，我们一直在使用容器。你的早餐装在盒子里，书页被封面和装订物固定在一起，你也可以在家中的各种容器里存放任意数量的物品。如果没有容器，使用这些对象将非常不方便。想象一下，试着读一本没有任何装订的书，或者不用碗吃菜，那会一团糟。容器的主要价值在于，它能够帮助我们组织和存储放入其中的项。
类似地，容器类是一种用于保存和组织另一种类型（另一个类或基本类型）的多个实例的类。容器类有许多不同类型，每一种在使用时都有各自的优点、缺点和限制。到目前为止，编程中最常用的容器是数组，您已经看过许多这样的例子。尽管C++具有内置数组功能，但程序员通常会使用数组容器类（std::array或std::vector），因为它们提供了额外的好处。与内置数组不同，数组容器类通常能够动态调整大小（当添加或删除元素时）、知道当前存储的元素数量，并执行边界检查。这不仅使数组容器类比普通数组更方便，也更安全。
容器类通常会实现一组相当标准化的最小功能。大多数设计良好的容器都会包括以下功能：
- 创建空容器（通过构造函数）
- 将新对象插入容器
- 从容器中移除对象
- 查看容器中当前对象的数量
- 清空所有对象的容器
- 提供对存储对象的访问
- 对元素排序（可选）
有时，某些容器类会省略其中一些功能。例如，数组容器类通常会省略insert和remove函数，因为它们很慢，并且类设计者不希望鼓励使用它们。
容器类实现的是“成员”关系。例如，数组的元素是（属于）数组的成员。注意，这里说的是传统意义上的“成员”，而不是C++类成员。
容器分类
容器类通常可以分为两类。值容器按值存储所持有的对象，属于组合关系（因此负责创建和销毁这些对象）。引用容器存储指向其他对象的指针或引用，属于聚合关系（因此不负责创建或销毁这些对象）。
现实生活中的容器可以保存任何类型的对象，但在C++中，容器通常只保存一种类型的数据。例如，如果有一个整数数组，它将只保存整数。与其他一些语言不同，大部分C++容器不允许您任意混合类型。如果需要容器同时保存整数和双精度数，通常必须编写两个单独的容器来完成这项工作（或使用模板，这是一个高级C++功能）。尽管存在这些限制，容器仍然非常有用，它们能让编程更容易、更安全、更高效。
数组容器类
在这个例子中，我们将从头开始编写一个整数数组类，该类实现容器应该具有的大多数常见功能。这个数组类将是一个值容器，它会保存元素的副本。顾名思义，这个容器将保存一个整数数组，类似于std::vector<int>。
首先，让我们创建IntArray.h文件：
1
2
3
4
5
6
7
8
|
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
};
#endif
|
IntArray需要跟踪两个值：数据本身和数组的大小。因为我们希望数组能够改变大小，所以必须进行一些动态分配，这意味着必须使用指针来存储数据。
1
2
3
4
5
6
7
8
9
10
11
|
#ifndef INTARRAY_H
#define INTARRAY_H
class IntArray
{
private:
int m_length{};
int* m_data{};
};
#endif
|
现在，我们需要添加一些允许创建IntArrays的构造函数。这里将添加两个构造函数：一个用于构造空数组，另一个用于构造指定大小的数组。
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
|
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
};
#endif
|
我们还需要一些函数来帮助清理IntArrays。首先，编写一个析构函数，用于释放动态分配的数据。然后，编写一个名为erase()的函数，用于擦除数组并将长度设置为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
~IntArray()
{
delete[] m_data;
// 这里没有将 m_data 设为 null，m_length 设置为 0，因为对象被销毁，没有任何人可以使用
}
void erase()
{
delete[] m_data;
// 需要将 m_data 设置为 nullptr
// 不然它指向的是被销毁的内存!
m_data = nullptr;
m_length = 0;
}
|
现在让我们重载 operator[]，以便访问数组元素。应该确保index参数具有有效值，这可以通过assert()函数实现。我们还将添加一个访问函数，用于返回数组长度。到目前为止，完整代码如下：
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
|
#ifndef INTARRAY_H
#define INTARRAY_H
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
~IntArray()
{
delete[] m_data;
// 这里没有将 m_data 设为 null，m_length 设置为 0，因为对象被销毁，没有任何人可以使用
}
void erase()
{
delete[] m_data;
// 需要将 m_data 设置为 nullptr
// 不然它指向的是被销毁的内存!
m_data = nullptr;
m_length = 0;
}
int& operator[](int index)
{
assert(index >= 0 && index < m_length);
return m_data[index];
}
int getLength() const { return m_length; }
};
#endif
|
此时，我们已经有了一个可以使用的IntArray类。可以分配给定大小的IntArrays，并且可以使用 operator[] 来检索或更改元素的值。
然而，仍然有一些事情无法通过IntArray完成。我们还不能更改它的大小，不能插入或删除元素，也不能对其进行排序。复制数组也会导致问题，因为会发生浅拷贝，只复制数据指针。
首先，让我们编写一些允许调整数组大小的代码。我们将编写两个不同的函数来实现这一点。第一个函数reallocate()会在调整数组大小时销毁数组中的现有元素，因此运行较快。第二个函数resize()会在调整数组大小时保留数组中的现有元素，因此运行较慢。
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
|
#include <algorithm> // for std::copy_n
// reallocate 重新设置数组大小. 任何现有的元素都被销毁. 这个函数运行较快.
void reallocate(int newLength)
{
// 首先删除现有元素
erase();
// 如果设置为空，那么什么也不做
if (newLength <= 0)
return;
// 分配新内存
m_data = new int[newLength];
m_length = newLength;
}
// 重新设置数组大小. 老元素会被保留 这个函数会慢一些.
void resize(int newLength)
{
// 如果数组长度已经符合预期，就不需要操作了
if (newLength == m_length)
return;
// 如果设置为空，清除现有数据，然后返回
if (newLength <= 0)
{
erase();
return;
}
// 这里能确定至少有一个元素
// 先分配新的数组
// 再拷贝数据
// 然后销毁旧的数组
// 最后m_data指向新的数组
// 首先分配新的数组
int* data{ new int[newLength] };
// 判断有多少元素要拷贝
// 拷贝两个数组，长度小的对应个数的元素
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
std::copy_n(m_data, elementsToCopy, data); // 进行实际拷贝
}
// 不再需要老的数组，进行销毁
delete[] m_data;
// 现在开始，可以使用新的数组
// 这里只需要将 m_data 指向新分配的数组即可
// IntArray销毁时，数据会自动销毁
m_data = data;
m_length = newLength;
}
|
呼！这确实稍微有些绕！
现在再添加一个拷贝构造函数和赋值运算符，以便复制数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
IntArray(const IntArray& a): IntArray(a.getLength()) // 拷贝构造函数，调用普通的构造函数
{
std::copy_n(a.m_data, m_length, m_data); // 拷贝数据
}
IntArray& operator=(const IntArray& a)
{
// 自赋值检查
if (&a == this)
return *this;
// 设置合适的存储空间
reallocate(a.getLength());
std::copy_n(a.m_data, m_length, m_data); // 拷贝数据
return *this;
}
|
许多数组容器类到这里就不会再提供新的接口了。然而，如果您希望了解如何实现插入和删除功能，我们也会继续编写这些功能。这两个算法都与resize()非常类似。
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
|
void insertBefore(int value, int index)
{
// 检查index值有效
assert(index >= 0 && index <= m_length);
// 创建一个比老数组大一个的空间
int* data{ new int[m_length+1] };
// 拷贝index之前的数据
std::copy_n(m_data, index, data);
// 将value插入新数组对应的位置
data[index] = value;
// 拷贝插入位置之后的数据
std::copy_n(m_data + index, m_length - index, data + index + 1);
// 最后，销毁老数组，用新数组替代
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// 检查index值有效
assert(index >= 0 && index < m_length);
// 如果要移除的是数组最后一个元素，直接清空数组
if (m_length == 1)
{
erase();
return;
}
// 创建比老数组少一个的新空间
int* data{ new int[m_length-1] };
// 拷贝index之前的数据
std::copy_n(m_data, index, data);
// 拷贝被移除的index之后的数据
std::copy_n(m_data + index + 1, m_length - index - 1, data + index);
// 最后，销毁老数组，用新数组替代
delete[] m_data;
m_data = data;
--m_length;
}
|
下面是完整的IntArray容器类。
IntArray.h:
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
|
#ifndef INTARRAY_H
#define INTARRAY_H
#include <algorithm> // for std::copy_n
#include <cassert> // for assert()
class IntArray
{
private:
int m_length{};
int* m_data{};
public:
IntArray() = default;
IntArray(int length):
m_length{ length }
{
assert(length >= 0);
if (length > 0)
m_data = new int[length]{};
}
~IntArray()
{
delete[] m_data;
// 这里没有将 m_data 设为 null，m_length 设置为 0，因为对象被销毁，没有任何人可以使用
}
IntArray(const IntArray& a): IntArray(a.getLength()) // 拷贝构造函数，调用普通的构造函数
{
std::copy_n(a.m_data, m_length, m_data); // 拷贝数据
}
IntArray& operator=(const IntArray& a)
{
// 自赋值检查
if (&a == this)
return *this;
// 设置合适的存储空间
reallocate(a.getLength());
std::copy_n(a.m_data, m_length, m_data); // 拷贝数据
return *this;
}
void erase()
{
delete[] m_data;
// 需要将 m_data 设置为 nullptr
// 不然它指向的是被销毁的内存!
m_data = nullptr;
m_length = 0;
}
int& operator[](int index)
{
assert(index >= 0 && index < m_length);
return m_data[index];
}
// reallocate 重新设置数组大小. 任何现有的元素都被销毁. 这个函数运行较快.
void reallocate(int newLength)
{
// 首先删除现有元素
erase();
// 如果设置为空，那么什么也不做
if (newLength <= 0)
return;
// 分配新内存
m_data = new int[newLength];
m_length = newLength;
}
// 重新设置数组大小. 老元素会被保留 这个函数会慢一些.
void resize(int newLength)
{
// 如果数组长度已经符合预期，就不需要操作了
if (newLength == m_length)
return;
// 如果设置为空，清除现有数据，然后返回
if (newLength <= 0)
{
erase();
return;
}
// 这里能确定至少有一个元素
// 先分配新的数组
// 再拷贝数据
// 然后销毁旧的数组
// 最后m_data指向新的数组
// 首先分配新的数组
int* data{ new int[newLength] };
// 判断有多少元素要拷贝
// 拷贝两个数组，长度小的对应个数的元素
if (m_length > 0)
{
int elementsToCopy{ (newLength > m_length) ? m_length : newLength };
std::copy_n(m_data, elementsToCopy, data); // copy the elements
}
// 不再需要老的数组，进行销毁
delete[] m_data;
// 现在开始，可以使用新的数组
// 这里只需要将 m_data 指向新分配的数组即可
// IntArray销毁时，数据会自动销毁
m_data = data;
m_length = newLength;
}
void insertBefore(int value, int index)
{
// 检查index值有效
assert(index >= 0 && index <= m_length);
// 创建一个比老数组大一个的空间
int* data{ new int[m_length+1] };
// 拷贝index之前的数据
std::copy_n(m_data, index, data);
// 将value插入新数组对应的位置
data[index] = value;
// 拷贝插入位置之后的数据
std::copy_n(m_data + index, m_length - index, data + index + 1);
// 最后，销毁老数组，用新数组替代
delete[] m_data;
m_data = data;
++m_length;
}
void remove(int index)
{
// 检查index值有效
assert(index >= 0 && index < m_length);
// 如果要移除的是数组最后一个元素，直接清空数组
if (m_length == 1)
{
erase();
return;
}
// 创建比老数组少一个的新空间
int* data{ new int[m_length-1] };
// 拷贝index之前的数据
std::copy_n(m_data, index, data);
// 拷贝被移除的index之后的数据
std::copy_n(m_data + index + 1, m_length - index - 1, data + index);
// 最后，销毁老数组，用新数组替代
delete[] m_data;
m_data = data;
--m_length;
}
// 额外的函数，提供简化的接口
void insertAtBeginning(int value) { insertBefore(value, 0); }
void insertAtEnd(int value) { insertBefore(value, m_length); }
int getLength() const { return m_length; }
};
#endif
|
现在，来测试它，证明它可以正常工作：
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
|
#include <iostream>
#include "IntArray.h"
int main()
{
// 声明有10个元素的数组
IntArray array(10);
// 设置为1到10
for (int i{ 0 }; i<10; ++i)
array[i] = i+1;
// 重置为8个元素
array.resize(8);
// 位置5之前，插入20
array.insertBefore(20, 5);
// 移除位置 3 对应的数据
array.remove(3);
// 将30 和 40 分别插入到头和尾
array.insertAtEnd(30);
array.insertAtBeginning(40);
// 测试拷贝构造和赋值运算符
{
IntArray b{ array };
b = array;
b = b;
array = array;
}
// 打印数组中的数据
for (int i{ 0 }; i<array.getLength(); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
}
|
这将产生以下结果：
尽管编写容器类可能相当复杂，但好消息是通常只需要编写一次。一旦容器类可以正常工作，您就可以根据需要频繁地使用和复用它，而不需要额外的编程工作。
还可以并且应该做出一些额外改进：
- 可以将其实现为模板类，以便它可以与任何可复制的类型一起工作，而不仅仅是int。
- 应该为各种成员函数添加const重载，以正确支持const IntArrays。
- 应该添加对移动语义的支持（通过添加移动构造函数和移动赋值）。
- 在执行调整大小或插入操作时，可以移动元素，而不是复制元素。
还有一件事：如果标准库中的类已经满足您的需要，请使用它，而不是创建自己的类。例如，与其使用IntArray，不如使用std::vector<int>。它经过了充分测试，效率高，并且能与标准库中的其他类良好配合。
有时，您也会需要一个标准库中不存在的专用容器类，因此需要知道何时以及如何创建自己的容器类。
对于高级读者
与异常处理相关的一些高级改进：
- 执行调整大小或插入操作时，仅当元素的移动构造函数为noexcept时才移动元素，否则复制它们（参考后面讲解的 std::move_if_noexcept）。
- 为调整大小或插入操作提供强大的异常安全保证（参考后面讲解的 异常规范和noexcept）。
23.6 std::initializer_list
下一节
