C++——vector的模拟实现
引言:
本篇主要针对以下两点做出简要分析(个人角度):
1、部分模拟实现vector类的的代码;
2、在模拟实现vector类过程中遇到的问题;
总体框架:
因为是模拟实现vector,因此要在命名空间中实现,避免与重命名与库函数冲突,因此整体的大框架如下:
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace jc
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//成员函数
private:
iterator _start = nullptr; //初始化列表的缺省参数
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
}
}
注:
1、因为vector容器的数据不单单是字符,因此需要类模板来实现
2、此处的iterator类似为指针,但需要知道的是iterator不单单是指针,还有其他(尚未学习)
一、vector中各类函数的返回值
1:size() / capacity()
在模拟实现string类时,string类的成员函数分别为:字符数组指针—_str、当前字符串个数—_size、和字符串容量—_capacity。因此通过capacity()以及size()求字符串个数和字符串容量时,其返回类型为无符号的整型变量(size_t)。返回值为: _size、_capacity。
而在模拟实现vector类时,vector类的成员函数分别为:类似指针的起始数据地址—_start、类似指针的有效数据结束时的地址—_finish、和所开辟的空间最后一个地址—_end_of_storage。
虽然对于vector类中capacity()和size()函数返回类型也为无符号的整型(size_t),但是不是像string类那样简单的将成员变量的值返回即可,而是通过地址减的方式来实现。代码如下
//size() size_t size() const { return _finish - _start; } //capacity() size_t capacity() const { return _end_of_storage - _start; }
注:通过上述需要知道的是:在模拟实现vector的过程中,大多是通过指针减的方式,来确定变量间的关系,最终实现vector类的
2:reserve() / push_back() / insert() / erase()
这四个成员函数本应该都是无返回类型(void)的函数,但是后两个在某些情况下需要改为返回类型为iterator类型
reserve():
void reserve(size_t n);
void reserve(size_t n) { if (n > capacity()) { size_t oldsize = size(); T* tmp = new T[n]; if (_start) { //memcpy(tmp, _start, sizeof(T) * oldsize); //delete[] _start; for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + oldsize; _end_of_storage = _start + n; } }
在模拟实现reserve()的过程中,存在两个注意点:
1、_finish为nullptr
2、当vector容器中存储的是其他类类型的数据(涉及更加深层次的拷贝时)
注意点1:
前面提到 _finish是vector容器中最后一个数据的地址,那么按理来说,_start+size()即为当前vector容器的最后一个数据的地址,为什么为得到nullptr呢?如下图
再仔细想象size()函数,他的返回值为 _finish-_start,这下就明白为什么_finish会是nullptr了,因为前后两个_start相互抵消了。
为此我们需要记录原来数据的大小并保存到oldsize中,当扩容完时,再通过_start+oldsize确定_finish的大小。如下图
注意点2:
这个有点难以叙述,通过图像来解决,假设现在在vector容器中的数据类型为string即:vector<string> v1;
通过memcpy(),我们确实能够得到一个地址完全不同于 v1 的空间 tmp,并且指向string。
但问题是:不管是v1还是tmp中,各个string中的_str都指向的是同一块空间,因此在调用delete [] _start 时,会对string的内容进行析构,tmp中无法存储有效数据,且最后对_tmp进行析构时,会对同一块空间析构两次,因此会报错。
注:知识点复习:出作用域时,系统会对临时对象和局部对象自动调用析构
因此为了避免这种错误的发生,需要使用以下写法:
for (size_t i = 0; i < size(); i++) { tmp[i] = _start[i]; } delete[] _start;
push_back():
void push_back( const T& x);
void push_back(const T& x) { if (_finish == _end_of_storage) { reserve(_end_of_storage == 0 ? 4 : 2 * (_end_of_storage-_start)); } *_finish = x; _finish++; }
这一块没什么可说的,与顺序表实现的思路完全一致
insert():
void/iterator insert(iterator pos, T x);
void insert(iterator pos, T x) { assert(pos >= _start && pos < _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator i = _finish; while (i > pos) { *i = *(i - 1); i--; } *pos = x; _finish++; }
在模拟实现insert()时,同样需要注意两个地方
1、pos失效问题
2、迭代器失效问题
注意点1:
原pos指针是指向空间A的某一位置处,方才通过分析reserve()函数时,可知:我们析构了原来的空间A,转而开辟了一块新的空间B,因此原来指向空间A的指针pos就变成了野指针,我们需要对pos进行更新,记录原来pos指针较_start的相对位置len,在开辟的新的空间B后,_start也得到了更新,将_start+len便可得到新的pos指针。
注意点2:
这个问题是由系统造成的,系统为了解决这个问题,将返回值从 void 转变为 iterator,并且将pos返回,代码如下:
iterator insert(iterator pos, T x) { assert(pos >= _start && pos < _finish); if (_finish == _end_of_storage) { size_t len = pos - _start; reserve(capacity() == 0 ? 4 : 2 * capacity()); pos = _start + len; } iterator i = _finish; while (i > pos) { *i = *(i - 1); i--; } *pos = x; _finish++; return pos; }
并且在测试文件中,通过接收返回值来更新当前指针的一个位置
erase():
iterator erase(iterator pos);
iterator erase(iterator pos) { assert(pos >= _start && pos < _finish); iterator i = pos; while (i != _finish) { *i = *(i + 1); ++i; } _finish--; return pos; }
erase()同样存在迭代器失效的问题,与insert()函数的解决方式一致
二、vector中其他成员函数的实现
1:现代版本的深拷贝
// v3(v2) vector(const vector<T>& v) { reserve(v.capacity()); for (auto ch : v) //范围for { push_back(ch); } }
不要忘了拷贝构造的写法:类名(const 类型& 变量名)
2:其他拷贝构造
// 类模板的成员函数,也可以是一个函数模板 template <class InputIterator> vector(InputIterator first, InputIterator last) while (first != last) { push_back(*first); ++first; } } vector(size_t n, const T& val = T()) { reserve(n); for (size_t i = 0; i < n; i++) { push_back(val); } }
上述拷贝构造存在的问题:
如果构造类型为:vector<int> v4(10, 1); // 拷贝构造10个1
系统认定模板函数相较于非模板函数更加匹配,系统会调用模板函数,而整型是不能解引用的因此会报错。那么如何解决这个问题呢?
代码如下:
vector(int n, const T& val = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(val); } }
写一个更加匹配的函数,来避免上述问题
注:知识点复习:系统在调用函数时,会有一个最佳匹配的问题,即系统会默认调用更加匹配的函数来运行
3:现代版的运算符重载
void swap(vector<T>& tmp) { std::swap(_start,tmp._start); std::swap(_finish,tmp._finish); std::swap(_end_of_storage, tmp._end_of_storage); } //现代版的运算符重载 v3 = v1 vector<T>& operator=(vector<T>& v) { swap(v); return *this; }
交换后v1中的数据全部丢失
4:operator[]实现
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}