自定义容器：从零开始造一个STL兼容的轮子

说实话，我在刚接触C++那会儿，觉得STL容器就是黑魔法。直到后来工作需要，必须写一个内存池分配器配合自定义容器，才真正理解了这套设计有多精妙。今天咱们就聊聊，怎么造一个像模像样的自定义容器。

嗯，先别急着写代码。咱们得搞清楚，一个容器要能在STL算法里愉快地玩耍，得满足哪些条件。

容器的最低要求：三件套

一个容器，说白了就是管理一堆对象的集合。STL对容器有基本要求，我总结成三件套：

• 类型定义：value_type、iterator、const_iterator 这些别名不能少
• 基本操作：begin()/end()、size()、empty() 得有
• 内存管理：默认用 std::allocator，但也要支持自定义分配器

我在项目中遇到过有人自己写了个容器，结果 std::sort 用不了——就是因为没定义迭代器类别。这种坑，踩一次就记住了。

分配器支持：别把内存管死

分配器是容器的幕后英雄。你想想看，如果每个容器都自己 new/delete，那内存池、对象池这些优化手段就没法用了。

template<typename T, typename Allocator = std::allocator<T>>
class MyVector {
    using alloc_traits = std::allocator_traits<Allocator>;
    Allocator alloc_;
    T* data_;
    size_t size_;
    size_t capacity_;

    void allocate_memory(size_t n) {
        data_ = alloc_traits::allocate(alloc_, n);
        capacity_ = n;
    }

    void deallocate_memory() {
        alloc_traits::deallocate(alloc_, data_, capacity_);
    }
};

这里有个细节：永远不要直接调用 allocator.allocate()。要用 std::allocator_traits 包装一下。为什么？因为自定义分配器可能没有成员函数 allocate，但 traits 会帮你兜底。我曾经因为这个原因，排查了一下午的编译错误。

迭代器支持：容器的灵魂

迭代器就是容器的指针。但要注意，不是随便写个类就能当迭代器。STL 要求迭代器必须满足 Iterator 概念。

我一般这么写：

template<typename T>
class MyVectorIterator {
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    // 必须的操作
    reference operator*() const { return *ptr_; }
    pointer operator->() const { return ptr_; }
    
    // 前向迭代器
    MyVectorIterator& operator++() { ++ptr_; return *this; }
    MyVectorIterator operator++(int) { auto tmp = *this; ++ptr_; return tmp; }
    
    // 双向迭代器
    MyVectorIterator& operator--() { --ptr_; return *this; }
    MyVectorIterator operator--(int) { auto tmp = *this; --ptr_; return tmp; }
    
    // 随机访问
    MyVectorIterator& operator+=(difference_type n) { ptr_ += n; return *this; }
    reference operator[](difference_type n) const { return ptr_[n]; }
    
    // 比较
    bool operator==(const MyVectorIterator& other) const { return ptr_ == other.ptr_; }
    bool operator<(const MyVectorIterator& other) const { return ptr_ < other.ptr_; }

private:
    T* ptr_;
};

异常安全：别让程序崩得莫名其妙

异常安全分三个等级：

我个人习惯，至少保证基本异常安全。怎么做？核心就是 RAII 和 copy-and-swap 惯用法。

template<typename T>
void MyVector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        // 先分配新内存，再拷贝元素
        auto new_cap = calculate_new_capacity();
        auto new_data = alloc_traits::allocate(alloc_, new_cap);
        
        // 构造新元素
        try {
            alloc_traits::construct(alloc_, new_data + size_, value);
            // 拷贝旧元素
            for (size_t i = 0; i < size_; ++i) {
                alloc_traits::construct(alloc_, new_data + i, std::move_if_noexcept(data_[i]));
                alloc_traits::destroy(alloc_, data_ + i);
            }
        } catch (...) {
            // 清理新分配的资源
            for (size_t i = 0; i < size_; ++i) {
                alloc_traits::destroy(alloc_, new_data + i);
            }
            alloc_traits::deallocate(alloc_, new_data, new_cap);
            throw;  // 重新抛出
        }
        
        // 释放旧内存
        alloc_traits::deallocate(alloc_, data_, capacity_);
        data_ = new_data;
        capacity_ = new_cap;
    } else {
        alloc_traits::construct(alloc_, data_ + size_, value);
    }
    ++size_;
}

这段代码看着啰嗦，但每个异常路径都处理了。你想想看，如果构造新元素时抛异常，旧数据还在，容器状态是完整的——这就是基本保证。

知识体系总览

下面这张图，是我自己总结的自定义容器核心脉络：

写在最后

自定义容器这事儿，说难不难，说简单也不简单。关键是把分配器、迭代器、异常安全这三个点吃透。我刚开始写的时候，也是照着 std::vector 的接口抄，慢慢才理解为什么人家要这么设计。

嗯，如果你现在要写自己的容器，我建议先画个接口清单，把每个操作的异常安全等级标出来。这样写代码的时候心里有数，不容易出bug。

公众号:蓝海资料掘金营，微信deep3321