网站开发的后台开发工具,东莞建设工程公司,安卓网页制作软件,桂林象鼻山附近的酒店文章目录1、vector介绍和使用2、vector模拟实现insert和erase和迭代器失效补齐其他函数深浅拷贝难点思考1、vector介绍和使用
vector可以管理任意类型的数组#xff0c;是一个表示可变大小数组的序列容器。
通过vector文档来看它的使用。
#include iostream
#inclu…
文章目录1、vector介绍和使用2、vector模拟实现insert和erase和迭代器失效补齐其他函数深浅拷贝难点思考1、vector介绍和使用
vector可以管理任意类型的数组是一个表示可变大小数组的序列容器。
通过vector文档来看它的使用。
#include iostream
#include vector
using namespace std;void test_vector1()
{vectorint 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;//迭代器vectorint::iterator it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;//范围forfor (auto e : v){cout e ;}cout endl;创建一个数组并遍历可以这样写
void test_vector2()
{vectorint v1(10, 1);for (auto e : v1){cout e ;}cout endl;vectorint v2(v1.begin(), v1.end());//用迭代器范围来遍历数组for (auto e : v2){cout e ;}cout endl;
}刚才提到vector可以传任何类型string类也可以。 string s1(hello world);vectorint v3(s1.begin(), s1.end());for (auto e : v3){cout e ;}cout endl;不过打印的是ANSCII码值罢了。
写一下反向迭代器 //vectorint::reverse_iterator rit v.rbegin();auto rit v.rbegin();//也可以使用autowhile (rit ! v.rend()){cout *rit ;rit;}cout endl;对于vector初始化变得很简单
void test_vector4()
{vectorint v;v.resize(10, 0);//初始化10个元素为0
}vector的insert和erase和string不一样它要配合迭代器。且vector的查找元素是用std的find函数。 vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vectorint::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;
#includeassert.hnamespace zyd
{templateclass Tclass 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(){vectorint 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();vectorint::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 vectorint v){for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;vectorint::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。但是指针不能这样写。 templateclass Tvoid f(){T i T();cout i endl;}void test_vector2(){/*int a int();int b int(1);cout a endl;cout b endl;*/fint();fint*();fdouble();}引入模板后什么内置类型就可以了。
回到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(){vectorint 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;}vectorint 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(){vectorint 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(){vectorint 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;vectorint::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::vectorint 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 。 greaterint g;sort(v1.begin(), v1.end(), g);也可以 sort(v1.begin(), v1.end(), greaterint());深浅拷贝 vector(const vectorT v){reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());_finish _start v.size();}但是这个程序应对string类对象的拷贝就崩了。 vectorstd::string v3(10, 1111111);for (auto e : v3){cout e ;}cout endl;vectorstd::string v4(v3);for (auto e : v4){cout e ;}cout endl;用vectorvector 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:vectorvectorint generate(int numRows){vectorvectorint vv;vv.resize(numRows, vectorint());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;}};vectorvectorint 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 vectorT 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(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vectorT operator(vectorT v){swap(v);return *this;}结束。
