C++STL详解（三）——vector的介绍和使用

vector的介绍

1: vector是表示可变大小数组的容器。
2：vector就像数组一样，也采用的连续空间来存储元素，这也意味着vector可以采用下标对vector的元素进行访问。
3：vector与普通数组不同的是，vector的大小是可以动态改变的。
4：vector需要分配大小时，其做法是，分配一个新的数组，然后将全部元素移入到这个数组当中，并且释放原来的空间。
5：由于vector采用连续的空间来存储元素，与其他动态序列容器相比，vector在访问元素的时候更加高效，在其末尾添加和删除元素相对高效，而对于不在其末尾进行的删除和插入操作效率则相对较低。

vector的使用

vector的定义方式

方式一：构造一个vector类型的容器。

vector<int> v1;   

方式二： 构造一个含有n各val的vector容器

vector<int> v2(10, 2);

方式三：vector容器的拷贝构造

vector<int>v3(v2);

方式四：使用迭代器区间构造（该方式也可用于构造其他容器，例如string类型。）

vector<int> v4(v2.begin(), v2.end());

方式6：像C语言定义数组一样定义。

vector<int> v5{ 1,2,3,4,5};

vector的空间增长问题

reserve和resize

reserve说明：
1：改变容器的最大的最大容量，当我们所传的值大于容器当前的
capacity时，会将capacity扩大到该值。
2：当所给值小于容器当前的capacity是，reserve无效果。
resize说明：
1：当所传值大于容器当前的size时，会将size扩大到所传值，扩大的元素为第二个所传值，如果用户没有给出，则编译器会给上缺省值为0；
2：当所传值小于容器当前的size时，则会将vector容器的size缩小到所传值大小。

int main()
{vector<int> v(10, 2);v.resize(15);//扩容，并让size（）大小为15，5个0用来填充。for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;v.resize(10); //让size()大小变为10，vector容量不变。for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << v.capacity() << endl; //20return 0;
}

vector的迭代器使用

begin 和end

int main()
{vector <int>v(10, 6);vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << endl;it++;}cout << endl;
}

rbegin和rend

int main()
{vector<int> v{ 1,2,3,4,5,6 };//反向迭代器遍历容器:reverse_iteratorvector<int>::reverse_iterator rit = v.rbegin();while (rit != v.rend()){cout << *rit << " ";rit++;}cout << endl;return 0;
}

insert 和erase

insert函数可以在目标位置插入1个或者多个指定元素。
erase函数可以删除迭代器指定位置的元素，也可以使用迭代器
进行删除。（左闭右开）

int main()
{vector<int> v;v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.pop_back();//插入位置，插入个数，插入值。v.insert(v.begin(), 3,1);for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;v.erase(v.begin(), v.begin() + 1);for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;return 0;
}

find函数

find函数说明：
使用find函数要确认所要删除位置的迭代器区间，第三个参数则要确定用户所要寻找的值。
如果find函数在所传的迭代器区间找到了目标元素，则返回目标元素迭代器，否则则返回end（）位置迭代器。

int main()
{vector<int> v;v.push_back(1); //尾插元素1v.push_back(2); //尾插元素2v.push_back(3); //尾插元素3v.push_back(4);v.push_back(5);vector<int>::iterator it = v.begin();//在区间寻找值为2的元素，并返回对应迭代器。//auto 根据后面的返回值类型主动判断。auto  pos = find(it, it + 4, 2);if ( pos != v,end()){//删除pos所指的元素。v.erase(pos);}for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;return 0;
}

元素访问

vector中除了使用vector迭代器进行访问的，还可以使用[]操作符重载访问。

int main()
{vector<int> v(10, 1);//使用“下标+[]”的方式遍历容器for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;return 0;
}

另外，vector还支持迭代器，这也就说明vector还支持范围for进行访问。

int main()
{vector<int> v(10, 6);for (auto e : v){cout << e << " ";}cout << endl;return 0;
}

vector迭代器失效问题

1：inserse插入扩容时空间销毁造成野指针问题

例如，当我们从vector容器3的位置前插入30，不对vector进行扩容时，发现程序正常运行。
但是当我们插入数据时要对vector进行扩容却发现程序而不能崩溃了。

void test_vector1()
{vector <int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto p = find(v.begin(), v.end(), 3));if (p != v.end()){v.insert(p, 30);}for (auto e : v){cout << e << " ";}}

原因：
当我们插入30时会发生第二次扩容，此时find 找到了vector容器元素为3的位置并返回指向3的迭代器，但是因为vector扩容后会对这原来的vector空间销毁，此时返回的p并不是原来3的迭代器位置，此时p已经变成了野指针，insert时pos会导致导致程序崩溃。
以下insert 和 reserve 方法的底层实现：

pos此时的值已经变成了随机值。

改善方法探讨：
我们可以在扩容后更新pos指向的元素的位置。但是此时又有一个问题，我们在扩容后重新修正了pos的位置时，却发现p依旧是失效的，原因是pos是形参，p是实参。形参的改变并不会影响到实参。

此时，我们可以在pos形参位置加入引用，但是当我们使用
v.begin()为实参传入时，却发现调用不成功，因为此时的v.begin()
返回的值具有常性，权限由小变大。

又或者我们可以返回pos位置的引用，又说明引用的值可以被修改，这又与STL insert方法的实现相违背。

解决方法：
当使用insert后又要使用insert或者erase操作进行扩容或者缩容时，因为在insert时，扩容后已经重新对pos进行赋值，但是因为pos终究是形参的改变无法影响到实参，所以在insert后要使用变量去接受pos的位置。

void test_vector1()
{vector <int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto p = find(v.begin(), v.end(), 3);if (p != v.end()){v.insert(p, 30);//插入一个数后及时接受pos的位置后才能继进行插入。auto p = find(v.begin(), v.end(), 3);v.insert(p, 30);}for (auto e : v){cout << e << " ";}}
int main()
{test_vector1();
}

2：erase删除或者insert插入时元素移动迭代器问题：

如果erase函数具有缩容功能时，也会导致迭代器失效，所以erase之后我们尽量不要直接对它进行访问。
第一种情况：
程序正常运行：
如果我们插入5个元素，当it指向元素5时，it正好指向v.end（），所以程序正常退出。

第二种情况：
程序崩溃：
如果我们插个4个元素，当it指向元素4进行删除后 it++，但是v.end()指向了元素3的下一个位置，而此时it又进行++，与v.end()正好错过了。所以本来应该删除4之后结束循环的，如今只能进行删除。如果一直循环下去的化，it就变成了野指针的，在erase中对野指针访问后就会造成程序崩溃。

第三种情况：
程序结果不对：
当我们连续插入偶数时，it指向元素2删除后，原来在2后面的4向前移动了以为，在下一次while循环中，原本it指向4的现在指向了元素3，元素4未被删除。

解决方法：
针对插入4个元素时，在不对迭代器i重新赋值时，我们可以当it指向偶数就删除，指向奇数就++；这样在最后删除4后，it就不会像之前++了，此时it指向的位置正好等于v.end()，结束循环。

再例如：我们在偶数之前插入这个偶数的两倍。
如果我们不对it进行操作，直接让it++后进行访问，
又因为再2的前面插入一个数后，此时的2已经在原来的位置基础上向后移动了以为，这样it又会指向元素2，此刻便会不断循环对2的前面一个元素插入数字。
造成程序崩溃。

解决办法：
我们要解决插入元素后it一直指向同一个数问题，如果it指向偶数，可以在偶数前插入一个术后，it++两次，从而跳过已经插过数的偶数了。如果为奇数，则直接++it。