深入理解vector 【C++】

一、vector的介绍：

1.vector是表示可变大小的顺序容器。

2.就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3.本质讲，vector使用动态分配数组来存储它的元素。当空间满了并且插入新元素的时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。

4.vector分配空间策略：我们一般会按照两倍进行扩容来避免频繁扩容。

5.vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

6.与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其他不在末尾的删除和插入操作，效率更低。比起list和forward_list 统一的迭代器和引用更好。

总结：它底层实际上和顺序表差不多可以使用下标来访问为了提高效率扩容一般是按照两倍扩容

二、vector的定义：

方法一：构造一个某类型的空容器

vector<int> v1; // 构造一个int类型的空容器

方法二：构造一个含有n个val值的容器

vector<int> v2(10, 2); // 构造一个int类型的容器初始化为10个2

方式三：拷贝构造

vector<int> v3(v2);

方式四：使用迭代器拷贝

vector<int> v4(v2.begin(), v2.end()); //迭代器拷贝构造

注：

1.使用别的容器的迭代器也可以拷贝（不是vector 以string为例）

string s1("hello world");
vector<char> v5(s1.begin(), s1.end()); // 使用string类的迭代器构造

2.vector也可以嵌套自己，vector<vector<int>>相当于二维数组

第一个vector中的指针指向了一块存放vector<int>类型的空间，而之后的每一个vector中的指针又指向存放int类型的空间。（就相当于二维数组，只不过这个是动态的并且有成员函数）

三、空间相关

3.1 size

size_type就是size_t

返回容器中占用的元素个数

#include <iostream>
#include <vector>int main()
{std::vector<int> myints;std::cout << "0. size: " << myints.size() << '\n';for (int i = 0; i < 10; i++) myints.push_back(i);std::cout << "1. size: " << myints.size() << '\n';myints.insert(myints.end(), 10, 100);   //从最后的位置开始插入10个100std::cout << "2. size: " << myints.size() << '\n';myints.pop_back();std::cout << "3. size: " << myints.size() << '\n';return 0;
}

3.2 capacity

size_type就是size_t

#include <iostream>
#include <vector>int main()
{std::vector<int> myvector;// set some content in the vector:for (int i = 1; i <= 100; i++){myvector.push_back(i);if (i % 10 == 0){std::cout << "size: " << (int)myvector.size() << '\n';std::cout << "capacity: " << (int)myvector.capacity() << '\n';}}return 0;
}

VS保持一贯的作风，先有一段空间存放数据，超了之后按1.5倍扩容。

3.3 empty

判断vector是否为空（size是否为0）为空就返回true 不为空返回false

3.4 resize

resize函数可以改变容器的有效元素个数

value_type就是模板类型T ，不传的话，就会去调用对应的 T() 构造函数

使用规则是这样子的

假设所给值小于当前容器size值 size缩小至所给值
假设所给值大于当前容器size值并且小于capacity值 size扩大至所给值扩大的范围赋值（调用对应的构造函数）
假设所给值大于当前容器size值并且大于capacity值先扩容后面操作和2一样

调用对应的构造函数：

C++规定：内置类型也有对应的构造函数

int --> 0

double -->0.0

int* -->nullptr

对应自定义类型，调用对应的构造函数

// resizing vector
#include <iostream>
#include <vector>int main()
{std::vector<int> myvector;// set some initial content:for (int i = 1; i < 10; i++) myvector.push_back(i);myvector.resize(5);myvector.resize(8, 100);myvector.resize(12);std::cout << "myvector contains:";for (int i = 0; i < myvector.size(); i++)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;
}

3.5 reserve

使用规则如下

1.假设所给值小于当前容量值什么都不做

2 假设所给值大于当前容量值扩容至所给值

// vector::reserve
#include <iostream>
#include <vector>int main()
{std::vector<int>::size_type sz;//std全局域 vector<int>类 typedef的size_type  就是 size_tstd::vector<int> foo;sz = foo.capacity();std::cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();std::cout << "capacity changed: " << sz << '\n';}}std::vector<int> bar;sz = bar.capacity();bar.reserve(100);   // this is the only difference with foo abovestd::cout << "making bar grow:\n";for (int i = 0; i < 100; ++i) {bar.push_back(i);if (sz != bar.capacity()) {sz = bar.capacity();std::cout << "capacity changed: " << sz << '\n';}}return 0;
}

reserve会先把空间括好，你想要括多少，就传参。

四、迭代器相关

在前面的string类里面已经讲过迭代器了。这里我就贴一下代码就过了。后面的insert和erase迭代器失效才是重头戏！

// vector::reserve
#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v1; // 构造一个int类型的容器for (int i = 0; i < 10; i++){v1.push_back(i);}//正向迭代器vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}cout << endl;//反向迭代器vector<int>::reverse_iterator rit = v1.rbegin();while (rit != v1.rend()){cout << *rit << " ";rit++;}
}

五、访问数据

5.1 operator[] 对[]运算符进行了重载，一个通过下标来访问元素。

5.2 at和operator[] 一样，通过下标来访问。

5.3 front 访问第一个元素

5.4 back 访问最后一个元素（v.size()-1的下标的元素）

5. data 用于返回指向vector中第一个元素的指针

// vector::data
#include <iostream>
#include <vector>int main()
{std::vector<int> myvector(5);int* p = myvector.data();*p = 10;++p;*p = 20;p[2] = 100;std::cout << "myvector contains:";for (unsigned i = 0; i < myvector.size(); ++i)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;
}

可以通过p指针来访问vector类中的元素

六、增删查改

增：

5.1 push_back 向尾部插入一个数据

vector<int> v1;

v1.push_back(1);

v1.push_back(2);

v1.push_back(3);

就存放了1 2 3三个数据到v1对象中

5.2 insert 指定位置插入数据

第一种：（返回值是iterator，在之后讲迭代器失效会提到）

选择一个位置（迭代器），选择要插入的数据。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v1; // 创造一个空容器v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin(), 100); // 我们再开头插入一个元素100vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}return 0;
}

第二种：

选择一个位置（迭代器），选择要插入的个数，选择要插入的数据。

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v1; // 创造一个空容器v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.insert(v1.begin(), 10, 5); // 我们头插100个5vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}return 0;
}

删：

5.2 pop_back 从尾部删除一个数据

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v1; // 创造一个空容器v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto u : v1){cout << u << ' ';}cout << endl;v1.pop_back();v1.pop_back();v1.pop_back();for (auto u : v1){cout << u << ' ';}cout << endl;return 0;
}

5.3 erase 指定位置删除数据

注意这里的返回值是iterator，在之后讲迭代器失效的时候会提到。

第一种：删除一个指定位置的元素

第二种：删除一段区间的元素

// erasing from vector
#include <iostream>
#include <vector>int main ()
{std::vector<int> myvector;// set some values (from 1 to 10)for (int i=1; i<=10; i++) myvector.push_back(i);// erase the 6th elementmyvector.erase (myvector.begin()+5);std::cout << "myvector contains:";for (unsigned i=0; i<myvector.size(); ++i)std::cout << ' ' << myvector[i];std::cout << '\n';// erase the first 3 elements:myvector.erase (myvector.begin(),myvector.begin()+3);std::cout << "myvector contains:";for (unsigned i=0; i<myvector.size(); ++i)std::cout << ' ' << myvector[i];std::cout << '\n';return 0;
}

查：

5.4 find

find函数可以找到容器中我们要寻找的值并且返回迭代器

find函数有三个参数迭代器左区间迭代器右区间要查找元素（左闭右开）适用于所有的迭代器。

为什么string类里面要自己设计一个find函数呢？因为要满足对各种字符串查找的需求。

        注意！！！！！！

        这里的find函数的头文件是 algorithm !!!!!!!!!

        一定要记住！不是容器的默认函数

#include <iostream>
#include <vector>
#include<algorithm>//为了能够使用find函数
using namespace std;
int main()
{vector<int> v1; // 创造一个空容器v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);// v1.erase(v1.begin(), v1.begin()+2);vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);  // 找到3v1.erase(pos); // 删除3vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";it++;}return 0;
}

改：

operator=

// vector assignment
#include <iostream>
#include <vector>
using namespace std;
int main()
{std::vector<int> foo(3, 1);std::vector<int> bar(5, 2);bar = foo;foo = std::vector<int>();//打印foo中的元素for (auto u : foo){cout << u << " ";}cout << endl;std::cout << "Size of foo: " << int(foo.size()) << '\n';//打印bar中的元素for (auto u : bar){cout << u << " ";}cout << endl;std::cout << "Size of bar: " << int(bar.size()) << '\n';return 0;
}

这个运算符会改变size大小和内部的变量

七、迭代器失效：

在使用insert和earse的时候，会出现迭代器失效的问题。

7.1 实例1：

#include <iostream>
#include <vector>
using namespace std;
void test_1()
{vector<int> vec;vec.push_back(0);vec.push_back(1);vec.push_back(2);vec.push_back(3);vec.push_back(4);cout << vec.size() << ":" << vec.capacity() << endl;vector<int>::iterator it = vec.begin();while (it != vec.end()){if (*it % 2 == 0){vec.insert(it, 5);   //这里会出现错误++it;}++it;}cout << vec.size() << ":" << vec.capacity() << endl;for (auto e : vec){cout << e << " ";}cout << endl;
}
int main()
{test_1();return 0;
}

分析：

vec.insert(it, 5); //这里会出现错误当你把it传进去的时候，是传值传进去的，

它在insert内部会进行扩容（异地扩容）操作。内部的pos指针还指向原地，就不再准确了。

就会造成野指针问题。

而如果传引用传递的话，会让其他一些函数不能使用。

原因：insert之后vector会分配新的空间，旧迭代器便会失效。

解决方法：取insert函数的返回值为新的迭代器。

用图片来帮助理解：

改法：（接收新的it作为返回值）

while (it != vec.end())
{if (*it % 2 == 0){it=vec.insert(it, 5);//这样子写是错误的，应该怎么改？it++;}++it;}

7.2 实例2：

#include <iostream>
#include <vector>
using namespace std;
int main()
{vector<int> v1; // 创造一个空容器v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);vector<int>::iterator it = find(v1.begin(), v1.end(), 2); // 意思是我们要删除2v1.erase(v1.begin()); //删除头元素v1.erase(it); //删除元素2return 0;
}