昆明网站建设设计,民宿设计公司,做网站需要公司,天津滨海新区网站建设目录前言一、项目结构1. vector的简介2. 项目结构二、vector的底层结构三、默认成员函数(Member functions)1. 构造函数(1)无参构造函数(2)使用n个值来构造对象(3)使用一段迭代器区间来进行初始化(4)测试构造函数2. 拷贝构造函数#xff08;现代写法#xff09;3. 析构函数4.…
目录前言一、项目结构1. vector的简介2. 项目结构二、vector的底层结构三、默认成员函数(Member functions)1. 构造函数(1)无参构造函数(2)使用n个值来构造对象(3)使用一段迭代器区间来进行初始化(4)测试构造函数2. 拷贝构造函数现代写法3. 析构函数4. 赋值运算符重载函数现代写法四、迭代器(Iterators)1. 普通对象的正向迭代器2. const 对象的正向迭代器五、容量接口(Capacity)1. size()2. capacity()3. reserve()4. resize()六、元素访问接口(Element access)1. operator[](size_t pos)(1)const T operator[](size_t pos)(2)const T operator[](size_t pos) const2. at(size_t pos)(1)T at(size_t pos)3. front()4. back()七、修改接口(Modifiers)1. push_back(const T x)2. pop_back()3. iterator insert(iterator pos,T val T()))4. iterator erase(iterator pos)八、vector中更深层次的深浅拷贝问题前言 vector本质就是一个支持顺序存储数据并且容量支持修改得到顺序表。但是vector的底层结构实现相比于之前实现的string来说略有不同。string中的底层结构是通过一个指针数组和两个变量来标识数组中数据的变化。vector是通过三个迭代器来标识上述过程。 一、项目结构
1. vector的简介 2. 项目结构
这个项目有两个文件一个是test.cpp文件另一个是vector.h文件。test.cpp文件主要是用来测试实现的vector的代码逻辑。vector.h文件主要是模拟实现vector的代码逻辑。
二、vector的底层结构 效果图 代码实现
namespace hjt
{// 实现vectortemplate class Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;// 指向存储的第一个有效数据iterator _finish;// 指向存储的最后一个有效数据的下一个位置iterator _endofstorage;// 指向能够存储的最后一个位置的下一个位置};
}代码中是通过三个迭代器来实现底层的。
_start指向存储的第一个有效数据_finish指向存储的最后一个有效数据的下一个位置_endofstorage 指向能够存储的最后一个位置的下一个位置 其实这个实现方法和string中的实现方法其实差不多相当于_start表示空间的起始地址_finish表示有效数据的个数_endofstorage表示vector的实际容量。
三、默认成员函数(Member functions)
1. 构造函数 (1)无参构造函数
代码 // 无参构造函数vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){}练习
int main()
{hjt::vectorint v1;hjt::vectorchar v2;hjt::vectordouble v3;hjt::vectorstring v4;return 0;
}分析v1表示一个存储int类型的vector对象v2表示一个存储char类型的vector对象v3表示一个存储double类型的vector对象v4表示一个存储string类型对象的vector对象。
(2)使用n个值来构造对象
代码1 // 构造函数使用n个值来构造对象vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (n--){push_back(val);}}代码2 // 构造函数使用n个值来构造对象vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){while (n--){push_back(val);}}(3)使用一段迭代器区间来进行初始化
代码 // 构造函数使用一段迭代器区间来进行初始化template class InputIteratorvector(InputIterator left, InputIterator right){while (left right){push_back(*left);left;}}(4)测试构造函数
测试代码
void test_vector1()
{// 测试构造函数hjt::vectorint 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);v1.push_back(7);hjt::vectorint::iterator vit v1.begin();while (vit ! v1.end()){cout *vit ;vit;}cout endl;hjt::vectorint v2(6, 6);hjt::vectorint::iterator vit2 v2.begin();while (vit2 ! v2.end()){cout *vit2 ;vit2;}cout endl;hjt::vectorint v3(v1.begin(), v1.end());hjt::vectorint::iterator vit3 v3.begin();while (vit3 ! v3.end()){cout *vit3 ;vit3;}cout endl;}运行结果
2. 拷贝构造函数现代写法
代码
// 拷贝构造函数vector(const vectorT v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){vectorT tmp(v.begin(), v.end());swap(tmp);}测试代码
void test_vector2()
{// 测试拷贝构造函数hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 调用构造函数hjt::vectorint v1(v);hjt::vectorint v2 v1;// 打印v1for (auto e : v1){cout e ;}cout endl;// 打印v2for (auto e : v2){cout e ;}cout endl;}
运行结果 3. 析构函数
代码
// 析构函数~vector(){if (_start){delete[]_start;_start _finish _endofstorage nullptr;}}4. 赋值运算符重载函数现代写法
代码 // 赋值运算符重载函数vectorT operator(vectorT v){swap(v);return *this;}测试代码
void test_vector3()
{// 测试拷贝构造函数hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 调用赋值运算符重载函数hjt::vectorint v1;v1 v;hjt::vectorint v2;v2 v1;// 打印v1for (auto e : v1){cout e ;}cout endl;// 打印v2for (auto e : v2){cout e ;}cout endl;}运行结果
四、迭代器(Iterators)
1. 普通对象的正向迭代器 代码
// 普通迭代器iterator begin(){return _start;}iterator end(){return _finish;}代码使用
2. const 对象的正向迭代器
代码
// const迭代器const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}五、容量接口(Capacity)
1. size()
代码 size_t size() const{return _finish - _start;}
2. capacity()
代码 size_t capacity() const{return _endofstorage - _start;}
3. reserve()
代码
// 扩容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;_endofstorage _start n;}}4. resize()
测试代码
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;v.resize(100,6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;return 0;
}运行结果
测试代码2
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;v.resize(3, 6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;return 0;
}运行结果
测试代码3
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;v.reserve(60);cout size: v.size() endl;cout capacity: v.capacity() endl;for (auto e : v){cout e ;}cout endl;v.resize(50, 6);for (auto e : v){cout e ;}cout endl;cout size: v.size() endl;cout capacity: v.capacity() endl;return 0;
}运行结果
六、元素访问接口(Element access)
1. operator[](size_t pos)
(1)const T operator[](size_t pos)
代码 T operator[](size_t pos){return _start[pos];}测试代码
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (size_t i 0; i v.size(); i){cout v[i] ;}cout endl;return 0;
}运行结果
(2)const T operator[](size_t pos) const
代码 const T operator[](size_t pos) const{return _start[pos];}测试代码
2. at(size_t pos)
(1)T at(size_t pos)
代码 T at(size_t pos){return _start[pos];}测试代码
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (size_t i 0; i v.size(); i){cout v.at(i) ;}cout endl;return 0;
}运行结果
3. front()
代码
// frontT front() const{return *_start;}4. back()
代码
// back()T back() const{return *(_finish - 1);}测试
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);cout front: v.front() endl;cout back: v.back() endl;
}运行结果
七、修改接口(Modifiers)
1. push_back(const T x)
代码
// 尾插void push_back(const T x){if (_finish _endofstorage){// 需要进行扩容reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}测试
// 测试尾插
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);hjt::vectorint::iterator vit v.begin();while (vit ! v.end()){cout *vit ;vit;}cout endl;cout v.size() endl;cout v.capacity() endl;for (auto e : v){cout e ;}cout endl;return 0;
}运行结果
2. pop_back()
代码
// 尾删void pop_back(){assert(_finish _start);_finish--;}测试代码
int main()
{hjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);hjt::vectorint::iterator vit v.begin();while (vit ! v.end()){cout *vit ;vit;}cout endl;v.pop_back();v.pop_back();v.pop_back();for (auto e : v){cout e ;}cout endl;return 0;
}运行结果 没有数据继续删除
3. iterator insert(iterator pos,T val T()))
在实现insert函数的时候需要注意迭代器的问题因为在实现insert的时候可能会进行扩容根据扩容的底层原理我们知道扩容之后的空间和扩容前的空间是不一样的扩容之后会将原来的空间进行释放而原来的迭代器指向的是原来空间的位置所以当原来空间释放之后原来的迭代器就变成了一个野指针也就是所谓的迭代器失效了此时如果再去访问原来的迭代器就是访问野指针程序就会崩溃。因此我们在实现insert的时候如果需要进行扩容则需要在扩容的时候将迭代器进行更新防止出现野指针。在使用insert函数的时候可能会出现迭代器意义变化的情况比如在123456中的偶数前插入20第一个偶数是2此时调用insert函数插入20之后会返回一个迭代器这个迭代器指向的是新插入的20而不是原来指向的2所以这种情况下调用insert函数之后需要更新迭代器的位置到当前位置的下一个位置这样才能够使迭代器保持原来的意义。
代码
// insert()iterator insert(iterator pos, T val T()){assert(pos _start pos _finish);if (_finish _endofstorage){// 扩容// 如果需要进行扩容注意更新迭代器否则会导致迭代器失效size_t n pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start n;}// 挪动数据iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}// 插入数据*pos val;_finish;return pos;}测试代码1
void test_vector4()
{// 测试inserthjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 头插10v.insert(v.begin(), 10);// 打印vfor (auto e : v){cout e ;}cout endl;// 在6前面插入10hjt::vectorint::iterator pos find(v.begin(), v.end(), 6);if (pos ! v.end()){// 找到了位置为:posv.insert(pos, 10);}// 打印vfor (auto e : v){cout e ;}cout endl;// 尾插10v.insert(v.end(), 10);// 打印vfor (auto e : v){cout e ;}cout endl;
}运行结果
测试代码2在偶数前插入66
void test_vector5()
{// 测试inserthjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 在偶数前面插入20hjt::vectorint::iterator vit v.begin();while (vit ! v.end()){if (*vit % 2 0){vit v.insert(vit, 20);vit;}vit;}// 打印vfor (auto e : v){cout e ;}cout endl;
}
}运行结果
4. iterator erase(iterator pos) 在删除函数中我们一般不考虑缩容方案所以一般不会出现野指针越界的问题但是很容易会发生迭代器的意义发生变化的问题。比如删除123456中所有的偶数的时候第一个偶数是2当删除2之后erase函数会返回一个迭代器这个迭代器指向的是删除元素的下一个位置在外面如果迭代器继续遍历下一个位置那么就会将之前删除元素的下一个元素跳过所以可能引发程序的逻辑异常。解决方案有两种 在遍历的过程中如果发生删除则迭代器不需要指向下一个位置erase函数已经更新没有发生删除时才指向下一个位置。在遍历的过程中无论是否发生删除每次都向前走一步但是如果发生删除迭代器需要先向后走一步。 代码
// eraseiterator erase(iterator pos){assert(pos _start pos _finish);// 挪动数据iterator begin pos 1;while (begin _finish){*(begin - 1) *begin;begin;}_finish--;return pos;}测试代码1
void test_vector6()
{// 测试erasehjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 头删v.erase(v.begin());// 打印vfor (auto e : v){cout e ;}cout endl;// 删除5hjt::vectorint::iterator pos find(v.begin(), v.end(), 5);if (pos ! v.end()){v.erase(pos);}// 打印vfor (auto e : v){cout e ;}cout endl;// 尾删v.erase(v.end() - 1);// 打印vfor (auto e : v){cout e ;}cout endl;
}
运行结果
测试代码2删除所有偶数
void test_vector7()
{// 测试erasehjt::vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);// 打印vfor (auto e : v){cout e ;}cout endl;// 删除所有偶数hjt::vectorint::iterator vit v.begin();while (vit ! v.end()){if (*vit % 2 0){vit v.erase(vit);vit--;}vit;}// 打印vfor (auto e : v){cout e ;}cout endl;
}运行结果
八、vector中更深层次的深浅拷贝问题
在学习vector中更深层次的深浅拷贝问题之前我们首先来学习一道经典的题目构造一个杨辉三角。
杨辉三角
题目 提交代码
class Solution {
public:vectorvectorint generate(int numRows) {// 确定容器vectorvectorint vv;// 确定容器的大小根据杨辉三角的行数进行确定vv.resize(numRows);// 根据杨辉三角的每一行中的元素个数确定容器中每个vector存放多少个intfor(size_t i 0;ivv.size();i){vv[i].resize(i1,0);}// 将每一行中的第一个元素和最后一个元素初始化成1for(size_t i 0;ivv.size();i){for(size_t j 0;jvv[i].size();j){if(j 0||j vv[i].size()-1){vv[i][j] 1;}}}// 处理不是1的元素for(size_t i 0;ivv.size();i){for(size_t j 0;jvv[i].size();j){if(vv[i][j]!1){vv[i][j] vv[i-1][j-1]vv[i-1][j];}}}return vv;}
};提交结果
解题思路 本题其实是需要一个二维数组所以我们采用vectorvector的类型的容器来存储杨辉三角。首先需要根据用户输入的杨辉三角的行数来确定容器的大小接下来根据杨辉三角每一行的元素个数确定vectorvector中的每一个vector存放多少个int这个过程使用一个for循环v.resize()进行开空间和初始化。接下来将每一行中的第一个元素和最后一个元素赋值成1最后处理最后其他元素。 对于vectorvector类型的遍历方法采用两重循环比如上面的二重循环中第一层循环第一次i 0,所以vv[i] vv[0]也就是找到vv中的第一个vector接下来进入第二层循环这个循环是从j 0开始知道jvv[i].size()结束也就是会将这个vector中的所有int类型的数据遍历完才会结束当第一个vector遍历结束时第一个内层for循环结束所以接下来i 1vv[i] vv[1]开始找到vv中的第二个vector重复上述过程。
当我们在VS中使用我们自己的vector的时候发生了下面现象
代码1构造一个5行的杨辉三角
class Solution {
public:hjt::vectorhjt::vectorint generate(int numRows) {// 确定容器hjt::vectorhjt::vectorint vv;// 确定容器的大小根据杨辉三角的行数进行确定vv.resize(numRows);// 根据杨辉三角的每一行中的元素个数确定容器中每个vector存放多少个intfor (size_t i 0; i vv.size(); i){vv[i].resize(i 1, 0);}// 将每一行中的第一个元素和最后一个元素初始化成1for (size_t i 0; i vv.size(); i){for (size_t j 0; j vv[i].size(); j){if (j 0 || j vv[i].size() - 1){vv[i][j] 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] ! 1){vv[i][j] vv[i - 1][j - 1] vv[i - 1][j];}}}return vv;}
};void test_vector8()
{hjt::vectorhjt::vectorint vv Solution().generate(5);for (auto e : vv){for (auto e1 : e){cout e1 ;}cout endl;}cout endl;}运行结果 分析结果通过上面的运行结果我们想要构造一个5行的杨辉三角结果前四行全部是随机值然后第五行是正常的。
代码2构造一个4行的杨辉三角
void test_vector9()
{hjt::vectorhjt::vectorint vv Solution().generate(4);for (auto e : vv){for (auto e1 : e){cout e1 ;}cout endl;}cout endl;}运行结果 分析当我们构造的是一个4行的杨辉三角时程序竟然能够正常给我们构造出来从4到5的区别就是需要一个扩容的过程显然需要vectorvector不需要进行扩容时程序就能够正常帮助我们构造出杨辉三角所以显然是我们实现的扩容函数中的逻辑出现问题。
通过仔细分析我们在扩容函数中拷贝原来空间中的数据到新空间时使用的是memcpy()函数memcpy()函数使用的是浅拷贝机制所以假如原来空间中有四个vector那么memcpy()函数就会将原来的四个vector中的_start,_finish,_endofstorage指针分别拷贝到新空间中对应的vector中的_start,_finish,_endofstorage所以原来的四个vector中的_start,_finish,_endofstorage指针和新空间中对应的vector中的_start,_finish,_endofstorage分别指向的是同一块空间的同一个位置在扩容的时候我们知道我们会将原来空间进行释放所以原来的数据将全部丢失对应的指针全部变成野指针所以就会出现上面的现象前四行的数据是随机值然后访问野指针的时候出现数组越界所以程序崩溃。 正确的处理方法实现深拷贝
扩容函数代码
void reserve(size_t n){if (n capacity()){// 需要进行扩容size_t sz size();// 需要先保存有效数据个数以便后面更新_finishiterator tmp new T[n];if (_start){for (size_t i 0; i size(); i){*(tmp i) *(_start i);}delete[] _start;}_start tmp;_finish _start sz;_endofstorage _start n;}}运行结果
