【STL序列式容器】剖析vector

vector的迭代器vector的数据结构vector的构造与内存管理

构造扩充空间其它操作

inserterase
C++语言本身提供了一个序列式容器 array， array是 静态空间，一旦配置了就不能改变，类似于 C语言的 数组。

vector的数据安排以及操作方式与array很像，但vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。

vector的嵌套型别定义如下：

template 
class vector {
public:
    typedef T value_type;
    typedef value_type *pointer;
    typedef value_type *iterator; // vector的迭代器是普通指针
    typedef value_type &reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
};

alloc是SGI STL的空间配置器。

vector维护的是一个连续线性空间，因此不论其元素型别如何，普通指针都可以作为vector的迭代器而满足所有必要条件，因为vector迭代器所需要的操作行为，如operator*、operator->、operator++、operator--、operator+=、operator-=，普通指针天生都具备，所以vector提供的是Random Access Iterators。

vector::iterator ivite;    // ivite的类型是int*
vector::iterator svite;  // svite的类型是Shape*

vector采用线性连续空间存储数据，它以两个迭代器start和finish分别指向配置得来的连续空间中已被使用的范围，并以迭代器end_of_storage指向整个配置空间的尾端。

template 
class vector {
protected:
    iterator start;           // 目前使用空间的头
    iterator finish;          // 目前使用空间的尾
    iterator end_of_storage;  // 目前可用空间的尾
};

当finish等于end_of_storage时，便是满载。下次再新增元素时，整个vector就得另觅居所。

如图所示，vector里保存了6个整型，已配置但未使用的空间里可以再存放两个元素。

使用这三个迭代器，便可轻松访问vector的元素，获取vector的容量和大小。

template 
class vector {
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
};

增加新元素时，如果超过当前的容量，则容量会扩充至两倍，如果两倍容量不足，就扩张至足够大的容量。

容量的扩张必须经历“重新配置、元素移动、释放原空间”等过程，工程浩大。

vector默认使用alloc作为空间配置器，并据此定义了一个data_allocator，可以更方便地以元素大小为配置单位。

template 
class vector {
protected:
    typedef simple_alloc data_allocator;
};

simple_alloc的实现如下：

template 
class simple_alloc {
public:
    static T *allocate(size_t n)
    {
        return n == 0 ? nullptr : (T*)Alloc::allocate(n * sizeof(T));
    }

    static T *allocate()
    {
        return (T*)Alloc::allocate(sizeof(T));
    }

    static void deallocate(T *p, size_t n)
    {
        if (n) {
            Alloc::deallocate(p, n * sizeof(T));
        }
    }

    static void deallocate(T *p)
    {
        Alloc::deallocate(p, sizeof(T));
    }
};

于是，data_allocator::allocate(n)表示配置n个元素空间。

vector提供了许多constructors，其中一个允许指定元素个数及初值。

template 
class vector {
public:
    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 &value)
    {
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, value);
        return result;
    }
};

uninitialized_fill_n会根据参数的型别特性决定使用fill_n或反复调用construct来完成任务。详见【空间配置器】内存基本处理工具

使用push_back将新元素插入vector尾端时，如果此时有备用空间，就直接构造元素，否则就需要扩充空间。

template 
class vector {
public:
    void push_back(const T &value)
    {
        if (finish != end_of_storage) {
            construct(finish, value);
            ++finish;
        } else {
            insert_aux(end(), value);
        }
    }

    void insert_aux(iterator position, const T &x)
    {
        if (finish != end_of_storage) { // 有备用空间
            construct(finish, *(finish - 1));
            ++finish;
            T x_copy = x;
            copy_backward(position, finish - 2, finish - 1);
            *position = x_copy;
        } else { // 无备用空间
            const size_type old_size = size();
            const size_type len = old_size == 0 ? 1 : 2 * old_size; // 计算新空间的大小

            iterator new_start = data_allocator::allocate(len); // 配置新空间
            iterator new_finish = new_start;

            try
            {
                // 把旧空间中position前的数据拷贝到新空间
                new_finish = uninitialized_copy(start, position, new_start);
                // 构造新增的元素
                construct(new_finish, x);

                ++new_finish;

                // 把旧空间中position后的数据拷贝到新空间
                new_finish = uninitialized_copy(position, finish, new_finish);
            }
            catch(const std::exception& e)
            {
                // commit or rollback
                destroy(new_start, new_finish);
                data_allocator::deallocate(new_start, len);
                throw;
            }

            // 析构旧对象、释放旧空间
            destroy(begin(), end());
            deallocate();

            // 调整迭代器
            start = new_start;
            finish = new_finish;
            end_of_storage = start + len;
        }
    }
};

所谓动态增加大小，是指以原大小的两倍另外配置一块更大的空间，将原内容拷贝过来，然后再构造新元素，最后释放原空间。此时，指向原空间的迭代器会失效。

vector是线性连续存储元素的，所以当在finish前的某个位置posiion处增删元素时，都会引起position后面元素的一轮拷贝。

template 
class vector {
public:
	void insert(iterator position, size_type n, const T &x);
};

在position所指的位置上加上n个值为x的元素，原来的position之后的元素要后移n个位置。

template 
class vector {
public:
	iterator erase(iterator first, iterator last);
};

将[first, last)区间内的元素删除，last及其之后的元素前移last - first个位置。

比如有如下的vector：

执行insert(begin() + 2, 2, 7);语句后，会变成这个样子：

再执行erase(begin() + 1, begin() + 4);后，是这个样子：