简介

vector,array,forward_list应该是容器中较简单的类型。下面对部分顺序容器类型进行一个简单的总结。
vector是可变大小数组，元素是连续存储的，因此支持随机访问。在尾部之外的其他位置插入删除元素很慢，因为需要进行元素的移动操作。array是固定大小的容器，编译期间就可以确定大小。同样是顺序存储支持快速随机访问。forward_list和list相似，只不过前者是单向，后者是双向，等下文章会说forward_list的结构。两者都不是顺序存储的，因此不支持随机访问的操作，但是优点是插入删除的速度很快。deque，string在后面的文章继续说明。

vector

vector定义的代码如下：

template <class T, class Alloc=alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator; // T*
    typedef value_type& reference;
    typedef size_t size_type;
protected:
    iterator start;
    iterator finish;
    iterator end_of_storage;
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);}
}

定义比较简单，很好理解。其中要注意的是其迭代器是指针。每个操作都进行了相应的定义,注意大多数容器是前闭后开的区间，因此注意back()函数的定义，end()返回的是尾后迭代器，因此要减1。
vector有一个很重要的函数就是push_back()。下面是push_back的源代码和相应的注释。

void push_back(const T &x)
{
    if (finish != end_of_storage) {
        //判断还有存储空间可用，直接在尾后迭代器
        //位置构造元素
        construct(finish, x);
        ++finish;
    }
    else
        //没有存储空间可以使用
        insert_aux(end(), x);
}
// 函数模板insert_aux()定义
template <class T, calss Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T &x) {
    if (finish != end_of_storage) {
        //复制最后位置元素
        construct(finish, *(finish -1));
        ++finish;
        T x_copy = x;
        //从后向前复制元素，相当于把position到(finish-2)
        //的元素统一向后移动一位。
        copy_backward(position, finish-2, finish-1);
        *position = x_copy;
    }
    else {
        //没有备用空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2*old_size:1;
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            //建立完新空间开始拷贝元素,第一步拷贝position位置前的元素
            new_finish = uninitialized_copy(start, position, new_start);
            //构造新元素x
            construct(new_finish, x);
            ++new_finish;
            //第二步拷贝position位置后的元素
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            //异常处理
            //销毁元素
            destroy(new_start, new_finish);
            //收回空间
            data_allocator::deallocate(new_start, len);
            //抛出异常
            throw;
        }
    }
}

这里有一个设计就是在push_back()函数和insert_aux函数中都进行了是否还有存储空间的判断，原因是不仅push_back函数会用到insert_aux函数，其他函数也可能用到该函数，所以这样增加了该函数的通用性。

array

array 和 vector 一样都支持随机访问，但是其大小是固定的。下面看看array的定义：

template <typename _Tp, std::size_t _Nm>
struct array{
    typedef _Tp          value_type;
    typedef _Tp*         pointer;
    typedef value_type*  iterator;
    value_type _M_instance[_Nm ? _Nm :1];
    iterator begin() {
        return iterator(&_M_instance[0]);
    }
    iterator end() {
        return iterator(&_M_instance[_Nm]);
    }
}

其中iterator也是指针，不是定义的一个复杂的模板类。

forward_list

forward_list是单向链表，应该说实现上和list很像。下面看forward_list的模型图。

在forward_list中有两个函数可以注意下

iterator begin() noexcept {
    return iterator(this->_M_impl._M_head._M_next);
}
iterator end() noexcept {
    return iterator(0);
}

forward_list中有一个伪头节点蓝色标记的，end()返回的实际上是一个空的节点。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。