C++_vector简单源码剖析：vector模拟实现

大家好！本文会模拟一个基本的vector类，帮助我们更好的理解vector的内置函数的实现与规则。

先在.h文件声明每个需要实现的函数，需要实现的成员：

namespace bit
{template<class T>class vector{public://1.迭代器// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin();iterator end();const_iterator begin() const ;const_iterator end() const;// 2.构造函数与析构函数vector();vector(int n, const T& value = T());vector<T>& operator= (vector<T> v);template<class InputIterator>vector(InputIterator first, InputIterator last);vector(initializer_list<T> il);vector(const vector<T>& v);~vector();// 3.内存相关size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& value = T());//4.获取T& operator[](size_t pos);const T& operator[](size_t pos)const;//5.修改void push_back(const T& x);void pop_back();void swap(vector<T>& v);iterator insert(iterator pos, const T& x);iterator erase(Iterator pos);private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}

备注：private有三个成员变量，都是迭代器，_start 指向数据块的开始 ,_finish指向有效数据的尾 ,_endOfStorage指向存储容量的尾。

接下来一步一步的剖析实现：

🚀1.迭代器

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

备注: begin()返回首元素的指针，end()返回尾元素下一个位置的指针，当然也要多实现一个const的版本，以适应const string类型。

🚀2.构造函数与析构函数

// 2.构造函数与析构函数vector();vector(int n, const T& value = T());vector<T>& operator= (vector<T> v);template<class InputIterator>vector(InputIterator first, InputIterator last);vector(initializer_list<T> il);vector(const vector<T>& v);~vector();

⚡️2.1 默认构造函数vector()

vector() =default;

备注：vector 不需要特别的默认构造，用编译器生成的就行，我们知道，编译器在我们写了其他的构造函数时是不会生成默认构造的，所以该代码的意思是使编译器强制生成默认构造。

⚡️2.2 vector(int n, const T& value = T())

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

备注： reserve是扩容函数，push_back是尾插函数，后面会实现。

⚡️内置类型也有构造函数

⚡️关于(重要)const T& temp = T()：

在C++中，为了满足模板的需要，为内置类型也添加了默认构造函数

什么意思呢？ 就是关于内置类型也可以这样初始化：

int i = 0;
int j(1);
int k = int();
int x = int(2);

是不是很像类的初始化的形式 ？没错，在C++中，内置类型可以像类一样传参初始化，当然就如原本的内置类型一样，不传参就是随机值，传了的那个形参就是参数的值。

这样做有什么好处呢？我们回到本函数实现的代码，如果T = int , 则：

vector(int num, const int& temp = int())
{reserve(num);for (int i = 0; i < num; i++){push_back(temp);}
};

const int& temp = int()由于int也可以用类的方式给缺省值，被赋予了一个int类型的匿名临时对象，cosnt又为这个临时对象赋予常性，就可以起别名，所以这样的语法就可以通过了。

最后，const T& temp = T()的参数形式可以满足T为自定义类型，也可以满足内置类型

⚡️2.3 赋值重载operator=

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

备注：swap是一个交换private内三个成员的函数，后面会实现。

⚡️2.4 通用迭代器拷贝

template<class InputIterator>
vector(InputIterator first, InputIterator last){reserve(last- first);while(first != last){push_back(*first);first++;}
}

备注：

1. 这里使用的是函数模板，由编译器推断迭代器类型，生成对应的函数。
2. 该函数的意义是支持通过其他类型的迭代器来拷贝内容，例子如下：

int main()
{string s1("123456");vector<int> test1(s1.begin(), s1.end());for (auto e : test1){cout << e<<" ";}
}

输出：49 50 51 52 53 54

这里就做到通过string的迭代器拷贝整个s1到test1

⚡️2.5 vector(initializer_list il)

vector(initializer_list<T> il){reserve(il.size());for (auto e : il){push_back(e);}
}

备注：

1. 先简单介绍一下 initializer_list 是什么， initializer_list是一种特殊的标准库类型，用于在函数参数或对象构造函数中初始化列表初始化的一种方式。它允许你以简洁的方式向函数传递一组值，或者在对象的构造函数中初始化一组值，可以让函数接受不定数量的参数，而在对象构造函数中使用它可以方便地初始化成员变量。

auto test = {1,2,3,4,5};
//这里编译器推断的类型是 initializer_list

2. 借助 initializer_list 我们就可以传入{1,2,3,4}这种形式的数组进行初始化。

int main()
{vector<int> test1 = {1,2,3,4};for (auto e : test1){cout << e<<" ";}
}

输出：1 2 3 4

⚡️2.6 拷贝构造vector(const vector& v)

vector(const vector<T>& temp)
{reserve(temp.capcitity());for (auto e : temp){push_back(e);}
};

备注：无。

⚡️2.6 析构函数~vector()

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

备注：只用释放 头迭代器_start 就行了。

🚀3.内存相关

// 3.内存相关size_t size() const{_finish - _start;}size_t capacity() const{_end_of_storage - _start;}void reserve(size_t n){if( n  > capacity()){size_t len = size();iterator tmp = new iterator[n+1];if(_start){for(int i = 0 ; i < len ; i++){tmp[i] = (*this)[i];}delete[] _start;}_start = tmp;_finish = tmp+len;	_endOfStorage = tmp + n ;		}}void resize(size_t n, const T& value = T()){if(n <= size()){_finish = _start +n;return;}if(n > capacity()){reserve(n);}iterator it = _finish;_finish = _start +n;while(it !=_finish ){*it = value;it++;}}

备注：

1. size() 返回 vector的数据个数， capacity() 返回 vector的数据个数的容量，迭代器相减(本质是指针相减)是迭代器指向位置的距离。
2. reserve()修改内存，本质上是new了一段新空间，将内容拷贝到新空间，再释放旧空间。
3. 关于const T& value = T()的意思上文有讲，在2.2。

🚀4.获取

//4.获取T& operator[](size_t pos){return *(_start + x);}const T& operator[](size_t pos)const{return *(_start + x);}

备注：该函数使vector模板可以像数组一样访问元素，当然也要重载一个const版本。

🚀5.修改

//5.修改iterator insert(iterator pos, const T& x);iterator erase(Iterator pos);void push_back(const T& x);void pop_back();void swap(vector<T>& v);

⚡️5.1 insert插入

iterator insert(iterator pos, T x)
{int len = pos - _start;//记录pos的下标位置if (size() == capcitity())//判断扩容{size_t new_capcitity = capcitity() == 0 ? 4 : capcitity() * 2;reserve(new_capcitity);}iterator end = _finish - 1;//记录最后一个元素pos = _start + len;//重置pos,因为扩容后pos可能会失效while (end >= pos)//从最后一个数据开始，一个一个往后搬{*(end + 1) = *end;end--;}*pos = x;_finish++;return pos; //返回pos位置的指针
};

备注：

1. 关于重置pos，因为从上文的扩容函数可知，扩容的本质是开辟新空间，所以原来的pos可能不再指向新空间的pos位置了，则导致迭代器失效(迭代器指向错误的位置)， 则需要重置。
2. 同时在使用过insert函数的迭代器也是存在迭代器失效的问题，所以，建议失效后迭代器不要访问。除非赋值更新一下这个失效的迭代器，严格一点的编译器会直接报错。
3. 为了解决迭代器失效的问题，insert以返回值的形式返回重新生效的迭代器。

例子：

vector<int> test1 = {1,2,3,4};
int cnt = 2;
vector<int>::iterator pos = test1.begin()+1;
//错误写法，pos会失效
while (cnt--)
{test1.insert(pos, 0);
}
//实在要用的正确写法
while (cnt--)
{pos= test1.insert(pos, 0);
}

⚡️5.2 erase删除

iterator erase(iterator pos)
{if (_start){iterator head = pos;while (head < _finish){*(head) = *(head + 1);head++;}_finish--;}return pos;
};

备注：传入erase的迭代器也不推荐再使用，不同的平台的情况可能不同，可能会出现迭代器失效的问题。

⚡️5.2 push_back尾插

void push_back(const T& x)
{insert(_finish, x);
}

备注：复用insert。

⚡️5.3 pop_back尾删

void pop_back()
{erase(_finish - 1);
}

备注：复用erase。

所有的代码：

#include <assert.h>template <class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;//构造函数vector() = default;vector(const vector<T>& temp){reserve(temp.capcitity());for (auto e : temp){push_back(e);}};template <class other>vector(other begin, other end){reserve(end - begin);while (begin != end){push_back(*begin);begin++;}};vector(int num, const T& temp = T()){reserve(num);for (int i = 0; i < num; i++){push_back(temp);}};vector<T>& operator=(vector<T> v){swap(v);return (*this);};~vector(){delete[] _start;_start = nullptr;_end_of_storage = nullptr;_finish = nullptr;}vector(initializer_list<T> il){reserve(il.size());for (auto e : il){push_back(e);}}// reserve扩容void reserve(size_t n){if (n > capcitity()){size_t len = size();T* tmp = new T[n];if (_start){//不能用memcpy 要考虑深拷贝for (int i = 0; i < len; i++){tmp[i] = (*this)[i];}delete[] _start;}_start = tmp;_finish = tmp + len;_end_of_storage = tmp + n;}};//resize重设resizevoid resize(size_t n, const T& value = T()){/*for (int i = 0; i < n; i++){push_back(value);}*/if (n <= size()){_finish = _start + n;return;}//if (n > capcitity()){reserve(n);}iterator it = _finish;iterator _finish = _start + n;while (it != _finish){*it = value;++it;}}//迭代器iterator begin() {return _start;};iterator end() {return _finish;};const_iterator begin() const{return _start;};const_iterator end() const{return _finish;};//insert插入iterator insert(iterator pos, T x){int len = pos - _start;if (size() == capcitity()){size_t new_capcitity = capcitity() == 0 ? 4 : capcitity() * 2;reserve(new_capcitity);}iterator end = _finish - 1;pos = _start + len;while (end >= pos){*(end + 1) = *end;end--;}*pos = x;_finish++;return pos;};//push_back尾插void push_back(T x){insert(_finish, x);};//pop_back()尾删void pop_back(){erase(_finish - 1);}//capcitity容量size_t capcitity() const{return  _end_of_storage - _start;};//size最后元素下标size_t size() const{return  _finish - _start;};//[]T& operator[](int x){assert(x >= 0);assert(x < size());return *(_start + x);};const T& operator[](size_t x)const{assert(x >= 0);assert(x < size());return *(_start + x);};//删除iterator erase(iterator pos){if (_start){iterator head = pos;while (head < _finish){*(head) = *(head + 1);head++;}_finish--;}return pos;};//void swap(vector<T>& v){std::swap(v._start, _start);std::swap(v._finish, _finish);std::swap(v._end_of_storage, _end_of_storage);};
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;
};

本文就到这里，感谢你看到这里！
我知道一些人看文章喜欢静静看，不评论，但是他会点赞，这样的人，帅气低调有内涵，美丽大方很优雅，明人不说暗话，要你手上的一个点赞！