【C++初阶】vector的模拟实现

大家好我是沐曦希💕

一、前言

在模拟实现容器时候，我们需要的不是造一个更好的轮子，而是在了解原理更好理解和运用容器。

那么通过查看源码，抽出vector容器主题框架:

template <class T, class Alloc = alloc>
class vector {typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;
protected:iterator start;iterator finish;iterator end_of_storage;
}

本质上与T*a,size_t size,size_t capacity是类似的：

对于size = _finish - _start

对于capacity = _endofstorage-_start

二、无参构造&析构

• 无参构造

初始化值为空。

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

• 析构

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

三、基础接口

1.empty和clear

• empty

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

• clear

void clear()
{_finish = _start; //这里可不能置为nullptr
}

2.size和capacity

• size

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

-capacity

int capacity() const
{return _endofstarge - _start;
}

加const是让const类对象和非const类对象都能调用

3.[]和iterator

这里提供const和非const两个版本，加const是只可读，不能更改，不加const是可读可写。

• []

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

• iterator
  同理普通迭代器和const迭代器版本,同理，范围for循环此时也是可以实现的：

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

四、reserve和resize

• reserve

reserve最大问题是深拷贝，开辟新空间进行赋值的时候如果直接使用memcpy是浅拷贝。

void reserve(size_t n)
{if (n > capacity()){int Oldsize = size();//size需要保存，方便更改_finsihT* tmp = new T[n];//为空不需要拷贝if (_start){for (size_t i = 0; i < Oldsize; ++i){tmp[i] = _start[i];}}_start = tmp;_finish = _start + Oldsize;_endofstarge = _start + n;tmp = nullptr;}
}

• size()要保存

因为size = _finish - _start，_start已经改变了。而_finish没有改变，那么size就是一个任意数了，不再是原来的size了，就需要在开始时候用Oldsize进行存储size

• 使用memcpy问题

memcpy拷贝数据是按字节来拷贝的属于浅拷贝，对于需要在堆开辟空间的自定义类型存在问题，多次释放同一块空间将导致程序崩溃

vector<vector<int>> vv;
vector<int> v(4, 1);
//复用push_back尾插
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
vv.push_back(v);
//需要扩容成2倍
vv.push_back(v);
for (size_t i = 0; i < vv.size(); i++)
{for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;
}

• resize

用n个数据初始化vector，那么就要用n和size进行比对，分情况讨论:
1、当n大于当前的size时，将size扩大到n，扩大的数据为val，若val未给出，则默认为容器所存储类型的默认构造函数所构造出来的值。
 2、当n小于当前的size时，将size缩小到n。

根据resize函数的规则，进入函数我们可以先判断所给n是否小于容器当前的size，若小于，则通过改变_finish的指向，直接将容器的size缩小到n即可，否则先判断该容器是否需要增容，然后再将扩大的数据赋值为val即可。

void resize(size_t n, const T& value = T())
{if (n < size()){_finish = _start + n;}reserve(n); // reserve对于n<capacity是不会做任何事情的for (size_t i = 0; i < n - size(); ++i){_finish[i] = value;}_finish = _start + n;
}

resize的参数初始化值为T类型的构造，这里可不能直接初始化为0，要是T是自定义类型呢？是vector呢？所以这里如果T是vector的化调用的就是vector的构造函数。另外，这里还需要注意的一点是：构造vector的时候是匿名对象，匿名对象具有常性，不可修改所以要加上const修饰。对于内置类型比如int，都是有构造函数的

五、尾插尾删

void push_back(const T& value)
{if (_finish == _endofstarge){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = value;++_finish;
}
void pop_back()
{assert(_start < _finish);if (_finish > _start){--_finish;}
}

六、其他构造

1.迭代器区间构造

vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endofstarge(nullptr)
{while (first != last){push_back(*first);//int不能解引用++first;}
}

类模板的成员函数可以是函数模板，使之可以是任意类型的迭代器区间，包括了自身的迭代器区间构造
另外，初始化列表全部初始化为nullptr，没有初始化就是随机值，出现野指针

2.拷贝构造

初始化列表全都要初始化为nullptr，否则就是随机值

//写法一
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstarge(nullptr)
{reserve(v.capacity());for (const auto& e : v){push_back(e);}
}
//写法二
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstarge, v._endofstarge);
}
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstarge(nullptr)
{vector<T> tmp(v.begin(), v._end());swap(tmp);
}

• 赋值重载

可以复用拷贝构造

//缺陷是不能自己拷贝自己
vector& operator=(vector<T> v)
{swap(v);return *this;
}

这种写法就是有一个小问题：如果是自己拷贝自己呢？加个判断？没用，因为此时已经传值传参过来了，加个判断没啥意义了。但是这个问题不大，我们允许存在，平时自己也很少自己赋值自己。

另外，这里是传值调用，有人会说了：传引用也可以啊，此时如果是引用的话，v2赋值给v1,v1不是v2的拷贝，直接把v2换成了v1,v1换给了v2,v2本身已经发生变化了，这不是赋值了。

七、memcpy问题

如果拷贝的是内置类型的元素，memcpy即高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝，指向同一块空间，假设我们仍然在reserve接口中使用memcpy进行拷贝：

int main()
{bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;
}

问题分析：

1. memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
2. 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

结论：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

八、完整代码

• vector.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace lj
{template<class T>class vector{public:// Vector的迭代器是一个原生指针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;}iterator rbegin(){return _finish;}iterator rend(){return _start;}const_iterator rbegin() const{return _finish;}const_iterator rend() const{return _start;}// construct and destroyvector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}vector(int n, const T& value = T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(n);for (size_t i = 0; i < n; ++i){push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(const vector<T>& v){int* tmp = new T[v.capacity()];for (size_t i = 0; i < v.size(); ++i){tmp[i] = v[i];}_start = tmp;_finish = _start + v.size();_endofstorage = _start + v.capacity;}vector<T>& operator=(vector<T> v){vector tmp(v);_start = _finish = _endofstorage = nullptr;swap(_start, tmp._start);swap(_finish, tmp._finish);swap(_endofstorage, tmp._endofstorage);}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}// capacitysize_t capacity() const{return _endofstorage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){int Oldsize = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];}}_start = tmp;_finish = _start + Oldsize;_endofstorage = _start + n;tmp = nullptr;}}void resize(size_t n, const T& value = T()){if (n <= size()){_finish = _start + n;}reserve(n);for (size_t i = 0; i < n - size(); ++i){_finish[i] = value;}_finish = _start + n;}///access///T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}///modify/void push_back(const T& x){if (_finish == _endofstorage){int newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;++_finish;}void pop_back(){assert(_start < _finish);if (_finish > _start){--_finish;}}void swap(vector<T>& v){vector tmp;tmp._start = _start;_start = v._start;v._start = tmp._start;tmp._finish = _finish;_finish = v._finish;v._finish = tmp._finish;tmp._endofstorage = _endofstorage;_endofstorage = v._endofstorage;v._endofstorage = tmp._endofstorage;tmp._start = tmp._finish = tmp._endofstorage = nullptr;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);size_t Olddel = pos - _start;if (_finish == _endofstorage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}pos = _start + Olddel;auto it = _finish;while (it > pos){*it = *(it - 1);it--;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);auto it = pos;while (it < _finish){(*it) = *(it + 1);it++;}--_finish;return pos;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endofstorage; // 指向存储容量的尾};void test_vector1(){vector<int> v1(10, 2);for (auto e : v1){cout << e << " ";}cout << endl;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);for (auto e : v1){cout << e << " ";}cout << endl;v1.reserve(20);cout << v1.size() << endl;cout << v1.capacity() << endl;vector<int> v2;for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;}void test_vector2(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2(v1.rend(), v1.rbegin());for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v2.resize(10, 1);for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v2.resize(5);for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v2.resize(15, 2);vector<int>::iterator it = v2.begin();while (it < v2.end()){cout << (*it) << " ";++it;}cout << endl;for (size_t i = 0; i < v2.size(); ++i){cout << v2[i] << " ";}cout << endl;v2.pop_back();for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();v2.pop_back();for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v2.swap(v1);cout << "------------------ v1 --------------------" << endl;for (auto e : v1){cout << e << " ";}cout << endl;cout << v1.size() << endl;cout << v1.capacity() << endl;cout << "------------------ v2 --------------------" << endl;for (auto e : v2){cout << e << " ";}cout << endl;cout << v2.size() << endl;cout << v2.capacity() << endl;v1.resize(15);cout << v1.size() << endl;cout << v1.capacity() << endl;v1.insert(v1.begin(), 1);v1.insert(v1.end(), 1);for (auto e : v1){cout << e << " ";}cout << endl;cout << v1.size() << endl;cout << v1.capacity() << endl;}
}