福永网站建设公司/网站推广有哪些方式

说到迭代器，首先我们要了解STL提供的六大组件，彼此可以组合套用：
1、 容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。
2、 算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种 function template。
3、 迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
4、 仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator（）的class或class template。一般的函数指针也可视为狭义的仿函数。
5、 配接器（adapters）；一种用来修饰容器、仿函数、迭代器接口的东西。
6、 配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
接下来我们着重学习迭代器!
迭代器：不用暴露出对象的内部结构，iterator在底层已经定义好了，可以在不了解容器的底层实现的情况下更方便地访问容器的数据。
类型：iterator（普通迭代器）；
const_iterator（该类型只能访问容器内元素，但不能改变其值。）；
reverse_iterator（反向迭代器：与正向迭代器只是方向不同）；
const_reverse_iterator。
功能：迭代器能够与算法互不干扰的发展，最后又能无间隙地粘合起来，重载了*，++，==，！=，=运算符。
使用：在不需要清楚容器底层实现机制的条件下，更方便的访问容器的数据。通过一定的封装暴露出接口，然后再进行使用。
迭代器内部构造

#include<iostream>
#include<list>
#include<string>
using namespace std;
template<class T,class Ref,class ptr>//T控制数据类型，Ref引用，ptr指针
struct __ListIterator
{
typedef __ListNode<T> Node;
typedef __ListIterator<T,Ref,ptr>Self;Node* _node;__ListIterator(Node* x):node(x)
{}Ptr operator->()
{return &(operator*());
}
Ref operator*()
{return _node->_data;
}
Ptr operator->() const
{return &(operator*()) const;
}
Ref operator*()const
{return _node->_data const;
}
bool operator !=(const Self& s)
{return _node!= s._node;
}
inline Self& operator++()//前置加加返回引用
{_node = _node->_next;return *this;
}
Self& operator++(int)//后置加加返回Self
{Self tmp(*this);_node = _node->_next;return tmp;
}
inline Self& operator--()//前置减减
{_node = _node->_prev;return *this;
}
Self& operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}
bool operator != (const Self& s) const
{return this->_node !=s._node;
}
bool operator == (const Self& s) const
{return !(operator!=(s));
}

通过了解迭代器的构造函数我们似乎发现它在底层封装一个指针，最后对这个类进行各种各样的运算符重载. 让它成为一个拥有指针功能的特殊类.那么它也有类似于野指针的问题，那就是迭代器失效。
迭代器失效问题

    void Erase(Iterator& it){ assert(it != End() && it._node);  Node* cur = it._node;  Node* prev = cur->_prev;  Node* next = cur->_next;  prev->_next = next;  next->_prev = prev;  delete cur;  }  测试部分：int main()  {  List<int> l;  l.PushBack(1);  l.PushBack(2);  l.PushBack(3);  l.PushBack(4);  List<int>::Iterator it = l.Begin();  while (it != l.End())  {  if (*it % 2 == 0)  {l.Erase(it); }  ++it;}it = l.Begin();  while (it != l.End())  {  cout << *it << " ";  ++it;  }  cout << endl;  return 0;
}  

删除所有偶数后预料结果是1 3，但是结果显示却出现了问题

经调试发现，在进入Earse之前调试过程都没有问题，并且在接收第一个要删除的数据也没有问题。

但是在Earse要删除的数据时，却发现it变为了随机值，再++it，生成的还是随机值，直到访问某个*it便会发生访问越界，这里便是导致程序崩溃的原因了。也即是我们的迭代器失效问题。

分析原因：

解决迭代器失效的措施：

   void Erase(Iterator& it)  {  assert(it != End() && it._node);  Node* cur = it._node;  Node* prev = cur->_prev;  Node* next = cur->_next;  prev->_next = next;  next->_prev = prev;  delete cur;  it = prev;}在删除cur之后把cur前面的节点赋值给it

分析：

list的实现：

//带头双向循环链表
template <class T>
class List
{
public:typedef ListNode<T> Node;typedef __ListIterator<T, T&, T*> Iterator;typedef __ListIterator<T, const T&, const T*> ConstIterator;//const迭代器Iterator Begin(){return _head->_next;}ConstIterator Begin() const{return _head->_next;}Iterator End(){return _head;}ConstIterator End()const{return _head;}List(){_head = new Node(T());_head->_next = _head;_head->_prev = _head;}~List(){Clear();delete _head;_head = NULL;}void Clear(){Iterator cur = Begin();while (cur != End()){Node* tmp = cur._node;++cur;delete tmp;}_head->_prev = _head;_head->_next = _head;}List(const List<T>& l){_head = new Node(T());_head->_next = _head;_head->_prev = _head;ConstIterator it = l.Begin();while(it != l.End()){PushBack(*it);++it;}}void PushBack(const T& x){Insert(End(),x);}void PushFront(const T& x){Insert(Begin(), x);}void Insert(Iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* tmp = new Node(x);tmp->_next = cur;cur->_prev = tmp;prev->_next = tmp;tmp->_prev = prev;}void PopBack(){Erase(--End());}void PopFront(){Erase(Begin());}//考虑迭代器失效问题,返回前一位置迭代器void Erase(Iterator& it)  {  assert(it != End() && it._node);  Node* cur = it._node;  Node* prev = cur->_prev;  Node* next = cur->_next;  prev->_next = next;  next->_prev = prev;  delete cur;  it = prev;}void PrintList(){Node* cur = Begin()._node;while (cur != End()._node){cout << cur->_data << " ";cur = cur->_next;}cout << endl;}protected:Node* _head;
};
int main()  
{  List<int> l;  l.PushBack(1);  l.PushBack(2);  l.PushBack(3);  l.PushBack(4);  List<int>::Iterator it = l.Begin();l.PrintList();
}