个人主页~

vector类

一、vector的介绍和使用1、vector的介绍2、vector的使用（1）vector的定义（2）vector iterator的使用（3）vector 空间增长（4）vector的增删查改（5）vector迭代器失效①引起底层改变的操作②指定元素的删除操作③string类似于vector

3、vector的优越性

一、vector的介绍和使用

1、vector的介绍

这里是cplusplus官方介绍

vector是表示可变大小数组的序列容器

vector类似于数组，采用连续存储空间来存储元素，可以用下标对vector元素进行访问，但它的大小是可以动态改变的，而且这个改变可以被容器自动处理

因为vector使用动态分配数组来存储它的元素，当新元素插入的时候需要扩容，一般来说进行扩容都是按照倍数扩容的，在VS上以1.5倍扩容，在gcc上以2倍扩容，这样后来的几位数字插入的复杂度就很低了

与其他动态序列容器相比，vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效，对于其它不在末尾的删除和插入操作，效率更低

2、vector的使用

（1）vector的定义

<code>void test1()

{

vector<int> v1;

vector<int> v2(10, 0);

vector<int> v3(v2);

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

}

（2）vector iterator的使用

<code>void test2()

{

vector<int> v1(10, 0);

int a = 0;

for (auto& i : v1)

{

i += a;

a++;

}

for (auto it = v1.begin(); it != v1.end(); ++it)

{

cout << *it << " ";

}

cout << endl;

}

（3）vector 空间增长

<code>void test3()

{

vector<int> v1(10,0);

cout << v1.size() << endl;

cout << v1.capacity() << endl;

cout << v1.empty() << endl;

v1.resize(5);

cout << v1.size() << endl;

cout << v1.capacity() << endl;

v1.reserve(15);

cout << v1.size() << endl;

cout << v1.capacity() << endl;

}

这里提一下不同模版的resize以及reserve基本是相同的，resize是改变size，reserve是改变capacity，清楚它们之间的一一对应的关系

（4）vector的增删查改

其中vector中没有find，find在标准函数库中有定义，第一个参数是开始位置的迭代器，第二个参数是结束位置的迭代器，第三个参数是一个常量的引用，它可以是任何模版实例化后的常量

<code>void test4()

{

vector<int> v1(10, 0);

v1.push_back(1);

v1.push_back(2);

v1.pop_back();

v1.push_back(3);

auto pos = find(v1.begin(), v1.end(), 3);

v1.insert(pos, 4);

v1.erase(v1.end() - 1);

for (int i = 0; i < v1.size(); i++)

{

cout << v1[i] << " ";

}

cout << endl;

vector<int> v2(10, 0);

v1.swap(v2);

for (int i = 0; i < v1.size(); i++)

{

cout << v1[i] << " ";

}

cout << endl;

for (int i = 0; i < v2.size(); i++)

{

cout << v2[i] << " ";

}

cout << endl;

}

（5）vector迭代器失效

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针或被封装的指针，vector的迭代器就是原生态指针T*，因此迭代器失效就是迭代器底层对应指针所指向的空间销毁了，而使用一块已经被释放的空间，如果继续使用已经失效的迭代器，程序可能会崩溃

下面是可能导致迭代器失效的操作

①引起底层改变的操作

resize、reserve、insert、assign、push_back等可能引起扩容的函数

这里拿resize来举例

<code>void test1()

{

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

auto it = v.begin();

v.resize(100, 0);

while (it != v.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

包括上面提到的其他函数，因为需要空间的增大，所以vector需要扩容，而vector扩容的操作是开辟新空间，拷贝数据到新空间，销毁旧空间，而寄存器it指向的位置是旧空间的位置，所以会出现操作已经被释放的空间的问题

解决方法是扩容之后重新赋值it

②指定元素的删除操作

<code>void test2()

{

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

auto pos = find(v.begin(), v.end(), 3);

v.erase(pos);

cout << *pos << endl;

}

当使用erase删除元素时，所有在 erase() 之后的迭代器（包括 erase() 使用的迭代器）都会变得无效。这意味着一旦 pos 被用于 erase() 操作，pos 就不能再被用来访问或解引用任何元素了

③string类似于vector

string在上述过程之后，迭代器也会失效，原因相同，解决办法相同，性质相似

3、vector的优越性

杨辉三角问题

对于这个杨辉三角问题，我们需要一个二维数组，用C语言来写的话稍微的复杂一些，需要malloc一个指针数组，然后指针数组的指针指向一个一维数组

对于C++来说，我们需要一个vector<vector< int>>

最上面的_a的类型是vector< int>*

中间的_a的类型是int *

<code>class Solution {

public:

vector<vector<int>> generate(int numRows)//numRows是杨辉三角行数

{

vector<vector<int>> vv;

vv.resize(numRows);//扩容numRows行

for(size_t i = 0;i < vv.size();i++)

{

vv[i].resize(i+1,0);//将每一行所有的数字置为0

vv[i][0] = vv[i][vv[i].size() - 1] = 1;//将三角两边的数字全部置为1

}

for(size_t i = 0;i < vv.size();i++)

{

for(size_t j = 0;j < vv[i].size();j++)

{

if(vv[i][j] == 0)

{

vv[i][j] = vv[i-1][j]+vv[i-1][j-1];

//将所有不在三角两边的按照杨辉三角的原则相加得数

}

}

}

return vv;

}

};

今日分享就到这里了~