如何矢量用C ++实现 [英] How is vector implemented in C++

问题描述

我想到的是我怎样才能从根本上实现的std ::向量。

I am thinking of how I can implement std::vector from the ground up.

它是如何调整的载体？

How does it resize the vector?

realloc的似乎只是为普通的旧stucts工作，还是我错了？

realloc only seems to work for plain old stucts, or am I wrong?

推荐答案

这是它封装本地阵列一个简单的模板类。它的不使用的malloc / 的realloc 。相反，它使用了通过分配器（默认情况下为的std ::分配器）。

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 being 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_;
};

其他常见的实现是指针存储阵列的不同部分。这贱卖的端（）（它不再需要一个加法）非常轻微，但其代价一个稍微更昂贵的尺寸（）<成本/ code>调用（现在需要一个减法）。在这种情况下，它可能是这样的：

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_;
};

我相信，海湾合作委员会的libstdc ++做到这一点，这两种方法都同样有效，符合

I believe gcc's libstdc++ does this, both approaches are equally valid and conforming.

当然，你也可以使用 PIMPL成语使交换过程中需​​要额外的间接成本更简单访问。但是，这是preference的问题。

Of course, you could also use the PIMPL idiom to make swap much simpler at the cost of an extra indirection during access. But that's a matter of preference.

这篇关于如何矢量用C ++实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！