C++模拟实现vector

🌈模拟实现vector

☀️一、成员变量设置

由源码可知，用三个迭代器就可以构建出一个vector顺序容器，三个迭代器分别指向顺序容器的头（start）、有效大小截止处（finish）、总容量截止处（end_of_storage）：

模拟实现时也借鉴次方法，步骤如下：

1. 设置命名空间为mine；命名空间中建立模版vector，模版参数只有一个，就是数据类型T。
2. private部分就是三个分别指向头（_start）、有效大小截止处（_finish）、总容量截止处（_endofstorage）的迭代器（指针）。

namespace mine {template<class T>class vector {public:private:iterator _start;iterator _finish;iterator _endofstorage;};
}

☀️二、迭代器相关

🎈1.vector的迭代器的表示

vector是顺序容器，因此其指针就相当于迭代器，直接将数据指针T*typedef即可。注意迭代器还有const类型的。

namespace mine {template<class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;};
}

🎈2.指向首元素的迭代器（const+非const）

iterator begin() {return _start;}
const_iterator begin() const {return _start;}

🎈3.指向末尾元素下一个位置的迭代器（const+非const）

iterator end() {return _finish;}
const_iterator end() const {return _finish;}

☀️三、大小、容量函数

🎈1.计算大小：size()

T size() {return _finish - _start;}

🎈2.计算容量：capacity()

T capacity() {return _endofstorage - _start;}

🎈3.改变大小：resize()

将容器改变至指定大小，有3种情况：

1. 指定大小小于实际大小
2. 指定大小大于实际大小、小于当下容量
3. 指定大小大于当下容量

三种情况对应的解决方式为：

1. 相当于删除了部分数据，减小_finish即可
2. 尾插数据，模版里放了啥数据类型，就尾插该类型的数据，数据可以显式传参，不传参的话就由该类型默认构造函数生成
3. 与2同理

注：默认构造函数T()

1. 对于自定义类型：自定义类型都有默认构造函数，即空构造函数、全缺省构造函数、编译器自动生成的函数（三个只出现其中一个）；
2. 内置类型：内置类型按道理不需要默认构造函数，但为了此处的逻辑闭环，给内置类型也安排上了默认构造函数。
   调用int的默认构造函数int()会得到整型数据0；
   调用double的默认构造函数double()会得到0.0；
   调用char的默认构造函数char()会得到字符零’\0’，即ASCII码值为0的字符；
   调用指针类型的默认构造函数会得到空指针。

void resize(int n, T val = T()){if (n < size()) {_finish -= (size() - n);}else {for (int i = size();i <= n;i++) {push_back(val);}}}

🎈4.扩充容量：reserve()

只能扩充不能缩减容量。

🌟注意以下错误写法：

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

❌错误点1：（红色框）

指向原来空间的迭代器被释放而失效：

分析：

1. 由于delete[]的原因，原先的三个迭代器指向的空间已经被释放，三个迭代器此时为空指针；
2. size()=_finish - _start这句话就无意义了，变成了一个空洞的表达式；
3. _finish = _start + size()，转换到编译器底层就变成了_finish = _start+_finish - _start=_finish，相当于这句话并没有起到给_finish赋值的作用，_finish仍然是空指针；

💡改进错误1：

在释放原_start之前，就计算好容器大小，即为oldSize。

void reserve(size_t n) {if (n > capacity()) {int oldSize = size();T* tmp = new T[n];if (_start) {memcpy(tmp, _start, sizeof(T) * oldSize);delete[] _start;}_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}

注意：一定要在memcpy前先判断_start是否为空指针。当对一个空容器扩容时，由于_start为空指针，此时_start不可以作为memcpy的第二个参数（数据源头），并且此时不需要使用memcpy函数拷贝数据；只有_start不为空指针，即容器内有有效数据时才能使用memcpy函数，也有必要使用该函数。

❌错误点2：（橘色框）

memcpy只能进行浅拷贝，不可以用于储存自定义类型元素的vector：

memcpy的本质是浅拷贝，对于内置类型数据而言，使用该函数无可厚非，但自定义类型使用该函数后，会导致多次释放同一块空间而程序崩溃。因此我们设计模版时要充分考虑到所有数据类型。

例如，vector$<string>$容器中最开始放置了4个字符串，现由于扩充容量，要将这些数据全部用memcpy函数移动至新的空间：

string类型的对象的成员函数中都有一个指针_str，则memcpy拷贝会将_str原模原样拷贝过去，此时就会出现两个指针指向同一块空间的现象，后序必定会导致程序崩溃。
实际上，我们需要的是指针指向的数据，而不是指向数据的指针，因此应该做的是拷贝数据，用到赋值重载函数。

✅最终正确写法：

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

tmp[i] = _start[i]这句话做到了把指针_str指向的字符串、描述字符串大小和所占容量的信息拷贝至tmp指向的空间。

☀️四、构造、拷贝构造、析构

🎈1.构造：

🌟重载1：vector()

构造空vector

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

🌟重载2：vector(int n, const T& val)

构造大小为n且全初始化为val的vector。
这里用到了push_back()函数，下面增相关函数中会介绍。

vector(int n, const T& val) {while (n > 0) {push_back(val);n--;}}

🌟重载3：vector(inputIterator first, inputIterator last)

用迭代器区间来构造。

template<class inputIterator>
vector(inputIterator first, inputIterator last) {while (first != last) {push_back(*first);_finish++;}}

注：inputIterator是迭代器类型，与本类的迭代器iterator区分，意味着这个区间不一定来自相同类型的类对象，也可以来自不同类型的类对象，其中涉及到类型的隐式转换。例如，可以用vector$<char>$类型的类对象的一段区间，去构造vector$<int>$类型的类对象，编译器内部会涉及从char到int的隐式转换。

🎈2.拷贝构造：vector(const vector$<T>$& v)

🌟写法1：传统方法

开辟一段相同大小的空间，将原数据拷贝至新空间。

vector(const vector<T>& v) {_start = new T[v.capacity()];for (int i = 0;i < v.capacity();i++) {_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}

注意：不可以用memcpy函数拷贝原数据，原因和reserve相同，应该一个一个对新空间赋值，赋指针指向的实际数据而不是指向数据的指针：

🌟写法2：现代方法

创建一个新的空容器，将原容器中的数据按顺序依次尾插进新容器。不过要先通过初始化列表的方式将成员变量置为空指针。

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_endofstorage(nullptr){for (const auto& e : v) {push_back(e);}}

注意：用e这个变量接收时v中的内容时，e的类型最好是auto&即引用。因为auto类型的e本质上是对v容器中数据的拷贝，当v容器中存储的是自定义类型的数据，则e得到拷贝数据的过程需要调用该自定义类型的拷贝构造函数，消耗太大；此时完全可以换个思路，直接用引用，共享原来的空间内的数据。不过要注意不可以因为引用而改变原来空间内的值，因此在auto&的前面加上const，保证原来的数据不被修改。

🌟写法3：现代方法的改进

进一步优化写法2，即在设置成员变量时就设置好缺省值，三个迭代器变量全是nullptr。

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

🎈3.析构：~vector()

析构函数不需要在所有时候都显示写。如果类内部存储的是内置类型数据，则自动生成的析构函数就足以；但如果类内部存储的是自定义类型数据，每个数据都涉及到空间的开辟，则需显式写出析构函数，并在析构函数内写入正确的语句，确保自定义类型的数据本身和数据所占空间都被销毁。

~vector() {delete[] _start;//对于容器内内置类型的数据，则直接回收空间即可//对于自定义类型的数据，则调用该内置类型的析构函数_start = _finish = _endofstorage = nullptr;}

☀️五、操作符重载

🎈1.赋值

借助swap函数，在operator=函数传参时，通过拷贝传参建立了局部对象，再将this中指向原数据的指针和局部对象中指向新数据的指针交换，this中的指针就指向我们想要的值了。

注意：operator=函数的传参方式一定是传值传参而不是传引用，以便生成局部对象。因为swap会将this中不要的旧值和局部对象中的新值交换，局部对象不会影响被拷贝的对象v本身；传引用则会改变v的本身，相当于把数据偷走了。

void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}
vector<T>& operator=(vector<T> v) {swap(v);return *this;}

🎈2.下标访问

注意：

1. 返回值是那个下标对应位置上的数据的引用，不是容器本身的引用。
2. 必须使用引用是因为可能会通过下标访问的方式来赋值。
3. 被访问的对象可能被const修饰也可能没有，因此要写两个重载分别对应这两种情况。

T& operator[](int i) {assert(i >= 0 && i < size());return *(_start + i);}const T& operator[](int i) const{assert(i >= 0 && i < size());return *(_start + i);}

🎈 注：对于物理空间连续的容器而言，不需要重载++、–、>、<操作符。

☀️六、增相关函数

🎈1.尾插：push_back()

void push_back(const T& val) {if (_finish == _endofstorage) {reserve(capacity() == 0 ? 4 : capacity() + 4);}*_finish = val;_finish++;}

🎈2.任意位置插入：insert()

注：insert的返回值为一个新的迭代器。为避免旧的迭代器失效，insert函数结束时都会返回一个新的迭代器，用新的迭代器给之前的旧迭代器赋值，这样才能保证迭代器永远处于能使用的状态。

🌟重载1：在迭代器指向位置插入一个数据

iterator insert(iterator pos, const T& val) {assert(pos >= _start && pos <= _finish);int site = pos - _start;int len = _finish - pos;if (_finish == _endofstorage) {reserve(capacity() == 0 ? 1 : capacity() + 1);}pos = _start + site;iterator source = pos;iterator destin = pos + 1;while (len > 0) {*(destin + len - 1) = *(source + len - 1);len--;}*pos = val;_finish++;return pos;}

🌟重载2：在迭代器指向位置插入n个相同数据

iterator insert(iterator pos, int n, const T& val) {assert(pos >= _start && pos <= _finish);int site = pos - _start;int len = _finish - pos;if (_finish == _endofstorage) {reserve(capacity() == 0 ? n : capacity() + n);}pos = _start + site;iterator source = pos;iterator destin = pos + n;while (len > 0) {*(destin + len - 1) = *(source + len - 1);len--;}for (int i = 0;i < n;i++) {*(pos + i) = val;}_finish += n;return pos;}

☀️七、删相关函数

🎈1.尾删：pop_back()

void pop_back() {assert(size() > 0);_finish--;}

🎈2.删除指定数据：erase()

注：erase函数有返回值。在std中的erase为了避免迭代器失效（两种失效，一种是后面的数据往前挪导致迭代器指向的数据已经不是原来数据，另一种是erase让空间缩减，使得迭代器指向的位置已经被释放，迭代器此时相当于野指针），从而erase函数结束时会返回一个迭代器，指向被删除的所有元素的下一个元素。

🌟重载1：删除一个数据

iterator erase(iterator pos) {assert(pos >= _start && pos <= _finish);int len = _finish - pos;iterator source = pos + 1;iterator destin = pos;for (int i = 0;i < len;i++) {destin[i] = source[i];}_finish--;return source;}

🌟重载2：删除一段数据

iterator erase(iterator first, iterator last) {assert(first >= _start && first <= _finish);assert(last >= _start && last <= _finish);int n = last - first;assert(n > 0);int len = _finish - last;iterator source = pos + n;iterator destin = pos;for (int i = 0;i < len;i++) {destin[i] = source[i];}_finish -= n;return source;}

🎈3.清空数据：clear()

void clear() {_finish = _start;}

☀️八、打印函数

为方便查看测试结果，在mine命名空间中写一个非成员函数print_vector，用来打印vector容器。

注意：

1. print_vector是模版函数，可以打印多种vector$<T>$中的多种类型数据；
2. 用引用传参接收vector$<T>$类型的对象，避免拷贝构造导致的效率降低；
3. 用const类型变量接收，这样不管有没有const修饰的vector容器，都可以适用；
4. 用for循环遍历vector$<T>$类型的对象内部时，for里面的局部变量e也是被const修饰、引用类型的变量（T有可能是自定义类型）。

template<class T>void print_vector(const vector<T>& v) {for (const auto& e : v) {std::cout << e << ' ';}std::cout << std::endl;}

👻九、思考：关于构造函数vector(int n, const T& val)

为啥参数n的类型不是size_t？

用vector(size_t n, const T& val)代替vector(int n, const T& val)，看看发生了什么。

💡运行程序：

int main() {vector<int> v(5, 2);print_vector(v);
}

💡程序出错，错因：

💡分析：

非法的间接寻址意思是将不可以看作地址的东西当成了地址。在此就是调用vector(inputIterator first, inputIterator last)函数中，把5和2被当成了地址处理，而不是调用vector(size_t n, const T& val)。

为什么会匹配错函数？

1. 因为函数调用匹配的是最相近的那个函数重载，即所传递的参数能最快、最方便转化成哪个函数重载对应的参数，就调用哪个重载。
2. 如果要匹配vector<size_t n,const T& val>这个构造函数，编译器会先将1这个整形数字隐式转换成const int& val（const T& val）类型；
3. 如果要匹配vector<InputIterator first,InputIterator last>这个构造函数，编译器会直接将两个整形数字5和1当做迭代器（指针），不需要类型转换；
4. 对于编译器而言，匹配vector<InputIterator first,InputIterator last>是件更容易的事，则最终调用该函数。
5. 但是真正这样匹配了之后，函数内部无法将整型数字当做指针（迭代器）解引用，最终程序崩溃。

💡解决方法：

要让vector$<string>$ v1(5,1)语句匹配vector<size_t n,const T& val>这个构造函数，就是想方设法让这个构造函数更匹配两个整形参数，将第一个参数类型size_t改为int就行。
因此vector构造函数的这个重载写成vector(int n, const T& val)。

C++库里面是将vector(int n, const T& val)和vector(size_t n, const T& val)都写进去了：

🌈完整程序

主要由两文件构成：vector.h与test.cpp

☀️vector.h：函数实现

#pragma once
#include<iostream>
#include<stdio.h>
#include<assert.h>
namespace mine
{template<class T>class vector{public://迭代器typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _start;}const_iterator begin() const {return _start;}iterator end() {return _finish;}const_iterator end() const {return _finish;}//大小、容量int size() const{return _finish - _start;}int capacity() const{return _endofstorage - _start;}void resize(int n, T val = T()){if (n < size()) {_finish -= (size() - n);}else {for (int i = size();i < n;i++) {push_back(val);}}}void reserve(size_t n) {if (n > capacity()) {T* tmp = new T[n];int oldSize = size();if (_start) {for (int i = 0;i < oldSize;i++) {tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}//构造vector(){}vector(int n, const T& val) {while (n > 0) {push_back(val);n--;}}template<class inputIterator>vector(inputIterator first, inputIterator last) {while (first != last) {push_back(*first);first++;}}//拷贝构造void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}vector<T>& operator=(vector<T> v) {swap(v);return *this;}T& operator[](int i) {assert(i >= 0 && i < size());return *(_start + i);}const T& operator[](int i) const{assert(i >= 0 && i < size());return *(_start + i);}//传统写法//vector(const vector<T>& v) {//	_start = new T[v.capacity()];//	for (int i = 0;i < v.capacity();i++) {//		_start[i] = v._start[i];//	}//	_finish = _start + v.size();//	_endofstorage = _start + v.capacity();//}//现代写法（成员变量已经有默认值nullptr）vector(const vector<T>& v){for (const auto& e : v) {push_back(e);}/*或写成这样：for (int i = 0;i < v.size();i++) {push_back(*(v._start + i));}*/}~vector() {delete[] _start;//对于容器内内置类型的数据，则直接回收空间即可//对于自定义类型的数据，则调用该内置类型的析构函数_start = _finish = _endofstorage = nullptr;}void push_back(const T& val) {if (_finish == _endofstorage) {reserve(capacity() == 0 ? 4 : capacity() + 4);}*_finish = val;_finish++;}//重载1：iterator insert(iterator pos, const T& val) {assert(pos >= _start && pos <= _finish);int site = pos - _start;int len = _finish - pos;if (_finish == _endofstorage) {reserve(capacity() == 0 ? 1 : capacity() + 1);}pos = _start + site;iterator source = pos;iterator destin = pos + 1;while (len > 0) {*(destin + len - 1) = *(source + len - 1);len--;}*pos = val;_finish++;return pos;}//重载2：iterator insert(iterator pos, int n, const T& val) {assert(pos >= _start && pos <= _finish);int site = pos - _start;int len = _finish - pos;if (_finish == _endofstorage) {reserve(capacity() == 0 ? n : capacity() + n);}pos = _start + site;iterator source = pos;iterator destin = pos + n;while (len > 0) {*(destin + len - 1) = *(source + len - 1);len--;}for (int i = 0;i < n;i++) {*(pos + i) = val;}_finish += n;return pos;}void pop_back() {assert(size() > 0);_finish--;}//重载1：iterator erase(iterator pos) {assert(pos >= _start && pos < _finish);int len = _finish - pos;iterator source = pos + 1;iterator destin = pos;for (int i = 0;i < len;i++) {destin[i] = source[i];}_finish--;return source;}//重载2：iterator erase(iterator first, iterator last) {assert(first >= _start && first <= _finish);assert(last >= _start && last <= _finish);int n = last - first;assert(n > 0);int len = _finish - last;iterator source = last;iterator destin = first;for (int i = 0;i < len;i++) {destin[i] = source[i];}_finish -= n;return source;}void clear() {_finish = _start;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};//非成员函数template<class T>void print_vector(const vector<T>& v) {for (const auto& e : v) {std::cout << e << ' ';}std::cout << std::endl;}
}

☀️test.cpp：测试

🎈1.包含头文件

#include"vector.h"
#include<list>
#include<string>
using namespace mine;

🎈2.测试构造、拷贝构造

testVector()函数：

void testVector() {vector<int> v1;print_vector(v1);vector<int> v2(10, 1);print_vector(v2);//1 1 1 1 1 1 1 1 1 1 std::list<int> l1(10, 2);vector<int> v3(l1.begin(), l1.end());print_vector(v3);//2 2 2 2 2 2 2 2 2 2vector<int> v4(v3);print_vector(v4);//2 2 2 2 2 2 2 2 2 2std::list<std::string> lstr(5, "aaa");vector<std::string> vstr(lstr.begin(), lstr.end());print_vector(vstr);//aaa aaa aaa aaa aaa aaa
}

🎈3.测试迭代器

testIterator()函数：

void testIterator() {std::list<int> l(10, 2);vector<int> v(l.begin(), l.end());print_vector(v);std::cout << *v.begin() << ' ' << *(v.end() - 1);
}

🎈4.测试resize

testResize()函数：

void testResize() {vector<int> v(5, 1);print_vector(v);std::cout << v.size() << ' ' << v.capacity() << std::endl;v.resize(2);print_vector(v);std::cout << v.size() << ' ' << v.capacity() << std::endl;v.resize(4);print_vector(v);std::cout << v.size() << ' ' << v.capacity() << std::endl;v.resize(10);print_vector(v);std::cout << v.size() << ' ' << v.capacity() << std::endl;
}

🎈5.测试reserve

testReserve()函数：

void testReserve() {vector<std::string> v(2, "abc");print_vector(v);std::cout << v.capacity() << std::endl;v.reserve(10);print_vector(v);std::cout << v.capacity() << std::endl;
}

🎈6.测试两个重载

testOperator()函数：

void testOperator() {vector<std::string> vstr1(5, "aaa");vector<std::string> vstr2(2, "bbb");print_vector(vstr2);//bbb bbbvstr2 = vstr1;print_vector(vstr2);//aaa aaa aaa aaa aaavstr2[2] = "ccc";print_vector(vstr2);//aaa aaa ccc aaa aaa
}

🎈7.测试insert

testInsert()函数：

void testInsert() {vector<std::string> v;v.insert(v.begin(), "aaa");print_vector(v);//aaav.insert(v.end(), 5, "bbb");print_vector(v);//aaa bbb bbb bbb bbb bbb
}

🎈8.测试删除操作

void test_pop_back_and_erase() {vector<int> v;for (int i = 0;i < 5;i++) {v.push_back(i+1);}print_vector(v);//1 2 3 4 5v.erase(v.begin() + 2);print_vector(v);//1 2 4 5v.pop_back();print_vector(v);//1 2 4v.erase(v.begin(), v.end()-1);print_vector(v);//4
}