迭代器示意图：
为什么方式都是一样？ 因为迭代器遍历完当前元素跳到下一个元素，底层数据结构的具体的遍历方式都封装在这个迭代器的++运算符函数了。
所以，作为使用方，我们不需要知道底层的数据结构原理。
我们只知道底层数据元素的遍历都封装在++运算符重载函数里面。
迭代器一般实现成容器的嵌套类型
只有容器底层数据结构内存是连续的，才提供[]运算符的重载
对于vector来说，我们可以通过[]运算符重载函数遍历访问容器，也可以定义迭代器访问容器，也可以使用for_each访问容器
场景1
如果只删除容器中第一个偶数
进程返回为0，没有问题。
如果是把容器中所有的偶数都删除
进程运行出现了意外的中止，不可预期的错误。
进程不是正常结束运行
迭代器失效了，再进行++it就有问题了，是非法操作
场景2
如果只增加元素1次
进程是正常的结束。
如果把break去掉。需要添加元素多次。
进程意外中止
对失效的迭代器加加，就是非法的操作了。
我们分析一下
当我们使用迭代器从首元素开始遍历的时候，遇到一个偶数88，要进行删除操作。
把it指向的元素删除掉，当我们把88删除以后，删除点到容器末尾的位置的所有生成的迭代器就都失效了，也就是删除元素的迭代器本身，和后边有生成的迭代器都失效了，再使用就都出现错误了。
增加元素的情况也是一样的。
删除点或者增加点之前的迭代器都是好的，删除点或者增加点的迭代器及之后的迭代器都是失效的。
增加元素还有一种情况：扩容了，就是在其他地方重新开辟内存，相当于原来的容器底层上保持的迭代器就全部都失效了，因为vector底层是数组，vector的迭代器就是指针，原来的迭代器指向的是原来的数组内存空间，肯定完全失效了。
a：当容器调用erase方法后，当前位置到容器末尾元素的所有的迭代器全部失效了
b：当容器调用insert方法后，当前位置到容器末尾元素的所有的迭代器全部失效了
c：对于insert插入来说，如果引起容器内存扩容，那么原来容器的所有的迭代器就全部失效了
d：不同容器的迭代器是不能进行比较运算的
对插入/删除点的迭代器进行更新操作
我们发现：erase和insert都会返回一个新的迭代器。给当前位置插入元素或者删除元素，当前元素的后边元素都会发生移动，指向当前元素的迭代器就失效了。
当我们增加或者删除操作，会把操作完的当前位置的新的迭代器返回。
（生成当前位置的合法的迭代器并返回）
我们用it去接收返回的更新的迭代器。
我们删除了元素以后，后边的元素都会前移，所以it就不要++了。
//把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
{
it = vec.erase(it);//更新删除当前元素的位置的迭代器
}
else
{
++it;
}
}
我们现在来解决插入元素的问题
插入一个元素，就把原当前位置的元素都后移了。
所以我们的it还要再多执行1次++了。
//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
it = vec.insert(it, *it - 1);
++it;
}
}
总笔记代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100 + 1);
}
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
#if 0
//给vec容器中所有的偶数前面添加一个小于偶数值1的数字
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
if (*it % 2 == 0)
{
it = vec.insert(it, *it-1);
++it;
}
}
#endif
#if 0
//把vec容器中所有的偶数全部删除
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
{
//迭代器失效的问题，第一次调用erase以后，迭代器it就失效了
it = vec.erase(it); // insert(it, val) erase(it)
//break; 迭代器失效了，再进行++it就有问题了，是非法操作
}
else
{
++it;
}
}
#endif
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
return 0;
}
#endif
迭代器的构造函数：
构造完生成1个节点
构造函数的内容相当于头插法
形成链表，记录用户从容器中获取的是哪个元素的迭代器
迭代器的成员：
#include <iostream>
using namespace std;
//定义容器的空间配置器，和C++标准库的allocator实现一样
template<typename T>
struct Allocator
{
T* allocate(size_t size)//负责内存开辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void *p)//负责内存释放
{
free(p);
}
void construct(T *p, const T &val)//负责对象构造
{
new (p) T(val);//定位new
}
void destroy(T *p)//负责对象析构
{
p->~T();// ~T()代表了T类型的析构函数
}
};
/*
容器底层内存开辟，内存释放，对象构造和析构，都通过allocator空间配置器来实现
*/
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
vector(int size = 10)//构造函数
{
//需要把内存开辟和对象构造分开处理
//_first = new T[size];
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()//析构函数
{
//析构容器有效的元素，然后释放_first指针指向的堆内存
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);//把_first指针指向的数组的有效元素进行析构操作
}
_allocator.deallocate(_first);//释放堆上的数组内存
_first = _last = _end = nullptr;
}
vector(const vector<T> &rhs)//拷贝构造函数
{
int size = rhs._end - rhs._first;
//_first = new T[size];
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;
for (int i = 0; i < len; ++i)
{
//_first[i] = rhs._first[i];
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T> &rhs)//重载赋值函数
{
if (this == &rhs)
return *this;
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);//把_first指针指向的数组的有效元素进行析构操作
}
_allocator.deallocate(_first);
int size = rhs._end - rhs._first;
//_first = new T[size];
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;
for (int i = 0; i < len; ++i)
{
//_first[i] = rhs._first[i];
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
return *this;
}
void push_back(const T &val)//向容器末尾添加元素
{
if (full())
expand();
//*_last++ = val; _last指针指向的内存构造一个值为val的对象
_allocator.construct(_last, val);
_last++;
}
void pop_back() // 从容器末尾删除元素
{
if (empty())
return;
//erase(it); verify(it._ptr, _last);
//insert(it, val); verify(it._ptr, _last);
verify(_last - 1, _last);//检查指定范围的迭代器
//--_last; //不仅要把_last指针--，还需要析构删除的元素
--_last;
_allocator.destroy(_last);
}
T back()const//返回容器末尾的元素的值
{
return *(_last - 1);
}
bool full()const { return _last == _end; }
bool empty()const { return _first == _last; }
int size()const { return _last - _first; }
T& operator[](int index) // vec[2]
{
if (index < 0 || index >= size())
{
throw "OutOfRangeException";
}
return _first[index];
}
//#1迭代器一般实现成容器的嵌套类型
class iterator
{
public:
friend class vector<T, Alloc>;
iterator(vector<T, Alloc> *pvec=nullptr
, T *ptr = nullptr)
:_ptr(ptr), _pVec(pvec)
{
Iterator_Base *itb =
new Iterator_Base(this, _pVec->_head._next);
_pVec->_head._next = itb;
}
bool operator!=(const iterator &it)const
{
//检查迭代器的有效性
if (_pVec == nullptr || _pVec != it._pVec)//不同容器的迭代器不能进行比较
{
throw "iterator incompatable!";
}
return _ptr != it._ptr;
}
void operator++()
{
//检查迭代器的有效性
if (_pVec == nullptr)//创建的时候是不为空的
{
throw "iterator invalid!";
}
_ptr++;
}
T& operator*()
{
//检查迭代器的有效性
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
const T& operator*()const
{
//检查迭代器的有效性
if (_pVec == nullptr)
{
throw "iterator invalid!";
}
return *_ptr;
}
private:
T *_ptr;
//当前迭代器迭代的是哪个容器对象
vector<T, Alloc> *_pVec;
};
//需要给容器提供begin和end方法
iterator begin() { return iterator(this, _first); }
iterator end() { return iterator(this, _last); }
//检查迭代器失效
void verify(T *first, T *last)
{
Iterator_Base *pre = &this->_head;
Iterator_Base *it = this->_head._next;
while (it != nullptr)//遍历存储迭代器的链表
{
if (it->_cur->_ptr > first && it->_cur->_ptr <= last)//在指定检查的范围检查，让这个范围里的迭代器失效
{
//迭代器失效，把iterator持有的容器指针置nullptr
it->_cur->_pVec = nullptr;
//删除当前迭代器节点，继续判断后面的迭代器节点是否失效
pre->_next = it->_next;
delete it;
it = pre->_next;
}
else
{
pre = it;
it = it->_next;
}
}
}
//自定义vector容器insert方法的实现
iterator insert(iterator it, const T &val)
{
/*
我们：
1.不考虑扩容 verify(_first - 1, _last);
2.不考虑it._ptr的指针合法性
*/
verify(it._ptr - 1, _last);//检查这个范围的迭代器，让其失效
T *p = _last;//最后一个元素的后继位置
while (p > it._ptr)
{
_allocator.construct(p, *(p-1));//在当前位置p上构造*(p-1)的对象
_allocator.destroy(p - 1);//把p-1位置的对象析构掉
p--;//从后向前走
}
_allocator.construct(p, val);
_last++;
return iterator(this, p);//返回p位置生成的新的迭代器
}
//自定义vector容器erase方法的实现
iterator erase(iterator it)
{
verify(it._ptr - 1, _last);
//检查这个范围的迭代器，让其失效 -1是为了让当前传入的这个迭代器也失效
T *p = it._ptr;
while (p < _last-1)//删除元素，元素的后边位置都要前移
{
_allocator.destroy(p);//析构当前p位置的元素
_allocator.construct(p, *(p + 1));//在当前p位置上构建后一个位置上的元素
p++;//后移
}
_allocator.destroy(p);
_last--;
return iterator(this, it._ptr);
}
private:
T *_first;//指向数组起始的位置
T *_last;//指向数组中有效元素的后继位置
T *_end;//指向数组空间的后继位置
Alloc _allocator; // 定义容器的空间配置器对象
//容器迭代器失效增加代码
struct Iterator_Base
{
Iterator_Base(iterator *c=nullptr, Iterator_Base *n=nullptr)
:_cur(c), _next(n) {}
iterator *_cur;//指向某个迭代器的指针
Iterator_Base *_next;//next指针，保存地址
};
Iterator_Base _head;//头结点，形成链表，记录用户从容器中获取的是哪个元素的迭代器
void expand()//容器的二倍扩容
{
int size = _end - _first;
//T *ptmp = new T[2 * size];
T *ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
//ptmp[i] = _first[i];
_allocator.construct(ptmp + i, _first[i]);
}
//delete[]_first;
for (T *p = _first; p != _last; ++p)
{
_allocator.destroy(p);
}
_allocator.deallocate(_first);
_first = ptmp;
_last = _first + size;
_end = _first + 2 * size;
}
};
int main()
{
vector<int> vec(200);
for (int i = 0; i < 20 ; ++i)
{
vec.push_back(rand() % 100 + 1);
}
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
{
//迭代器失效的问题，第一次调用erase以后，迭代器it就失效了
it = vec.erase(it);//insert(it, val) erase(it)
}
else
{
++it;
}
}
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
#if 0
auto it1 = vec.end();
vec.pop_back();//verify(_last-1, _last)
auto it2 = vec.end();
cout << (it1 != it2) << endl;
int size = vec.size();
for (int i = 0; i < size; ++i)
{
cout << vec[i] << " ";
}
cout << endl;
auto it = vec.begin();
for (; it != vec.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
//foreach
for (int val : vec)//其底层原理，就是通过容器的迭代器来实现容器遍历的
{
cout << val << " ";
}
cout << endl;
#endif
return 0;
}
#endif