《STL源码剖析》-序列式容器（一）vector容器

对于STL而言，其中最重要的就是容器了，容器也是许多人对STL的第一印象。STL跟据容器的不同，分为序列式容器（array， vector， heap, priority-queue, list, slist, deque, stack, queue）和关联式容器（set, map, multiset, multimap, hashtable, hash_set, hash_map, hash_multiset, hash_multimap）。

首先我们先来看序列式容器vector。

vector的数据结构： 线性连续空间。以两个迭代器start和finish分别指向配置的来的来内需空间中目前已经被使用的范围，并且以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端。

template<class T, class Alloc = alloc>
class vector{
...
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
...
}

为了降低配置空间时的速度成本，vector实际配置的大小可能比客户端需求的量更大一些，以备将来的扩充，这便是容量（capacity）的概念。
有了以上三个三个迭代器，我们便可轻松的得到容器的首尾标、大小、容量、空容器判断、最前端元素。。。等机能。

template<class T, class Alloc = alloc>
class vector{
...
public:
    iterator begin() {return start;}
    iterator end() {return finish;}
    iterator size() const {
        return size_type(end() - begin());
    }
    iterator capacity() const {
        return size_type(end_of_storage - begin());
    }
    iterator empty() const {
        return end() == begin();
    }
    reference operator[](size_type n) {
        return *(begin() + n);
    }

    reference front() {return *begin();}
    reference back() {return *(end() - 1);}
...
}

vector的构造与内存管理：constructor，push_back:
vector缺省使用alloc作为空间适配器，并据此另外定义了一个data_allocator，方便以元素大小为配置单位

template<class T, class Alloc = alloc>
class vector{
    protected：
        typedef simple_alloc<value_type, Alloc> data_allocator;
}

因此data_allocate(n)表示配置n个元素空间。

vector提供了许多constructors，其中之一允许我们指定空间大小以及初值。

//构造函数，允许指定vector大小n和初值value
vector(size_type n, const T& value)
{
    fill_initialize(n ,value);
}

//填充并予以初始化
void fill_initialize(size_type n, const T& value)
{
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

//配置而后填充
iterator allocate_and_fill(size_type n, const T& x)
{
    iterator result = data_allocator::allocate(n); //配置n个元素空间
    uninitialized_fill_n(result, n, x); //全局函数

    return result；
}

uninitialized_fill_n( )会根据第一个参数的型别特性（type traits）,决定使用算法fill_n()或反复调用construct( )来完成任务。

当我们以push_back()将新元素插入vector尾端时，则该函数首先检查是否还有备用空间，有的话就直接在备用空间上构造元素，并调整迭代器finish。如果没有备用空间，就扩充空间（重新配置、移动数据、释放原有空间）：

void push_back(const T& x)
{
    if(finish != end_of_storage){  //还有备用空间
        construct（finish，x）;   //全局函数
        ++finish;               //调整水位高度
    }
    else
        insert_aux(end(), x);   //vector成员函数
}