---

1、vector介绍和使用

vector可以管理任意类型的数组，是一个表示可变大小数组的序列容器。

通过vector文档来看它的使用。

#include <iostream>
#include <vector>
using namespace std;void test_vector1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);
}int main()
{test_vector1();return 0;
}

要使用vector需要先引头文件。现在插入一些元素后，要遍历v，可以用[]，范围for，迭代器。

	//[]for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;//迭代器vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;//范围forfor (auto e : v){cout << e << " ";}cout << endl;

创建一个数组并遍历可以这样写

void test_vector2()
{vector<int> v1(10, 1);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1.begin(), v1.end());//用迭代器范围来遍历数组for (auto e : v2){cout << e << " ";}cout << endl;
}

刚才提到vector可以传任何类型，string类也可以。

	string s1("hello world");vector<int> v3(s1.begin(), s1.end());for (auto e : v3){cout << e << " ";}cout << endl;

不过打印的是ANSCII码值罢了。

写一下反向迭代器

	//vector<int>::reverse_iterator rit = v.rbegin();auto rit = v.rbegin();//也可以使用autowhile (rit != v.rend()){cout << *rit << " ";++rit;}cout << endl;

对于vector，初始化变得很简单

void test_vector4()
{vector<int> v;v.resize(10, 0);//初始化10个元素为0
}

vector的insert和erase和string不一样，它要配合迭代器。且vector的查找元素是用std的find函数。

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

而想删除不能直接erase

	pos = find(v.begin(), v.end(), 2);if (pos != v.end()){v.erase(pos);}for (auto e : v){cout << e << " ";}cout << endl;

因为这时候迭代器失效了。头删就可以直接v.erase(v.begin())。

2、vector模拟实现

基本功能。扩容函数需要注意一下，防止程序崩掉，三个变量的赋值要考虑具体的结果。

vector.h

#pragma once
#include <iostream>
using namespace std;
#include<assert.h>namespace zyd
{template<class T>class vector{public:typedef T* iterator;vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}iterator begin(){return _start;}iterator end(){return _finish;}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}void pop_back(){assert(!empty());--_finish;}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}bool empty(){return _start == _finish;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}private:iterator _start;iterator _finish;iterator _end_of_storage;};void test_vector1(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (size_t i = 0; i < v1.size(); ++i){cout << v1[i] << " ";}cout << endl;v1.pop_back();v1.pop_back();v1.pop_back();v1.pop_back();vector<int>::iterator it = v1.begin();while (it != v1.end()){cout << *it << " ";}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;}
}

针对const对象的访问，我们写一个func函数放在和test函数同样的位置。

	void func(const vector<int>& v){for (size_t i = 0; i < v.size(); ++i){cout << v[i] << " ";}cout << endl;vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;}}

然后再写上所调用成员函数的const函数，以及const版本的迭代器。

		typedef T* iterator;typedef const T* const_iterator;

写一下resize()。如果传的参数n小于size，那就是删数据，如果大于，那么要扩容，还有新的空间要初始化，库里用了缺省参数，T val = T()。T()其实是一个匿名的默认构造，对自定义类型有用，对内置类型也适用，C++做了相关的函数，int a = int();，就会初始化a为0。但是指针不能这样写。

	template<class T>void f(){T i = T();cout << i << endl;}void test_vector2(){/*int a = int();int b = int(1);cout << a << endl;cout << b << endl;*/f<int>();f<int*>();f<double>();}

引入模板后，什么内置类型就可以了。

回到resize函数。

		void resize(size_t n, T val = T()){if (n < size()){//删除数据_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}

	void test_vector3(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);}

扩容后新空间就是0

insert和erase和迭代器失效

		void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;}

		vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);/*cout << v1.size() << endl;cout << v1.capacity() << endl;v1.resize(10);cout << v1.size() << endl;cout << v1.capacity() << endl;func(v1);*/v1.insert(v1.begin(), 0);func(v1);auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.insert(pos, 30);}func(v1);

一个头插，一个第3个位置插入，结果如下

如果是5个，也就是进行了一次扩容后，就没问题了。有的编译器这里会崩掉。

在insert函数里，我们插入了4个数据，那么就会扩容一次，开新空间，旧空间释放，扩容之后_start _finish _end_of_storage都会变，但是pos还是指向原先的空间，pos就变成了野指针，这时候就变成了迭代器失效。为了解决这个问题，我们需要找到pos的新的相对位置。

		void insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;}

如果是插入5个，那么在找pos之前就已经扩容了，pos是按照新空间去找位置，所以就没问题。

都插入完成后，对pos位置++

	auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.insert(pos, 30);}func(v1);(*pos)++;func(v1);

会发现什么都没发生。实际上这里越界了。这是因为虽然函数里面改正了pos，但是没传出去，所以外面还是以前的pos。如果函数里面pos没有改，那就没问题。insert目前是传值传参，但不能把pos改成引用传参，会报错。这是因为begin和end函数是传值，不能传给引用，所以insert返回pos就好。也可以不写这个返回，不在外面用pos就行。

erase函数

		void erase(iterator pos){assert(pos >= _start && pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;}

	void test_vector4(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;auto pos = find(v1.begin(), v1.end(), 3);if (pos != v1.begin()){v1.erase(pos);}for (auto e : v1){cout << e << " ";}cout << endl;}

刚才insert之后pos失效了，erase这里也会报错，pos会失效，最好不要访问，不容易控制，因为行为结果未定义，不同平台不同结果。

erase也可以认为是迭代器失效。如果pos是最后一个数据位置，那么删除后，finish会往前一步，但依然在最后一个元素后面，这时候pos和finish同一位置，实际上这时候pos已经失效了。

改一下erase函数

		iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator start = pos + 1;while (start != _finish){*(start - 1) = *start;++start;}--_finish;return pos;}

测试代码

	void test_vector5(){vector<int> v1;v1.push_back(10);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(50);for (auto e : v1){cout << e << " ";}cout << endl;vector<int>::iterator it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){it = v1.erase(it);}else{++it;}}cout << endl;for (auto e : v1){cout << e << " ";}cout << endl;}

补齐其他函数

		~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}

vector还有别的构造。vector接口参数里的缺省参数通常不用0，而是const T& val = T()，防止类型冲突。但这里是否需要考虑匿名对象的生命周期只在这一行？

先测一下这个问题

class A
{
public:A(){cout << "A()" << endl;}~A(){cout << "~A()" << endl;}
};A a1;A();A a2;return 0;

可以看到确实是这样，a1和a2是在return0那里才都销毁，而A（）直接就销毁。但入如果const A& xx = A()，就会使用上这个对象，一直到引用对象xx生命周期结束时才析构。

但不加const就不行，因为像匿名对象这样的临时对象都是有常性的。

继续写初始化构造函数。

		vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}

测试代码

		zyd::vector<int> v1(10, 5);for (auto e : v1){cout << e << " ";}cout << endl;

vector也有排序

		v1.insert(v1.begin(), 10);sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;

除此之外，数组也可以。默认为升序。如果想降序，需要用到greater这个模板，它可以用任何类型，以及头文件#include < functional >。

		greater<int> g;sort(v1.begin(), v1.end(), g);

也可以

		sort(v1.begin(), v1.end(), greater<int>());

深浅拷贝

		vector(const vector<T>& v){reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();}

但是这个程序应对string类对象的拷贝就崩了。

		vector<std::string> v3(10, "1111111");for (auto e : v3){cout << e << " ";}cout << endl;vector<std::string> v4(v3);for (auto e : v4){cout << e << " ";}cout << endl;

用vector<vector< int >>也出错。这是因为虽然我们自己写了深拷贝，但是开空间后，memcpy在一个个拷贝时也相当于浅拷贝，v4和v3的_start都指向了同一块空间，所以这里是memcpy浅拷贝了，函数析构时会崩掉。

这里的解决办法就是挨个赋值。自定义类型的赋值会开一样大的空间，然后填充内容。

同样地，扩容也是memcpy，调起调试可以看出memcpy的两个对象是同一个指针。所以这里也要改。

		void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}

这样其他类型的也都可以了。

难点思考

	void test_vector8(){class Solution{public:vector<vector<int>> generate(int numRows){vector<vector<int>> vv;vv.resize(numRows, vector<int>());for (size_t i = 0; i < vv.size(); ++i){vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 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;}};vector<vector<int>> ret = Solution().generate(5);for (size_t i = 0; i < ret.size(); ++i){for (size_t j = 0; j < ret[i].size(); ++j){cout << ret[i][j] << " ";}cout << endl;}cout << endl;}
}

我们的拷贝构造函数是这样

		vector(const vector<T>& v){reserve(v.capacity());//memcpy(_start, v._start, sizeof(T) * v.size());for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];}_finish = _start + v.size();}

程序崩了，是因为浅拷贝问题，赋值浅拷贝。vv是深拷贝，而ret是浅拷贝。

赋值=没有重载函数

		void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}

结束。