【C++】模拟实现vector

在上篇中我们已经了解过的vector各种接口的功能使用,接下来我们就试着模拟实现一下吧!

注意:我们在此实现的和C++标准库中实现的有所不同,其目的主要是帮助大家大概理解底层原理。

我们模拟vector容器的大致框架是:

template<class T>
class vector
{
public:typedef T* iterator;  //普通迭代器typedef const T* const_iterator; //const迭代器//...
private:iterator _start = nullptr; //指向容器起始位置(第一个有效数据)iterator _finish = nullptr;	 //指向容器最后一个有效数据的下一个位置iterator _end_of_storage = nullptr; //指向容器所开空间的最后一个位置的下一个位置
};

注意这里要与string类进行区别,我们在模拟string类时它有3个成员变量,其中,2个内置类型分别表示数据个数和容量大小,还有1个指针,指向空间起始位置,在这里我们换成了3个指针,它可以间接表示数据个数和容量大小,它和之前写的差别不大,只是形式上略有不同。

inerator是参数模板T类型的指针,容器中数据元素的类型是T。

我们本篇以实现为主,不再细讲各个函数功能介绍。

如果大家对各个成员函数还不太了解其功能时,可以去先看一下这篇文章->vector容器的基本使用

一、成员函数

1、size()

//返回vector容器元素个数
size_t size() const
{return _finish - _start;
}

2、capacity()

//返回vector容器容量大小
size_t capacity() const
{return _end_of_storage - _start;
}

3、empty()

//判断容器中元素是否为空,若为空返回true,否则返回false
bool empty()
{return _start == _finish;
}

4、clear()

//清空容器中的数据,容量不变
void clear()
{_finish = _start;
}

4、operator[]

//返回下标为i位置上的值
T& operator[](size_t i)
{assert(i < size());  //若i>=size(),说明越界了,程序就会发生断言错误return _start[i]; 
}

 空间是在堆上开辟的,所以可以传引用返回,传引用范围的目的是:(1)若T是自定义类型就可以减少一次拷贝构造。(2)方便我们修改对应下标的值。

如果对象被const修饰,也就是禁止修改对应的值,我们可以再写一个重载函数:

const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

5、reserve()

//预留n个元素的空间
void reserve(size_t n)
{if (n > capacity()){//扩容T* tmp = new T[n]; //新开一段空间memcpy(tmp, _start, sizeof(T) * size()); //旧空间的值赋给新空间delete[] _start; //释放旧空间_start = tmp;  //获得新空间_finish = _start + size();  //改变_finish_end_of_storage = _start + n; //改变_end_of_storage}
}

当n大于capacity时,我们将扩容,当n小于capacity时,C++标准明确不缩容,所以我们什么也不做。 

扩容的逻辑就是新开一段空间,将原有的空间中的值拷贝给新空间,然后释放旧的空间,将我们新开的空间作为现在的空间。

6、resize()

//改变元素个数
void resize(size_t n, T val = T())
{if (n < size()) //如果n小于size()就更新_finish{_finish = _start + n;}else  //否则就需要扩容{reserve(n); //reserve会检查,大于capacity才会扩容,如果扩容,不多扩,要多大给多大while (_finish < _start + n){*_finish = val; //初始化新添加的元素值为val++_finish; }}
}

一些函数参数有缺省值,但在此之前见到的缺省值一般都是内置类型,这里却不同,因为在模板被调用之前T的类型是未知的,它有可能是自定义类型,若是自定义类型,就不能单纯的给内置类型的缺省值,所以我们这里给的是T类型的默认构造参数。

那如果T是内置类型,这样行吗?内置类型也有构造函数?

我们暂且可以认为内置类型有构造函数,我们可以看几个例子:

int main()
{int a = int();int b = int(1);int c(10);cout << "a:" << a << endl;cout << "b:" << b << endl;cout << "c:" << c << endl;return 0;
}

运行结果: 

从代码的写法风格和结果上,我们可以认为内置类型有构造函数。 

利用resize我们可以直接初始化:

vector<int> v;
v.resize(10,1);  //初始化为10个1

 我们写一段代码来测试一下:
在主函数中调用test_vector0():

void test_vector0()
{vector<int> v;v.resize(10, 1);print_container(v);v.reserve(20); //初始空间给20cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//1、size() < n < capacity()v.resize(15, 2);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//2、n > capacity()v.resize(30, 100);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//3、n < size()v.resize(5);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;
}

运行结果: 

这里的print_container()是我们自己写的通用容器的打印方法,大家在下面的9(3)可以看到。

7、push_back()

它的功能是在尾部插入一个元素。

//尾插,在最后一个有效元素后插入一个新元素
void push_back(const T& x)
{if (_finish == _end_of_storage){//扩容reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

插入前,先判断需不需要扩容,若需要就先扩容,之后再进行尾插并更新_finish指针。

我们写完了尾插可以先测试一下,看看功能是否正确:

在主函数中调用test_vector1():

void test_vector1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0;i < v.size();++i)cout << v[i] << " ";
}

运行结果: 

程序崩溃了,这是什么原因导致的呢?

在插入数据时,首先要判断是否扩容,我们首次尾插,_strat和_finish是相同的,所以要扩容。问题就出在这扩容上。经过调试:

我们发现,扩容后_finish竟然还是空指针,那一会插入数据必然报错,空指针不可以解引用的。

所以,问题的根本是在_finish = _start + size();这行代码。_start因该是没问题的,它不再是空指针了,而是一个新的值,最终定位,问题出在size()上。

此时的size()中,_finish是扩容前的,_start是扩容后的,而_finish = _start + size()中的_strat也是扩容后的,所以抵消掉就是_finish = _finish,扩容前的_finish我们默认给的就是nullptr。所以问题出在这里。

我们可以对reserve()进行简单的修改:

void reserve(size_t n)
{if (n > capacity()){//扩容T* tmp = new T[n]; //新开一段空间memcpy(tmp, _start, sizeof(T) * size()); //旧空间的值赋给新空间delete[] _start; //释放旧空间_finish = tmp + size();  //先修改_finish_start = tmp;  //再修改_start_end_of_storage = _start + n; //改变_end_of_storage}
}

这样size()中的_finish和_start都是扩容前的了,这样就解决了问题。但不难免有些人会感觉看着别扭,万一有些人有强迫症,就要先写_start = tmp 再写  _finish = tmp + size(); 那程序就还是会崩溃。有没有方法既可以看着舒服,又可以使程序正常运行呢?

答案是有的。

void reserve(size_t n)
{ if (n > capacity()){size_t old_size = size(); //扩容前先记录数据个数//扩容T* tmp = new T[n]; //新开一段空间memcpy(tmp, _start, sizeof(T) * old_size); //旧空间的值赋给新空间delete[] _start; //释放旧空间//都用tmp,这样可以随便调整它们3个的位置_start = tmp;  //获得新空间_finish = tmp + old_size;  //改变_finish_end_of_storage = tmp + n; //改变_end_of_storage}
}

我们在扩容前,定义一个old_size就解决问题啦,它用于记录扩容前数据个数。

8、pop_back()

//尾删,删除最后一个有效元素
void pop_back()
{assert(!empty());--_finish;
}

9、迭代器

(1)begin()

普通迭代器:

iterator begin()
{return _start;
}

const迭代器:

const_iterator begin() const
{return _start;
}
(2)end()

普通迭代器:

iterator end()
{return _finish;
}

const迭代器:

const_iterator end() const
{return _finish;
}
 (3)print_container()

我们在类外面来写一个通用的,打印容器中数据的函数。

template<class Container>
void print_container(const Container& v)
{//vector<T>::const_iterator表达含义不清淅,这种写法既可以将const_iterator看作静态成员变量,也可以将它看作类型//规定--不能在没有实例化的类模板里面取东西。因为编译器不能区分这里的//const_iterator是类型还是静态成员变量,如果不加typename在语法上就会报错//如果加了typename编译器就知道了这是类型而不是静态成员变量,编译器认为在语法上没问题,所以不会报错//typename Container::const_iterator it = v.begin();auto it = v.begin(); //简单起见,我们可以直接用auto来让编译器自动帮我们识别类型while (it != v.end()){cout << *it << " ";++it;}cout << endl;//for(auto e : v)//{//	cout << e << " ";//}//cout << endl;
}

我们知道,编译器在编译代码时是从上到下进行编译的,当编译到 print_container这个函数模板时,类模板还没有实例化,如果贸然从中取到东西,就可能导致出现许多问题,就比如这里的const_iterator,所以我们规定不要在没有实例化的类模板里面取东西,这里我们明确知道了const_iterator是一个类型名,要想在语法上过的去,就必须加上typename关键字。

假设这里的const_iterator是静态成员变量,那么编译器只会认为你加了typename,是个类型,it的类型是const_iterator,这样定义语法上不会出错,别的它可就不管啦。但实际上语法虽然可以通过,但const_iterator是静态成员变量,运行时绝对会出问题的。

如果它本身就是静态成员变量,我们可以不加typename,因为静态变量我们在书写时就不会以这种方式去写vector<T>::const_iterator  it。

如果不加typename,编译器就会按照静态成员变量去识别了。

10、insert()

//在pos位置前插入新元素x
void insert(iterator pos,const T& x)
{//判断是否需要扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}//end指向最后一个有效数据的位置iterator end = _finish - 1;while (end >= pos)  //依次挪动数据{*(end + 1) = *end;--end;}*pos = x;  //pos位置上赋值++_finish; //更新_finish
}

代码写起来很容易,那我们来测试一下:

在主函数中调用test_vector2():

void test_vector2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_container(v);//在下标为0的位置上插入100v.insert(v.begin() + 0, 100);print_container(v);
}

运行结果: 

结果没有任何问题。 

在这段代码中,我们在push_back之前,容量是4,而我们插入了5个数据,所以会扩容,在扩容后,我们调用insert进行插入数据,运行结果也没有任何问题。

接下来我们修改一下测试代码:

void test_vector2()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_container(v);//在下标为0的位置上插入100v.insert(v.begin() + 0, 100);print_container(v);
}

我将这段代码的第5个push_back给注释了,其目的是在调用insert时再扩容,看看会发生什么情况?

运行结果: 

这段代码已经崩了。

这里就出现了问题,而这个问题就是迭代器失效

我们来分析一下,我们让insert插入时扩容,就导致了问题,画个图让大家能更好的理解:

扩容后,原先的空间就被释放了,但pos指向的还是原来空间的位置, 在insert中依次挪动数据时就会导致出现问题,这就是迭代器失效的一个例子,此时的pos就是野指针。

为了解决这个问题,我们可以在扩容之前记录一下pos与_satrt的相对位置,扩容后,再更新pos。

void insert(iterator pos,const T& x)
{if (_finish == _end_of_storage){size_t len = pos - _start; //记录相对位置reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len; //更新pos}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

运行结果:

这样就解决了问题。

我们接下来再来实现一个小功能:

输入一个值,然后用查找算法看看这个值是否在vector中存在。

在主函数中调用test_vector3():

void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);int x;cin >> x;auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找if (p != v.end()){v.insert(p, 2000); //如果找到,就在该位置上插入2000print_container(v);}else{cout << "不存在:" << x << endl;}
}

其中,find是定义在<algorithm>这个头文件中的,它是一个函数模板,支持所有容器在一段区间中查找相应元素。它大概是这样的:

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{while (first!=last) {if (*first==val) return first;++first;}return last;
}

它是在[first,last)这个区间去找val,注意是左闭右开。

 test_vector3()运行结果:

我们输入的x值为3,结果并没有任何错误。

现在,我们让查找到的pos位置上的值乘100:

void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_container(v);int x;cin >> x;auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找if (p != v.end()){v.insert(p, 2000); //如果找到,就在该位置上插入2000(*p) *= 100;print_container(v);}else{cout << "不存在:" << x << endl;}
}

运行结果: 

我们本意是让3乘以100,而不是让2000乘以100,这也是一种迭代器失效。p的意义发生了改变,它的本意是指向3,然而插入了2000,它的指向由3变为2000,这时对p指向的数据进行操作就会发生迭代器失效。虽然语法上没有报错,但它也是迭代器失效的一种情况。 这在vs2019下调用标准库中的vector会进行强制检查,若访问失效的迭代器就会报错。这种不扩容的场景,在Linux(g++)下不会报错。

那如果我将第5个push_back给注释呢?

void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_container(v);int x;cin >> x;auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找if (p != v.end()){v.insert(p, 2000); //如果找到,就在该位置上插入2000(*p) *= 100;print_container(v);}else{cout << "不存在:" << x << endl;}
}

 运行结果:

发现这时2000也没有乘100,这就奇了怪了?

我们把第5个push_back注释掉的结果是在调用insert时扩容。我们传的第一个参数p,reserve进行接收,但形参改变不会影响实参,在reserve内部,pos(形参)确实是更新了,但外部的p(实参)却不会更新,所以在一块被释放的空间上进行操作是没用的,也就是2000还是2000,它不会乘100。

有人可能就会想,insert函数的第一个参数改为引用不就行了?这是不行的,我们在调用insert时传的第一个参数是临时变量(p),临时变量具有常性,如果insert函数的第一个参数(pos)是引用,那就是典型的权限放大,那如果再加一个const呢(const iterator& pos )?那也不行,如果insert中要更新pos,那就不能加const。

实际中,我们调用insert后,到底扩不扩容是不清楚的,所以尽量不要对p"动手脚"。

在扩容的情况下,Linux也不会报错。

总结一下:insert后p就失效了,不要访问!

当然,也可以有另外一种处理方式,就是将pos作为返回值:

iterator insert(iterator pos, const T& x)
{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 = x;++_finish;return pos;
}

修改测试代码:

void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);int x;cin >> x;auto p = std::find(v.begin(), v.end(), x);if (p != v.end()){//insert后p就失效,不要直接访问,要访问就要更新这个失效的迭代器的值p = v.insert(p, 2000); //更新p(*(p + 1)) *= 100;print_container(v);}else{cout << "不存在:" << x << endl;}
}

运行结果:

这样就可以解决问题了。 

11、erase()

通常情况下,删除数据后,容量是不会变的。

//删除pos位置上的数据
void erase(iterator pos)
{assert(pos >= _start && pos < _finish);auto it = pos + 1; //记录要删除位置的下一位置while (it != end()) //依次覆盖{*(it - 1) = *it;++it;}--_finish;  //更新_finish
}

删除pos位置上的数据后,pos的意义发生了改变,这也是迭代器失效。

我们来测试一下:

在主函数中调用test_vector4():

void test_vector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print_container(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it; //it的意义发生了改变}print_container(v);
}

运行结果: 

从结果上看,满足了要求。

修改一下测试代码:

void test_vector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(4); //多插入一个4v.push_back(5);print_container(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}print_container(v);
}

再看运行结果: 

没删除干净? 

这很容易理解,我们在删除一个偶数后,会++it,如果我们删除的偶数后面紧跟着一个偶数,在删除第一个偶数的时候,所有数据往前挪,那么第一个偶数的位置就会被第二个偶数所取代,这时++it,就会跳过对第二个偶数的判断,导致漏删。

这段代码还会出现一个问题:

如果最后一个数是偶数的话,erase在删除数据时,会--_finish,删除后,在测试代码中的while循环中还会++it,然后进行while循环条件判断,发现条件为真(这时就出问题了),此时如果if条件为假就是死循环,如果if条件为真,调用erase就会发生断言错误。

在Linux下,运行该代码时,它会和我们产生一样的效果。如果在vs2019下,这3种情况都跑不通。 

这里如果解决迭代器失效带来的问题,我们可以把删除位置的下一位置作为返回值进行返回:

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

修改测试代码: 

void test_vector4()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it); //用返回值更新itelse++it; //加一个else,这样就能删除干净,且不会发生最后一个是偶数时程序报错的问题。}print_container(v);
}

运行结果: 

这样就可以解决问题啦。

二、析构函数

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

三、拷贝构造

 抛弃以往的写法,我们现在换一种写法:

vector(const vector<T>& v)
{reserve(v.capacity()); //提前开好空间,就不需要频繁扩容了for (const auto& e : v)push_back(e);
}

这里的v有可能是自定义类型,所以我在范围for中加了一个引用,防止多次构造,我们这里只是赋值,不修改,所以又加了一个const。

我们来测试一下:

在主函数中调用test_vector5():

void test_vector5()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);vector<int> v2 = v1; //拷贝构造print_container(v2);
}

运行结果: 

四、赋值重载

1、传统写法

vector<T>& operator=(const vector<T>& v)
{if (this != &v){//方式1clear();reserve(v.capacity());for (const auto& e : v)push_back(e);//方式2//delete[] _start;//_start = new T[v.capacity()];//memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();}return *this;
}

2、现代写法

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)  //这里不能用引用,假设v1 = v2,我们不能改变v2
{swap(v);return *this;
}

额外说明一点,在类中,类名可以替代类型。比如:

vector<int> 可以直接写成 vector

我们写一段代码测试一下: 

在主函数中调用test_vector6():

void test_vector6()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);cout << v1.size() << endl;cout << v1.capacity() << endl;vector<int> v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);print_container(v3);	cout << v3.size() << endl;cout << v3.capacity() << endl;v1 = v3;print_container(v1);cout << v1.size() << endl;cout << v1.capacity() << endl;
}

运行结果: 

 五、构造函数

1、默认构造

vector(){}

虽然我们只写了框架,没有实质内容,但编译器依然会去走初始化列表,用缺省值进行初始化。

在C++11中,还有另外一种表示方法:

//C++11 强制生成默认构造
vector() = default;

 2、迭代器区间构造(通用)

注意:类模板中还可以定义函数模板。

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

我们将它定义为函数模板的好处是,它不仅可以用vector容器类型的迭代器区间初始化,还可以用其他类型容器的迭代器区间初始化,提高了复用性。 但有一个要求是类型需要匹配,比如我这个容器是vector里面数据类型是int,你传过来的容器是list里面的数据类型是string,这是不匹配的。要保证传过来的容器中的数据类型是int,或者能隐式类型转换为int。

我们写一段代码测试一下迭代器区间初始化:

在主函数中调用test_vector7():

void test_vector7()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);//用迭代器区间初始化,从下标为1的位置开始到下标为2的位置结束(左闭右开)vector<int> v2(v1.begin() + 1, v1.begin() + 3);print_container(v2);
}

运行结果: 

3、用n个m初始化

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

我们来测试一下:

在主函数中调用test_vector8():

void test_vector8()
{//用n个m初始化vector<string> v1(10, "1111111");print_container(v1);vector<int> v2(10);print_container(v2);
}

运行结果: 

运行结果没有任何问题。

我们修改一下测试数据:

void test_vector8()
{vector<int> v3(10, 1);print_container(v3);
}

运行结果: 

这里会报错,非法的间接寻址。 它这里是匹配到迭代器区间构造上了,将InputIterator推导为int类型,它里面中的while循环里的*first是对int类型解引用,所以会产生非法间接寻址。

原因是,编译器在处理时只会找最匹配的函数进行调用,我们传的是10和1,它们的默认类型是int,调用函数模板时推出两个InputIterator都为int,挺合适的,我传的是int类型,如果调用vector(size_t n, const T& val = T())这个函数,那么我还需要隐式转换一下(将int转换为size_t),这没第一种舒服,所以编译器去调用了函数模板,这就导致出现了问题。

解决方法1:

void test_vector8()
{vector<int> v3(10u, 1);print_container(v3);
}

在参数10后面添加一个u,代表无符号整形(size_t)。

解决方法2:

修改构造函数,将第一个参数指定为int类型:

vector(int n, const T& val = T()) //第一个参数指定为int类型
{reserve(n);for (int i = 0;i < n;++i){push_back(val);}
}

六、浅拷贝问题

我们先来看一段代码:

void test_vector9()
{vector<string> v;v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");print_container(v);
}

在主函数中调用test_vector9()运行结果:

结果没问题,正常打印。

现在我们修改一下测试代码的内容:

void test_vector9()
{vector<string> v;v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");print_container(v);v.push_back("11111111111111111");print_container(v);
}

再看运行结果: 

结果出现乱码了,这可不是我们期望的结果。 

我们在添加第5个push_back时出现了问题,说明问题出现在扩容的地方。其实是memset这里出现了问题,我画个图来帮助大家理解:

扩容前:

扩容后:

在reserve函数中,当值复制拷贝完后,要对原来的空间(_start)进行释放,问题就出在释放身上,我们使用memcpy拷贝时,memcpy是一个字节一个字节的进行拷贝(浅拷贝),每个string中都有一个指针,指向对应的空间,memcpy拷贝给tmp时,tmp中的每个string中的指针跟旧的空间(_start)中每个string中的指针一模一样(一个字节一个字节),所以当释放旧的空间(_start)时,tmp中的string中的指针指向的空间也被释放了,这就导致了问题所在,即打印乱码。

大致就是这样一张图(画的不太好,见谅):

总结:

  1.  memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。

  2.  如果拷贝的是内置类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因memcpy是浅拷贝,可能会引起内存泄漏和程序崩溃。

 如何解决这种浅拷贝带来问题呢?

当然是用深拷贝啦,请看代码:

void reserve(size_t n)
{ if (n > capacity()){size_t old_size = size(); //扩容前先记录数据个数//扩容T* tmp = new T[n]; //新开一段空间//用for循环进行深拷贝for (size_t i = 0;i < old_size;++i){tmp[i] = _start[i];  //赋值重载,如果是内置类型也可以直接赋值}delete[] _start; //释放旧空间_start = tmp;  //获得新空间_finish = _start + old_size;  //改变_finish_end_of_storage = _start + n; //改变_end_of_storage}
}

七、源码

 1、vector.h

#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
#include <vector>
#include <string>
using namespace std;namespace blue
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//拷贝构造vector(const vector<T>& v){reserve(v.capacity());for (const auto& e : v)push_back(e);}//赋值重载,方式1//vector<T>& operator=(const vector<T>& v)//{//	if (this != &v)//	{//		//方式1//		clear();//		reserve(v.capacity());//		for (const auto& e : v)//			push_back(e);//		//方式2//		//delete[] _start;//		//_start = new T[v.capacity()];//		//memcpy(_start, v._start, sizeof(T) * v.size());//		_finish = _start + v.size();//		_end_of_storage = _start + v.capacity();//	}//	return *this;//}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}//赋值重载,方式2//vector<T>& operator=(vector<T> v)//在类里面可以用类名替代类型vector& operator=(vector v){swap(v);return *this;}//默认构造//vector()//{}//C++11 强制生成默认构造vector() = default;//迭代器区间构造//类模板的成员函数还可以继续是函数模板template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//用n个m初始化构造,方式1(弃)/*vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0;i < n;++i){push_back(val);}}*///用n个m初始化构造,方式2vector(int n, const T& val = T()){reserve(n);for (int i = 0;i < n;++i){push_back(val);}}//返回vector容器元素个数size_t size() const{return _finish - _start;}//返回vector容器容量大小size_t capacity() const{return _end_of_storage - _start;}//判断容器中元素是否为空,若为空返回true,否则返回falsebool empty(){return _start == _finish;}//清空容器中的数据,容量不变void clear(){_finish = _start;}//返回下标为i位置上的值T& operator[](size_t i){assert(i < size());  //若i>=size(),说明越界了,程序就会发生断言错误return _start[i];}void reserve(size_t n){ if (n > capacity()){size_t old_size = size(); //扩容前先记录数据个数//扩容T* tmp = new T[n]; //新开一段空间//memcpy(tmp, _start, sizeof(T) * old_size); //旧空间的值赋给新空间for (size_t i = 0;i < old_size;++i){tmp[i] = _start[i];}delete[] _start; //释放旧空间_start = tmp;  //获得新空间_finish = _start + old_size;  //改变_finish_end_of_storage = _start + n; //改变_end_of_storage}}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}}//尾插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;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//void insert(iterator pos,const T& x)//{//	if (_finish == _end_of_storage)//	{//		size_t len = pos - _start; //记录相对位置//		reserve(capacity() == 0 ? 4 : capacity() * 2);//		pos = _start + len; //更新pos//	}//	iterator end = _finish - 1;//	while (end >= pos)//	{//		*(end + 1) = *end;//		--end;//	}//	*pos = x;//	++_finish;//}iterator insert(iterator pos, const T& x){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 = x;++_finish;return pos;}/*void erase(iterator pos){assert(pos >= _start && pos < _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;}*/iterator erase(iterator pos){assert(pos >= _start && pos < _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};//通用的,打印容器中数据template<class Container>void print_container(const Container& v){//规定--不能在没有实例化的类模板里面取东西,因为编译器不能区分这里的const_iterator是类型还是静态成员变量,如果加了typename编译器就知道了这是类型而不是静态成员变量,所以编译器认为语法上没问题,所以不会报错 //typename Container::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;/*for(auto e : v){cout << e << " ";}cout << endl;*/}void test_vector0(){vector<int> v;v.resize(10, 1);print_container(v);v.reserve(20); //初始空间给20cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//1、size() < n < capacity()v.resize(15, 2);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//2、n > capacity()v.resize(30, 100);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;cout << "------------------" << endl;//3、n < size()v.resize(5);print_container(v);cout << v.size() << endl;cout << v.capacity() << endl;}void test_vector1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i = 0;i < v.size();++i)cout << v[i] << " ";}//void test_vector2()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	v.push_back(5);//	print_container(v);//	//在下标为0的位置上插入100//	v.insert(v.begin() + 0, 100);//	print_container(v);//}void test_vector2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);//v.push_back(5);print_container(v);//在下标为0的位置上插入100v.insert(v.begin() + 0, 100);print_container(v);}//void test_vector3()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	print_container(v);//	int x;//	cin >> x;//	auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找//	if (p != v.end())//	{//		v.insert(p, 2000); //如果找到,就在该位置上插入2000//		print_container(v);//	}//	else//	{//		cout << "不存在:" << x << endl;//	}//}//void test_vector3()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	v.push_back(5);//	print_container(v);//	int x;//	cin >> x;//	auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找//	if (p != v.end())//	{//		v.insert(p, 2000); //如果找到,就在该位置上插入2000//		(*p) *= 100;//		print_container(v);//	}//	else//	{//		cout << "不存在:" << x << endl;//	}//}//void test_vector3()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	//v.push_back(5);//	print_container(v);//	int x;//	cin >> x;//	auto p = std::find(v.begin(), v.end(), x); //利用库中的find函数在两个迭代区间进行查找//	if (p != v.end())//	{//		v.insert(p, 2000); //如果找到,就在该位置上插入2000//		(*p) *= 100;//		print_container(v);//	}//	else//	{//		cout << "不存在:" << x << endl;//	}//}void test_vector3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);int x;cin >> x;auto p = std::find(v.begin(), v.end(), x);if (p != v.end()){//insert后p就失效,不要直接访问,要访问就要更新这个失效的迭代器的值p = v.insert(p, 2000); //更新p(*(p + 1)) *= 100;print_container(v);}else{cout << "不存在:" << x << endl;}}//void test_vector4()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	v.push_back(5);//	print_container(v);//	//删除所有的偶数//	auto it = v.begin();//	while (it != v.end())//	{//		if (*it % 2 == 0)//			v.erase(it);//		++it; //it的意义发生了改变//	}//	print_container(v);//}//void test_vector4()//{//	vector<int> v;//	v.push_back(1);//	v.push_back(2);//	v.push_back(3);//	v.push_back(4);//	v.push_back(4); //多插入一个4//	v.push_back(5);//	print_container(v);//	//删除所有的偶数//	auto it = v.begin();//	while (it != v.end())//	{//		if (*it % 2 == 0)//			v.erase(it);//		++it;//	}//	print_container(v);//}void test_vector4(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(3);v.push_back(4);print_container(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0)it = v.erase(it); //用返回值更新itelse++it; //加一个else,这样就能删除干净,且不会发生最后一个是偶数时程序报错的问题。}print_container(v);}void test_vector5(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);vector<int> v2 = v1; //拷贝构造print_container(v2);}void test_vector6(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);cout << v1.size() << endl;cout << v1.capacity() << endl;vector<int> v3;v3.push_back(10);v3.push_back(20);v3.push_back(30);print_container(v3);cout << v3.size() << endl;cout << v3.capacity() << endl;v1 = v3;print_container(v1);cout << v1.size() << endl;cout << v1.capacity() << endl;}void test_vector7(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);print_container(v1);//用迭代器区间初始化,从下标为1的位置开始到下标为2的位置结束(左闭右开)vector<int> v2(v1.begin() + 1, v1.begin() + 3);print_container(v2);}//void test_vector8()//{//	//用n个m初始化//	vector<string> v1(10, "1111111");//	print_container(v1);//	vector<int> v2(10);//	print_container(v2);//}//void test_vector8()//{//	vector<int> v3(10, 1);//	print_container(v3);//}void test_vector8(){vector<int> v3(10u, 1);print_container(v3);}//void test_vector9()//{//	vector<string> v;//	v.push_back("11111111111111111");//	v.push_back("11111111111111111");//	v.push_back("11111111111111111");//	v.push_back("11111111111111111");//	print_container(v);//}void test_vector9(){vector<string> v;v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");v.push_back("11111111111111111");print_container(v);v.push_back("11111111111111111");print_container(v);}}

2、Test.h

#include "vector.h"int main()
{	//blue::test_vector0();//blue::test_vector1();//blue::test_vector2();//blue::test_vector3();//blue::test_vector4();//blue::test_vector5();//blue::test_vector6();//blue::test_vector7();//blue::test_vector8();//blue::test_vector9();return 0;
}

这里用了一个命名空间blue其目的是为了防止和C++标准库中的vector发生冲突,在类模板中的大型函数可以在类内声明类外定义(这里没有分开),小型函数可以直接在类内定义。

八、结语

本篇到这里就结束了,主要讲了vector是怎么模拟实现的,希望对大家有些许帮助,祝大家天天开心!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/426571.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java入门程序-HelloWorld

Java程序开发的三个步骤 1.编写代码得到 .java 源代码文件 2.使用javac编译得到 .class 字节码文件 3.使用java运行 注意事项 建议代码文件名全英文&#xff0c;首字母大写&#xff0c;满足驼峰命名法&#xff0c;源代码文件的后缀必须是.java 开发HelloWorld程序 &…

进程的属性

tips&#xff1a; task_struct就是linux下的PCB 操作系统不相信任何外部用户&#xff0c;而是只提供窗口&#xff0c;不可能直接与用户打交道&#xff0c;而是通过操作系统 tast_struct用来描述所有进程&#xff0c;用来管理 &#xff1b; 和 && 可以同时跑两个命令 进…

AI修手有救了?在comfyui中使用Flux模型实现局部重绘案例

&#x1f431;‍&#x1f409;背景 局部重绘相关的话题我们已经讨论和测试过很多次了&#xff0c;比如说inpaint模型、brushnet模型、powerpaint模型等等&#xff0c;最近对于flux模型重绘画面的案例也越来越多了&#xff0c;那我们就结合flux模型的重绘来试试看效果。 &…

高级大数据开发协会

知识星球——高级大数据开发协会 协会内容: 教你参与开源项目提供新技术学习指导提供工作遇到的疑难问题技术支持参与大数据开源软件源码提升优化以互利共赢为原则&#xff0c;推动大数据技术发展探讨大数据职业发展和规划共享企业实际工作经验 感兴趣的私聊我&#xff0c;…

『功能项目』窗口可拖拽脚本【59】

本章项目成果展示 我们打开上一篇58第三职业弓弩的平A的项目&#xff0c; 本章要做的事情是给坐骑界面挂载一个脚本让其显示出来的时候可以进行拖拽 创建脚本&#xff1a;DraggableWindow.cs using UnityEngine; using UnityEngine.EventSystems; public class DraggableWindo…

linux网络编程2

24.9.18学习目录 一.数据包的传送1.数据包在每层间的传送2.链路层的封包3.网络层、传输层封包格式 二.字节序1.概念2.字节序转换函数 三.IP地址转换四.UDP1.概述2.网络编程接口socket3.UDP的C/S架构4.UDP编程 一.数据包的传送 1.数据包在每层间的传送 传送方数据从运用层到链…

MySQL之内置函数

目录 一&#xff1a;日期函数 二:字符串函数 三&#xff1a;数学函数 四&#xff1a;其他函数 一&#xff1a;日期函数 举例: (1) mysql> select current_date(); ---------------- | current_date() | ---------------- | 2024-09-17 | ---------------- 1 row …

# 利刃出鞘_Tomcat 核心原理解析(十一)-- Tomcat 附加功能 WebSocket -- 3

利刃出鞘_Tomcat 核心原理解析&#xff08;十一&#xff09;-- Tomcat 附加功能 WebSocket – 3 一、Tomcat专题 - WebSocket - 案例 - OnMessage分析 1、WebSocket DEMO 案例 实现流程分析&#xff1a;OnMessage 分析 2、在项目 dzs168_chat_room 中&#xff0c;在 websocke…

CSP-CCF★★★201903-2二十四点★★★

目录 一、问题描述 二、解答 方法一&#xff1a;穷举法&#xff08;只列举了一部分&#xff09; 方法二&#xff1a;中缀表达式直接求值&#xff0c;两个栈&#xff0c;一个存放数值&#xff0c;一个存放符号 方法三&#xff1a;将中缀表达式转换为后缀来计算注意&#xff…

SpringBoot2:web开发常用功能实现及原理解析-@ControllerAdvice实现全局异常统一处理

文章目录 前言1、工程包结构2、POM依赖3、Java代码 前言 本篇主要针对前后端分离的项目&#xff0c;做的一个统一响应包装、统一异常捕获处理。 在Spring里&#xff0c;我们可以使用ControllerAdvice来声明一些关于controller的全局性的东西&#xff0c;其用法主要有以下三点…

建模杂谈系列256 规则函数化改造

说明 之前尝试用FastAPI来构造规则&#xff0c;碰到的问题是由于请求量过大(TPS > 1000), 从而导致微服务端口资源耗尽。所以现在的point是: 1 如何使用函数来替代微服务(同时要保留使用微服务的优点)2 进一步抽象并规范规则的执行3 等效合并规则的方法 内容 0 机制讨论…

数据中台建设(六)—— 数据开发-提取数据价值

数据开发-提取数据价值 数据开发涉及的产品能力主要包括三部分&#xff1a;离线开发、实时开发和算法开发。 离线开发主要包括离线数据的加工、发布、运维管理&#xff0c;以及数据分析、数据探索、在线查询和及时分析相关工作。实时开发主要涉及数据的实时接入和实时处理。算…

【算法】动态规划—最长回文子序列

思路分析 关于”回文串“的问题&#xff0c;是面试中常见的&#xff0c;本文提升难度&#xff0c;讲一讲”最长回文子序列“问题&#xff0c;题目很好理解&#xff1a; 输入一个字符串 s&#xff0c;请找出 s 中的最长回文子序列长度。 比如输入 s"aecda"&#xff0c…

WSL中使用AMBER GPU串行版

前提是已经安装过wsl 1 在 WSL 2 中启用 NVIDIA CUDA 参考在 WSL 2 上启用 NVIDIA CUDA | Microsoft Learn 注意&#xff1a;勿在 WSL 中安装任何 Linux 显示驱动程序。Windows 显示驱动程序将同时安装本机 Windows 和 WSL 支持的常规驱动程序组件。 2 在WSL2中配置Cuda 不安…

5G毫米波阵列天线仿真——CDF计算(手动AC远场)

之前写过两个关于阵列天线获取CDF的方法&#xff0c;一个通过Realized Gain&#xff0c;一个通过Power Flow&#xff0c; 三个案例中都是3D中直接波束扫描&#xff0c;并没有展示场路结合的情况。这期我们用Power Flow的方法&#xff0c;手动合并AC任务的波束计算CDF。 还是用…

Linux(7)--目录文件的创建、删除、移动、复制、重命名

文章目录 1. 创建目录、文件2. 删除目录、文件3. 移动目录、文件4. 复制目录、文件5. 重命名目录、文件 1. 创建目录、文件 使用mkdir创建目录&#xff1a; 使用touch创建文件&#xff1a; 2. 删除目录、文件 使用rm可以删除文件: 使用rm -f可以强制删除文件&#xff0c;…

C++掉血迷宫

目录 开头程序程序的流程图程序游玩的效果下一篇博客要说的东西 开头 大家好&#xff0c;我叫这是我58。 程序 #include <iostream> #include <string> #include <cstring> using namespace std; enum RBYG {R 1,B 2,Y 4,G 7, }; struct heal {int ix…

Linux权限理解【Shell的理解】【linux权限的概念、管理、切换】【粘滞位理解】

目录 Linux权限理解1.Xshell命令以及运行原理2.linux权限的学习2.1linux权限的切换2.2linux权限的概念2.3linux权限管理2.3.1linux中文件访问者的分类2.3.2文件类型和访问权限(文件属性)2.3.2.1文件类型2.3.2.2文件权限拓展—文件的起始权限 2.3.3文件权限管理2.3.4文件权限的应…

一文搞定WeakHashMap

写在前面 在缓存场景下&#xff0c;由于内存是有限的&#xff0c;不能缓存所有对象&#xff0c;因此就需要一定的删除机制&#xff0c;淘汰掉一些对象。这个时候可能很快就想到了各种Cache数据过期策略&#xff0c;目前也有一些优秀的包提供了功能丰富的Cache&#xff0c;比如…

十八,Spring Boot 整合 MyBatis-Plus 的详细配置

十八&#xff0c;Spring Boot 整合 MyBatis-Plus 的详细配置 文章目录 十八&#xff0c;Spring Boot 整合 MyBatis-Plus 的详细配置1. MyBatis-Plus 的基本介绍2. Spring Boot 整合 MyBatis Plus 的详细配置3. Spring Boot 整合 MyBatis plus 注意事项和细节4. MyBatisx 插件的…