【C++】vector的模拟实现

个人主页

⭐一、基本框架

vector是一种类模板，它可以存储不同类型的元素，其底层是一段连续的线性内存空间。

template<class T>
class vector
{
public://普通迭代器typedef T* iterator;//const常量迭代器typedef const T* const_iterator;
private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;

🚆二、默认成员函数

1.构造

构造函数我们又可以分为两种，一种是无参构造，另一种则为带参构造。
无参构造：什么参数都没有传，其内部并没有开辟空间。

//构造
vector()
{};

我们也可以用C++11前置生成默认构造

vector() = default;

带参构造：构造并初始化n个val

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}

2.拷贝构造

先开辟要拷贝对象的空间大小，然后使用范围for进行遍历，不断尾插即可。

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

3.赋值重载

我们可以使用和string一样的思路，直接复用库里面标准的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<T>& operator=(vector<T> v)
{swap(v);return *this;
}

4.析构

完成对空间和资源的释放操作。

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

🎄三、迭代器

vector的begin是返回容器的_start的位置，end则返回容器的_finish的位置。

iterator begin()
{return _start;
}iterator end()
{return _finish;
}

既然有了普通迭代器，我们就会考虑到有const对象的调用，因此就会有const迭代器。

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

⏱️四、容量及大小相关函数

1.size和capacity

size函数是用来返回数据vector对象中的有效数据个数，capacity函数则返回vector对象的容量空间的大小。

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

2.resize和reserve

resize函数是用来调整vector对象中的内容以及大小的。

void resize(size_t n,T val = T())
{//当n<size时，会截断n后面的数据if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish < _start + n){*_finish = val;++_finish;}}
}

reserve函数是完成对对象空间进行扩容操作的，当插入的数据大于对象的空间时，则会进行扩容操作，如果插入的数据小于对象空间时，则不会进行任何操作。

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

这里需要注意的是：在代码最后三行我们可以看出，此时的_start是指向新空间的起始位置，_finish如果想调用size()时，而此时的size()不是之前的size()了。 因为size()的返回值是_finish - _start，而由于_start改变了，而_finish的值并没有发生改变，因此会产生报错。所以我们需要用一个变量来存储旧空间的size()，就可以解决这一问题了。

🎡五、有关增加的函数

1.insert

首先要判断插入的位置是否越界，其次还需判断空间是否需要扩容，接着挪动数据，最后再进行插入操作。

iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <=  _finish);//扩容if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){//挪动数据*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}

2.push_back

这一函数是用来尾插数据的。和insert函数也相似，都是需要判断一下是否需要扩容，再将数据进行插入，然后更新一下_finish即可。

void push_back(const T& x)
{//空间满了就扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

🚀六、有关删除的函数

1.pop_back

我们可以断言一下数据内不为空，然后进行尾删操作。

void pop_back()
{assert(!empty());--_finish;
}

2.erase

首先判断一下需要删除的位置pos是否合法，然后从pos+1的位置开始往前覆盖pos的位置即可完成删除。

void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;
}

3.clear

用来清空数据，只需把起始位置的指针_start赋值给_finish即可。

void clear()
{_finish == _start;
}

🏠七、operator[]运算符重载

普通对象调用版本：检查一下i的位置是否合法，然后用下标+[ ]的方式进行访问即可。

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

const对象调用版本：也是需要检查一下位置是否合法，然后采用下标+[ ]的方式访问。

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

💎八、判空empty

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