[C++]vector的模拟实现

        下面是简单的实现vector的功能，没有涉及使用内存池等复杂算法来提高效率。

一、vector的概述

（一）、抽象数据类型定义

容器：向量（vector）

vector是表示大小可以变化的数组的序列容器。像数组一样，向量对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样高效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。

模板类 template<class T> 操作 一、构造函数 vector();        默认构造 vector(size_t n,const T val = T());        用n个val进行填充初始化 vector(int n, const T val = T());   防止vector(int,int)与下面的模板函数发生歧义 template<class InputIterator>         vector(InputIterator first, Inputiterator last);        迭代器区间初始化 vector(std::initializer_list list);        用初始化列表进行初始化 vector(const vector<T>& v)；        拷贝构造函数 vector<T>& operator=(const vector<T>& v);       赋值构造 ~vector();        析构函数 二、迭代器 iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; 三、容量 size_t size() const;        返回当前容器存储的数据个数 size_t capacity() const;        返回当前容器的容量大小 void resize(size_t n);        改变容器数据个数 bool empty() const;        判断当前容器是否为空 void reserve(size_t n);        改变容量大小 四、访问数据 T& operator[](size_t n);        可读可写 const T& operator[](size_t n) const;        只可读 五、修改操作 void push_back(const T& val);        尾插操作 void pop_back();        尾删操作 iterator insert(iterator pos, const T& x);        在指定位置插入 iterator erase(iterator pos);        指定位置删除 void swap(vector<T>& v);        交换两个vector容器的数据

（二）、成员变量

template<class T>
class vector
{
public://vector的迭代器可以为原生指针typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;//指向第一个数据的迭代器iterator _finish = nullptr;//指向最后一个有效数据的后一个位置iterator _endOfStorage = nullptr;//指向数组末尾的后一个位置
};

         这里的迭代器就是我们的原生指针T*，它的私有成员变量就和线性表一样，要存储数据的起始位置的指针、数据的有效数据的个数、存储容量等。这里直接全部定义成指针来维护容器的数据数组，_start指向数组的起始位置，_finish指向有效数据个数的后一个的位置，当我们将这两个指针相减，_finish - _start 就能得到数据的有效数据个数了。最后一个endOfStorage就是指向数组的末尾的下一个位置(虽然越界但不解引用就没事),当我们拿_endOfStorage -  _start 就得到了这段空间的容量个数。

        注意：我们的每个构造函数，在一开始时都要把迭代器置为空指针，而我们在声明迭代器时，顺便给上初始值，这样会更好，以免忘记初始化带来不必要的麻烦。

迭代器维护的空间示意图:

二、具体实现

        我们不按上面的函数声明的顺序来依次定义函数，我们按照从易到难的顺序，一点一点实现其成员函数的定义，每个阶段测试一下。

（一）、默认构造、析构、迭代器、尾插、尾删、下标访问

（1）、默认构造、析构

//默认构造
vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { ; }

         因为是空容器，所以三个指针都初始化为nullptr。

//析构
~vector()
{delete[] _start;_start = _finish = _endOfStorage = nullptr;
}

        删除动态分配的空间后记得将指针置为空，因为析构是可以手动调用的。

（2）、迭代器

//迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

       两组迭代器分别构成重载。

        注意：重载不是因为返回值的不同，而是其参数不同，一个是this，另一个是const this的指针。

（3）、尾插和尾删操作

         注意:需要对容器满时进行扩容处理。

1、辅助其扩容的函数

empty()：判断容器是否为空

bool empty() const { return (_finish - _start) == 0; }

size()：返回容器的有效数据个数

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

capacity()：返回容器的容量

size_t capacity() const { return _endOfStorage - _start; }

reserve()：扩容操作

void reserve(size_t n)//改变容量大小
{//如果n为0,默认给4个空间n = n == 0 ? 4 : n;//不允许缩容if (n <= capacity())return;//扩容size_t nSize = size();//保存有效数据个数iterator itTem = new T[n];//拷贝到新数组for (int i = 0; i < nSize; i++){*(itTem + i) = *(_start + i);}delete[] _start;_start = itTem;_finish = _start + nSize;_endOfStorage = _start + n;
}

2、尾插、尾删

//修改操作
void push_back(const T& val)//尾插操作
{//判断容器空间是否足够if (size() == capacity()){size_t newCapacity = capacity() * 2;//两倍扩容//扩容reserve(newCapacity);//std::cout << capacity() << " ";}//尾插*_finish = val;_finish++;
}

void pop_back()//尾删操作
{if (!empty())_finish--;
}

（4）、下标访问

		//访问操作T& operator[](size_t n){//防止越界访问assert(n >= 0 && n < size());return *(_start + n);}const T& operator[](size_t n) const{//防止越界访问assert(n >= 0 && n < size());return *(_start + n);}

        注意：构成函数重载的是参数，不是返回值。

（5）、代码测试

void test1()
{const int N = 10;//测试数据的个数MySpace::vector<int> v1;for (int i = 0; i < N; i++){v1.push_back(i + 1);}//手动使用迭代器遍历MySpace::vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}cout << endl;//数组方式访问for (int i = 0; i < N; i++)cout << v1[i] << " ";cout << endl;//测试尾删for (int i = 0; i < N + 2; i++)//+2是为了测试一下删空容器{cout << endl;for (auto e : v1)//测试范围for{cout << e << " ";}v1.pop_back();}
}

运行结果:

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

---

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7
1 2 3 4 5 6
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

---

---

（二）、其余的构造函数

（1）、迭代器区间和参数初始化表初始化

迭代器区间初始化构造函数

        因为迭代器的类型可能不同，不一定所有的迭代器的类型都是指针，有可能是自定义类型。所以用模板函数。注意：迭代器不一定都支持加减操作，所以用迭代器加减的方式获得迭代器区间的大小是不安全的做法。

//迭代器区间初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{//这里不可以像指针那样直接 last - first 算出数据个数//因为有的迭代器是不支持加减的//可以采取以下方法先算大小，防止频繁扩容导致效率降低size_t n = 0;InputIterator itFirst = first;InputIterator itLast = last;while (itFirst != itLast){n++;itFirst++;}reserve(n);while (first != last){push_back(*first);first++;}
}

参数初始化列表初始化构造函数

//用参数初始化表初始化
vector(std::initializer_list<T> list) 
{ reserve(list.size());for (auto& e: list){push_back(e);}
}

（2）拷贝构造函数

		//拷贝构造vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

（3）交换两个容器和赋值构造函数

实现交换容器的函数swap()来辅助赋值构造函数的实现

void swap(vector<T>& v)//交换两个的数据
{std::swap(_start, v._start);std::swap(_finish,v._finish);std::swap(_endOfStorage, v._endOfStorage);
}

赋值构造函数

//赋值构造
vector<T>& operator=(const vector<T>& v)
{//复用拷贝构造函数vector<T> tem(v);swap(tem);return *this;
}

（4）填充初始化

		//填充初始化vector(size_t n, const T val = T())//用n个val进行初始化{reserve(n);for (int i = 0; i < n; i++){push_back(val);}}//用来防止调用vector(int,int)时发生歧义//发生歧义的函数:vector<InputIterator InputIterator>vector(int n, const T val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}

（5）、代码测试

void test2()
{const int N = 8;MySpace::vector<int> v1;for (int i = 0; i < N; i++){v1.push_back(i + 1);}for (auto e : v1){cout << e << " ";}cout << endl;//测试迭代器区间初始化构造MySpace::vector<int> v2(v1.begin() + 2, v1.end()-2);for (auto e : v2){cout << e << " ";}//测试参数初始化列表构造cout << endl;MySpace::vector<int> v3({ 1,2,3,4,5,6,7,8,9,10 });for (auto e : v3){cout << e << " ";}//测试拷贝构造cout << endl;MySpace::vector<int> v4(v3);for (auto e : v4){cout << e << " ";}//测试赋值构造cout << endl;MySpace::vector<int> v5;v5 = v4;for (auto e : v5){cout << e << " ";}//测试填充初始化cout << endl;MySpace::vector<int> v6(10,7);for (auto e : v6){cout << e << " ";}
}

运行结果： 

1 2 3 4 5 6 7 8
3 4 5 6
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
7 7 7 7 7 7 7 7 7 7 

（三）、指定位置插入和删除

（1）、指定位置插入

		iterator insert(iterator pos, const T& x)//在指定位置插入{//判断插入的位置及是否合法assert(pos >= _start && pos <= _finish);//判断是否需要扩容if (size() == capacity()){//防止扩容后pos迭代器失效size_t nPos = pos - _start;//计算pos距离_start的偏移量size_t newCapacity = capacity() * 2;reserve(newCapacity);pos = _start + nPos;}//将插入位置及之后的元素往后挪iterator it = _finish;while (it > pos){*it = *(it - 1);it--;}//插入元素*pos = x;_finish++;return pos;}

        注意：扩容时pos迭代器会失效，扩容前要计算pos距离起始位置的偏移量，然后再更新pos的迭代器。所以，外部的迭代器pos是有失效的可能性的，而不管怎么样外部的pos是不能再继续使用的，若要继续使用，则需要接受函数的返回值更新pos的迭代器，防止迭代器失效，此时pos迭代器指向新插入的数据。

（2）、指定位置删除 

iterator erase(iterator pos)//指定位置删除
{//判断删除的位置是否合法assert(pos >= _start && pos <= _finish - 1);//将pos位置后的元素往前挪iterator cur = pos + 1;while (cur != _finish){*(cur - 1) = *cur;cur++;}_finish--;return pos;
}

        注意：vector删除元素时有可能缩容的，虽然这里实现的vector不会缩容，为了防止外部的迭代器失效，我们也需要返回一个迭代器更新其pos的位置，此时pos指向的位置是删除的元素的下一个元素的位置。

（3）、代码测试

void test3()
{MySpace::vector<int> v1{ 1,2,3,4,5,6 };//测试指定位置插入v1.insert(v1.begin(), 999);v1.insert(v1.end(), 999);v1.insert(v1.end() - 2, 999);for (auto e : v1){cout << e << " ";}cout << endl;//结合find删除所有999//找不到则返回结尾的迭代器MySpace::vector<int>::iterator itFind;while ((itFind = std::find(v1.begin(), v1.end(), 999)) != v1.end()){cout << endl;v1.erase(itFind);for (auto e : v1){cout << e << " ";}}
}

（4） 运行结果：

999 1 2 3 4 5 999 6 999 

---

1 2 3 4 5 999 6 999
1 2 3 4 5 6 999
1 2 3 4 5 6

（四）、修改有效数据个数大小

具体实现代码：

void resize(size_t n)//改变容器数据个数
{assert(n >= 0);//判断是否需要扩容if (n > capacity()){reserve(n);}//将其他位置初始化为数据的默认构造for (int i = size(); i < n; i++){*(_start + i) = T();}_finish = _start + n;
}

代码测试：

void test4()
{//测试resizeMySpace::vector<int> v1{ 1,2,3,4,5,6,7,8,9,10 };for (auto e : v1){cout << e << " ";}cout << endl;//缩容v1.resize(2);for (auto e : v1){cout << e << " ";}cout << endl;//调大有效数据个数大小v1.resize(10);for (auto e : v1){cout << e << " ";}
}

1 2 3 4 5 6 7 8 9 10
1 2
1 2 0 0 0 0 0 0 0 0 

        以上就是vector的简易实现。