C++中向量是如何实现的

我正在考虑如何实施std::vector从头开始。

它如何调整向量的大小？

realloc似乎只适用于普通的旧结构，还是我错了？

它是一个简单的模板类，它包装了一个本机数组。它does not use malloc/realloc。相反，它使用传递的分配器（默认情况下是std::allocator).

调整大小是通过分配一个新数组并从旧数组中复制构造新数组中的每个元素来完成的（这样对于非 POD 对象来说是安全的）。为了避免频繁分配，它们通常遵循非线性增长模式。

UPDATE:在 C++11 中，如果存储类型可能，则将移动元素而不是构造复制。

除此之外，它还需要存储当前的“大小”和“容量”。大小是向量中实际有多少个元素。容量是多少could位于向量中。

因此，作为起点，向量需要看起来像这样：

template <class T, class A = std::allocator<T> >
class vector {
public:
    // public member functions
private:
    T*                    data_;
    typename A::size_type capacity_;
    typename A::size_type size_;
    A                     allocator_;
};

另一种常见的实现是存储指向数组不同部分的指针。这降低了成本end()（不再需要添加）稍​​微贵一些size()调用（现在需要减法）。在这种情况下，它可能看起来像这样：

template <class T, class A = std::allocator<T> >
class vector {
public:
    // public member functions
private:
    T* data_;         // points to first element
    T* end_capacity_; // points to one past internal storage
    T* end_;          // points to one past last element
    A  allocator_;
};

我相信 gcc 的 libstdc++ 使用后一种方法，但这两种方法同样有效且一致。

NOTE:这忽略了一个常见的优化，其中空基类优化用于分配器。我认为这是实施细节的质量，而不是正确性的问题。