vector
- 引言（实现概述）
- 接口实现详解
- 默认成员函数
- 构造函数
- 析构函数
- 赋值重载
- 迭代器
- 容量
- size与capacity
- reserve
- resize
- empty
- 元素访问
- 数据修改
- insert
- erase
- push_back与pop_back
- swap
- 模拟实现源码概览
- 总结
引言（实现概述）
在前面，我们介绍了vector的使用：
戳我康vector介绍与使用
在本篇文章中将重点介绍vector的接口实现，通过模拟实现可以更深入的理解与使用vector。
我们可以在网上搜索到vector的实现源码， 与string中使用一个指针指向存储数据的空间，两个整型来刻画size与capacity不同，vector中是通过三个迭代器 _start、_finish、_endOfStorage分别指向数据块的起始位置、有效数据末尾的下一个位置、存储容量末尾的下一个位置来管理数据的。vector中迭代器就是原生指针，本质上就是使用三个指针来管理动态申请的存储数据的空间。
vector是一个类模板，其声明与定义不能分离。我们将模拟实现的vector放在我们创建的命名空间内，以防止与库发生命名冲突。
在vector的模拟实现中，我们只实现一些主要的接口，包括默认成员函数、迭代器、容量、元素访问与数据修改：
接口实现详解
默认成员函数
构造函数
构造函数的模拟实现包括无参构造、n个指定元素构造、迭代器区间构造与拷贝构造：
无参构造：即首先在初始化列表中，将三个属性全部初始化为空指针即可：
vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
n个指定元素构造：
这个重载版本有两个参数，第一个是int，第二个是const T&，表示用n个value构造vector，第二个参数缺省值为其默认构造T()
首先new一块大小为n个元素大小的空间，将其赋值给_start；
然后_finish的值就是_start + n， _endOfStorage的值与_finish相同；
最后for循环将n个value写入空间中：
vector(int n, const T& value = T()) //
{
_start = new T[n];
_finish = _start + n;
_endOfStorage = _finish;
for (int i = 0; i < n; ++i)
{
*(_start + i) = value;
}
}
迭代器区间构造：
使用迭代器区间的构造，是一个函数模板，即可以使用其他容器的迭代器区间来构造vector。
这个重载版本的实现有许多方式，这里的实现是偷懒版本的，即首先将三个属性初始化为空指针后，再复用push_back（后面实现）来将迭代器区间中的元素尾插到新vector中：
template<class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
while (first < last)
{
push_back(*first);
++first;
}
}
拷贝构造：
拷贝构造时，首先将三个属性都初始化为空指针；
然后使用reserve（后面会实现）将新vector扩容与原vector一致；
最后循环将原vector中的数据拷贝到新vector中即可：
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
int sz = v.size();
reserve(sz);
for (int i = 0; i < sz; ++i)
{
*(_start + i) = v[i];
}
}
析构函数
析构函数即释放动态申请的资源，即delete[] _start即可，同时可以顺便将三个属性均置空：
~vector()
{
if (_start != nullptr)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
赋值重载
在实现赋值运算符重载时，存在深浅拷贝的问题，为了简便我们使用现代版本：
现代版本的参数类型为vector<T>，而不是引用，这就使得vector对象在传参时会生成一个临时对象，我们将这个临时对象与要替换的对象*this互换，就实现了将一个对象赋值到了*this，最后返回*this即可，临时对象会在函数栈帧销毁时析构（swap后面实现）。
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
迭代器
vector的迭代器本质上就是原生指针，所以我们只需要将T* 重命名为iterator即可实现迭代器，并且具有原生指针的++、--、+、-、指针相减等的属性：
typedef T* iterator;
typedef const T* const_iterator;
与string部分相同，我们暂时只实现begin与end，关于反向迭代器的实现在后面会详细介绍。
begin返回首元素的地址，end返回尾元素下一个位置的地址，他们分别重载有const版本：
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
容量
size与capacity
之前讲到vector迭代器的底层是原生指针，支持指针减指针的操作。
对于size即元素的个数，_finish - _start的值即空间中数据的末尾的下一个位置的指针减首元素位置的指针，即元素个数；
对于capacity即容量的大小，_endOfStorage - _start的值即空间末尾下一个位置的指针减首元素位置的指针，即容量大小：
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
reserve
reserve用于扩容
对于C++而言，使用new扩容时，必须进行重新开辟空间，将原空间中的元素转移至新空间，最后释放原空间的操作。这样的过程将是十分影响效率的：
在库实现中，当传参的n大于原容量时，reserve会实现扩容，小于原容量时，reserve不进行缩容操作。所以我们模拟实现时，先判断n是否大于原容量，当大于原容量时在再进行后续操作；
首先new一块大小为n个元素大小的空间；
然后就需要挪动数据，需要注意的是，不能使用memcpy来拷贝数据到新空间中，因为memcpy是逐字节拷贝，而自定义类型是会有动态申请的资源的，这样在释放原空间时就会使新空间中的属性为野指针，当生命周期结束时释放资源时就会释放野指针从而崩溃。所以我们需要调用operator=逐一拷贝数据到新空间中，并释放原空间；
最后令_start指向新空间的首元素，_finish指向数据的结尾（可以在释放前记录size的值，此时加上即可），_endOfStorage指向空间的结尾，即_start + n：
void reserve(size_t n)
{
if (n > capacity())
{
T* temp = new T[n];
int sz = size();
if (sz != 0)
{
//当T为自定义类型时，memcpy为浅拷贝，temp中的自定义类型的数据与*this是相同的，delete调析构释放原空间就会使temp中数据为野指针
//memcpy(temp, cbegin(), sizeof(T) * size());
for (size_t i = 0; i < size(); ++i)
{
*(temp + i) = *(_start + i);
}
delete[] _start;
}
_start = temp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
resize
resize用于改变元素个数
当n小于元素个数时，删除多于的元素；n大于元素个数时，使用指定的元素value补足（value为缺省参数，缺省值为T()）
首先判断n是否大于元素个数，当大于元素个数时还需要进一步判断n是否大于容量需要扩容；
之后逐一用value补足，这里同样需要是用operator=，来避免浅拷贝带来的问题，并调整_finish的指向；
当小于元素个数时，直接将_finish的值调整为_start + n即可：
void resize(size_t n, const T& value = T())
{
if (n > size())
{
if (n > capacity())
{
reserve(n);
}
int oldSize = size();
_finish = _start + n;
for (size_t i = oldSize; i < n; ++i)
{
*(_start + i) = value;
}
}
else
{
_finish = _start + n;
}
}
empty
empty用于判断vector是否为空，为空返回true，否则返回false。这里复用size即可，当size返回0时即为空：
bool empty()
{
if (size() == 0)
{
return true;
}
return false;
}
元素访问
元素访问即实现operator[]，可以实现通过下标访问元素：
有两个重载版本即普通对象与const对象。
首先判断pos是否越界，因为pos为无符号整型，所以只需要判断_start + pos 是否小于 _finish即可；
然后直接返回_start + pos的解引用即可：
T& operator[](size_t pos)
{
assert(_start + pos < _finish);
return *(_start + pos);
}
const T& operator[](size_t pos) const
{
assert(_start + pos < _finish);
return *(_start + pos);
}
数据修改
insert
insert用于在pos位置插入数据，模拟实现insert时，我们只实现在pos位置（迭代器）插入一个元素的情况：
首先判断pos是否越界，没有越界时还需要再判断是否需要扩容；
这里就存在一个问题，在上一篇文章提到了迭代器失效的问题：扩容后，指向原来空间的迭代器pos就会成为野指针而失效。为解决这个问题，我们可以事先计算pos对于_start的相对位置sz，从而在释放原空间后通过这个相对位置在新空间中重新找到pos，即_start + sz；
然后就可以循环将pos位置及以后的元素逐一向后移动一个元素。这个过程是十分影响效率的；
最后将要插入的元素放在pos位置，并++_finish：
iterator insert(iterator pos, const T& x) //pos传参，在reserve后会出现迭代器失效
{
assert(pos >= _start && pos <= _finish);
int sz = pos - _start;
if (size() >= capacity())
{
reserve(capacity() == 0 ? 10 : capacity() * 2);
pos = _start + sz; //解决迭代器失效
}
vector<T>::iterator it = end() - 1;
while (it >= pos)
{
*(it + 1) = *it;
--it;
}
*pos = x;
++_finish;
return _start;
}
erase
erase用于删除一段数据，这里只模拟实现删除pos位置（迭代器）的一个元素：
首先判断pos是否越界，如果没有越界再判断容器是否为空，为空就直接返回_start；
然后循环将pos后面的元素逐一向前移动一个元素（从后向前覆盖）；
最后--_finish，并返回_start：
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
if (empty())
{
return _start;
}
vector<T>::iterator it = pos + 1;
while (it < _endOfStorage)
{
*(it - 1) = *it;
++it;
}
--_finish;
return _start;
}
push_back与pop_back
由于在任意位置插入与删除十分影响效率，头插与头删更甚，所以库中只提供了尾插与尾删的接口，不用挪动数据使得其效率很高：
模拟实现时其实只需要调用上面实现的insert与erase即可：
push_back即在end()的位置插入一个元素x；
pop_back即在end() - 1的位置删除一个元素：
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(end() - 1);
}
swap
swap函数用于交换两个对象的数据：
使用算法库中的swap通过创建临时变量交换的话，就会发生多次深拷贝，十分影响效率。
对于vector对象的交换，只需要逐一交换他们的三个属性即可：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
模拟实现源码概览
（关于反向迭代器的实现在后面会详细介绍，现在可以暂时忽略）
#include<iostream>
#include<cassert>
#include"my_reverse_iterator.h"
namespace qqq
{
template<class T>
class vector
{
public:
/ iterator ///
//vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cbegin() const
{
return _start;
}
const_iterator cend() const
{
return _finish;
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
/// construct and destroy //
vector()
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{}
vector(int n, const T& value = T()) //
{
_start = new T[n];
_finish = _start + n;
_endOfStorage = _finish;
for (int i = 0; i < n; ++i)
{
*(_start + i) = value;
}
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
while (first < last)
{
push_back(*first);
++first;
}
}
//vector(const vector<T>& v)
//{
// _start = new T[v.size()];
// _finish = _start + v.size();
// _endOfStorage = _start + v.capacity();
//
// memcpy(begin(), v.cbegin(), sizeof(T) * v.size());
//}
vector(const vector<T>& v)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
int sz = v.size();
reserve(sz);
for (int i = 0; i < sz; ++i)
{
*(_start + i) = v[i];
}
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start != nullptr)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
capacity ///
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
bool empty()
{
if (size() == 0)
{
return true;
}
return false;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* temp = new T[n];
int sz = size();
if (sz != 0)
{
//当T为自定义类型时，memcpy为浅拷贝，temp中的自定义类型的数据与*this是相同的，delete调析构释放原空间就会使temp中数据为野指针
//memcpy(temp, cbegin(), sizeof(T) * size());
for (size_t i = 0; i < size(); ++i)
{
*(temp + i) = *(_start + i);
}
delete[] _start;
}
_start = temp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
if (n > size())
{
if (n > capacity())
{
reserve(n);
}
int oldSize = size();
_finish = _start + n;
for (size_t i = oldSize; i < n; ++i)
{
*(_start + i) = value;
}
}
else
{
_finish = _start + n;
}
}
///access
T& operator[](size_t pos)
{
assert(_start + pos < _finish);
return *(_start + pos);
}
const T& operator[](size_t pos) const
{
assert(_start + pos < _finish);
return *(_start + pos);
}
///modify/
void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(end() - 1);
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
iterator insert(iterator pos, const T& x)//pos传参，在reserve后会出现迭代器失效
{
assert(pos >= _start && pos <= _finish);
int sz = pos - _start;
if (size() >= capacity())
{
reserve(capacity() == 0 ? 10 : capacity() * 2);
pos = _start + sz; //解决迭代器失效
}
vector<T>::iterator it = end() - 1;
while (it >= pos)
{
*(it + 1) = *it;
--it;
}
*pos = x;
++_finish;
return _start;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
if (empty())
{
return _start;
}
vector<T>::iterator it = pos + 1;
while (it < _endOfStorage)
{
*(it - 1) = *it;
++it;
}
--_finish;
return _start;
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾
iterator _endOfStorage; // 指向存储容量的尾
};
}
总结
到此，关于vector的主要接口实现就结束了
相信通过接口的模拟实现可以使我们更深入的了解vector
关于STL容器的介绍才刚刚开始，欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出
如果本文对你有帮助，希望一键三连哦
希望与大家共同进步哦
