Skip to content
English

16.6 - 容器类

Key Takeaway

-

在现实生活中我们经常会用到容器。麦片是装在盒子里的，书也有封面和装订，你的车库里应该也装了不少东西吧。如果没有容器，使用这些东西的时候一定会非常的混乱。容器最大的功能，就是帮助我们组织和存储存在容器中的东西。

类似的，容器类是一种被设计用来存放和组织多种其他类型（可以是类也可以是基本数据类型）实例的类。容器类的种类有很多，每种都有其自己的优势和劣势，以及使用限制。到目前为止，最有用的容器是数组，你在前面的例子中以及多次使用它了。尽管C++ 提供了内建的数组功能，程序员却大多使用数组容器类（std::array 或std::vector) 。和内建的数组不同，这些数组容器类通常可以动态地调整其大小（当资源被添加或删除时）、可以在传递到函数时保留其大小信息，还可以进行边界检查。这些功能不但使得数组容器类简单易用，而且安全性也更好。

容器类通常会实现一系列标准的、最小化的功能。大多数实现良好的容器类通常包括下面这些功能：

  • 创建一个空的容器（通过构造函数）；
  • 向容器添加一个对象；
  • 从容器中删除一个对象；
  • 报告容器中对象的个数；
  • 清空容器；
  • 提供存储对象的访问方式；
  • 元素排序（可选的）。

有些容器会忽略上述功能中的某些。例如，数组容器类通常会忽略插入和删除操作，因为数组数据结构在进行插入和删除时效率很低，所以类的设计者不鼓励我们使用这两种操作。

容器类实现了一种成员关系。例如，数组中的元素是该数组的一个成员（属于）。注意，我们这里说的成员是平常意义上的成员，而不是指类成员。

容器类型

容器类通常有两个变种。值容器是组合关系，它存放了其元素的拷贝（因此必须负责创建和销毁这些拷贝）。引用容器则是聚合关系，它保存了元素的指针或引用（因此无需操心它们的创建和销毁）。

数组容器类

在这个例子中，我们会从头编写一个整型数组类并实现它应该提供的大部分功能。该数组类是一个值容器，它保存元素的拷贝。和它们的名字暗示的那样，这个容器会保存一个整型数构成的数组，类似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

我们还需要创建用于清理数组的函数。首先，定义一个析构函数，它的功能就是释放数据占用的内存。然后，再编写一个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;
}

现在，重载[]操作符用于访问数组中的元素。在重载下标运算符的时候，必须确保索引是合法的，该操作可以使用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
#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，然后使用下标运算符获取元素的值。

但是，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
// reallocate 会调整数组大小，但是它会在工作时销毁所有的数组元素。该函数的速度很快
void reallocate(int newLength)
{
    // 首先，删除全部的元素
    erase();

    // 如果要创建空数组，此处返回即可
    if (newLength <= 0)
        return;

    // 分配新的元素
    m_data = new int[newLength];
    m_length = newLength;
}

// resize 会调整数组大小，数组中的元素会被保存下来。该函数的速度比较慢
void resize(int newLength)
{
    // 如果数组的长度已经满足要求，完成
    if (newLength == m_length)
        return;

    // 如果需要将数组调整为一个空数组，完成并返回
    if (newLength <= 0)
    {
        erase();
        return;
    }

    // 假设 newLength 大于等于1。该算法的原理如下：
    // 首先，分配一个新的数组。然后将旧数组中的元素都拷贝到新的数组中。完成后，销毁旧数组。
    // 然后让 m_data 指向新的数组

    // 分配一个新的数组
    int* data{ new int[newLength] };

    // 确定有多少个元素需要从旧数组中拷贝到新数组。
    // 这里我们希望从旧数组中拷贝尽可能多的元素（新数组不一定比旧数组大）
    // 拷贝的元素个数是新旧两个数组中较小的一个
    if (m_length > 0)
    {
        int elementsToCopy{ (newLength > m_length) ? m_length : newLength };

        // Now copy the elements one by one
        for (int index{ 0 }; index < elementsToCopy; ++index)
            data[index] = m_data[index];
    }

    // 删除旧数组
    delete[] m_data;

    // 开始使用新的数组作为数据！最简单的办法就是让 m_data指向新数组的地址。
    // 由于该数组是动态分配的，所以不会在离开作用域时被销毁
    m_data = data;
    m_length = newLength;
}

还挺复杂！

多数的数组容器类会止步于此。不过，也许你想知道插入和删除操作应该如何实现，所以我们继续实现这两个功能。其实现方法和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
void insertBefore(int value, int index)
{
    // 检查数组索引合法性
    assert(index >= 0 && index <= m_length);

    // 首先创建一个新的数组，其长度比旧数组大1
    int* data{ new int[m_length+1] };

    // 拷贝到当前索引的所有元素
    for (int before{ 0 }; before < index; ++before)
        data[before] = m_data[before];

    // 插入新的元素到新数组
    data[index] = value;

    // 继续拷贝剩余的元素
    for (int after{ index }; after < m_length; ++after)
        data[after+1] = m_data[after];

    // 最后，删除旧数组，然后使用新的数组作为数据
    delete[] m_data;
    m_data = data;
    ++m_length;
}

void remove(int index)
{
    // 检查数组索引合法性
    assert(index >= 0 && index < m_length);

    // 如果这已经是最后一个数组元素，将数组设置为空数组然后完成
    if (m_length == 1)
    {
        erase();
        return;
    }

    // 创建一个新数组，其大小比旧数组小1
    int* data{ new int[m_length-1] };

    // 拷贝到索引的全部元素
    for (int before{ 0 }; before < index; ++before)
        data[before] = m_data[before];

    // 继续拷贝被删除元素后面的所有元素
    for (int after{ index+1 }; after < m_length; ++after)
        data[after-1] = m_data[after];

    // 最后，删除旧数组并使用新的数组作为数据
    delete[] m_data;
    m_data = data;
    --m_length;
}

// A couple of additional functions just for convenience
void insertAtBeginning(int value) { insertBefore(value, 0); }
void insertAtEnd(int value) { insertBefore(value, 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
#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;
        // we don't need to set m_data to null or m_length to 0 here, since the object will be destroyed immediately after this function anyway
    }

    void erase()
    {
        delete[] m_data;
        // We need to make sure we set m_data to nullptr here, otherwise it will
        // be left pointing at deallocated memory!
        m_data = nullptr;
        m_length = 0;
    }

    int& operator[](int index)
    {
        assert(index >= 0 && index < m_length);
        return m_data[index];
    }

    // reallocate resizes the array.  Any existing elements will be destroyed.  This function operates quickly.
    void reallocate(int newLength)
    {
        // First we delete any existing elements
        erase();

        // If our array is going to be empty now, return here
        if (newLength <= 0)
            return;

        // Then we have to allocate new elements
        m_data = new int[newLength];
        m_length = newLength;
    }

    // resize resizes the array.  Any existing elements will be kept.  This function operates slowly.
    void resize(int newLength)
    {
        // if the array is already the right length, we're done
        if (newLength == m_length)
            return;

        // If we are resizing to an empty array, do that and return
        if (newLength <= 0)
        {
            erase();
            return;
        }

        // Now we can assume newLength is at least 1 element.  This algorithm
        // works as follows: First we are going to allocate a new array.  Then we
        // are going to copy elements from the existing array to the new array.
        // Once that is done, we can destroy the old array, and make m_data
        // point to the new array.

        // First we have to allocate a new array
        int* data{ new int[newLength] };

        // Then we have to figure out how many elements to copy from the existing
        // array to the new array.  We want to copy as many elements as there are
        // in the smaller of the two arrays.
        if (m_length > 0)
        {
            int elementsToCopy{ (newLength > m_length) ? m_length : newLength };

            // Now copy the elements one by one
            for (int index{ 0 }; index < elementsToCopy; ++index)
                data[index] = m_data[index];
        }

        // Now we can delete the old array because we don't need it any more
        delete[] m_data;

        // And use the new array instead!  Note that this simply makes m_data point
        // to the same address as the new array we dynamically allocated.  Because
        // data was dynamically allocated, it won't be destroyed when it goes out of scope.
        m_data = data;
        m_length = newLength;
    }

    void insertBefore(int value, int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index <= m_length);

        // First create a new array one element larger than the old array
        int* data{ new int[m_length+1] };

        // Copy all of the elements up to the index
        for (int before{ 0 }; before < index; ++before)
            data[before] = m_data[before];

        // Insert our new element into the new array
        data[index] = value;

        // Copy all of the values after the inserted element
        for (int after{ index }; after < m_length; ++after)
            data[after+1] = m_data[after];

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        ++m_length;
    }

    void remove(int index)
    {
        // Sanity check our index value
        assert(index >= 0 && index < m_length);

        // If we're removing the last element in the array, we can just erase the array and return early
        if (m_length == 1)
        {
            erase();
            return;
        }

        // First create a new array one element smaller than the old array
        int* data{ new int[m_length-1] };

        // Copy all of the elements up to the index
        for (int before{ 0 }; before  < index; ++before)
            data[before] = m_data[before];

        // Copy all of the values after the removed element
        for (int after{ index+1 }; after < m_length; ++after)
            data[after-1] = m_data[after];

        // Finally, delete the old array, and use the new array instead
        delete[] m_data;
        m_data = data;
        --m_length;
    }

    // A couple of additional functions just for convenience
    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
#include <iostream>
#include "IntArray.h"

int main()
{
    // Declare an array with 10 elements
    IntArray array(10);

    // Fill the array with numbers 1 through 10
    for (int i{ 0 }; i<10; ++i)
        array[i] = i+1;

    // Resize the array to 8 elements
    array.resize(8);

    // Insert the number 20 before element with index 5
    array.insertBefore(20, 5);

    // Remove the element with index 3
    array.remove(3);

    // Add 30 and 40 to the end and beginning
    array.insertAtEnd(30);
    array.insertAtBeginning(40);

    // Print out all the numbers
    for (int i{ 0 }; i<array.getLength(); ++i)
        std::cout << array[i] << ' ';

    std::cout << '\n';

    return 0;
}

程序运行结果：

1
40 1 2 3 5 20 6 7 8 30

虽然编写一个容器类是非常复杂的事情，好消息是你只需要编写一次即可。一旦某个容器类可以正常工作了。那么你接下来就可以不断地使用它了。

尽管我们的 IntArray 容器中存放的是基本数据类型 (int)，我们其实也可以使用用户定义类型(例如 Point 类).

还有一件事：如果标准库中的一个类可以满足你的需求，那你应该直接使用它而不是创建自己的类。例如，与其使用 IntArray，不如使用 std::vector<int>。它是经过检验的，效率很高，并且与标准库中的其他类可以很好地配合。但有时你需要标准库中不存在的专用容器类，因此最好知道在需要时如何创建自己的容器类。在介绍了一些更基本的主题之后，我们将更多地讨论标准库中的容器。