vector介绍

在C++标准库中，vector是一个常用的序列式容器（线性结构），它就好比c语言中的数组，但是vector有一些数组没有的功能，是一个封装好了的类。

想要使用vector需要先引入头文件：

#include<vector>

要使用vector的一些泛型算法需要引入头文件：

#include<algorithm>

vector底层实现

vector底层数据结构是一个动态开辟的一维数组

其内部含有三个指针（start，finish，end_of_storage）

vector的使用

初始化vector

vector的一些内置函数

vector<int> a;
a.front();  //返回容器第一个元素的值
a.back();   //返回容器最后一个元素的值
a.begin();  //返回指向容器第一个元素的迭代器
a.end();  //返回指向容器最后一个元素下一个位置的迭代器
a[i];  //返回容器第i下标的值
a.clear();  //清空容器的值（size=0， capacity不变）
a.empty();  //判空，如果容器为空则返回true,不为空返回false

vector迭代器iterator的使用

vector增删查改

查：

vector find( vector begin,vector end,int val ):在begin到end范围查找val

begin：查找范围起始位置的迭代器

end：查找范围终止位置的迭代器（查找的数包括这一个数）

val：要查找的数值

返回值：如果找到，返回指向此数的迭代器

如果没有找到，返回此容器的end()【指向最后一个元素的下一个位置的迭代器】

查找范围内存在的数

查找范围内不存在的数

增：

尾插：push_back( int a ):尾部插入元素a

指定位置之前插入：insert( 指向此位置的迭代器,int a ):

返回值：新插入位置的迭代器

typedef vector<int> _vector;
typedef vector<int>::iterator _it;

_vector _insert()
{
    _vector a;
    for (int i = 0; i < 5; i++)
    {
        a.push_back(i);
    }
    return a;
}

void print(_vector a,_it it)
{
    for (it = a.begin(); it != a.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
int main()
{
    _vector a;
    a = _insert();
    _it it = a.begin();
    print(a,it);
    it = find(a.begin(),a.end(),3);
    a.insert(it, 10);   //在容器内3的前面插入数据10
    print(a, it);
    return 0;
}

运行结果：

insert插入原理:

增容

改变size和capacity大小的vector内置函数

void resize( int newsize,int value )：重新设置容器的size

newsize：新设置的大小（小于原本的size则删除原本多出来的数据，大于原本的size则）

value：如果newsize>原本的size，则将多出来的空间赋值为value，如果不写默认是0

void reserve(int newstorage)：重新设置容器的容量大小

newstorage：新的容量大小（如果小于原本大小就不进行任何操作）

vs的增容机制

总结：vs中vector增容按照1.5倍增容，Linux中vector增容按照2倍增容

增容的底层原理

删：

void pop_back()：尾删

iterator arease( const_iterator first,const_iterator end )：删除范围内的元素（在内部erase会让迭代器++一次）

first：删除起始位置的迭代器

end：删除终止位置的迭代器

注意：如果只传一个迭代器，则只此位置的元素

返回值：删除后下一个元素的迭代器

错误演示：

在循环中使用erase的正确写法

erase删除原理

改：

通过[ ]运算符来进行修改，例如：

vector迭代器失效问题

迭代器的作用是让算法不用关心底层的数据 ，其底层实际就是一个指针。因此迭代器失效就是迭代器底层的指针指向的空间被销毁了，去使用一块已经被释放的空间，结果就是程序崩溃

在vector中，当我们在循环中使用push_back和erase时容易发生迭代器失效问题（即底层指针指向被释放的空间还依然去使用这个指针）

我们分别举两个例子来带大家了解迭代器失效问题。

erase删除导致的迭代器失效

我们在循环中去删除容器中的一个值

我们先给出错误代码

#include<iostream>
#include<vector>
using namespace std;

typedef vector<int> _vector;
typedef vector<int>::iterator _it;

int main()
{
    _vector a;
    for(int i =0;i<10;i++)
    {
        a.push_back(i);
    }
    _it it = a.begin();
    for (it; it != a.end();)
    {
        if (*it == 4)    //删除容器中的4
        {
            a.erase(it);  //没有去接收erase的返回值
        }
        else
        {
            it++;
        }
    }
    return 0;
}

在for循环中，当我们调用erase去删除2时，删除完成后没有用迭代器去接收erase的返回值(2的下一个元素的迭代器)，此时迭代器不知道指向的哪里，此时若对迭代器进行操作会导致程序崩溃，也就是迭代器失效

如何避免erase导致的迭代器失效：

a.erase(it) 改为 it = a.erase(it)

insert插入导致的迭代器失效

我们在循环中去向容器中的一个元素前新插入一个值

我们先给出错误代码：

#include<iostream>
#include<vector>
using namespace std;

typedef vector<int> _vector;
typedef vector<int>::iterator _it;

int main()
{
    _vector a;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i);
    }
    _it it = a.begin();

    for (it; it != a.end();)
    {
        if (*it == 4)  //在元素4前新插入一个数15
        {
            a.insert(it, 15);
        }
        else
        {
            it++;
        }
    }
    return 0;
}

在for循环中，当我们调用insert在4前新插入元素时，插入完成后没有用迭代器去接收insert的返回值(新插入元素的下一个元素的迭代器)，此时迭代器不知道指向的哪里，此时若对迭代器进行操作会导致程序崩溃，也就是迭代器失效

如何避免insert导致的迭代器失效：

a.insert(it,15) 改为 it = a.insert(it,15)

模拟实现vector

私有成员：

_iterator _start;
_iterator _finish;
_iterator _end_of_storage;

成员函数：

My_vector();
My_vector(int n,const T& val);
My_vector(otheriterator start,otheriterator finish);
My_vector(const My_vector<T>& v);
My_vector<T>& operator=( My_vector<T> v );

迭代器相关：

begin();
end();
rbegin();
rend();

容量大小相关：

size();
capacity();
resize( int newsize,const T& val = T() );
reserve( int newstorage );

元素访问：

T& front();
T& back();
T& operator[]( const int index );

元素修改：

push_back( const T& val );
pop_back();
insert( _iterator pos,const T& val );
erase( _iterator pos );

整体函数实现：

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;

template<class T>
class My_vector
{
public:
    //vector的迭代器是原生态的指针
    typedef T* _iterator;
    typedef const T* _const_iterator;
private:
    _iterator _start;
    _iterator _finish;
    _iterator _end_of_storage;
public:
/*-------------------------------------类的默认成员函数--------------------------------------------*/
    //缺省构造
    My_vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
    //构造
    My_vector(int n, const T& val = T()) :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
    {
        _start = new T[n];
        for (int i = 0; i < n; i++)
        {
            _start[i] = val;
        }
        _finish = _start + n;
        _end_of_storage = _finish;
    }
    
    //部分拷贝构造
    template<class otheriterator>
    My_vector(otheriterator start, otheriterator finish)
    {
        int size = 0;
        otheriterator it = start;
        while (it != finish)
        {
            ++it;
            ++size;
        }

        _start = new T[size];
        int i = 0;
        while(i < size)
        {
            _start[i] = *start;
            ++start;
            ++i;
        }
        _finish = _start + size;
        _end_of_storage = _finish;
    }

    //拷贝构造
    My_vector(const My_vector<T>& v):_start(new T[v.size()])
    {
        int size = v.size();
        for (int i = 0; i < size; i++)
        {
            _start[i] = v[i];
        }
        _finish = _start + size;
        _end_of_storage = _finish;
    }

    //重载=
    My_vector<T>& operator=(My_vector<T> v)
    {
        _start = new T[v.size()];
        for (int i = 0; i < v.size(); i++)
        {
            _start[i] = v[i];
        }
        _finish = _start + v.size();
        _end_of_storage = _finish;
        return *this;
    }

    //析构函数
    ~My_vector()
    {
        if (_start)
        {
            delete[]_start;
            _start = nullptr;
            _finish = nullptr;
            _end_of_storage = nullptr;
        }
    }

/*-------------------------------------迭代器相关------------------------------------------*/
    //获取容器起始位置的迭代器
    _iterator begin() { return _start; }
    _const_iterator begin() const { return _start; }

    //获取容器最后一个元素的下一个位置的迭代器
    _iterator end() { return _finish; }
    _const_iterator end() const { return _finish; }

    //获取容器逆向起始位置的迭代器
    _iterator rbegin() { return _finish - 1; }
    _const_iterator rbegin() const { return _finish - 1; }

    //获取容器逆向最后一个元素的前一个位置的迭代器
    _iterator rend() { return _start - 1; }
    _const_iterator rend() const { return _start - 1; }

/*-------------------------------------容量相关------------------------------------------*/
    //获取容器size大小
    int size() const { return _finish - _start; }
    
    //获取容器容量大小
    int capacity() const { return _end_of_storage - _start; }
    
    //判空
    bool empty() const { return _start == _finish; }

    //重新设置size
    void resize(int newsize, const T& val = T())
    {
        int oldsize = this->size();
        if (newsize <= oldsize)
        {
            _finish = _start + newsize;
        }
        else
        {
            reserve(newsize);
            while (_finish != _end_of_storage)
            {
                *_finish = val;
                ++_finish;
            }
        }
    }

    //重新设置容量
    void reserve(int newstorage)
    {
        int oldstorage = this->capacity();
        if (newstorage > oldstorage)
        {
            T* new_start = new T[newstorage];
            if (new_start)
            {
                int size = this->size();
                int i = 0;
                while (i < size)
                {
                    new_start[i] = _start[i];
                    i++;
                }
                delete[]_start;
                _start = new_start;
                _finish = _start + size;
                _end_of_storage = _start + newstorage;
            }
        }
    }

/*-------------------------------------元素访问------------------------------------------*/
    //获取容器第一个元素
    T& front() { return *_start; }
    const T& front() const { return *_start; }

    //获取容器最后一个元素
    T& back() { return *(_finish - 1); }
    const T& back() const { return *(_finish - 1); }

    //重载[]
    T& operator[](const int index)
    {
        if (index < size())
        {
            return _start[index];
        }
    }
    const T& operator[](const int index) const
    {
        if (index < size())
        {
            return _start[index];
        }
    }

/*-------------------------------------元素修改------------------------------------------*/
    //尾插
    void push_back(const T& val)
    {
        int size = this->size();
        if (size == capacity())
        {
            if (size == 0)
            {
                reserve(1);
            }
            else if (size == 1)
            {
                reserve(2);
            }
            else
            {
                reserve(size * 1.5);
            }
        }
        *_finish = val;
        ++_finish;
    }

    //尾删
    void pop_back()
    {
        if (!empty())
        {
            --_finish;
        }
    }

    //任意位置插入
    _iterator insert(_iterator pos, const T& val)
    {
        //插入位置是否合法
        assert(!(pos < _start || pos > _finish));
        //是否需要扩容
        int size = this->size();
        if (size == capacity())
        {
            if (size == 0)
            {
                reserve(1);
            }
            else if (size == 1)
            {
                reserve(2);
            }
            else
            {
                reserve(size * 1.5);
            }
        }
        //插入位置及以后元素全部向后移动一位
        _iterator it = _finish;
        while (it != pos)
        {
            *it = *(it - 1);
            --it;
        }
        //插入元素
        *it = val;
        //__finish也后移一位
        _finish++;
        //返回新插入元素的迭代器
        return pos;
    }

    //删除元素
    _iterator erase(_iterator pos)
    {
        //删除位置是否合法
        assert(!this->empty() && !(pos < _start || pos >= _finish));
        _iterator it = pos;
        //删除位置之后位置向前移动一位
        while (it != _finish)
        {
            *(it - 1) = *it;
            ++it;
        }
        //并且_finish也向前移动一位
        --_finish;
        //返回删除元素的下一个元素的迭代器
        return pos;
    }

    void clear()
    {
        _finish = _start;
    }
};