首页 > 代码库 > 斩获新知——记一次reverse的实现过程
斩获新知——记一次reverse的实现过程
让swap函数支持迭代器
1 // version 0.1版本,问题版本 2 template <class IN> 3 void swap_my(IN left, IN right) 4 { 5 // 如何完成? 6 } 7 8 template <class IN> 9 void reverse_my(IN begin, IN end)10 {11 while ((begin != end) && (begin != --end))12 {13 swap_my(begin, end);14 ++begin;15 }16 }17
这是一个没有完工的实现版本。在编写swap_my的时候,尽管可以通过IN知道迭代器的类型,也能够通过*IN实现对迭代器所指向元素的访问,但这个时候我需要知道迭代器所指向的元素的类型(考虑到指代方便,这里将迭代器所指向的元素的类型称为其value type,下文同),以便于申请一局部变量来协助完成swap_my的功能,这便是第一个问题。思前想后没有想出答案,随即更换了一种思路,使用引用来完成其功能,不过这会牵涉到reverse实现中对于swap_my的调用方式,如下:
1 // version 1.0版本,swap仅支持引用参数 2 3 template <class IN> 4 5 void swap_my(IN& left, IN& right) 6 { 7 IN tmp = left; 8 left = right; 9 right = tmp;10 }11 12 template <class IN>13 void reverse_my(IN begin, IN end)14 {15 while ((begin != end) && (begin != --end))16 {17 swap_my(*begin, *end);18 ++begin;19 }20 }
version1.0版本“通过引用来实现swap_my函数”,这的确是一个可以完成功能的reverse版本,但并不完美(后文可见即便reverse实现使用了支持迭代器的swap_my版本也有其不足)。回到最初的问题上面,上面的swap_my版本仅仅引用参数,如果想让swap_my也支持迭代器参数,是不是没有其他办法了?毕竟这要求也不高,STL当中的库函数不都要求要支持迭代器参数嘛。
1 // version 1.1版本,swap仅支持迭代器参数 2 template <class IN, class T> 3 void swap_my(IN begin, IN end, T t) 4 { 5 T tmp = *begin; 6 *begin = *end; 7 *end = tmp; 8 } 9 10 template <class IN>11 void swap_iter(IN begin, IN end)12 {13 swap_my(begin, end, *begin);14 }15 16 template <class IN>17 void reverse_my(IN begin, IN end)18 {19 while ((begin != end) && (begin != --end))20 {21 swap_iter(begin, end);22 ++begin;23 }24 }
将此版本与version1.0版本相比较,其实也就是在reverse与swap_my之间多了一次转换,这次转换通过对迭代器的“解引用(dereference)”操作,将迭代器指向元素的类型剥离了出来,大妙哉!
省思录:作为一名程序员,心中虽然明白一些被业界精灵共同推崇的一些编程书籍,应该早日研读,并借此进阶技术并修得毕业。但是实际当中并没有做好。这一点是自己需要立即加以改进的地方。
不完整的reverse
1 template <class _ForwardIter1, class _ForwardIter2, class _Tp> 2 inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) { 3 _Tp __tmp = *__a; 4 *__a = *__b; 5 *__b = __tmp; 6 } 7 8 template <class _ForwardIter1, class _ForwardIter2> 9 inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {10 __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);11 __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);12 __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,13 typename iterator_traits<_ForwardIter2>::value_type);14 15 __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,16 typename iterator_traits<_ForwardIter1>::value_type);17 __iter_swap(__a, __b,18 __VALUE_TYPE(__a));19 }20 // 以上为swap支持迭代器参数的实现,STL中的reverse实现并未使用支持引用参数的swap。支持引用参数的swap作为单独的库函数出现。21
1 // 如下为reverse的主体实现 2 template <class _BidirectionalIter> 3 void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 4 bidirectional_iterator_tag) { 5 while (true) 6 if (__first == __last || __first == --__last) 7 return; 8 else 9 iter_swap(__first++, __last);10 }11 12 template <class _RandomAccessIter>13 void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,14 random_access_iterator_tag) {15 while (__first < __last)16 iter_swap(__first++, --__last);17 }18 19 template <class _BidirectionalIter>20 inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {21 __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator);22 __reverse(__first, __last, __ITERATOR_CATEGORY(__first));23 }
在打开STL源码时,就如同儿时解决完一道题去对照参考答案一样,本是怀着自信满满的喜悦之情,可阅读之后却反生诸多疑惑:那个__STL_REQUIRES是什么东西?为什么要把reverse分成两层架构,之前自己的那个版本不行嘛?__ITERATOR_CATEGORY是干什么的?还有,那个__STL_CONVERTIBLE站在那里干嘛啊?天啦!还有一个__VALUE_TYPE!!!
1 // 针对双向迭代器的处理 2 3 while (true) 4 if (__first == __last || __first == --__last) 5 return; 6 else 7 iter_swap(__first++, __last); 8 9 // 针对随机访问迭代器的处理10 while (__first < __last)11 iter_swap(__first++, --__last);
正着去想,随机访问迭代器的处理的确可以复用双向迭代器的部分,这的确是没有错的。不过尝试着换一种思路去想,为什么STL的实现高手没有按照那样去做呢?
1 #define __STL_REQUIRES(__type_var, __concept) 2 do { 3 void (*__x)( __type_var ) = __concept##_concept_specification< __type_var > 4 ::__concept##_requirement_violation; __x = __x; } while (0) 5 6 // Use this to check whether type X is convertible to type Y 7 #define __STL_CONVERTIBLE(__type_x, __type_y) 8 do { 9 void (*__x)( __type_x , __type_y ) = _STL_CONVERT_ERROR< __type_x , 10 __type_y >::__type_X_is_not_convertible_to_type_Y; 11 __x = __x; } while (0)
以__STL_REQUIRES源代码为例,宏当中的第一个语句定义了一个函数指针__x,指向针对__concept当中的__type_var对象。接下来的__x = __x会触发编译阶段__concept_concept_specification对应__type_var的实例化,在这个过程当中,一旦发现当前的__type_var并不能满足__concept的一些条件,这个时候就会出错(尽管报错的信息也是千百怪,好歹会给予一个提示)。__STL_CONVERTIBLE的基本原理大致也如此。自己当前对这一块还没有达到完全理解的程度,所以具体的原理留待日后分析。
do...while(0)的技巧
1 int TestFunc() 2 { 3 somestruct *ptr = malloc (...); 4 5 ... 6 if (error) 7 { 8 free(ptr ); 9 return -1;10 }11 ...12 if (error)13 {14 free(ptr );15 return -1;16 }17 ...18 19 free(ptr );20 return 0;21 }
如上,代码中涉及到对多个函数调用的处理,当函数调用返回失败并且需要进行一些相同的操作,常见如释放内存的操作;在这种情况下,如果针对每一个函数调用进行单独的处理就会显得冗余、臃肿不堪,这时可以对其进行优化。
1 int TestFunc() 2 { 3 somestruct *ptr = malloc (...); 4 5 ... 6 if (error) 7 goto ErrorCatch; 8 ... 9 if (error)10 goto ErrorCatch;11 ...12 free(ptr );13 return 0;14 15 ErrorCatch:16 free(ptr );17 return -1;18 }
尽管上述的代码在结构上面显得工整和整洁,但不幸的是,它使用了goto语句,而goto语句在软件工程学当中是一直被诟病、不建议使用的。而这个时候使用do...while(0)语句进行优化来得那么的“柳暗花明”了。
1 int TestFunc() 2 { 3 somestruct *ptr = malloc (...); 4 5 ... 6 do 7 { 8 if (error) 9 break;10 ...11 if (error)12 break;13 ...14 15 free(ptr );16 return 0;17 }while(0)18 19 free(ptr );20 return -1;21 }
场景二:定义复杂的宏
1 #define __STL_REQUIRES(__type_var, __concept) 2 do { 3 void (*__x)( __type_var ) = __concept##_concept_specification< __type_var >4 ::__concept##_requirement_violation; __x = __x; } while (0)
平时使用到的宏,通常只见单个语句,而如上的宏定义当中则包括了两条执行语句。我们可以试着去想一想,对于定义一个包含多个语句的宏,我们该如何去完成它:)如下是我自己的思考过程,很傻瓜,不过有利于自己的理解。
1 if (true)2 MICRO_FUNC(arg1, arg2); // C/C++当中规定分号作为一行语句的结束符号,所以一直以来的编码习惯上,我们都会在每条语句后面加上分号。3 else4 ...
这个时候宏展开将会是这样子的情况:
1 if (true)2 {statement1; statement2;}; // 这里将多了一个分号,这个分号便会承接if条件不满足时的处理,也就意味着if语句的范围到这里结束3 else4 ...
此时,else语句掉空,无法通过编译。
1 SGI-STL3.3当中的代码片段2 // Some compilers lack the features that are necessary for concept checks.3 // On those compilers we define the concept check macros to do nothing.4 #define __STL_REQUIRES(__type_var, __concept)5 do {} while(0)
linux-3.3.1 当中的代码片段static void check_spinlock_acquired_node(struct kmem_cache *cachep, int node){#ifdef CONFIG_SMP check_irq_off(); assert_spin_locked(&cachep->nodelists[node]->list_lock);#endif} #else#define check_irq_off() do { } while(0)#define check_irq_on() do { } while(0)#define check_spinlock_acquired(x) do { } while(0)#define check_spinlock_acquired_node(x, y) do { } while(0)#endif
在我们自己做过的项目当中,或许极少使用过空宏的情况,不过它确实存在。比如STL源码当中一些编译器不支持concept check,在内核代码保持对不同体系结构兼容时也有需要使用到空宏的地方(见如上两个代码片段)。对于简单的定义一个宏的值为空,编译器都会提示warning。而do...while(0)语句可以用于消除这些warning。
1 int main() 2 { 3 int ret = TEST_INIT_VALUE; 4 printf("ret = %d\n", ret); 5 6 int val = 0; // 错误。 7 DoSomethingToY(&val); 8 ret = ret + val; 9 10 return ret; 11 }
在C99当中新增了对混合变量的声明(有关C99新增特性的介绍,这篇文章介绍得比较通俗),如果需要考虑到移植性或者在特定的情况需要如此,使用do...while(0)进行修改是一个不错的方法。
1 int main() 2 { 3 int ret = TEST_INIT_VALUE; 4 printf("ret = %d\n", ret); 5 6 do 7 { 8 int val = 0; 9 DoSomethingToY(&val);10 ret = ret + val;11 }while(0);12 13 return ret;14 }
正文完。本篇笔记从一个reverse函数的实现开始,先后涉及到了C++当中的traits机制和concept checking机制,再到对do...while(0)技巧的简要归纳,自以为学有所得,也挺觉得心满意足。予以分享,希望有用:)
斩获新知——记一次reverse的实现过程