vector的作用

vector是c++的stl库提供的顺序表容器，也就是可变大小数组的序列容器。是c++中经常使用，非常方便的stl容器。

vector中的接口

构造函数

//默认构造，初始化成0
explicit vector (const allocator_type& alloc = allocator_type());
//第一个参数指定初始化的数组大小，第二个参数指定初始化数组中的值（不写默认0）
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());
//使用迭代器初始化，所有支持迭代器的容器(数组使用指针也算一种迭代器)都可以使用这种初始化方式转化成vector。
template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());
//拷贝构造，使用别的创建好的vector来初始化。
vector (const vector& x);

四种构造方式都较为常用

赋值运算符重载

vector& operator= (const vector& x);

使用运算符重载将数组赋值操作用‘=’表示，提升代码阅读性。

迭代器相关

      iterator begin();
const_iterator begin() const;
      iterator end();
const_iterator end() const;

//反向迭代器
      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
      reverse_iterator rend();
const_reverse_iterator rend() const;

//const迭代器
const_iterator cbegin() const noexcept;
const_iterator cend() const noexcept;

const_reverse_iterator crbegin() const noexcept;
const_reverse_iterator crend() const noexcept;

数组尺寸相关

size

size_type size() const;

返回数组的元素数

capacity

size_type capacity() const;

返回vector的实际尺寸，没什么用，顺序表为了性能考虑会在扩容时预留一些空间后面用，防止扩容过于频繁带来性能损耗，capacity可以返回数组实际的大小，也就是比size要大，但不同编译器对于vector扩容的内存管理都不同，同样的操作，同样的size对应的capacity也有可能不同，所以这个函数没用什么实际意义，也很少用到。

resize

void resize (size_type n, value_type val = value_type());

resize可以改变数组的大小，若n小于数组size，则将size变为n，并删除数组超出n大小部分的元素；若n大于数组size，也会将size变为n，多出来的部分填充value（不指定就填0）；若n等于size，什么都不会发生。注意这个函数会改变数组的相对元素位置，所以会引发迭代器失效。

reserve

void reserve (size_type n);

reserve可以改变capacity的大小，但reserve绝对无法改变size的大小，这个函数对于编译器来说像一条建议，编译器是可以无视这条建议的，一般来说对于n小于capacity的情况，编译器会选择无视，因为可能会影响到size大小也就是会影响数组的内容，而对于n大于capacity的情况，编译器会执行。这个函数是用来在直到需要多少空间的情况下提前开好空间减少扩容带来的性能开销用的。

shrink_to_fit

void shrink_to_fit();

这个函数可以减少capacity以匹配size的大小，但还是会预留一定的空间优化性能的，这个函数常用来将一个原本很大的数组突然减的很小时调整caapcity用，因为数组中的capacity是不会冒然减小的，如果后面用不到这么多空间，减小一下来优化再好不过。

empty

bool empty() const;

数组判空用。

operator[]

      reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

返回数组中序号为n处的元素的引用，和普通数组的用法一致。

at

      reference at (size_type n);
const_reference at (size_type n) const;

返回数组中序号为n处的元素的引用，越界会抛异常，用法不如[]方便，但它会检查越界但[]不会。

front

      reference front();
const_reference front() const;

返回对于数组第一个元素的引用

back

      reference back();
const_reference back() const;

返回对于数组最后一个元素的引用

data

      value_type* data() noexcept;
const value_type* data() const noexcept;

返回一个指向数组第一个元素的指针，因为vector本质上时一个存储连续元素的容器，所以它的底层就是数组，可以直接返回指针用来访问而不用迭代器。

assign

//迭代器初始化
template <class InputIterator>
  void assign (InputIterator first, InputIterator last);

//指定大小和填充元素初始化
void assign (size_type n, const value_type& val);

这个函数可以重新初始化数组替代当前的数组。

push_back

void push_back (const value_type& val);

尾插。

pop_back

void pop_back();

尾删。

insert

//迭代器位置插入，返回新元素的迭代器
iterator insert (iterator position, const value_type& val);

//迭代器位置插入复数元素
void insert (iterator position, size_type n, const value_type& val);

//迭代器位置插入一段元素
template <class InputIterator>
    void insert (iterator position, InputIterator first, InputIterator last);

插入函数常用第一种，在插入操作触发扩容时会引发迭代器失效，可以利用第一种函数返回新插入元素的迭代器来避免。

erase

iterator erase (iterator position); 	
iterator erase (iterator first, iterator last);

从数组中删除一个或一段元素，注意这个函数会改变数组的相对元素位置，所以会引发迭代器失效。

swap

void swap (vector& x);

交换两个数组。

clear

void clear();

清空数组中的元素，capacity不会改变，也就是不会改变已分配给数组的空间。

关系运算符重载（非成员函数）

template <class T, class Alloc>
  bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
  
template <class T, class Alloc>
  bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

template <class T, class Alloc>
  bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

template <class T, class Alloc>
  bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

template <class T, class Alloc>
  bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

template <class T, class Alloc>
  bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

swap（非成员函数,标准库提供的swap的vector版重载）

template <class T, class Alloc>
  void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

vector的模拟实现

namespace jiunian
{
    template<class T>
    class vector
    {
    public:
        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; }
        size_t size() { return _finish - _start; }
        size_t size() const { return _finish - _start; }
        size_t capacity() { return _end_of_storage - _start; }
        size_t capacity() const { return _end_of_storage - _start; }
        vector() {}
        vector(int n, const T& value = T()) { resize(n, value); }
        vector(std::initializer_list<T> il)
        {
            auto it = il.begin();
            while (it != il.end())
            {
                push_back(*it);
                ++it;
            }
        }
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }
        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (auto e : v)
                push_back(e);
        }
        void swap(vector<T>& v)
        {
            std::swap(v._start, _start);
            std::swap(v._finish, _finish);
            std::swap(v._end_of_storage, _end_of_storage);
        }
        const T& operator[](size_t pos)const
        {
            assert(pos < size());
            return _start[pos];
        }
        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }
        ~vector()
        {
            if (_start == nullptr) return;
            delete[] _start;
            _start = nullptr;
            _finish = nullptr;
            _end_of_storage = nullptr;
        }

        void reserve(size_t sz)
        {
            if (sz < capacity()) return;
            size_t new_size = capacity() == 0 ? 4 : capacity();
            while (new_size < sz) new_size *= 2;
            iterator tmp = new T[new_size]{};
            if (!tmp) { printf("new error."); return; }
            size_t old_size = size();
            if (old_size > 0)
            {
                memcpy(tmp, _start, old_size * sizeof(T));
                delete[] _start;
            }
            _start = tmp;
            _finish = tmp + old_size;
            _end_of_storage = tmp + new_size;
        }

        iterator insert(iterator pos, const T& value)
        {
            size_t len = pos - _start;
            if (len > size()) return iterator();
            if (_finish == _end_of_storage)
            {
                reserve(capacity() + 1);
                pos = _start + len;
            }
            iterator cur = _finish;
            while (cur >= _start && cur != pos)
            {
                *(cur) = *(cur - 1);
                cur--;
            }
            *cur = value;
            _finish++;
            return pos;
        }

        iterator erase(iterator pos)
        {
            if (pos > _finish) return;
            size_t len = pos - _start;
            while (pos + 1 != _finish) *pos = *(pos + 1), pos++;
            _finish--;
            return _start + len;
        }

        void resize(size_t sz, const T& value = T())
        {
            if (sz < size()) { _finish = _start + sz; return; }
            reserve(sz);
            while (_finish != _start + sz)
            {
                *_finish = value;
                ++_finish;
            }
        }

        void pop_back()
        {
            iterator pos = end() - 1;
            erase(pos);
        }

        void push_back(const T& value) { insert(end(), value); }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}

对于vector，我使用三个指针来维护，一个指向数组的开头，一个指向数组的结尾，一个指向数组的实际分配空间的结尾。

reserve

void reserve(size_t sz)
{
    if (sz < capacity()) return;
    size_t new_size = capacity() == 0 ? 4 : capacity();
    while (new_size < sz) new_size *= 2;
    iterator tmp = new T[new_size]{};
    if (!tmp) { printf("new error."); return; }
    size_t old_size = size();
    if (old_size > 0)
    {
        memcpy(tmp, _start, old_size * sizeof(T));
        delete[] _start;
    }
    _start = tmp;
    _finish = tmp + old_size;
    _end_of_storage = tmp + new_size;
}

首先要对sz与capacity的关系进行一个判断，如果sz小于等于capacity，优先保护数据，直接返回，不做处理。只有大于capacity才做进一步处理。如果大于capacity，就需要重新开辟一片空间再将之前数组的数据拷贝过去，这里我们需要提前保存一下size的大小一面拷贝完之后更新指针时丢失数据产生错误。拷贝完成之后更新指针就行。

resize

void resize(size_t sz, const T& value = T())
{
    if (sz < size()) { _finish = _start + sz; return; }
    reserve(sz);
    while (_finish != _start + sz)
    {
        *_finish = value;
        ++_finish;
    }
}

首先判断sz和size之间的关系，如果sz小于size就直接更改_finish返回就行。如果不是，就调整capacity的大小，一边将多出来的空间赋值为指定值一边挪动_finish。

insert

iterator insert(iterator pos, const T& value)
{
    size_t len = pos - _start;
    if (len > size()) return iterator();
    if (_finish == _end_of_storage)
    {
        reserve(capacity() + 1);
        pos = _start + len;
    }
    iterator cur = _finish;
    while (cur >= _start && cur != pos)
    {
        *(cur) = *(cur - 1);
        cur--;
    }
    *cur = value;
    _finish++;
    return pos;
}

首先我们要确保pos指向的位置不是无效位置，之后要检查是否需要扩容，即检查_finish是否等于_endOfStorage，如果等于就要扩容。这里我们采取的是两倍扩容的方案，因为我们可能使用默认构造函数构造了一个空数组，即申请的空间为0，这时就需要特殊处理因为0的二倍还是0，我们在申请的空间为0时直接申请4字节的空间，不是的时候两倍扩容就行。扩容完毕之后，我们还需要挪动数据，在pos对应的位置留出空间，之后将数据插入，返回新插入的元素的迭代器就行了。

erase

iterator erase(iterator pos)
{
    if (pos > _finish) return;
    size_t len = pos - _start;
    while (pos + 1 != _finish) *pos = *(pos + 1), pos++;
    _finish--;
    return _start + len;
}

首先判断迭代器是否合法，之后将pos之后的元素逐个向前覆盖再–_finish就行。

构造函数

默认构造

vector() {}

由于三个成员变量都是内置变量，且都给了缺省值，所以默认构造函数可以什么都不写。

有参非全缺省构造函数

vector(int n, const T& value = T()) { resize(n, value); }

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}

拷贝构造函数

        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (auto e : v)
                push_back(e);
        }

析构函数

~vector()
{
    if (_start == nullptr) return;
    delete[] _start;
    _start = nullptr;
    _finish = nullptr;
    _end_of_storage = nullptr;
}

对于析构函数来说，首先要判断一下是否相堆申请了空间，没申请就直接返回让内置类型自行销毁就行，若申请了就delete掉再将各个成员变量置空。

赋值运算符重载

vector<T>& operator= (vector<T> v)
{
    swap(v);
    return *this;
}

直接使用局部变量拷贝要复制的数组再交换，这样原本的局部变量维护的数组变成自己维护，自己维护的数组变成了局部变量维护，局部变量在函数结束后自动析构，完美完成了赋值。

迭代器相关

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;
}

数组尺寸

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

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

[]运算符重载

T& operator[](size_t pos)
{
    assert(pos < size());
    return _start[pos];
}

const T& operator[](size_t pos)const
{
    assert(pos < size());
    return _start[pos];
}

先判断数组是否越界，在返回对应的值的引用。

尾删尾插

void push_back(const T& x)
{
    insert(end(), x);
}

void pop_back()
{
    iterator pos = end() - 1;
    erase(pos);
}

复用insert()和erase()就行。

swap

void swap(vector<T>& v)
{
    std::swap(v._start, _start);
    std::swap(v._finish, _finish);
    std::swap(v._endOfStorage, _endOfStorage);
}

交换三个成员变量就行。