???? 樊梓慕： 个人主页
???? 个人专栏： 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》
???? 每一个不曾起舞的日子，都是对生命的辜负
本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题，都是一些需要注意的细节问题，希望与大家共勉。
欢迎大家???? 收藏 ????以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码： ???? fanfei_c的仓库 ????
=========================================================================
迭代器失效可以大致总结为：
之前我们说迭代器的底层可以理解为指针，那么迭代器失效其实就是『 底层指针的指向发生了改变，而迭代器没有』，这就会导致使用迭代器时报错或者出现错误数据。
并且迭代器失效一般具有下面的特点：
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, old * sizeof(T));
//delete[] _start;
for (size_t i = 0; i < old; i++)//解决方案
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endOfStorage = _start + n;
}
}可以看到我注释掉的代码，在最开始可能你会利用memcpy来简化代码，一步到位非常方便，但这就引发了一些意想不到的后果：『 迭代器失效』。
假设vector中存储的为string类：
用memcpy会导致：如果调用了reserve函数，执行到memcpy，memcpy实际为一种『 浅拷贝行为』
『 delete[]会调用析构然后释放空间』
执行过memcpy后，如果执行delete[] _start就会调用析构函数，然后string的析构导致_ str成为野指针， 进而导致vector的迭代器_start失效。
同样这个问题到insert的模拟实现处也存在，因为利用了memmove，比如：
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;//保存长度
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
pos = _start + len;//扩容后更新pos的位置，否则pos依旧指向被释放的旧空间
}
//memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
iterator end = _finish - 1;//解决方案
while (end > pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}解决memcpy、memmove浅拷贝行为导致迭代器失效的问题：
以上是模拟实现过程中解决的迭代器时效问题。
那么在应用中，我们可以利用erase、insert的返回值将迭代器重新赋值，防止迭代器失效。
it = s.begin();
while (it != s.end())
{
it = s.erase(it);
// 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
// it位置的迭代器就失效了
// s.erase(it);
++it;
}另一种解决方案是可以利用『 引用计数』的方式，这里我就不多赘述了，不了解的小伙伴可以自行百度。
迭代器区间构造是一种十分精妙的构造方式，它可以将任意类型（只要支持迭代器）初始化给vector，参数只需要传递两个迭代器即可，比如：
template <class InputIterator>//泛型迭代器
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
void test_vector()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
//同类型构造
vector<int> v2(v1.begin(), v1.end());
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
//不同类型构造
vector<int> v3(lt.begin(), lt.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
//甚至是数组
int a[] = { 100, 200, 300 };//底层物理空间连续，天然的迭代器-指针
vector<int> v4(a, a+3); //指向连续物理地址空间的指针就是天然的迭代器，符合迭代器要求
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}但vector中有某类构造函数是这样的：
vector(size_t n, const T& val = T())//将容器初始化为n个val
{
resize(n, val);
}如果你写了这样的代码：
void test_vector()
{
vector<string> v1(5, "1111");//ok
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2(5, 1);//err
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}这就会引发报错：
原因就是你的程序可能没有按你的本意走，你的本意是想『 将v2初始化为5个1』。
可是编译器会将5和1识别为迭代器，因为5和1的类型相同，不需要发生类型转换。
为什么不会识别为(size_t n,const T& val = T())呢，很明显编译器也不想发生类型转换，size_t为unsigned char，另一个参数为const T&（这里为int），需要发生类型转转换才可以匹配。
所以为了解决这一问题，我们需要再额外重载一个：
vector(size_t n, const T& val = T())//将容器初始化为n个val
{
resize(n, val);
}
vector(int n, const T& val = T())//为了解决两个参数都为int，会自动匹配迭代器区间初始化函数导致报错
{
resize(n, val);
}虽然看起来好像不太高级，但是实际上STL也是这么做的。
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;
}
// construct and destroy
vector()
{}
vector(const vector<T>& v)
{
//传统写法
/*_start = new T(v.capacity());
memcpy(_start, v._start, v.size() * sizeof(T));
_finish = _start + v.size();
_endOfStorage = _start + v.capacity();*/
//现代写法
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
//迭代器区间初始化 “泛型”
//可以穿任意类型的迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector(size_t n, const T& val = T())//如果传参两个int，会导致不匹配该函数而匹配迭代器区间初始化函数
{
resize(n, val);
}
vector(int n, const T& val = T())//为了解决两个参数都为int，会自动匹配迭代器区间初始化函数导致报错
{
resize(n, val);
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
}
// capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t old = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, old * sizeof(T));//用memcpy会导致模板为string类时，如果vector需要扩容，此时memcpy实际为一种“浅拷贝行为”，string成员_str会因为delete[] _start成为野指针
//delete[] _start;//delete[]会调用析构然后释放空间
//同样这个问题到insert的模拟实现处也存在，因为利用了memmove
for (size_t i = 0; i < old; i++)//解决方案 另一种解决方案是可以利用“引用计数”
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + old;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
if (n > size())
{
if (n > capacity())
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
else
_finish = _start + n;
}
///access///
T& operator[](size_t pos)
{
return _start + pos;
}
const T& operator[](size_t pos)const
{
return _start + pos;
}
///modify/
void push_back(const T& x)
{
//1.判断容量
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
//2.尾插
*_finish = x;
++_finish;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
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)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;//保存长度
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
pos = _start + len;//扩容后更新pos的位置，否则pos依旧指向被释放的旧空间
}
//memmove(pos + 1, pos, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为，可能会造成模板为string类时，野指针的问题
iterator end = _finish - 1;
while (end > pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)//未测试
{
assert(size() > 0);
assert(pos >= _start && pos < _finish);
//memmove(pos , pos+1, (_finish - pos) * sizeof(T));//memmove是一种浅拷贝行为，可能会造成模板为string类时，野指针的问题
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
private:
iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};以上就是本篇文章的全部内容。
模拟实现的意义就是『 让我们更好的使用』，像迭代器失效、构造函数重载-迭代器区间构造导致歧义等问题，只有我们模拟实现过，才能更深切得体会到为什么STL库的设计者要这么写，这么写的意义是什么。
=========================================================================
如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容
????博主很需要大家的支持，你的支持是我创作的不竭动力????
???? ~ 点赞收藏＋关注 ~ ????
=========================================================================