STL库——vector（类模拟实现）

ʕ • ᴥ • ʔ

づ♡ど

 🎉 欢迎点赞支持🎉

个人主页：励志不掉头发的内向程序员；

专栏主页：C++语言；

---

前言

我们上一章节了解到了vector的成员函数的使用方法，我们发现它和string相比容易了不少，同时引入了类模板让其可以满足各种类型变量的需求，本章节我们来继续加深对vector的了解，尝试模拟实现一个vector吧。

---

一、基本框架

vector和string的成员变量都差不多，都有size和capacity以及一个指向自己的空间，唯一不同的是vector指向的是一个模板变量的空间而不是固定变量的空间。但是我们这里按照源码的方式实现，它本质上就是开辟了三个空间。

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;namespace zxl
{template <class T>class vector{public:typedef T* iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

第一个变量是指向vector头空间的指针，第二个变量是指向vector储存数据的末尾指针，第三个则是vector容量的指针。原本的size变成了finish - start了，capacity则变成了end_of_storage - start了。

二、构造函数

默认构造函数：

vector()
{}

我们这样写就可以了，因为构造函数不管写不写都会走初始化列表，而我们给每个变量都提供了缺省值，所以这里啥也不写也是可以的。

当然我们还可以这样写

vector() = default;

这是C++11的用法，就是强制生成我们的默认构造。

拷贝构造：

vector(vector<T>& v)
{for (auto& e : v){push_back(e);}
}

拷贝构造也好写，就把vector每个元素都复制一份即可。当然如果不想开辟太多次空间浪费性能我们可以提前开好空间，这很容易就不多赘述。

我们还有一个靠迭代器区间初始化的方式，我们也来试着实现一下。

// 类模板的成员函数，还可以继续是函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

这里使用模板而不是iterator的原因是因为我们不一定是用vector的迭代器才能完成初始化，而是任意迭代器都可以的vector进行初始化。

还有n个相同元素初始化的方式。

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

但是当我们去尝试使用我们的这些构造函数时会产生一些问题。

int main()
{zxl::vector<string> a(10, "11111");for (int i = 0; i < a.size(); i++){cout << a[i] << ' ';}cout << endl;return 0;
}

我们可以发现，我们的这个代码可以正常运行。

但是这样就会报错了

int main()
{zxl::vector<int> a(10, 1);for (int i = 0; i < a.size(); i++){cout << a[i] << ' ';}cout << endl;return 0;
}

报错原因是因为编译器认为我们传的实参是迭代器类型，所以走的是迭代器的那个构造，但是由于是整型而非迭代器，所以就报错了。这个原因是因为编译器在函数重载时会走最适合它的那个函数，而这两个整型变量刚好就比较适合走模板函数，因为我们的这个函数的第一个形参是size_t而非int，所以想要解决的办法就是写一个第一个形参是int的函数重载，给编译器多一种选择。

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

三、析构函数

把我们指向的资源全部销毁即可。

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

四、运算符重载

4.1、赋值运算符重载

我们的赋值运算符重载无非就是先清空数据再插入数据。

vector<T>& operator=(vector<T>& v)
{if (this != &v){clear();reserve(v.size());for (auto& e : v){push_back(e);}}return *this;
}

这样写不难，但是还有更简单的办法，那就是交换资源。

void swap(vector<T>& v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_end_of_storage, v._end_of_storage);
}vector<T>& operator=(vector<T> v)
{if (this != &v){swap(v);}return *this;
}

这种操作就是用我们传值传参调用拷贝构造，构造了一个临时对象，我们通过把我们的对象和临时对象进行交互从而完成赋值运算符重载，返回this后临时变量也就自动销毁了。这两种效率差不多，看个人喜好来选择。

4.2、[]运算符重载

这个运算符的要重载的功能就是像数组那样可以对下标进行查看和修改，所以我们直接返回它的下标的引用即可。同时也可以检查一下pos是否超过了size的边界。

T& operator[](size_t pos)
{assert(pos < _size);return _start[pos];
}

五、增删查改

5.1、push_back函数

vector的尾插和string没有什么区别，都是不够就扩容然后插入即可。

void push_back(const T& x)	
{// 不够就扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}// 尾插*_finish = x;++_finish;
}

5.2、pop_back函数

此函数也很好实现，只要让vector的数据长度减少一个元素大小即可。

void pop_back()
{assert(!empty());--_finish;
}

5.3、insert函数

在讲vector的insert函数的时候，我们不得不去讨论一下我们所谓迭代器失效的问题，

5.2.1、迭代器失效

通过上一章节的对vector运用的知识学习，我们可以知道我们的vector想要在任意位置插入数据时得用我们的迭代器去指明位置，这就容易出现一个问题，那就是我们的数据是否扩容的问题（可以先看下面的reserve扩容函数再来看这里），我们已经知道了我们vector扩容时会让我们的_start指向一个新的地址，但是我们所预期的位置pos却没有变，此时就会产生一个迭代器失效的问题。

我们pos迭代器此时就相当于一个野指针，想要解决的办法也很简单，那就是和扩容那里一样把pos的相对位置保存起来即可，所以我们的insert可以这样写。

void 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;
}

此时我们便可实现在任意位置插入数据了，但是此时我们出去的实参还是没有变化的，也就是还是错误的，因为形参的改变不会影响实参，所以我们建议insert过后我们的pos就是失效的，不能直接访问，如果要访问的话就得更新我们的失效的迭代器的值。当然，哪怕不是野指针，我们的pos在insert时因为数据的平移，pos的含义也已经改变了，原来指向的值已经变成别的值了。

5.4、erase函数

我们insert涉及到的问题erase也涉及到，虽然我们erase不涉及到扩容，但是也要挪动数据，挪动数据后pos原来指向的元素已经改变了，所以erase后我们的pos就是失效的，不能直接访问。

void erase(iterator pos)
{assert(pos >= _start && pos <= _finish);iterator end = _pos + 1;while (end < _finish){*(end - 1) = *(end);++end;}--_finish;}

当然我们几乎所以容器erase都会迭代器失效，而insert是否迭代器失效要看情况。string在insert和erase后迭代器也会失效，但是由于我们一般很少要用string的insert和erase的迭代器版本，所以就没有说明。

六、其他成员函数

6.1、reserve函数

此扩容函数主要和string差不多，就是先开辟一个新空间，然后再把老空间的数据复制过去，再析构老空间，但是我们由于是用3个指针来表达我们原来的数据、size和capacity的，所以当我们开辟空间前得先保存一下我们_start到_finish的相对值方便对开辟空间后的_finish和_end_of_storage的位置进行调整。

void reserve(size_t n)
{if (capacity() < n){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

当我们尝试去用string插入时会发生这样的一个问题，本来插入的好好的，忽然就乱码或者报错了。

int main()
{zxl::vector<string> a;a.push_back("111");a.push_back("111");a.push_back("111");a.push_back("111");for (int i = 0; i < a.size(); i++){cout << a[i] << ' ';}cout << endl;return 0;
}

此时再多插入一次看看

int main()
{zxl::vector<string> a;a.push_back("111");a.push_back("111");a.push_back("111");a.push_back("111");a.push_back("111");for (int i = 0; i < a.size(); i++){cout << a[i] << ' ';}cout << endl;return 0;
}

这是怎么一回事呢？其实很简单，问题就在扩容上。我们的memcpy本质上就是一个字节一个字节的拷贝的，也就是浅拷贝，而我们原来的string被销毁了，这就意味着我们拷贝的内容指向的是一个野指针，所以就会报错或者打印乱码。

而解决办法也不难，我们一个元素一个元素进行深拷贝即可。

void reserve(size_t n)
{if (capacity() < n){size_t old_size = size();T* tmp = new T[n];for (int i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = tmp + n;}
}

这样把每个元素都复制到新空间种就可以解决了。

6.2、resize函数

我们上一章节讲过resize总共有三种情况，我们可以来试着实现一下。

// 默认构造给缺省值的方法
void resize(size_t n, T val = T())
{// 第一种情况if (n < size()){_finish = _start + n;}else{// 第二和第三种情况，靠reserve看看到底要不要扩容reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}
}

6.3、size函数

我们之前就说明了vector成员变量的不同之处，所以想要返回数据长度的size函数其实也就是vector指向数据尾部的指针减去vector指向头部的指针即可。

size_t size()
{return _finish - _start;
}

6.4、capacity函数

这个和size函数差不多，用指向vector内存空间的指针减去vector头部指针即可。

size_t capacity()
{return _end_of_storage - _start;
}

6.5、empty函数

判空也十分的容易。

bool empty()
{return _start == _finish;
}

6.6、clear函数

想要清空vector其实很简单。

void clear()
{_finish = _start;
}

6.7、迭代器

6.7.1、begin函数

在这里实现了两个，一个是普通迭代器的begin函数，一个是const迭代器的begin函数，也可以是cbegin函数。

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}const_iterator begin() const
{return _start;
}

6.7.2、end函数

同理也实现了两个end函数。

typedef T* iterator;
typedef const T* const_iterator;iterator end()
{return _finish;
}const_iterator end() const
{return _finish;
}

---

总结

以上便是vector的模拟实现原理，大家可以好好学习，这样可以加深对vector的理解，我们下一章节回去了解我们STL库中的list链表，我们下一章节再见。

🎇坚持到这里已经很厉害啦，辛苦啦🎇

ʕ • ᴥ • ʔ

づ♡ど