C++STL的vector模拟实现

前言

成员变量

namespace but
{template<class T>class vector{public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

我们之前实现顺序表是用指向数组的的指针和数组个数和容量来维护顺序表的，这里用三个指针来实现其实大差不差。

成员函数

构造函数

vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{}

push_back

void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);//避免容量为0扩容还是0的情况}*_finish = x;++_finish;
}

首先放数据怎么放呢？
直接赋值。

为什么可以直接赋值？
因为空间是new出来的，如果是内置类型，有没有初始化都可以直接赋值。
但是自定义类型没有初始化不能直接赋值。

扩容

void reserve(size_t n)
{//避免缩容//1.缩容的代价太大//2.反复缩容与扩容，降低了性能。if (n > capacity()){size_t sz = size();T* tmp = new T[n];//如果旧空间没有数据就不用拷贝了if (_start){//因为是类型不一定是字符串，所以得使用memcpymemcpy(tmp, _start, sizeof(T)*size());delete[] _start;}_start = tmp;//这里有个小坑//_finish=_start + size();//提前把size()记录下来，防止这里出错//改成tmp也可以，但是有点影响我们原本的理解，不利于维护。_finish = _start + sz;_end_of_storage = _start + n;}
}

我们把其他一些需要用到的代码补上，然后测试一下。

	size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}

迭代器

//这个普通迭代器实现起来也相当简单
iterator begin()
{return _start;
}iterator end()
{return _finish;
}

pop_back

删除数据好像也很简单，直接finish- -就可以，但是也有一些问题，那具体有什么问题呢？我们来看一下。

我们简单测试一下。
我们一直pop,就出问题了。

_finish一直减就走到前面去了，这样我们使用迭代器就出问题了。

我们简单改一下。

void pop_back()
{assert(!empty());--_finish;
}
bool empty()
{return _start == _finish;
}

针对const对象的访问

本质还是涉及到权限的放大，我们把成员函数都改为const就可以了。

resize()

void resize(size_t n, T val = T())//T()默认构造，是匿名对象，具体解释看下面
{if (n < size()){// 删除数据_finish = _start + n;}else{if (n > capacity())reserve(n);while (_finish != _start+n){*_finish = val;++_finish;}}
}

上面resize的缺省值能不能给0？
其实答案很明显， 显然不行，因为T是泛型编程，类型不一定是int,如果是double或者指针，对象都不行。

那问题又来了，int有默认构造函数吗？
我们在之前学习类和对象的时候知道，内置类型是没有构造函数的，但是有了模板之后它需要有。

insert

下面这段代码有什么问题？

如果容量不够，挪动数据就越界了。

除了容量不够还有没有其他什么问题？
提示一下pos==0; 好吧，其实不会发生之前模拟实现string的时候发生的无符号整型最大值的问题。

大家看这样子去测试就出问题了

注意，func(v1)是两次读取
程序运行时崩了。

先简单分析一下，这可能时内存问题，可能时数组越界。
为什么push_back 5次的时候没问题，push_back 4次就出问题了？
5个和4个的区别是什么？

insert的时候扩容出问题了。

注意看


发生了什么，扩容之后，start和finish变了，start 和finish为什么会变？
这是我们遇见的最经典的迭代器失效的问题。

pos变成野指针了。
这也就导致一直在循环的问题。

那这个怎么解决呢？
更新一下pos.

//void insert(iterator pos, const T& val)
iterator insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);// 扩容后更新pos，解决pos失效的问题pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = val;++_finish;return pos;
}

接下来，继续问一个问题，看前面的测试图片，insert之后能不能修改迭代器的位置。

(*pos)++;//我想修改这个3的位置。
func(v1);

程序没有报错，但是很明显不符合我们的预期。为什么？
不是已经把pos更新了吗，为什么外面还是不行呢？怎么不起作用。
因为自己写的insert是传值形参，形参的改变 不会影响实参的改变 。

怎么解决？

能不能用引用传参解决，看起来不错，实际不好。用引用传参会报错，为什么？

insert 引起迭代器失效的两种情况：
1.野指针问题
2.意义已经变了

通过返回值去解决
但是最好别用，你也不知道是什么时候失效。
insert以后我们认为pos失效了，不能再使用。

erase

现在又有一个问题，erase以后pos会不会失效？
不会，但是库里面的失效了，并且vs报错非常强烈，看下面。

报了一个断言错误。

再看一下g++下的运行。

那到底erase以后pos失效还是不失效？vs比较合理还是g++合理？
如果pos位置是4呢，那这个位置就很不合理了。

所以我们认为失效，不要访问，行为结果未定义，跟具体的编译器有关。
一定要注意，不然会被坑的很惨。

要想解决一下这种情况，我们都是用返回值来处理一下，其实本质就是不要pos跳过。

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

下面这个测试，连续的偶数和最后一个是偶数都能解决，就没什么大问题了。

1. vs进行强制检查，erase以后，迭代器不能访问。
2.g++没有强制检查，具体问题具体分析，结果未定义。

string有没有迭代器失效？
有，但是string不容易发生迭代器失效问题。
insert和erase不喜欢用迭代器，用的都是下标。

析构函数

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

下面的构造函数。

给大家看一个大坑。
先看下面的代码，这样写有没有什么问题？

程序崩了

不初始化会出各种问题。
一调试很容易看到会出现哪些问题。

加上初始化列表

vector(size_t n, const T& val = T())//T()是什么前面已经讲得很清楚了: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}
}

看一下这个构造函数。


如果是用iterator就写死了，你必须用vector的迭代器来进行初始化。

迭代器区间初始化，是必须用vectro的迭代器初始化吗？
一个容器用迭代器区间初始化，需要时任意类型的迭代器。

这里引出了另一个语法，允许一个类的成员函数再是函数模板。

// [first, last)
template <class InputIterator>
vector(InputIterator first, InputIterator last): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last) //不能用 <=,如果是链表肯定就不行{push_back(*first);++first;}
}

如果我们不写初始化列表，可用c++11的语法，成员变量声明的时候给个缺省值
缺省值是给构造函数的初始化列表用的。

奇怪的事情发生了，编译的时候报了一个这样的错误

为什么匹配错了，匹配到上面写的那个迭代区间初始化那个？

我们知道编译器会调用最匹配的那个，仔细分析一下其实可以发现，如果推演一下的话，如果要匹配 vector(size_ t n, const T& val =T()); 的话，就会发生类型转换，而调用迭代器区间初始化的话，进行推演，如果类型是int 直接就匹配上了。

然后看迭代器区间初始化的代码，int不能解引用，就直接报错了。

怎么解决？
1.加个u, 代表我这个变量是无符号。

2…看STL的源码，看源码是怎么解决这个问题的。
我们这里可以用一个很简单的方式去就解决，提供一个重载的版本。

引用返回时有风险的，要谨慎使用，除非你想想operator【】那样，可以去修改。

给大家看一下神奇的东西。

只要类型能匹配，char可以发生转换。

最神奇的还是可以这么玩。

甚至可以是数组，为什么可以是数组？
原生指针可以是天然的迭代器，有个前提，这个原生指针是指向数组。
其实vector的迭代器，string的迭代器也可以是原生指针。

接着扩展一下。
sort

默认是升序

这是一个函数模板，它的名字叫随机访问迭代器，那随机访问是什么呢？一般底层是数组。

它可以帮我们排序，并且用起来很爽。

如果是降序，我们就这么用。
1.

2.

这两个其实是等价了。

拷贝构造

我们还涉及深浅拷贝的问题。

首先这样写，是我们经典的浅拷贝的问题。

我们先写一个传统写法的深拷贝。

vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

看下面的代码，崩了，为什么？

也就是说当我们数据是int的时候程序能正常运行，当我们的数据是string的时候就崩的。

因为memcpy也是一种浅拷贝。调用拷贝构造的时候，memcpy干了什么事情。
从起始位置开始依次把所有值拷贝下来。

这里面还有一层是我们没有考虑的，这是深拷贝里面又套了一层深拷贝。memcpy就是深层次的浅拷贝。
调用析构的时候会崩。

怎么解决呢？
我们肯定是要解决三个问题，数据是int类型，或者string类型，或者vector的vector类型。

怎样完成深拷贝呢？难道是我们自己写吗？
我们不能自己解决，因为T是模板，我们也不知道它具体是什么类型。
不能自己给它写一个深拷贝，因为它们是私有的，动不了里面的。

所以我们这里面调一个深拷贝的函数来完成。
赋值就是深拷贝。

其实我们还没有完全解决所有的问题 ，除了拷贝构造用了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;}
}

那接着，哪里还有问题呢？vector里面的数据比如说是vector对象呢，比如vectro<vector >,给大家看一下，一个杨辉三角的例子。

测试

出错了，为什么？还有什么问题没有解决。
外面的vector是深拷贝，里面的vector是浅拷贝。
问题还是出现在拷贝构造，我们并没有自己写赋值。所以编译器还是用的默认生成的，是浅拷贝。

我们自己写个赋值就解决了。

现代写法
直接复用。

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(const vector<T>& v)
{vector<T> tmp(v.begin, v.end());swap(tmp);
}

最后一个小问题，不加模板参数语法上也允许，但是不推荐这样写。