摘要：vector 模拟实现讲解（附代码示例），隐藏的浅拷贝，迭代器失效
在进行 vector 的模拟实现之前，我们先粗略浏览一下 stl_vector.h 文件中的源码来确定模拟实现的大体框架。
这里提供一些粗略浏览源码的技巧：
1.不要一行一行地看2.先不要研究细节，先看整体的框架（类：成员变量+成员函数）
3.理解的时候连蒙带猜，再验证自己的猜测
ps.在已经模拟实现过 string类的前提下，vector 的模拟实现的讲解在一些非必要的地方不多赘述，直接给出代码示例。
框架：👇
template<class T>
class vector
{
private:
iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾(指向最后一个有效数据的下一个)
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};首先，同 string 类的匿名实现一样，我们先创建一个自己的命名空间，将 vector 的模拟实现在这个自定义的命名空间中以区分库中的vector。
1. Constructor and Destructor
不多赘述。示例如下。
#pragma once
namespace Bottle
{
template<class T>
class vector
{
public:
// construct and destroy
vector()
{}
~vector()
{
delete[]_start;
_start = _finish = _endOfStorage = nullptr;
}
private:
iterator _start; // 指向数据块的开始
iterator _finish; // 指向有效数据的尾(指向最后一个有效数据的下一个)
iterator _endOfStorage; // 指向存储容量的尾
};
}2. push_back
（1）这里需要顺便实现 size_t capacity()函数 和 size_t size()函数
（2）思路：检查容量 → 插入数据
（注意：检查容量时，如果是遵循两倍扩容的思路，就需要注意容量为0的情况，如果此时直接按两倍扩容会导致错误）
代码示例：
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
//push_back
void push_back(const T& x)
{
if (_finish == _endOfStorage)
{
//check capacity
size_t new_capacity = capacity() == 0 ? 4 : (capacity() * 2);
reserve(new_capacity);
}
*(_finish) = x;//push back
++_finish;
}
3. reserve
思路：开新空间 → 拷贝数据到新空间 → 指向新空间（ps.原则上只扩容不缩容）
- 关于指向新空间这个操作需要注意的问题：不同于 string类 的size数据是由成员变量存储起来的，vector 的size是通过算两个指针之间的偏移量得出的。
如图所示，当 _start 发生改变之后_finish ≠ _start + size()，而应该提前记录下 _finish 相对于 _start 的偏移量。
代码示例：
//reserve
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n + 1];//new
size_t sz = size();
memcpy(tmp, _start, sizeof(T) * size());//copy
delete[]_start;
_start = tmp;
_finish = tmp + sz;
_endOfStorage = tmp + n;
tmp = nullptr;
}
}4. Access
1）operator[]
代码示例：
//operatorr[]
T& operator[](const size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T& operator[](const size_t pos)const
{
assert(pos < size());
return *(_start + pos);
}2）iterator
（迭代器实现之后就可以使用范围for了）
代码示例：
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;
}5. resize
有模板(template)之后，C++对内置类型进行了升级，即一切都是对象，以前在C语言里面只有变量，而在之后的C++中是变量，也是对象。
e.g. int vi = int(2);//该语句可看作调用默认构造函数用 ‘2’ 来构造一个 int 类型的对象 vi . (内置类型也会调用构造)
代码示例：
//resize
void resize(size_t n, const T& value = T())
{
if (n <= size())
{
//delete
_finish = _start + n;
}
else
{
reserve(n);//check capacity
size_t len = n - size();
while (len--)
{
*_finish = value;
++_finish;//改变finish的指向就是改变size的大小
}
}
}6. insert
iterator insert(iterator pos, const T& x){……}
- string 模拟实现 的 insert ：
思路：①检查 pos 位置的有效性；②检查容量；③挪动数据；④插入数据（strncpy）。
特殊情况：头插（pos==0）
-
vector ：
思路：①检查 pos 位置的有效性；②检查容量；③挪动数据；④插入数据。特殊情况：头插（pos==0）
-
区别：
string中的挪动数据时比较的是下标和下标，即 size_t 数据类型的比较，头插时比较特殊，下标不断变小的过程中可能会出现“-1>0” 的情况（详情见string类模拟实现的文章）；
vector中挪动数据时比较的是迭代器和迭代器，即 T* （因为这里迭代器的底层实现用的是原生指针）数据类型的比较，所以这里头插不属于特殊情况。但是，这也由此引发了另外的问题——迭代器失效。
迭代器失效
① iterator pos 底层是指针。reserve 扩容之后原空间被释放，而 pos 还指向原空间。所以我们需要获取 pos 相对于 _start 的偏移量。
② iterator pos 是传值传参。如下图所示。（提醒💡：这里也不适合用 传引用传参 (iterator& pos)，要引用只能是 const 引用 (const iterator& pos)，因为在类似 v.insert(v.begin(),数据) 的函数调用中，begin()函数是传值返回，则它的返回值具有常属性，只能用 const 引用，但 const 引用会使 pos 无法被修改，则对于下图所示的迭代器是没有意义的）
代码示例：
//insert
iterator insert(iterator pos, const T& x)
{
//check pos
assert(pos >= _start);
assert(pos <= _finish);
size_t len = pos - _start;//偏移量
//check capacity
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 4 : (capacity() * 2));
pos = _start + len;//reserve之后更新pos
}
for (iterator end = _finish; end > pos; --end)
{
*end = *(end - 1);//move data
}
*pos = x;//pos位置insert data
++_finish;
return pos;
}7. erase
思路：依次挪动数据覆盖
注意：erase 同样会导致迭代器失效。
- 关于erase导致的迭代器失效：
如下图，删除数据中偶数的行为出错是因为 erase 导致的迭代器失效，删除符合条件的元素之后，数据的内容发生了改变，就导致原本指向该元素（被删除的这个元素）的迭代器的指向是未知的，当我们在 erase 之后再去使用这个迭代器，行为也是位置的。
库里面的做法是 erase 函数会返回要删除的指定 pos 位置的元素的下一个元素的位置。
代码示例：
iterator erase(iterator pos)
{
//check pos
assert(pos >= _start);
assert(pos <= _finish);
//move data
for (iterator it = pos + 1; it < _finish; ++it)
{
*(it - 1) = *(it);
}
--_finish;
return pos;
}8. 隐藏的浅拷贝_reserve
memcpy：隐藏的浅拷贝 （ from reserve）（如下图所示，tip.如果这里运用 引用计数的浅拷贝就会很高效）
由上图可知，delete 释放空间，对于自定义类型 string 会自动调用析构函数，导致新空间指向已经被析构掉的空间。因此，拷贝数据最好通过赋值操作来实现，赋值会自动调用拷贝构造进行深拷贝。
代码示例：
//reserve
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n + 1];//new
size_t sz = size();
for (size_t i = 0; i < sz; ++i)//copy
{
tmp[i] = *(_start + i);
}
//memcpy(tmp, _start, sizeof(T) * size());//copy
delete[]_start;
_start = tmp;
_finish = tmp + sz;
_endOfStorage = tmp + n;
tmp = nullptr;
}
}
9. Copy Constructor
思路：
1）初始化成员变量
2）reserve
3）拷贝数据（push_back）
代码示例：
//copy constructor
vector(const vector<T>& v)//copy constructor
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
{
push_back(v[i]);
}
}
10. 赋值重载
现代写法同 string类 的模拟实现，详情见 string类 模拟实习的文章。
代码示例：
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;
}11. 其他构造函数重载
注意：自己写了构造函数之后，编译器不会在生成再生成默认构造，所以在构造函数中必须要有一个默认构造函数。
1)template <class InputIterator> vector (InputIterator first, InputIterator last);
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
size_t len = last - first;
reserve(len);
for (size_t i = 0; i < len; ++i)
{
*(_start + i) = *(first + i);
}
_finish = _start + len;
_endOfStorage = _finish;
}2)vector (size_t n, const T& val = T())
当 T 为 int 类型时，会出现类型匹配的问题，如下图：因此，对于 int 类型需要专门实现的一个函数重载。
vector(size_t n, const T& value = T())
{
reserve(n);
while (n--)
{
push_back(value);
}
}
vector(int n, const T& value = T())
{
reserve(n);
while (n--)
{
push_back(value);
}
}
ps.默认构造函数：
vector()
{}附
完整代码链接：My_vector/My_vector/My_vector.h · fantansy-13-07/Cpp - 码云 - 开源中国 (gitee.com)
END
![[AutoSar]BSW_Com03 DBC详解 （一）](https://img-blog.csdnimg.cn/direct/418aa8b67bd741d7b04ab4c22a2b5837.png)
