容器类

在现实生活中，我们无时无刻不在使用容器。早餐麦片装在盒子里，书籍的页面被封面与装订包裹，车库里的各种物品也被收纳于形形色色的容器之中。倘若没有容器，许多物品的使用将变得极为不便：设想阅读一本毫无装订的书，或在不用碗的情况下直接吃未装盒的麦片——必然是一团糟。容器所提供的主要价值，正在于它能够帮助整理并存储被置于其中的物品。

同理，容器类（container class）是一种为了保存并组织另一类型（可为其他类或基本类型）的多个实例而设计的类。容器类种类繁多，各自在使用时具有不同的优势、劣势与限制。迄今为止，编程中最常用的容器为数组（array），诸位已在诸多示例中见过。尽管 C++ 内置数组功能，程序员仍常选用数组容器类（std::array 或 std::vector），因其额外提供了诸多便利。与内置数组不同，数组容器类通常支持动态调整大小（增删元素后自动伸缩）、在作为函数参数传递时仍能记住自身大小，并可进行越界检查。这不仅使数组容器类较普通数组更易用，亦使其更安全。

容器类功能

容器类通常实现一套相当标准化的最小功能集合。任何定义良好的容器，大都包含以下函数：

  • 通过构造函数创建一个空容器
  • 向容器内插入新对象
  • 从容器中移除对象
  • 报告当前容器内的对象数目
  • 清空容器内全部对象
  • 提供对已存对象的访问
  • （可选）对元素进行排序

某些容器类有时会省略上述部分功能。例如，数组容器类常省略插入与删除函数，因其效率低下，设计者亦不希望鼓励其使用。

容器类体现的是“成员归属”（member-of）关系。例如，数组中的元素即为该数组的“成员”。请注意，此处“member-of”指日常语义，而非 C++ 中类成员（class member）之意。

容器的种类

容器类通常可分为两大类型。值容器（value container）属于组合（composition），保存所容纳对象的副本，故负责这些副本的创建与销毁。引用容器（reference container）属于聚合（aggregation），存储指向其他对象的指针或引用，故不负责这些对象的创建与销毁。

与现实生活不同，现实中的容器可随意容纳任意类型之物，而 C++ 中容器通常只能保存单一类型的数据。例如，若有一整数数组，则其只能存放整数。与某些其它语言不同，许多 C++ 容器不允许任意混用类型。若需容器同时存放整数与双精度浮点数，通常必须编写两个分离的容器（或采用模板——C++ 的高级特性之一）。尽管使用上存在限制，容器仍极其有用，它们令编程更轻松、更安全、更高效。

一个数组容器类示例

本节我们将从零开始编写一个整数数组类，实现容器应具备的大部分常用功能。该数组类为值容器，将保存所组织元素的副本。顾名思义，该容器将保存一个整数数组，功能类似于 std::vector<int>。

首先，创建 IntArray.h 文件：

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
};

#endif

IntArray 需记录两项数据：数据本身以及数组长度。由于我们希望数组大小可变，必须进行动态内存分配，因此需使用指针保存数据。

#ifndef INTARRAY_H
#define INTARRAY_H

class IntArray
{
private:
    int m_length{};
    int* m_data{};
};

#endif

接下来，添加若干构造函数，以支持创建 IntArray。我们提供两个构造函数：一个构造空数组，另一个按预定长度构造数组。

#ifndef INTARRAY_H
#define INTARRAY_H

#include <cassert> // for assert()
#include <cstddef> // for std::size_t

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[static_cast<std::size_t>(length)]{};
    }
};

#endif

我们尚需若干函数以清理 IntArray。首先编写析构函数，仅负责释放动态分配的内存；其次编写 erase() 函数，用于清空数组并将长度置零。

~IntArray()
{
    delete[] m_data;
    // 此处无需将 m_data 置空或将 m_length 置 0，因为对象将在该函数执行后立即销毁
}

void erase()
{
    delete[] m_data;

    // 必须将 m_data 设为 nullptr，否则它将悬空指向已释放的内存！
    m_data = nullptr;
    m_length = 0;
}

现在重载下标运算符 []，以便访问数组元素。我们需确保索引参数有效，可借助 assert() 实现；另增一函数返回数组长度。至此全部代码如下：

#ifndef INTARRAY_H
#define INTARRAY_H

#include <cassert> // for assert()
#include <cstddef> // for std::size_t

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[static_cast<std::size_t>(length)]{};
    }

    ~IntArray()
    {
        delete[] m_data;
        // 此处无需将 m_data 置空或将 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 类。可分配指定长度的 IntArray，并通过 [] 运算符访问或修改元素。

然而，当前 IntArray 仍无法：改变大小、插入或删除元素、排序；且复制数组时，会因浅拷贝数据指针而引发问题。

调整数组大小

首先，编写允许调整数组大小的代码。我们实现两个函数：其一 reallocate()，调整大小时销毁原有全部元素，但速度快；其二 resize()，调整大小时保留原有元素，但速度较慢。

#include <algorithm> // for std::copy_n

    // reallocate 调整数组大小。所有现有元素将被销毁。本函数执行迅速。
    void reallocate(int newLength)
    {
        // 首先删除现有元素
        erase();

        // 若调整后数组为空，直接返回
        if (newLength <= 0)
            return;

        // 然后分配新元素
        m_data = new int[static_cast<std::size_t>(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[static_cast<std::size_t>(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 指向动态分配的新数组地址，
        // 因 data 为动态分配，离开作用域时不会被销毁
        m_data = data;
        m_length = newLength;
    }

呼！这确实有些棘手！

拷贝构造函数与赋值运算符

再添加拷贝构造函数与赋值运算符，以支持数组拷贝。

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() 类似。

void insertBefore(int value, int index)
 {
     // 对索引值进行健全性检查
     assert(index >= 0 && index <= m_length);

     // 首先创建比旧数组大一个元素的新数组
     int* data{ new int[static_cast<std::size_t>(m_length+1)] };

     // 复制索引前的所有元素
     std::copy_n(m_data, index, data);

     // 在新数组的指定索引处插入新元素
     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)
 {
     // 对索引值进行健全性检查
     assert(index >= 0 && index < m_length);

     // 若数组仅剩最后一个元素，清空后返回
     if (m_length == 1)
     {
         erase();
         return;
     }

     // 首先创建比旧数组小一个元素的新数组
     int* data{ new int[static_cast<std::size_t>(m_length-1)] };

     // 复制索引前的所有元素
     std::copy_n(m_data, index, data);

     // 复制被删元素之后的所有值
     std::copy_n(m_data + index + 1, m_length - index - 1, data + index);

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

至此，给出完整的 IntArray 容器类。

IntArray.h：

#ifndef INTARRAY_H
#define INTARRAY_H

#include <algorithm> // for std::copy_n
#include <cassert> // for assert()
#include <cstddef> // for std::size_t

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[static_cast<std::size_t>(length)]{};
    }

    ~IntArray()
    {
        delete[] m_data;
        // 此处无需将 m_data 置空或将 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[static_cast<std::size_t>(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[static_cast<std::size_t>(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 指向动态分配的新数组地址，
        // 因 data 为动态分配，离开作用域时不会被销毁
        m_data = data;
        m_length = newLength;
    }

    void insertBefore(int value, int index)
    {
        // 对索引值进行健全性检查
        assert(index >= 0 && index <= m_length);

        // 首先创建比旧数组大一个元素的新数组
        int* data{ new int[static_cast<std::size_t>(m_length+1)] };

        // 复制索引前的所有元素
        std::copy_n(m_data, index, data);

        // 在新数组的指定索引处插入新元素
        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)
    {
        // 对索引值进行健全性检查
        assert(index >= 0 && index < m_length);

        // 若数组仅剩最后一个元素，清空后返回
        if (m_length == 1)
        {
            erase();
            return;
        }

        // 首先创建比旧数组小一个元素的新数组
        int* data{ new int[static_cast<std::size_t>(m_length-1)] };

        // 复制索引前的所有元素
        std::copy_n(m_data, index, data);

        // 复制被删元素之后的所有值
        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

测试 IntArray

下面简单测试以验证其可用性：

#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;
}

程序输出：

40 1 2 3 5 20 6 7 8 30

尽管编写容器类颇为复杂，但好消息是只需编写一次。一旦容器类正常工作，便可随时反复使用，无需额外编程。

改进方向

若干可/应进一步改进之处：

  • 可将其改为模板类，使之适用于任何可复制类型，而非仅限于 int。
  • 应添加各成员函数的 const 重载，以正确支持 const IntArray。
  • 应添加移动语义支持（通过增加移动构造函数与移动赋值运算符）。
  • 执行 resize 或插入操作时，可使用移动而非复制元素。

进阶读者

有关异常处理的高级改进：

  • 执行 resize 或插入操作时，仅当元素的移动构造函数为 noexcept 时才移动元素，否则复制（std::move_if_noexcept）。
  • 为 resize 或插入操作提供强异常安全保障（Exception specifications and noexcept）。

最后提醒：若标准库中的类已能满足需求，请优先使用，而非自行创建。例如，与其使用 IntArray，不如直接使用 std::vector<int>——它经过充分测试、高效，且与标准库中的其他类配合良好。然而，有时你需要标准库尚未提供的专用容器类，因此了解如何自行创建亦属必要。

关注公众号，回复"cpp-tutorial"

可领取价值199元的C++学习资料

公众号二维码

扫描上方二维码或搜索"cpp-tutorial"