一、vector是什么？

vector是表示可变大小数组的序列容器，它也采用连续存储空间来存储元素，因此可以采用下标对vector的元素进行访问，它的大小是动态改变的，vector使用动态分配数组来存储它的元素；

二、容器特性

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素;

2.动态数组

支持对序列中的任意元素进行快速直接访问，甚至可以通过指针进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作;

3.能够感知内存分配器的

容器使用一个内存分配器对象来动态地处理它的存储需求;

三、vector的模拟实现

• 定义一个类：

template<class T>
class Vector
{
    T* _start; //首元素地址
    T* _finish; //最后一个元素地址的下一个地址
    T* _endOfStorage; //空间的尾地址
public：
//成员函数
};

• 构造函数

Vector()
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{}

Vector(size_t n, const T& value = T())
    :_start(nullptr)
    , _finish(nullptr)
    , _endOfStorage(nullptr)
{
    reserve(n);
    while (n--)
    {
        push_back(value);
    }
}
Vector(InputInterator first, InputInterator last)
        :_start(nullptr)
        , _finish(nullptr)
        , _endOfStorage(nullptr)
    {
        while (first != last)
        {
            pushBack(*first);
            ++first;
        }
    }

• 数据大小、空间大小

size_t size() const
{
    return _finish - _start;
}

size_t capacity() const
{
    return _endOfStorage - _start;
}

• 尾插

void pushBack(const T& value)
    {
        if (_finish == _endOfStorage)
        {
            size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
            reverse(value);
        }
        *_finish = value;   
        ++_finish;
    }

• 扩容

  有资源进行拷贝时，使用深拷贝；类型为自定义类型时，发生浅拷贝，调用自定义类型析构函数，释放资源，导致资源二次释放，所以自定义类型的拷贝有资源时进行深拷贝；

  void reserve(size_t n)
  {
  if (n > capacity())
  {
  size_t sz = size();
  T* arr = new T[n];
  if (_start)
  {
  memcpy(arr, _start, sizeof(T) * sz);
  delete[] _start;
  }
  //update
  _start = arr;
  _finish = _start + sz;
  _endOfStorage = _start + n;
  }
  }

• 改变数据大小

void resize(size_t n, const T& val = T())
    {
        if (n > capacity())
        {
            reserve(n);
        }
        else if (n > size())
        {
            while (_finish != _start + n)
            {
                *_finish = val;
                _finish++;
            }
        }
            _finish = _start + n;
    }

• 位置插入值

void insert(iterator pos, const T& val)
    {
        size_t sz = pos - _start;
        //检查位置
        if (pos >= _start && pos <= _finish)
        {
            //检查容量
            if (_finish == _endOfStoage)
            {
                size_t n = _endOfStorage == nullptr ? 1 : 2 * capacity();               
                reserve(n);
                //更新迭代器
                pos = _start + sz;
            }
            //移动元素
            iterator end_u = _finish;
            while (end_u != pos)
            {
                *end = *(end_u - 1);
                --end_u();
            }
            //插入元素
            *pos = val;
            //更新位置
            ++_finish;
        }
    }

• 删除数据

iterator erase(iterator pos)
    {
        //检查位置
        if (pos < _finish && pos >= _start)
        {
            //移动元素
            iterator start = pos + 1;
            while (start!=_finish)
            {
                *(start - 1) = *start;
                start++;
            }
            //更新
            --_finish;
        }
        return pos;
    }
    //返回删除数据的下一个元素的位置

• operator[] 重载

T& operator[](size_t pos)
    {
        if (pos >= 0 && pos < size())
            return _start[pos];
    }

• operator= 重载

    Vector<T>& operator=(const Vector<T>& v)
    {
        if (this != &v)
        {
            delete[]_start;
            size_t n = v.capacity();
            _start = new T[n];
            for (size_t i = 0; i < v.capacity(); ++i)
            {
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
            _finish = _start + n;
        }
        return *this;
    }

• 迭代器

//vector迭代器：T*
typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}

const_iterator end() const
{
    return _finish;
}

• 析构函数

~Vector()
{
    if (_start)
    {
        delete[] _start;
        _start = _finish = _endOfStorage = nullptr;
    }
}