C++中vector是如何实现的
我正在考虑如何从头开始实现 std::vector.
I am thinking of how I can implement std::vector from the ground up.
它如何调整向量的大小?
How does it resize the vector?
realloc 似乎只适用于普通的旧结构，还是我错了?
realloc only seems to work for plain old stucts, or am I wrong?
推荐答案
它是一个简单的模板化类，它包装了一个原生数组.它不使用malloc/realloc.相反，它使用传递的分配器(默认为 std::allocator).
it is a simple templated class which wraps a native array. It does not use malloc/realloc. Instead, it uses the passed allocator (which by default is std::allocator).
调整大小是通过分配一个新数组并从旧数组复制构造新数组中的每个元素来完成的(这样对于非 POD 对象是安全的).为了避免频繁分配，它们通常遵循非线性增长模式.
Resizing is done by allocating a new array and copy constructing each element in the new array from the old one (this way it is safe for non-POD objects). To avoid frequent allocations, often they follow a non-linear growth pattern.
更新:在 C++11 中，如果存储类型可能，元素将被移动而不是复制构造.
UPDATE: in C++11, the elements will be moved instead of copy constructed if it is possible for the stored type.
除此之外，它还需要存储当前的大小"和容量".大小是向量中实际有多少元素.容量是向量中可以的数量.
In addition to this, it will need to store the current "size" and "capacity". Size is how many elements are actually in the vector. Capacity is how many could be in the vector.
所以作为起点，向量需要看起来像这样:
So as a starting point a vector will need to look somewhat like this:
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() 调用(现在需要一个减法).在这种情况下，它可能如下所示:
The other common implementation is to store pointers to the different parts of the array. This cheapens the cost of end() (which no longer needs an addition) ever so slightly at the expense of a marginally more expensive size() call (which now needs a subtraction). In which case it could look like this:
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++ 使用后一种方法，但这两种方法同样有效且一致.
I believe gcc's libstdc++ uses the latter approach, but both approaches are equally valid and conforming.
注意:这忽略了一个常见的优化，其中空基类优化用于分配器.我认为这是实现细节的质量，而不是正确性的问题.
NOTE: This is ignoring a common optimization where the empty base class optimization is used for the allocator. I think that is a quality of implementation detail, and not a matter of correctness.
相关文章