c语言实现向量,如何在C中实现向量

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

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

更新：在C 11中，如果存储类型是可能的，则将移动元素而不是复制。

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

所以作为一个起点，一个向量将需要看起来像这样：

template >

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 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这样做，这两种方法同样有效和符合。

当然，您也可以使用PIMPL idiom使交换更简单，但是在访问期间有额外的间接成本。但这是一个偏好的问题。