如何在 C++ 中实现一个高效的“自增长数组”容器

作者

在现代 C++ 开发中，经常需要一个既能快速访问元素，又能在需要时自动扩容的容器。标准库中的 std::vector 已经提供了大部分功能，但有时我们希望对其进行微调，以满足特定的性能或内存占用需求。本文将演示如何从头实现一个类似 std::vector 的“自增长数组”，并探讨其核心设计决策、复杂度分析以及常见使用场景。

1. 设计目标

  • 动态扩容：当容量不足时自动增大，扩容策略可自定义。
  • 连续内存：保持内部元素连续存储，兼容指针和引用。
  • 快速访问：支持 operator[]、at()、front()、back() 等常用接口。
  • 资源管理：RAII，避免内存泄漏。
  • 移动语义：实现移动构造和移动赋值，提升性能。

2. 核心类定义

template <typename T>
class DynArray {
public:
    // 构造、析构
    DynArray();
    explicit DynArray(size_t init_capacity);
    DynArray(const DynArray& other);
    DynArray(DynArray&& other) noexcept;
    ~DynArray();

    // 赋值
    DynArray& operator=(const DynArray& other);
    DynArray& operator=(DynArray&& other) noexcept;

    // 容量与大小
    size_t size() const noexcept { return sz; }
    size_t capacity() const noexcept { return cap; }
    bool empty() const noexcept { return sz == 0; }

    // 访问
    T& operator[](size_t i) noexcept { return data[i]; }
    const T& operator[](size_t i) const noexcept { return data[i]; }
    T& at(size_t i);
    const T& at(size_t i) const;

    T& front() noexcept { return data[0]; }
    const T& front() const noexcept { return data[0]; }
    T& back() noexcept { return data[sz-1]; }
    const T& back() const noexcept { return data[sz-1]; }

    // 插入删除
    void push_back(const T& value);
    void push_back(T&& value);
    void pop_back();

    // 预留空间
    void reserve(size_t new_cap);
    void clear() noexcept;

private:
    T* data{nullptr};
    size_t sz{0};
    size_t cap{0};

    void reallocate(size_t new_cap);
};

3. 关键实现细节

3.1 内存分配与析构

template <typename T>
DynArray <T>::DynArray() : data(nullptr), sz(0), cap(0) {}

template <typename T>
DynArray <T>::DynArray(size_t init_capacity) {
    if (init_capacity) {
        data = static_cast<T*>(::operator new(sizeof(T) * init_capacity));
        cap = init_capacity;
    }
}

template <typename T>
DynArray <T>::~DynArray() {
    clear();
    ::operator delete(data);
}

operator new 与 operator delete 用于原始内存分配，避免调用构造/析构。元素构造与析构手动控制。

3.2 复制与移动

template <typename T>
DynArray <T>::DynArray(const DynArray& other)
    : data(nullptr), sz(other.sz), cap(other.cap) {
    if (cap) {
        data = static_cast<T*>(::operator new(sizeof(T) * cap));
        std::uninitialized_copy(other.data, other.data + sz, data);
    }
}

template <typename T>
DynArray <T>::DynArray(DynArray&& other) noexcept
    : data(other.data), sz(other.sz), cap(other.cap) {
    other.data = nullptr;
    other.sz = other.cap = 0;
}

template <typename T>
DynArray <T>& DynArray<T>::operator=(const DynArray& other) {
    if (this != &other) {
        DynArray tmp(other);
        std::swap(data, tmp.data);
        std::swap(sz, tmp.sz);
        std::swap(cap, tmp.cap);
    }
    return *this;
}

template <typename T>
DynArray <T>& DynArray<T>::operator=(DynArray&& other) noexcept {
    if (this != &other) {
        clear();
        ::operator delete(data);
        data = other.data;
        sz = other.sz;
        cap = other.cap;

        other.data = nullptr;
        other.sz = other.cap = 0;
    }
    return *this;
}

采用 “copy-and-swap” 技术实现异常安全的赋值操作。

3.3 重新分配

template <typename T>
void DynArray <T>::reallocate(size_t new_cap) {
    T* new_data = static_cast<T*>(::operator new(sizeof(T) * new_cap));
    std::uninitialized_move(data, data + sz, new_data);
    for (size_t i = 0; i < sz; ++i) {
        data[i].~T();
    }
    ::operator delete(data);
    data = new_data;
    cap = new_cap;
}

我们使用 std::uninitialized_move 将已有元素搬到新内存，然后手动析构旧元素并释放旧内存。

3.4 push_back 与 pop_back

template <typename T>
void DynArray <T>::push_back(const T& value) {
    if (sz == cap) reallocate(cap ? cap * 2 : 1);
    new (data + sz) T(value);
    ++sz;
}

template <typename T>
void DynArray <T>::push_back(T&& value) {
    if (sz == cap) reallocate(cap ? cap * 2 : 1);
    new (data + sz) T(std::move(value));
    ++sz;
}

template <typename T>
void DynArray <T>::pop_back() {
    if (sz == 0) throw std::out_of_range("pop_back on empty array");
    data[--sz].~T();
}

扩容采用 双倍增长 策略，保证平均 O(1) 的插入复杂度。

3.5 reserve 与 clear

template <typename T>
void DynArray <T>::reserve(size_t new_cap) {
    if (new_cap > cap) reallocate(new_cap);
}

template <typename T>
void DynArray <T>::clear() noexcept {
    for (size_t i = 0; i < sz; ++i) {
        data[i].~T();
    }
    sz = 0;
}

reserve 让用户预留更大的容量，减少后续扩容次数。clear 只析构元素，不释放内存，适合重复使用。

4. 性能评估

操作 复杂度 说明
push_back Amortized O(1) 双倍增长策略
pop_back O(1) 仅析构
operator[] O(1) 直接访问
at O(1) + 运行时检查 边界检查
reserve O(n) 复制所有元素
clear O(n) 析构所有元素

对比 std::vector，本实现几乎相同；唯一差异在于手动控制内存分配与析构，可根据具体需求做细微优化（如自定义分配器、对齐等）。

5. 实际使用示例

#include <iostream>
#include "dynarray.h" // 假设文件名为 dynarray.h

int main() {
    DynArray <int> arr;
    for (int i = 0; i < 10; ++i) arr.push_back(i * i);

    std::cout << "Size: " << arr.size() << " Capacity: " << arr.capacity() << "\n";
    for (size_t i = 0; i < arr.size(); ++i)
        std::cout << arr[i] << " ";
    std::cout << "\n";

    arr.pop_back();
    std::cout << "After pop_back, size: " << arr.size() << "\n";

    return 0;
}

6. 高级扩展

  1. 自定义分配器：在 DynArray 构造函数中接受 Allocator，实现更灵活的内存管理。
  2. 线程安全：使用 std::mutex 或原子操作保护并发写入。
  3. 多维数组：在此基础上实现 `DynMatrix `，提供行列索引和矩阵运算。
  4. 序列化：实现 to_json / from_json 接口，方便网络传输。

7. 小结

本文从零实现了一个简单但完整的自增长数组容器，展示了 C++ 内存管理、移动语义和异常安全的典型做法。通过自行实现，我们更深入地理解了 std::vector 的内部机制，也为在特殊场景下对其进行定制奠定了基础。希望这篇文章能为你在项目中设计自己的容器提供参考。

发表评论