实现一个数据结构的迭代子,需要定义哪些东西？解决方案
实现一个数据结构的迭代子,需要定义哪些东西？
对于这个哈希表的迭代子,初步这么设想：
/*hash table iterator*/
struct hash_table_iterator
{
struct mapping* mp; /*迭代子当前的位置*/
int size; /*遍历哈希表的大小*/
};
/*新建一个哈希表迭代子*/
struct hash_table_iterator* hash_table_iterator_new(struct hash_table*);
/*遍历哈希表，遍历结束返回0，否则1*/
int hash_table_iterator_step(struct hash_table_iterator*);
/*释放哈希迭代子*/
void hash_table_iterator_free(struct hash_table_iterator*);
用起来如下：
struct hash_table_iterator iterator = hash_table_iterator_new(ht);
while(hash_table_iterator_step(iterator))
{
//do ...
}
hash_table_iterator_free(iterator);
------解决方案--------------------
http://www.cuj.com/experts/1901/austern.htm?topic=experts
----------------------------------
写一个iterator并不难，并且它是扩展C++标准运行库的一个自然方式。但如果你想做正确，还是一些应该知道的关键点的。
标准C++运行库被设计得可扩展的：标准算法（如reverse()和partition()）对预定义的容器（如vector和list）进行操作，并且它们也可以操作于用户自定义的提供了适当iterator的数据结构。对运行库的高效使用包括对它的扩充。
现如今，iterator对绝大多数的C++程序员都不陌生了。Iterator抽象了指针的绝大部分基本特征：forward iterator指向序列中的某个对象，而且它能进行增量运算以指向序列中的下一个元素。(更强的iterator范畴，bidirectional iterator和random iterator提供了额外的遍历序列的方法。更弱的iterator范畴则对绝大多数的数据结构都是不合适的。)
每iterator都有一个范畴类型category_type（对forward iterator来说则是std::forward_iterator_tag），一个value_type (它所指向的对象的类型)，一个difference_type(表示序列中两个元素间距离的一个整数类型)，以及一个pointer_type和reference_type(指向iterator的value_type的指针和引用)。这些类型都可通过std::iterator_traits来访问；当你定义自己的iterator类时，提供它们的最容易的方法是提供嵌套的typedefs： iterator_category，value_type，difference_type，pointer，和reference。
所谓forward iterator就是任何满足C++标准§24.1.3中的需求的类型；标准的那个小节告诉了你要定义什么成员函数和重载哪些运算符。一旦你已经知道iterator需要掌握的信息（以使得它能指向一个元素和找到其下一个元素），定义一个forward iterator只不过是对这些成员函数进行填空。
配对的Iterator
使问题变复杂的一个因素是通常定义一个iterator类是不够的。你可能需要定义两个iterator类，一个允许修改它所指向的对象（*i返回对象的引用），而另一个不允许（*i返回一个const的引用）。运行库预定义的容器类这么做了：举例来说，std::list类，有一个嵌套类型 iterator和另外一个不同的嵌套类型const_iterator；后者可以用来遍历const std::list。list <T> ::iterator和list <T> ::const_iterator的value_type都是T，但reference_type和pointer_type不同：对list <T> ::iterator它们分别是T&和T*，而对list <T> ::const_iterator它们是const T&和const T*。你能将一个list <T> ::iterator转换到一个list <T> ::const_iterator，但(由于const 的正确性的明显理由)不能反过来。
配对的iterator在用户自定义类型中如同在标准运行库预定义类型中一样常见。举例来说，假设你正在定义一个简单的单向链表类。你可能这样开始：
template <class T>
struct slist_node {
T val;
slist_node* next;
slist_node
(const T& t, slist_node* p)
: val(t), next(p) { }
};
template <class T> struct slist {
slist_node <T> * head;
...
};
供slist用的iterator类同样简单：
template <class T>
struct slist_iterator {
typedef std::forward_iterator_tag
iterator_category;
typedef T value_type;
typedef std::ptrdiff_t
difference_type;
typedef T& reference;
typedef T* pointer;
slist_iterator(slist_node <T> * x=0)
: p(x) { }
slist_iterator
(const slist_iterator& i)
: p(i.p) { }
reference operator*() const
{ return p-> val; }
pointer operator-> () const
{ return &(p-> val); }
slist_iterator& operator++() {
p = p-> next;
return *this;
对于这个哈希表的迭代子,初步这么设想：
/*hash table iterator*/
struct hash_table_iterator
{
struct mapping* mp; /*迭代子当前的位置*/
int size; /*遍历哈希表的大小*/
};
/*新建一个哈希表迭代子*/
struct hash_table_iterator* hash_table_iterator_new(struct hash_table*);
/*遍历哈希表，遍历结束返回0，否则1*/
int hash_table_iterator_step(struct hash_table_iterator*);
/*释放哈希迭代子*/
void hash_table_iterator_free(struct hash_table_iterator*);
用起来如下：
struct hash_table_iterator iterator = hash_table_iterator_new(ht);
while(hash_table_iterator_step(iterator))
{
//do ...
}
hash_table_iterator_free(iterator);
------解决方案--------------------
http://www.cuj.com/experts/1901/austern.htm?topic=experts
----------------------------------
写一个iterator并不难，并且它是扩展C++标准运行库的一个自然方式。但如果你想做正确，还是一些应该知道的关键点的。
标准C++运行库被设计得可扩展的：标准算法（如reverse()和partition()）对预定义的容器（如vector和list）进行操作，并且它们也可以操作于用户自定义的提供了适当iterator的数据结构。对运行库的高效使用包括对它的扩充。
现如今，iterator对绝大多数的C++程序员都不陌生了。Iterator抽象了指针的绝大部分基本特征：forward iterator指向序列中的某个对象，而且它能进行增量运算以指向序列中的下一个元素。(更强的iterator范畴，bidirectional iterator和random iterator提供了额外的遍历序列的方法。更弱的iterator范畴则对绝大多数的数据结构都是不合适的。)
每iterator都有一个范畴类型category_type（对forward iterator来说则是std::forward_iterator_tag），一个value_type (它所指向的对象的类型)，一个difference_type(表示序列中两个元素间距离的一个整数类型)，以及一个pointer_type和reference_type(指向iterator的value_type的指针和引用)。这些类型都可通过std::iterator_traits来访问；当你定义自己的iterator类时，提供它们的最容易的方法是提供嵌套的typedefs： iterator_category，value_type，difference_type，pointer，和reference。
所谓forward iterator就是任何满足C++标准§24.1.3中的需求的类型；标准的那个小节告诉了你要定义什么成员函数和重载哪些运算符。一旦你已经知道iterator需要掌握的信息（以使得它能指向一个元素和找到其下一个元素），定义一个forward iterator只不过是对这些成员函数进行填空。
配对的Iterator
使问题变复杂的一个因素是通常定义一个iterator类是不够的。你可能需要定义两个iterator类，一个允许修改它所指向的对象（*i返回对象的引用），而另一个不允许（*i返回一个const的引用）。运行库预定义的容器类这么做了：举例来说，std::list类，有一个嵌套类型 iterator和另外一个不同的嵌套类型const_iterator；后者可以用来遍历const std::list。list <T> ::iterator和list <T> ::const_iterator的value_type都是T，但reference_type和pointer_type不同：对list <T> ::iterator它们分别是T&和T*，而对list <T> ::const_iterator它们是const T&和const T*。你能将一个list <T> ::iterator转换到一个list <T> ::const_iterator，但(由于const 的正确性的明显理由)不能反过来。
配对的iterator在用户自定义类型中如同在标准运行库预定义类型中一样常见。举例来说，假设你正在定义一个简单的单向链表类。你可能这样开始：
template <class T>
struct slist_node {
T val;
slist_node* next;
slist_node
(const T& t, slist_node* p)
: val(t), next(p) { }
};
template <class T> struct slist {
slist_node <T> * head;
...
};
供slist用的iterator类同样简单：
template <class T>
struct slist_iterator {
typedef std::forward_iterator_tag
iterator_category;
typedef T value_type;
typedef std::ptrdiff_t
difference_type;
typedef T& reference;
typedef T* pointer;
slist_iterator(slist_node <T> * x=0)
: p(x) { }
slist_iterator
(const slist_iterator& i)
: p(i.p) { }
reference operator*() const
{ return p-> val; }
pointer operator-> () const
{ return &(p-> val); }
slist_iterator& operator++() {
p = p-> next;
return *this;