如何在C++中实现向量

Question

我在想如何从头开始实现std :: vector.

它如何调整向量的大小？

realloc似乎只适用于普通的旧结构,或者我错了吗？

Answer 1

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

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

更新:在C++ 11中,如果可以存储类型,则将移动元素而不是复制构造.

除此之外,它还需要存储当前的"大小"和"容量".大小是向量中实际有多少元素.容量是向量中可以有多少.

所以作为一个起点,矢量需要看起来像这样:

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 ++使用后一种方法,但这两种方法同样有效且符合要求.

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

Answer 2

来自维基百科，这是一个很好的答案。

典型的向量实现在内部由指向动态分配数组的指针组成，[2] 以及可能保存向量容量和大小的数据成员。向量的大小是指实际的元素数量，而容量是指内部数组的大小。当插入新元素时，如果向量的新大小变得大于其容量，则会发生重新分配。[2][4] 这通常会导致向量分配新的存储区域，将先前保存的元素移动到新的存储区域，并释放旧的区域。由于元素的地址在此过程中发生变化，因此对向量中元素的任何引用或迭代器都会变得无效。[5] 使用无效的引用会导致未定义的行为

Answer 3

调整向量大小需要分配一个新的空间块，并将现有数据复制到新空间（因此，要求可以复制放入向量中的项目）。

请注意，它不使用任何new []一个 - 它使用传递的分配器，但需要分配原始内存，而不是像那样的对象数组new []。然后您需要使用placement new它来构造对象。[编辑：好吧，从技术上讲，你可以使用new char[size]，并将其用作原始内存，但我无法想象有人会编写这样的分配器。]

当当前分配耗尽并且需要分配新的内存块时，与旧大小相比，大小必须增加一个常数因子，以满足 的摊余常数复杂度的要求push_back。尽管许多网站（等）将此称为大小加倍，但 1.5 到 1.6 左右的系数通常效果更好。特别是，这通常会提高重新使用释放的块进行未来分配的机会。