【C++】vector模拟实现

🔥个人主页： Forcible Bug Maker
🔥专栏： STL || C++

前言

本篇博客主要内容：STL库中vector的模拟实现。

在之前完成string以及学习了vector一些接口函数的基础上，这个vector的实现相当于是一个奖励内容，并不困难。不过我们这里vector底层实现和上次string的有所不同，是通过三个指针_start，_finish和_end_of_storage来维护这个模板类的。相信在看完今天vector的实现之后，能对C++的迭代器有更深的了解。

🔥vector需要实现的接口函数

由于涉及到了模板的内容，我们这次不会将vector实现的声明和定义分离。在后期模板进阶的阶段会进一步解答此问题，盲目将模板类的声明定义分离是很容易出错的（在对模板这部分内容不熟练的情况下）。
看看需要实现的接口函数：

#pragma once
#include<iostream>
#include<algorithm>
#include<cassert>
using namespace std;
namespace ForcibleBugMaker
{template<class T>class vector{public:// 这里vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;//迭代器获取接口iterator begin();iterator end()const_iterator cbegin()const;const_iterator cend() const;// 交换vector对象void swap(vector<T>& v);// 构造函数，析构函数以及赋值运算符重载vector();vector(int n, const T& value = T());template<class InputIterator>vector(InputIterator first, InputIterator last);vector(const vector<T>& v);vector<T>& operator=(vector<T> v);~vector();// 容量获取和调整接口size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& value = T());// 元素获取T& operator[](size_t pos);const T& operator[](size_t pos)const;// 插入和删除元素void push_back(const T& x);void pop_back();iterator insert(iterator pos, const T& x);iterator erase(iterator pos);private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _end_of_storage = nullptr; // 指向存储容量的尾};
}

本篇建议在string类实现的基础上进行，不然有些概念可能不太好理解。C++中包含交换函数swap，在命名空间std中，可以直接使用。在vector的实现中，你可能发现与string不同，接口函数大多使用迭代器（指针）来实现，传入和传出的参数基本上也都是迭代器。这么做是为了给后面一系列的STL容器打一个基础，大家要逐渐习惯这样的实现方式。

🔥vector的模拟实现

接下来进入主要内容，按照上面的接口列表逐一实现。

本篇都是直接在vector模板类内部实现，不用手动圈定命名空间。

swap交换

既然是用三个指针维护的，那么交换这三个指针即可完成交换。

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()
{}// 构造包含n个value的vector对象
vector(int n, const T& value = T())
{reserve(n);for (int i = 0; i < n; i++) {this->push_back(value);}
}// 通过迭代器区间构造vector对象
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{InputIterator it = first;while (it != last) {this->push_back(*it);++it;}
}

学习过vector的使用，应该也能看懂。其中有几个还待实现的接口函数，如push_back，reserve等。

对于第一个无参构造，其实编译器默认实现的也有相同的效果，但是一旦你实现了下面两个构造，那么编译器就不会生成默认的了。C++提供了一种语法，可以无视你的重载构造，强制生成一个编译器默认构造，所以，下面这样写也是正确的的。

 // 强制编译器生成默认无参构造vector() = default;vector(int n, const T& value = T()){reserve(n);for (int i = 0; i < n; i++) {this->push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){InputIterator it = first;while (it != last) {this->push_back(*it);++it;}}

第二个构造中缺省参数T()表示的是构造一个T类型的对象，赋值给value。在C++中不但T()可以用于表示自定义类型变量的无参构造，也同样可以表示内置类型的无参构造（C语言中并不支持这样做）。
如下：

int a = int();
int b = int(3);
cout << a << endl;
cout << b << endl;

对于第三个，迭代器构造，实现的是一个模板成员函数，支持各种类型迭代器的区间构造。

析构函数：

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

拷贝构造：

vector(const vector<T>& v)
{reserve(v.capacity());int size = v.size();for (int i = 0; i < size; i++) {this->push_back(v[i]);}
}

赋值运算符重载：

vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

这是一种比较新的实现方式，在string中也有使用过。

迭代器接口

本篇vector虽然使用指针实现了迭代器，但并不是说只有这一种实现方式。你也可以将迭代器定义成一个模板类，具体内容可以在不久后的list篇章学到。

typedef T* iterator;
typedef const T* const_iterator;iterator begin()
{return _start;
}iterator end()
{return _finish;
}const_iterator cbegin()const
{return _start;
}const_iterator cend() const
{return _finish;
}

reserve和resize

reserve开辟容量空间capacity，但不改变vector对象原本的size区间中的内容。

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

resize也可以用作开辟空间，同时会改变size的值。

void resize(size_t n, const T& value = T())
{if (n > capacity()) {reserve(n);}while (_finish < _start + n) {*_finish = value;++_finish;}_finish = _start + n;
}

size和capacity

获取vector对象的size和capacity，通过指针相减就可以得到。

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

operator[ ]下标获取

通过运算符重载的operator[]获取vector对象的元素。

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

同时重载了非const版本和const版本。

push_back和pop_back

push_back和pop_back分别是尾插一个元素和尾删一个元素。
复用之前的reserve接口函数push_back功能其实并不难实现。

void push_back(const T& x)
{if (_finish == _end_of_storage) {reserve(size() == 0 ? 4 : size() * 2);}*_finish = x;++_finish;
}void pop_back()
{assert(size() > 0);--_finish;
}

插入（insert）和删除（erase）

这两个函数需要传入的参数都为迭代器，从vector中间部分插入和删除元素。

插入：会将我们传入的元素插入到迭代器指向的对象之前；如果迭代器指向end()，则功能等同于尾插。
删除：将传入迭代器指向的元素删除。

iterator insert(iterator pos, const T& x)
{assert(_start <= pos && pos <= _finish);if (_finish == _end_of_storage) {int gap = pos - _start;reserve(size() == 0 ? 4 : size() * 2);pos = _start + gap;}iterator it = _finish;while (it > pos) {*it = *(it - 1);--it;}*it = x;++_finish;return it + 1;
}iterator erase(iterator pos)
{assert(_start <= pos && pos < _finish);int size = pos - _start;iterator itCur = pos + 1;while (itCur != _finish) {*(itCur - 1) = *itCur;++itCur;}--_finish;return _start + size;
}

注：vector的insert和erase可能导致大量数据的移动，开销较大，所以非必要情况少用。

结语

本篇博客主要介绍了vector常用接口的实现，包括迭代器以及迭代器接口，元素的插入和删除，以及各种默认成员函数的实现。
后续博主还会继续分享与STL相关的内容，感谢大家的支持。♥