定义自己的迭代器的步骤

定义自己的迭代器的步骤

基本上iterator必须做两件事情
1)必须指向某物
2)他必须能够遍历任何一个有效区间。一旦定义了operator* operator++通常剩下的行为就比较简单了。
必须确定iterator被正确的定义为constant或者mutable。这是常犯的错误之一。不过input iterator不在乎这一点,因为具有只读性。outputIterator具有只写性。
对于其他的类型的iterator就不一样了
定义自己的Iterator时,必须定义五个嵌套类型,iterator_categoryvalue_typedifference_typepointerreference
STL含有一个辅助类,base class iterator,
An empty base class that provides types and that may be used to ensure that a user-defines iterator class works properly with iterator_traits.
template<class Category, class Type, class Distance = ptrdiff_t
class Pointer = Type*, class Reference = Type&>
struct iterator {
typedef Category iterator_category;
typedef Type value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
Remarks
The template class serves as a base type for all iterators. It defines the member types
  • iterator_category (a synonym for the template parameter Category).
  • value_type (a synonym for the template parameter Type).
  • difference_type (a synonym for the template parameter Distance).
  • pointer (a synonym for the template parameter Pointer).
  • reference (a synonym for the template parameter Reference).
Note that value_type should not be a constant type even if pointer points at an object of const Type and reference designates an object of const Type.
下面是一个iterator的完整定义和使用
#include "stdafx.h"
#include <iterator>
using namespace std;
//下面函数主要来定义迭代器,一个专门针对还含有next的铁代器
template <typename Node, typename Reference = Node&, typename Pointer = Node*>
struct node_wrap_base_iterator:public iterator<forward_iterator_tag,Node,ptrdiff_t,Pointer,Reference>
{
typedef node_wrap_base_iterator<Node,Node&,Node*> iterator;
typedef node_wrap_base_iterator<Node,const Node&,const Node*> const_iterator;
Pointer ptr;
node_wrap_base_iterator(Pointer p = 0):ptr(p){}
node_wrap_base_iterator(const iterator& x):ptr(x.ptr){}
Reference operator*()const{return *ptr;}
Pointer operator->()const{return ptr;}
void incr(){ptr=ptr->next;}
node_wrap_base_iterator& operator++(){incr(); return *this;}
node_wrap_base_iterator operator++(int){node_wrap_base_iterator tmp=*this;incr();return tmp;}
bool operator==(const node_wrap_base_iterator& x) const {return ptr==x.ptr;}
bool operator!=(const node_wrap_base_iterator& x) const {return ptr!=x.ptr;}
};
 
测试:

typedef struct Node

{

int value;

Node* next;

}Node;

//重载<<

ostream& operator<<(ostream & out,Node node)

{

out<<node.value;

return out;

 

}

//使用迭代器

template<typename iterator>

void display(iterator begin,iterator end)

{

iterator tmp = begin;

while(tmp!=end&&tmp!=NULL)

{

cout<<*tmp<<" ";

tmp++;

}

cout<<endl;

}

template <typename Iterator>

//学习使用iterator_traits

typename iterator_traits<Iterator>::value_type test_traits(Iterator iter)

{

return *iter;

}

 

#define N 10

typedef node_wrap_base_iterator<Node>::iterator node_iterator;

int _tmain(int argc, _TCHAR* argv[])

{

Node node[N];

for(int i=0; i<N;i++)

{

node[i].value=i;

if(i < N-1)

node[i].next=&node[i+1];

else

node[i].next=NULL;

}

node_iterator beg(node);

node_iterator end(node+N);

display(beg,end);

Node test;

test.value=11;

test.next=NULL;

node_iterator iter(&test);

cout<<test_traits(iter);

cout<<endl;

return 0;

}