之前写过一个简单String类的实现,这次再写写简单Vector类的实现,主要参照《C++ Primer(第5版)》第 13 章的一个实现,做了一些简化和修改。我们知道new有一些灵活性上的局限,它将内存分配和对象构造组合在了一起,当分配一大块内存时,我们通常计划在这块内存上按需构造对象,标准库allocator类定义在memory中,它帮助我们将内存分配和对象构造分离开来。下面是实现代码,主要使用allocator而不是new分配内存:

图 1:Vector 内存布局

#include <memory>
using namespace std;
template <class T> class Vector {
public:
Vector() : elements(nullptr), first_free(nullptr), cap(nullptr) { }
Vector(const Vector &rhs) {
elements = alloc.allocate(rhs.size());
first_free = cap = uninitialized_copy(rhs.begin(), rhs.end(), elements);
}
Vector &operator=(Vector rhs) {
swap(rhs);
return *this;
}
~Vector() { free(); }
void push_back(const T &t) {
if (size() == capacity())
reallocate(); // check and reallocate if necessary
alloc.construct(first_free++, t);
}
void swap(Vector &rhs) {
std::swap(elements, rhs.elements);
std::swap(first_free, rhs.first_free);
std::swap(cap, rhs.cap);
}
size_t size() const { return first_free - elements; }
size_t capacity() const { return cap - elements; }
T *begin() const { return elements; }
T *end() const { return first_free; }
private:
allocator<T> alloc; // allocator to allocate memory
void free() {
if (elements) {
for (auto p = first_free; p != elements; )
alloc.destroy(--p);
alloc.deallocate(elements, cap - elements);
}
}
void reallocate() {
auto newcapacity = size() ? 2 * size() : 1;
auto newbegin = alloc.allocate(newcapacity);
auto dest = newbegin;
auto src = elements;
for (size_t i = 0; i < size(); ++i)
alloc.construct(dest++, move(*src++));
free(); // free old memory
elements = newbegin;
first_free = dest;
cap = elements + newcapacity;
}
T *elements; // the first element
T *first_free; // the first free place
T *cap; // the next place of tail
};