C++的封装(十三):迭代器问题
前面讨论了linux风格的链表的做法。那个例子没有用到迭代器。现在把它加上:
class list { public: struct node { pairlink; } handle; list() { handle.link.first=handle.link.second=&handle; } ~list() {} public: struct iterator_st { node *p; }; class iterator : iterator_st{ public: iterator operator++(); iterator operator++(int); iterator operator--(); iterator operator--(int) ; bool operator==(iterator it); }; iterator begin(); iterator end(); };
list部分的代码这里就省略了。参见前文https://blog.csdn.net/aaasssdddd96/article/details/139167455。
list需要创建begin()迭代器和end()迭代器。这两个是iterator类逻辑上的构造函数。这就是iterator的对象工厂了。这部分内容在前文https://blog.csdn.net/aaasssdddd96/article/details/139551253也讨论过了。list创建迭代器对象需要访问iterator的私有数据,所以iterator类应当声明list为友元。自然,友元不是唯一的办法,只要能解决好访问的问题,友元不友元无所谓了。这里打算用前文中讨论的方法来处理这个问题https://blog.csdn.net/aaasssdddd96/article/details/137865098。所以让class iterator 继承了struct iterator_st。这里想说明,在别人的代码里,看到代码不是自己想象的样子,也不用奇怪,因为有各种不同的实现方法。
有了这些之后,就可以给出一个客户化后的遍历的例子:
struct node { int x; list::node node; static struct node *recast(list::node *p) { struct node *q; list::node node::*r= &node::node; reinterpret_cast(q)= reinterpret_cast(p)- reinterpret_cast(r); return q; } }; void disp(list &l) { list::iterator it; node *p; for(it=l.begin(); it!=l.end(); it++){ p= node::recast((list::node*&)it); printf("%d ", p->x); } printf("End.\n"); }
disp()函数中有个iterator不等于的比较。iterator类重载operator!=()是第一反应。但这里不想这么做。因为iterator的对象太简单了,里面只有一个基本指针,如果做成成员函数,无论如何都要传一个this指针,然后婉转的通过指针引用iterator对象。这里想做成值传递,因为值传递更有效。这样在全局重载operator!=运算符。这个全局的operator!=需要访问iterator的私有数据,所以应当在iterator类中声明它是友元。和前面同样的道理,这里也没有。
typedef list::iterator iterator; bool operator!=(iterator i, iterator t) { typedef list::iterator_st iterator_st; return ((iterator_st&)i).p!=((iterator_st&)t).p; }
这些代码加到一起,就可以跑一下了:
#include #include using std::pair; class list { public: struct node { pairlink; } handle; list() { handle.link.first=handle.link.second=&handle; } ~list() {} public: struct iterator_st { node *p; }; class iterator : iterator_st{ public: iterator operator++() { p=p->link.first; return *this; } iterator operator++(int) { iterator q=*this; p=p->link.first; return q; } iterator operator--() { p=p->link.second; return *this; } iterator operator--(int) { iterator q=*this; p=p->link.second; return q; } bool operator==(iterator it) {return p==it.p;} }; iterator begin() {iterator i; ((iterator_st&)i).p=handle.link.first; return i;} iterator end() {iterator i; ((iterator_st&)i).p=&handle; return i;} }; typedef list::iterator iterator; bool operator!=(iterator i, iterator t) {return i!=t;} struct node { int x; list::node node; static struct node *recast(list::node *p) { struct node *q; list::node node::*r= &node::node; reinterpret_cast(q)= reinterpret_cast(p)- reinterpret_cast(r); return q; } }; void disp(list &l) { list::iterator it; node *p; for(it=l.begin(); it!=l.end(); it++){ p= node::recast((list::node*&)it); printf("%d ", p->x); } printf("End.\n"); } int main() { list l; disp(l); return 0; }
刚开始的版本,这里的operator!=代码不小心犯了个错误。因为默认的复制构造函数和赋值函数按位拷贝。顺理成章的误以为代码中的i!=t也会按位比较(实际是递归调用自己)。而编译器也没有报错。这样一run立刻就crash了。
调试看到错误发生在disp()函数中。为了搞清楚究竟发生了什么,用-S编译选项生成它的汇编代码:
LC0: .ascii "%d \0" LC1: .ascii "End.\12\0" .text .align 2 .globl __Z4dispR4list .def __Z4dispR4list; .scl 2; .type 32; .endef __Z4dispR4list: pushl %ebp movl %esp, %ebp subl $24, %esp movl 8(%ebp), %eax movl %eax, (%esp) call __ZN4list5beginEv movl %eax, -12(%ebp) movl -12(%ebp), %eax movl %eax, -4(%ebp) L4: movl 8(%ebp), %eax movl %eax, (%esp) call __ZN4list3endEv movl %eax, -16(%ebp) movl -16(%ebp), %eax movl %eax, 4(%esp) movl -4(%ebp), %eax movl %eax, (%esp) call __ZneN4list8iteratorES0_ testb %al, %al je L5 movl -4(%ebp), %eax movl %eax, (%esp) call __ZN4node6recastEPN4list4nodeE movl %eax, -8(%ebp) movl -8(%ebp), %eax movl (%eax), %eax movl %eax, 4(%esp) movl $LC0, (%esp) call _printf movl $0, 4(%esp) leal -4(%ebp), %eax movl %eax, (%esp) call __ZN4list8iteratorppEi jmp L4 L5: movl $LC1, (%esp) call _printf leave ret
汇编代码看起来虽然比较吃力,但还是可以看到,disp()函数调用了__ZN4list5beginEv函数,对应源代码的list::begin(),然后调用了 __ZN4list3endEv函数,对应源代码的list::end(),然后又调用了 _ZneN4list8iteratorES0,它对应源代码的operator!=。
继续察看__ZneN4list8iteratorES0_的代码:
.globl __ZneN4list8iteratorES0_ .def __ZneN4list8iteratorES0_; .scl 2; .type 32; .endef __ZneN4list8iteratorES0_: pushl %ebp movl %esp, %ebp subl $8, %esp movl 12(%ebp), %eax movl %eax, 4(%esp) movl 8(%ebp), %eax movl %eax, (%esp) call __ZneN4list8iteratorES0_ movzbl %al, %eax leave ret
它传完参数直接调用了自己!所以陷入无限递归了。operator!=中的i!=t递归调用了自己。这是造成crash的原因。哈哈,写的高兴就失误了。找到原因后改正就容易了,就是用((iterator_st&)i).p!=((iterator_st&)t).p来替换i!=t 表达式。这样就成了。
顺便说一下,察看生成的汇编代码时,因为编译器对原函数作了名称转化,运算符重载函数名不易辨认,可在源代码挨着运算符重载换个名字再写一下这个代码,这样在汇编代码中就容易找了。