山寨STL实现之vector (一)

首先是vector的定义
template
class vector
{
};
让我们先来看看vector中的一些别名
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef const T* const_iterator;
typedef reverse_iterator const_reverse_iterator;
typedef T* iterator;
typedef reverse_iterator reverse_iterator;由上可见，正如上一篇所说，vector的迭代器是由原生的指针来实现的。

下面是其内部的成员变量
protected:
typedef vector self;
typedef allocator Alloc;

iterator start;
iterator finish;
iterator end_of_element;start：指向vector的起始地址
finish：指向最后一个元素的后一个元素的地址
end_of_element：指向已申请内存块的结束位置（finish总是小于或等于end_of_element）

在STL中从begin到end总是以一个前闭后开的形式来表示的，形如[begin,end)，这样做的好处是可以使代码写的更简洁：
template
Iterator find(Iterator first, Iterator last, const T& value)
{
while(first != last && *first != value) ++first;
return first;
}
下面来看看vector中最基本的构造函数和析构函数
vector() : start(0), finish(0), end_of_element(0)
{
}

~vector()
{
destruct(start, end_of_element);
if (start != 0) Alloc::deallocate(start, end_of_element - start);
}这里将其中的3个成员变量都填充为0。
如 上一篇所说，在STL中是将内存分配与对象初始化分开的，同样对象析构与内存释放也是被分开的。

然后是其begin和end方法，用来获取第一个元素和最后一个元素的后一个元素的迭代器。
inline iterator begin()
{
return start;
}

inline const_iterator begin()const
{
return start;
}

inline iterator end()
{
return finish;
}

inline const_iterator end()const
{
return finish;
}
front和back分别被用来获取第一个元素和最后一个元素
inline reference front()
{
return *begin();
}

inline const_reference front()const
{
return *begin();
}

inline reference back()
{
return *(end() - 1);
}

inline const_reference back()const
{
return *(end() - 1);
}
empty、size、capacity分别被用来判别容器是否为空、容器内元素的个数和容器的大小
inline bool empty()const
{
return begin() == end();
}

inline const size_type size()const
{
return size_type(end() - begin());
}

inline const size_type capacity()const
{
return size_type(end_of_element - begin());
}
由于在vector的头部插入元素会使所有元素后移，应此它被设计为单向的，只能由尾部插入或移除数据
void push_back(const T& x)
{
if (end_of_element != finish)
{
construct(&*finish, x);
++finish;
}
else
{
insert_aux(end(), x);
}
}

inline void pop_back()
{
--finish;
destruct(fin