vector

一、vector的介绍和使用
1.vector的介绍

• vector是表示可变大小数组的序列容器
• vector采用连续存储空间来存储元素，也意味着可以采用下标对vector元素进行访问，和数组一样高效。但是它的大小可以动态改变，而且它的大小会被容器自动处理
• 本质上来讲，vector通过动态分配数组来存储它的元素。当新元素插入时，这个数组需要被重新分配大小。为了增加存储空间，其做法是，分配一个新的数组，将全部元素移到这个数组
• vector会分配一些额外空间以适应可能的增长，因此存储空间比实际需要的存储空间更大
• vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。

2.vector的使用

1. vector的定义

vector ()                            //无参构造
vector (size_type n,const value_type& val=value_type())                //构造并初始化n个val
vector (const vector& x);                                            //拷贝构造
vector (Inputlterator first,Inputlterator last)                         //使用迭代器进行初始化构造

2. vector iterator的使用

begin()                              //获取第一个数据位置的iterator
end()                                //获取最后一个数据位置下一个位置的iterator
rbegin()                            //获取最后一个位置的reverse_iterator
rend()                              //获取第一个数据前一个位置的reverse_iterator
cbegin()                           //获取第一个数据位置的const_iterator
cend()                             //获取最后一个数据的下一个位置的const_iterator

3. vector空间增长问题

size()                         //获取数据个数
capacity()                 //获取容量大小
empty()                     //判断是否为空
void resize(size_type n,value_type val=value_type()) ;                 //改变vector的大小
void reserve(size_type n);                                //改变vector放入capacity

注：
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题
resize在开空间的同时还会初始化，影响size

4.vector 增删查改

void push_back(const value_type& val) ;                             //尾插
void pop_back();             //尾删
iterator insert(iterator position,const value_type& val);        //在position之前插入val
iterator erase(iterator position);                       //删除position位置的数据
void swap(vector& x);                                  //交换两个vector的数据空间
reference operator[](size_type n);                 //像数组一样访问

5.vector迭代器失效问题

int main()
{ 
     int a[]={1,2,3,4};
     vector<int> v(a,a+sizeof(a)/sizeif(int));
     
     //使用find查找3所在位置的迭代器
     vector<int>::iterator pos=find(v.begin(),v.end(),3);
    
     //删除pos位置的数据，导致迭代器失效
     v.erase(pos);
     cout<<*pos<<end;       //导致非法访问
    
    //在pos位置插入数据，导致pos迭代器失效
    //insert导致迭代器失效，是因为可能会导致增容，增容后pos还指向原来的空间，而原来的空间已经被释放
    pos=find(v.begin(),v.end(),3);
    v.insert(pos,5);
    cout<<*pos<<endl;           //导致非法访问
   
    return 0；
 }

常见的迭代器失效的场景

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(）
{
     int a[]={1,2,3,4};
     vector<int> v(a,a+sizeof(a)/sizeof(int));  
     //实现删除v中的所有偶数
     //下面的程序会崩溃，如果是偶数，erase导致迭代器失效
     //对失效的迭代器++，会导致程序崩溃
     vector<int>::iterator it=v.begin();
     while(it!=v.end())
     {
         if(*it%2==0)
            v.erase(it);
            ++it;
     }
 
    //应改为下面程序，erase返回删除位置的下一个位置
    vector<int>::iterator it=v.begin();
    while(it!=v.end())
    {
        if(*it%2==0)
           it=v.erase(it);
        else
           ++it;
    }
    return 0;
 }