(C++ STL)vector类的简单模拟实现与源码展示

vector类的简单模拟实现

一、前言
二、vector 的成员变量
三、vector 部分函数实现
- size、capacity
- reserve
- resize
- insert 与注意事项
- erase
- 构造、析构、赋值拷贝
四、vector 源代码

以下代码环境为 VS2022 C++。

一、前言

vector类本质上就是数据结构中的顺序表。(可参考：顺序表的讲解与实现)

接下来我们来简单实现 vector类和部分对应函数。

参考：legacy.cplusplus.com中的 std::vector

二、vector 的成员变量

在 vector.hpp 中：

namespace my
{template<class T>class vector{// Vector的迭代器是一个原生指针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;}private:iterator _start = nullptr;        // 指向数据块的开始iterator _finish = nullptr;       // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};
}

vector 的成员变量：

vector 所存储数据的类型不确定，则使用模版。
vector 的迭代器本质是指针变量，指向内存的地址。
vector 有三个成员变量，_start、_finish、_endOfStorage，类型为 iterator。本质上都是指针变量，用来定位 vector 在内存上的位置。

vector 在内存中分布如图：

在这里插入图片描述

红色方块表示未开辟的空间，绿色方块表示有效数据，蓝色方块表示剩余存储容量。
这里采用 左闭右开 [ _start，_finish )，即 _start 开始就指向有效元素，_finish 指向最后一个元素的后面，_endOfStorage 同理。

三、vector 部分函数实现

size、capacity

vector 的有效长度和容量，是通过指针计算得到的。

指针 - 指针得到的是中间的元素个数。

在 my::vector 中：

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

reserve

参考：std::vector::reserve

C++ 规定：

原空间小于需求空间时，vector 扩容到需求空间或更多。
原空间大于或等于需求空间时，vector 容量不变。

这里扩容严格按照 2 倍扩容。

在 vector.hpp 中：

template<class T>
void my::vector<T>::reserve(size_t n)
{if (n <= capacity()){return;}size_t newCapacity = capacity() == 0 ? MY_VECTOR_INIT_CAPACITY : capacity() * 2;while (newCapacity < n){newCapacity <<= 1;}iterator newStart = new T[newCapacity];// 只能拷贝内置类型，如 string等非内置类型会失效//memcpy(newStart, _start, sizeof(T) * size());// 使用赋值拷贝for (int i = 0; i < size(); ++i){newStart[i] = _start[i];}_finish = newStart + size();            // 指向代码不能交换位置_endOfStorage = newStart + newCapacity;delete[] _start;_start = newStart;
}

resize

参考：std::vector::resize

在 vector.hpp 中：

template<class T>
void my::vector<T>::resize(size_t n, const T& value)
{if (n > capacity()){reserve(n);iterator it = end();iterator over = begin() + n;while (it != over){*it = value;}}_finish = begin() + n;
}

insert 与注意事项

参考：std::vector::insert

注意：
如果返回类型是在类里定义的，在类外使用时需要加上 typename 确定是类型，否则报错。

如 my::vector<T>::iterator 是类里 typedef 的一个类型，在类外使用时，编译器不能确定它是模版类的类型还是其静态变量，则会报错。

在 vector.hpp 中：

// 编译器不能分辨 my::vector<T>::iterator 是类型还是静态变量，
// 加上 typename 表示其为类型即可解决 
template<class T>   
typename my::vector<T>::iterator my::vector<T>::insert(my::vector<T>::iterator pos, const T& x)
{assert(_start <= pos && pos <= _finish);size_t sz = pos - begin();  // 考虑到扩容后 pos 可能失效，用中间值储存reserve(size() + 1);iterator it = nullptr;for (it = end(); it != begin() + sz; --it){*it = *(it - 1);}*it = x;resize(size() + 1);return it + 1;
}

erase

参考：std::vector::erase

在 vector.hpp 中：

template<class T>
typename my::vector<T>::iterator my::vector<T>::erase(my::vector<T>::iterator pos)
{assert(size() != 0);assert(_start <= pos && pos < _finish);for (iterator it = pos; it != end() - 1; ++it){*it = *(it + 1);}--_finish;return pos;
}

构造、析构、赋值拷贝

参考：std::vector::vector
参考：std::vector::~vector
参考：std::vector::operator=

在 my::vector 中：

        vector() = default; // default 后编译器会自动生成默认构造vector(size_t n, const T& value = T()){reserve(n);resize(n);for (auto& val : *this){val = value;}}vector(int n, const T& value = T()){reserve(n);resize(n);for (auto& val : *this){val = value;}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& val : v){push_back(val);}}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;}~vector(){if (_start != nullptr){delete[] _start;_start = nullptr;}_finish = _endOfStorage = _start;}

四、vector 源代码

在 vector.hpp 中：

#pragma once#include <iostream>
#include <cassert>#define MY_VECTOR_INIT_CAPACITY 4namespace my
{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 begin() const{return _start;}const_iterator end() const{return _finish;}//--------------------------------------vector() = default; // default 后编译器会自动生成默认构造vector(size_t n, const T& value = T()){reserve(n);resize(n);for (auto& val : *this){val = value;}}vector(int n, const T& value = T()){reserve(n);resize(n);for (auto& val : *this){val = value;}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& val : v){push_back(val);}}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;}~vector(){if (_start != nullptr){delete[] _start;_start = nullptr;}_finish = _endOfStorage = _start;}//--------------------------------------size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n);void resize(size_t n, const T& value = T());//--------------------------------------T& operator[](size_t pos){return *(begin() + pos);}const T& operator[](size_t pos) const{return *(begin() + pos);}//--------------------------------------void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}iterator insert(iterator pos, const T& x);iterator erase(iterator pos);private:iterator _start = nullptr;        // 指向数据块的开始iterator _finish = nullptr;       // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};}template<class T>
void my::vector<T>::reserve(size_t n)
{if (n <= capacity()){return;}size_t newCapacity = capacity() == 0 ? MY_VECTOR_INIT_CAPACITY : capacity() * 2;while (newCapacity < n){newCapacity <<= 1;}iterator newStart = new T[newCapacity];// 只能拷贝内置类型，如 string等非内置类型会失效//memcpy(newStart, _start, sizeof(T) * size());// 使用赋值拷贝for (int i = 0; i < size(); ++i){newStart[i] = _start[i];}_finish = newStart + size();            // 指向代码不能交换位置_endOfStorage = newStart + newCapacity;delete[] _start;_start = newStart;
}template<class T>
void my::vector<T>::resize(size_t n, const T& value)
{if (n > capacity()){reserve(n);iterator it = end();iterator over = begin() + n;while (it != over){*it = value;}}_finish = begin() + n;
}// 编译器不能分辨 my::vector<T>::iterator 是类型还是静态变量，
// 加上 typename 表示其为类型即可解决 
template<class T>   
typename my::vector<T>::iterator my::vector<T>::insert(my::vector<T>::iterator pos, const T& x)
{assert(_start <= pos && pos <= _finish);size_t sz = pos - begin();  // 考虑到扩容后 pos 可能失效，用中间值储存reserve(size() + 1);iterator it = nullptr;for (it = end(); it != begin() + sz; --it){*it = *(it - 1);}*it = x;resize(size() + 1);return it + 1;
}template<class T>
typename my::vector<T>::iterator my::vector<T>::erase(my::vector<T>::iterator pos)
{assert(size() != 0);assert(_start <= pos && pos < _finish);for (iterator it = pos; it != end() - 1; ++it){*it = *(it + 1);}--_finish;return pos;
}