STL源码剖析—序列式容器—vector

容器：array(数组)、list(串行)、tree（树）、stack（堆栈）、queue（队列）、hash table(散列表)、set(集合)、map…根据存储方式可以分为：序列式容器和关联式容器

• 序列式容器：容器里面的数据可以排序，但是不会自动有序，可以利用算法排序；
• 关联式容器：容器里面的数据不可排序，以键值对的形式存储。

VECTOR

• 数据结构：数组；

• vector和array的区别;
  (1)array是静态空间，一旦配置不能改变；要扩容需要客户端自己实现；
  (2)vector是动态空间，随着元素的加入，内部机制会自行扩容；
  都是线性连续空间；

• 扩容:
  (1)当vector空间满载时：为了降低控制配置时的速度成本，vector实际配置会比客户端要求大一些，capacity()>=size();
  (2)配置新空间-数据移动-释放就空间，当vector满载时，就会寻找一片合适的空间，将原有数据复制，并把原来的空间释放掉，一般以旧空间的两倍来扩充。(扩充：capacity())
  原来大小=0----capacity=1;
  原来大小不等于0----capacity=2*原来capacity;
  

• 外部接口

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	std::vector<int> iVec(2,9);//初始化9 9
	std::cout<<"size="<<iVec.size()<<std::endl;//2
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//2
 	iVec.push_back(1);
 	std::cout<<"size="<<iVec.size()<<std::endl;//3
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//4
	iVec.push_back(2);
 	std::cout<<"size="<<iVec.size()<<std::endl;//4
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//4
	iVec.push_back(3);
 	std::cout<<"size="<<iVec.size()<<std::endl;//5
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//8
	iVec.push_back(4);
 	std::cout<<"size="<<iVec.size()<<std::endl;//6
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//8
	for(int i=0;i<iVec.size();i++) std::cout<<iVec[i]<<'';//991234
	iVec.push_back(5);
 	std::cout<<"size="<<iVec.size()<<std::endl;//7
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//8
	for(int i=0;i<iVec.size();i++) std::cout<<iVec[i]<<'';//9912345
	iVec.pop_back();
	iVec.pop_back();
	std::cout<<"size="<<iVec.size()<<std::endl;//5
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//8
	iVec.pop_back();
	std::cout<<"size="<<iVec.size()<<std::endl;//4
	std::cout<<"capacity="<<iVec.capacity()<<std::endl;//8 pop元素时size改变，capacity不会改变
	std::vector<int>::iterator itVec=find(iVec.begin(),iVec.end(),1);
	if(itVec) iVec.erase(itVec);//迭代器指向1，则把1删除
	for(int i=0;i<iVec.size();i++) std::cout<<iVec[i]<<'';//992
	itVec=find(iVec.begin(),iVec.end(),2);
	if(itVec) iVec.insert(itVec,3,7);
	for(int i=0;i<iVec.size();i++) std::cout<<iVec[i]<<'';//997772 迭代器指向2，插入时要在2的前面插入
	iVec.clear();//清空所有元素，但是capacity()不改变
}

• vector声明

template <class T, class Alloc = alloc>
class vector
{
public:
    // 类型相关定义
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    //定义配置器
    typedef simple_alloc<value_type, Alloc> data_allocator;
    
    iterator start;             // 内存起始地址
    iterator finish;            // 当时使用内存的末尾地址，每次插入和删除都会修改
    iterator end_of_storage;     // 内存的结束地址
    
    // 关键函数，在某个位置插入一个数据
    void insert_aux(iterator position, const T& x);
    
    // 使用配置器释放内存
    void deallocate() 
    {
        if (start)
            data_allocator::deallocate(start, end_of_storage - start);
    }
    
    // 申请并初始化一块大小为n的内存，并初始化为value
    void fill_initialize(size_type n, const T& value) 
    {
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
    }

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(); }
    // 重载[]运算符，取出对应position的数据，下标从0开始
    reference operator[](size_type n) { return *(begin() + n); }
    // 构造函数
    vector() : start(0), finish(0), end_of_storage(0) {}
    
    vector(size_type n, const T& value) { fill_initialize(n, value); }
    
    vector(int n, const T& value) { fill_initialize(n, value); }
    
    vector(long n, const T& value) { fill_initialize(n, value); }
    
    explicit vector(size_type n) { fill_initialize(n, T()); }
    // 析构函数
    ~vector()
    {
        destroy(start, finish);
        deallocate();
    }
    // 取出起始数据
    reference front() { return *begin(); }
    // 取出末尾数据
    reference back() { return *(end() - 1); }
    // 从尾部插入一个数据
    void push_back(const T& x) 
    {
        if (finish != end_of_storage)
        {
            // 内存没有满，直接插入
            construct(finish, x);
            ++finish;
        }
        else
        {
            // 内存满了，需要扩容内存，然后插入数据
            insert_aux(end(), x);
        }
    }
    
    // 弹出最后一个数据
    void pop_back() 
    {
        --finish;
        destroy(finish);
    }
    
    // 删除时，将后面的数据覆盖前面的数据，然后释放最后一个数据；如果删除的数据是最后一个数据，那么直接
    // 释放即可
    iterator erase(iterator position)
    {
        if (position + 1 != end())
            // 将position + 1到finish的数据，拷贝到position开始的地方
            copy(position + 1, finish, position);
        
        --finish;
        destroy(finish);
        return position;
    }
    
    // 修改vector的大小，新的size比老的size小，直接删除多余的数据；新的size比老的size大，直接插入
    void resize(size_type new_size, const T& x)
    {
        if (new_size < size())
            erase(begin() + new_size, end());
        else
            insert(end(), new_size - size(), x);
    }
    // 外部统一调用接口，一层封装
    void resize(size_type new_size) { resize(new_size, T()); }
    // 删除容器中所有数据，不会释放内存
    void clear() { erase(begin(), end()); }
    
protected:
    // 申请并初始化一块内存
    iterator allocate_and_fill(size_type n, const T& x) 
    {
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, x); 
        return result;
    }
}

• 迭代器
  (1)维护一个线性空间，**普通指针（原生指针）**可以作为迭代器，满足统一接口的要求
  (2)类型：Random Access Iterator
  (3)当空间满载时，配置新空间-数据移动-释放旧空间，vector的迭代器会失效
  

• insert
  插入的数据在迭代器所指的前面。123迭代器指向2，插入9，变成1293；
  （1）剩余空间大于插入的个数
  
  （2）插入点到finish的个数小于插入数据的个数
  
  （3）剩余空间不够，直接重新申请内存
  

• 优缺点
  优点：随机存取。时间复杂度O（1）；
  缺点：插入和删除的事件复杂读O（N）。