如何在 C++ 中编写自己的 STL 容器

2025年3月22日 | 阅读11分钟

订阅列表、vector和map是C++标准模板库（STL）精确定义中所包含的众多复杂信息结构和算法中的一部分。然而，这些容器的目的是为了充分展示对组件行为和功能的深入理解。在本文中，您可以从头开始创建自己的STL容器，从而学到大量关于C++及其重要方面的知识。

为什么构建独特的容器？

一些客户可能需要一种解决方案，它能提供标准打包无法实现的特定功能或能力。

为什么要制作一个特殊的容器？

自我打包：一些客户可能需要一种配置，这种配置非常高效，运行良好，或者具有标准打包无法提供的功能。

学习：创建一个自己的特殊容器并将其集成到程序中的过程，有助于个人基本理解如何创建应用程序、如何使用对象以及如何分配内存。

改进：在某些情况下，可以针对特定任务或比平时更极端的情况优化一个清晰的容器，从而提高性能。

需要理解的关键概念

容器定义：容器可以被引用为一种数据类型，它包含并操作其他对象。建议您熟悉主要的STL容器（std::vector或std::list或std::map），并理解它们的特性及其使用目的。
迭代器：与为STL容器提供的默认函数允许暴露其元素类似，迭代器之所以有用，是因为它们确定了如何遍历和修改容器的内容。需要注意的是，您的容器必须支持多种类型的迭代器，例如前向迭代器和双向迭代器。
内存管理：在构建容器的过程中，动态内存分配是一个不可避免的问题。您应该清楚如何分配内存、释放内存以及调整内存分配的大小。
模板：STL容器中实现了模板类，以便它们能够接受任何数据类型。如果要构建一个通用的容器，开发人员需要学习模板以及实现这些功能的技巧。
异常安全性：如果容器没有被设计得足够健壮或没有有效地使用异常处理进行管理，就可能导致资源浪费和不可预测的行为。

创建自己的容器的基本指南

描述容器类：首先，创建您正在构建的容器的类。之后，选择要使用的主数据结构（链表、动态数组等）。
实现核心操作：实现基本操作，例如插入、删除和访问。这些步骤应在不损害容器结构的情况下执行。为了帮助用户在容器中导航，实现称为辅助迭代器的迭代器类。
分配：使用正确的复制构造函数、复制赋值运算符和析构函数来分配和释放内存。确保根据需要分配和更改资源。
容器测试：花时间对容器在某些情况下的行为进行详细测试，并确认其行为符合预期。同时不要忘记性能和边界情况。

性质

自己编写大部分C++标准描述模板库（STL）容器的代码会带来成就感和可观的知识，但您需要熟悉通用的C++语言和容器设计原则。在本快速基础指南中，您将找到一些关于如何开始开发自己的STL容器（在本例中是持久化对象）的基本技巧，以及一些有用的注意事项。

了解STL容器规则

在开始编写任何代码之前，开发STL容器需要了解要包含的内容。

迭代器：STL容器提供迭代器，以统一的方式访问和修改容器的元素。
分配器：分配器是容器必须包含的组成部分，以避免内存浪费。
异常安全性：容器应该是异常安全的，以避免破坏完整性并丢弃容器内的宝贵资源。

设计容器

决定您具体要创建哪种类型的容器，一些常见类型是

Vector：它是一个可扩展的列表。
List：它可以是项目的链，每个项目都连接到前一个和后一个项目。
Deque：它是一个队列，您可以从两端添加或删除。
Set/Map：之后是一个树，就红黑树而言，它不会失衡。

制定接口

创建将在容器类中提供的公共接口。这部分包括以下内容

构造函数/析构函数：在这种情况下，它是容器的创建和销毁的实现。
元素访问：获取元素的方法（如at()、operator[]）。
修改：修改元素的方法（如push_back()、pop_back()）。
容量：与容器的大小和范围相关的查询（size()、empty()等）。

内部结构的实现

根据容器类型选择合适的数据结构：使用合适的数组来动态扩展vector。
List：它使用带有指向前一个和后一个元素的指针的节点。
Deque：使用多个数组来有效地支持两端的插入和删除。

使用一个迭代器来创建一个递归类，使应用程序能够导航容器。

迭代器函数

支持标准操作（如++、--、*、->）。
与STL算法兼容。
包含用于内存管理的分配器，允许用户定义内存分配策略。

异常安全

确保您的容器能有效处理异常，包括
实现RAII原则（资源获取即初始化），为方法提供强大的异常保证。

彻底的测试

测试至关重要。确保您的容器
满足所有STL接口要求。
在各种场景下都能有效处理边界情况（如大型空容器）。

程序

让我们举个例子来说明如何在C++中创建自己的STL容器。

#include <iostream>
#include <stdexcept>

template <typename T>
class Vector {
public:
    Vector();                   // Default constructor
    ~Vector();                  // Destructor
    Vector(const Vector& other); // Copy constructor
    Vector& operator=(const Vector& other); // Copy assignment operator

    void push_back(const T& value); // Add element to the end
    void pop_back();                // Remove the last element
    T& operator[](std::size_t index); // Access element by index
    const T& operator[](std::size_t index) const; // Const version

    std::size_t size() const; // Return number of elements
    bool empty() const;       // Check if the vector is empty

private:
    void resize();            // Resize the internal storage
    void copy_from(const Vector& other); // Copy elements from another vector

    T* data_;                 // Pointer to the array of elements
    std::size_t size_;        // Number of elements in the vector
    std::size_t capacity_;    // Capacity of the vector (allocated space)
};

template <typename T>
Vector<T>::Vector()
    : data_(nullptr), size_(0), capacity_(0) {}

template <typename T>
Vector<T>::~Vector() {
    delete[] data_;
}

template <typename T>
Vector<T>::Vector(const Vector& other)
    : data_(nullptr), size_(0), capacity_(0) {
    copy_from(other);
}

template <typename T>
Vector<T>& Vector<T>::operator=(const Vector& other) {
    if (this != &other) {
        delete[] data_;
        copy_from(other);
    }
    return *this;
}

template <typename T>
void Vector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        resize();
    }
    data_[size_] = value;
    ++size_;
}

template <typename T>
void Vector<T>::pop_back() {
    if (size_ > 0) {
    --size_;
    }
}

template <typename T>
T& Vector<T>::operator[](std::size_t index) {
    if (index >= size_) {
        throw std::out_of_range("Index out of range");
    }
    return data_[index];
}

template <typename T>
const T& Vector<T>::operator[](std::size_t index) const {
    if (index >= size_) {
        throw std::out_of_range("Index out of range");
    }
    return data_[index];
}

template <typename T>
std::size_t Vector<T>::size() const {
    return size_;
}

template <typename T>
bool Vector<T>::empty() const {
    return size_ == 0;
}

template <typename T>
void Vector<T>::resize() {
    std::size_t new_capacity = capacity_ == 0 ? 1 : 2 * capacity_;
    T* new_data = new T[new_capacity];

    for (std::size_t i = 0; i < size_; ++i) {
        new_data[i] = data_[i];
    }

    delete[] data_;
    data_ = new_data;
    capacity_ = new_capacity;
}

template <typename T>
void Vector<T>::copy_from(const Vector& other) {
    size_ = other.size_;
    capacity_ = other.capacity_;
    data_ = new T[capacity_];

    for (std::size_t i = 0; i < size_; ++i) {
        data_[i] = other.data_[i];
    }
}

// Example usage
int main() {
    Vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    std::cout << "Vector contents:" << std::endl;
    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << ' ';
    }
    std::cout << std::endl;

    v.pop_back();
    std::cout << "After pop_back:" << std::endl;
    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << ' ';
    }
    std::cout << std::endl;

    return 0;
}

输出

Vector contents:
1 2 3 
After pop_back:
1 2

说明

它包含一些基本功能，如添加和删除元素、通过索引访问元素以及修改存储数组的大小。Vector类包含一个名为data_的指针，该指针指向一个动态数组，用于存储类的所有内部数据。它还包含size_和capacity_，分别表示数组中的元素数量和分配数组的大小。当调用默认构造函数时，该类没有设置任何参数，此时会初始化一个空vector，data_为null，size_为0，capacity_为0。析构函数在不再需要vector时可以释放内存，以帮助避免内存泄漏。

该类通过复制构造函数和复制赋值运算符提供了一种支持复制的方式。在复制构造函数中，新vector使用现有vector的副本构造，并为元素分配空间。在复制赋值运算符中，任何现有内存都会被置为无效，然后vector的内存会被完整复制，以防止内容丢失。

push_back()方法在向vector添加新元素之前会检查当前容量。如果当前容量不足，它将调用resize()方法来增加vector的内存空间，并将旧元素复制到新分配的数组中。pop_back()方法会删除最后一个元素并减小容器的大小，但它不会释放内存。这意味着它只减少了跟踪元素的数量，而不影响性能。

通过operator[]访问元素，该运算符执行所需的边界检查。如果用户尝试访问无效索引，将抛出std::out_of_range异常。resize()方法在需要时（例如，当大小增加时）获取vector中的一个地址。它创建一个新的、更大的数组，将旧数组的所有元素复制到新数组中，然后更新capacity和data指针。

有一些实用函数，如size()，它返回vector当前拥有的元素数量；以及empty()，顾名思义，如果vector为空，它会检查并返回true。这个实现有助于理解动态数组的工作原理以及容器如何管理其底层存储和容量。

复杂度

在C++中开发自己的STL容器需要驾驭多个复杂层面，这主要是由于需要遵守标准库容器的复杂设计和操作标准。从核心上讲，实现自定义容器需要对C++模板编程、内存管理和数据结构设计基础有深入的理解。STL容器是多功能且通用的，可以容纳各种数据类型和操作，这意味着您的自定义容器也必须使用模板支持不同的数据类型，同时确保高效的内存使用。

主要困难之一是掌握模板编程，因为STL容器设计为通用的，这需要使用C++模板来创建可以处理任何类型数据的容器。这不仅包括按大纲描述容器，还包括执行与之相关的操作，如构造函数、析构函数和赋值运算符。此外，正确处理复制语义也很重要，因为浅拷贝和内存泄漏等相关问题可能导致程序丢失或崩溃。

内存管理在此上下文中增加了另一个复杂性层面。std::vector等容器分配和管理各种资源来存储其元素。您的自定义容器应实现内存分配、调整大小和释放内存，以提高性能并防止内存泄漏。例如，一个类似vector的容器在超出其容量限制时应采用有效的重新分配策略，例如g、d和n。它们还为类型安全和STL库的封装提供了支持，因为它们带来了对象的可视化方面，这对于创建动态容器是必需的。创建容器也意味着创建迭代器，STL算法需要它们。迭代器有多种类型，您需要创建相应的迭代器并实现其操作。例如，随机访问迭代器和双向迭代器应支持++、--、*等操作。

这种类型的迭代器还必须与STL算法兼容，例如std::sort和std::find。

资源考虑是容器设计的基石。每个操作，如插入、删除，甚至访问，都应以优化的方式工作。例如，基于动态数组的容器应降低重新分配的成本，以维持性能水平，只要容器不断扩展。

异常安全性是另一个非常重要的问题。在容器声明但操作在完成前失败的正常情况下，也应该如此。这意味着要充分设计容器，提供强大的异常处理机制，并使用复制和交换方法进行资源操作。

总而言之，在C++中创建自己的STL容器是困难的，因为您需要掌握许多概念才能实现它，例如C++模板、内存分配技术、迭代器实现、性能调优以及确保异常安全性。所有这些考虑因素都需要解决，这增加了任务的复杂性，同时也使其非常有价值。

结论

总之，在C++中开发自己的STL容器是一项具有挑战性但有益的任务，它需要对许多高级编程原理有深刻的理解。它始于对C++模板的深刻理解，这对于构建能够管理不同数据类型的通用容器至关重要。它不仅包括定义容器，还包括执行构造函数、析构函数和赋值运算符等基本功能，以有效地处理资源并避免内存泄漏或浅拷贝等常见问题。

设计容器需要仔细考虑性能。每项操作，如添加、删除或访问元素，都需要进行优化，以确保效率和响应能力。这包括分析和改进时间复杂度，以满足不同应用程序的需求。创建自己的STL容器是一项复杂而详细的任务，涉及C++编程的高级方面。它提供了对STL工作原理的宝贵见解，并增强了对模板编程、内存管理和性能优化的理解。尽管存在挑战，通过这个过程获得的技能对于精通C++和构建高质量的定制数据结构至关重要。

下一个主题C++中预处理器指令和函数模板的区别

如何在 C++ 中编写自己的 STL 容器

为什么构建独特的容器？

为什么要制作一个特殊的容器？