前言
在学习STL容器中,不仅需要学会容器的使用,同时也需要了解容器的大体框架以及各个函数的模拟实现才能更好的去了解这个容器;
杨辉三角
在LeetCode中有一道这样的题目,给定一个非负整数 numRow ,生成「杨辉三角」的前 numRows 行;
从图中可知杨辉三角的概念,即每一个数都是它上方左右两数的和,且整个三角形呈对称关系;
这题若是使用c语言的话可以直接用二维数组的思路进行作答;
//c int** generate(int numRows, int* returnSize, int** returnColumnSizes){ int** ret = malloc(sizeof(int*)*numRows); //申请返回的指针空间 *returnSize = numRows; //返回行数 *returnColumnSizes = malloc(sizeof(int*)*numRows); //为每一列分配空间 for(int i=0;i<numRows;i++) { ret[i] = malloc(sizeof(int)*(i+1)); //分配每一行的个数 (*returnColumnSizes)[i] = i + 1; //为第一个以及最后一个赋值 ret[i][0] = 1; ret[i][i] = 1; for(int j=1;j<i;j++) { ret[i][j] = ret[i-1][j-1] + ret[i-1][j]; } } return ret; }
若是使用C++的话则可以使用STL容器中的vector来模仿二维数组;
//c++ class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>>triangle(numRows); for(int i = 0;i<numRows;i++){ triangle[i].resize(i+1,0); triangle[i].front() = triangle[i].back() = 1; } for(int i = 0;i<numRows;i++){ for(int j = 0;j<triangle[i].size();j++){ if(triangle[i][j]!=1){ triangle[i][j] = triangle[i-1][j-1]+triangle[i-1][j]; } } } return triangle; } };
且其思路与C语言中的二维数组法相同;
深浅拷贝问题
在该篇文章中,我写出了对于类似拷贝构造或者扩容时应该进行的深浅拷贝;
在学过一段时间的C++后就能知道,在默认成员函数中存在拷贝构造函数以及赋值重载等函数;
这些默认成员函数在没有显式定义时,编译器会自动生成一个默认的对应函数;
而对于编译器自动生成的拷贝构造以及赋值重载函数,对于内置类型将会进行值拷贝,而对于自定义类型来说将会调用它的默认构造函数;
在这篇文章中对于类似扩容,拷贝构造以及赋值重载函数,采用的方法都是:
开辟一块新的空间,再将原先的数据使用memcpy函数或者在string中使用的strcpy函数拷贝到新的空间;
| 拷贝构造 |
//拷贝 My_string::string::string(const string& str) :_str(new char[str._size+1]) ,_size(str._size) ,_capacity(str._size) { memcpy(_str, str._str,str._size); _str[_size] = '\0'; }
| 扩容 |
//扩容 void My_string::string::reserve(size_t n) { if (n > _capacity) { char* temp = new char[n+1];//多开1的空间确保n为有效数据的空间而+1为给'\0'的无效空间 strcpy(temp, _str); _capacity = n; delete[]_str; _str = temp; } }
| 赋值重载 |
My_string::string& My_string::string::operator=(const string& str)//赋值操作符重载 { if (this != &str) { char* temp = new char[str._capacity+1]; strcpy(temp, str._str); delete[]_str; _str = temp; _size = str._size; _capacity = str._capacity; } return *this; }
模拟实现的vector对题目杨辉三角引发的程序崩溃
同时,我模拟实现了一个vector容器,这个容器的完成程度暂且不提,在这里的拷贝构造函数,扩容以及赋值重载依旧按照模拟实现string那样使用memcpy进行原数据拷贝到新空间的方法;
//拷贝构造 vector(const vector<T>&v){ T* tmp = new T[v.size()]; _start = tmp; memcpy(tmp,v._start,sizeof(T)*v.size()); _finish = _end_of_storage = _start + v.size(); } /*扩容reserve*/ void reserve(size_t n){ if(n>capacity()){ size_t count = size(); T* tmp = new T[n]; memcpy(tmp,_start,sizeof(T)*count); delete[]_start; _start = tmp; _finish = _start+count; _end_of_storage = _start+n; } }
而使用这种方法对杨辉三角题目进行测试时,程序将崩溃;
而程序崩溃的原因为析构函数;
原因
当程序在析构函数处崩溃且析构函数并没有其他问题的时候,应该及时将问题的思路转变到对象的深浅拷贝问题;
而这里出的错误正是使用memcpy函数进行拷贝从而造成的浅拷贝;
那为什么在这里使用memcpy时将会造成浅拷贝;
在模拟这些成员函数中,一般优先会想到的类型为内置类型,即语言标准指定,编译器自带的类型;
如果为vector< int >,vector< char >将可以使用memcpy进行拷贝;
但是vector这类的容器为一种类模板,对于类模板来说,其给的模板参数不一定一定就是内置类型,也有可能出现自定义类型;
就如使用vector< vector< int > >来说,最外层的模板参数为一个自定义类型,而内层的模板参数为一个内置类型int;
而如果在这里使用了memcpy进行原数据到新空间的拷贝将会怎么做;
表面上这里进行了拷贝,但实际上,进行了深拷贝的只有最外层;
对于内层而言只是使用了memcpy将对应的对象进行拷贝;
也就是说,这里出现了指针指向同一块空间的问题;
而若是在这种情况下则会出现重复析构的问题;
解决办法
在这种情况下只能摒弃以往的使用memcpy进行数据拷贝,并使用赋值进行拷贝;
以拷贝构造为例:
vector(const vector<T>& v){ _start = new T[v.size()]; for(size_t i = 0;i<v.size();++i){ _start[i] = v._start[i];//若是自定义类型将会去调用它的赋值重载 } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
