斬獲新知——記一次reverse的實現過程，斬獲reverse

斬獲新知——記一次reverse的實現過程，斬獲reverse

最近學習C++，在實現reverse函數的時候，從一個小問題開始，在對這個問題的旁敲側擊當中帶起了更多疑惑，順籐摸瓜之後，盡管沒有將諸多問題完美解答，但整個過程下來卻也覺得似有所獲。最初的問題起自於使用C++實現reverse模板函數時碰到的swap問題，隨之在翻查STL中reverse源碼的實現過程當中產生了其他疑問，如__ITERATOR_CATEGORY，__VALUE_TYPE，__STL_REQUIRES宏的作用，do...while(0)技巧。之後在查找一些資料之後總算對這些問題都有一個解答，如下予以記錄。 

讓swap函數支持迭代器

reverse函數的功能很簡單。在C語言的編程場景中通常用在對字符串的逆轉。在C++當中，STL將其實現為算法當中的一員，其目的自然是為了支持對多種容器的操作。下面是自己第一次嘗試對其進行的實現，但在開頭就遇到問題。 

 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當中的庫函數不都要求要支持迭代器參數嘛。 

感歎人笨了有時真是沒得救，一陣苦思冥想，依舊沒有找到解決辦法。於是開始查找資料，終於在翻看《STL源碼剖析》的過程當中找到了一種方法，也就是借助編譯器的參數推導功能，來完成swap對於迭代器的支持。

 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

原本以為version1.1版本已經是一個很OK的實現版本。但在閱讀了STL當中的實現之後發現完全不如自己所想的那樣，非但如此，源碼當中的實現似乎還藏有不少高深的技法，自己反倒被搞得更加糊塗。一起看下STL當中是如何實現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!!! 

省思錄：生活似乎總是喜歡和人開玩笑，現實當中往往自己表現得非常樂觀的時候，往往就是失望的前奏。真是應了鬼腳七常說的那句話：“沒有期望，一切都是驚喜。”   對於上面幾個問題，自己按照它們對應的知識點進行了簡單劃分，分別分成了I，II和III這三個問題，並分別進行解答。   問題I: 為什麼reverse實現當中要進行分層實現？version1.1版本不行嗎？ 對比兩個版本當中的主要邏輯，似乎沒有什麼不一樣的地方。對於隨機迭代器的處理部分，完全可以復用雙向迭代器的處理，為什麼要一分為二？

 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的實現高手沒有按照那樣去做呢？ 

先假設STL當前這樣的實現自有其考慮，詳細對比每一條語句不難發現針對隨機訪問迭代器的處理來得更高效，在兩者的圈復雜度上，針對雙向迭代器的實現比隨機訪問迭代器的實現大1，相比之下它多了一倍的判斷操作。因此，便可明白其分為兩層架構實現的用意主要為了效率。   這裡或許有人會問，既然隨機訪問迭代器的處理高效，能不能讓雙向迭代器的處理也復用隨機訪問迭代器的處理呢？顯然是不可以的，原因是對於雙向迭代器來說，並不能保證__first < __last一判斷的有效性，這其實也是隨機訪問迭代器與其他分類迭代器的主要區別之一，可以拿鏈表與數組類比一下即可：）   綜上，問題I 即可解答：version1.1版本是可行的，但不是最優的實現，而STL的實現上效率是極其重要的一個考慮因素。   問題II: __ITERATOR_CATEGORY與__VALUE_TYPE是干什麼的？ 這個問題的解答不得不提到C++當中的traits編程技法，也揭露了version1.1版本的一個不足。上面提到了其第一個不足為效率低，那麼這裡要提到的第二個不足則是其可擴展性。version1.1版本當中使用了編譯器的參數推導功能，從而可以在一個函數當中通過迭代器類型推算出它的value type，但按照上面的方式，對於一個返回值為迭代器指向元素類型的函數而言，編譯器的參數推導功能是無法運作的。並且由此催生了C++ STL實現當中的traits編程技法。   具體有關traits編程技法這裡不展開，自己一言兩語也是講不清楚，在侯大師的《STL源碼剖析》當中可知其來龍去脈。簡單來說，__ITERATOR_CATEGORY和__VALUE_TYPE的產生都是traits機制當中的一個方法論的實現。__ITERATOR_CATEGORY借助了函數重載來使得算法支持不同迭代器，從而盡可能提高算法執行效率。而__VALUE_TYPE的產生則是源於上面的一個基本問題：“如何可以通過迭代器獲知其value type”。    問題III: __STL_REQUIRES與__STL_CONVERTIBLE有什麼用？ 這個，從何說起？在查看STL中reverse源碼的開始就留意到這兩個宏，兩者的實現顯得晦澀難懂的，所以把它留到最後來解答。在這裡有篇文章，從中可以得知這兩個宏與STL當中的concept機制有關，你也可以在之前劉未鵬的一篇文章裡面得到更多的信息 。   簡單說來，concept機制是一種針對泛型編程的一種檢測機制，用來幫助在模板的編程時針對各個參數提供有效性檢查，相當於一種特別的assert機制。如下見__STL_REQUIRES與__STL_CONVERTIBLE的源代碼：

 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)的技巧

在探究那些__STL_REQUIRES, __STL_CONVERTIBLE宏時，除了對宏本身不知其意，對於宏定義當中一再使用的do...while(0)式的語句同樣感到迷惑不解。所以，之後的一些工作也圍繞do...while(0)展開。網上有幾篇文章，可以參看這裡，這裡，這裡，之後也便有撥開了雲霧之感。自己依照這幾篇文章，對有關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 }

 場景二：定義復雜的宏

提到宏，我們平常更多的是將之與typedef，函數相比較，其他方面似乎鮮有提及。而在STL源碼當中、或者linux內核等開源項目當中如下的用法著實讓人眼前一亮。  

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等判斷語句的使用場景，必須將兩條語句放在一起，所以加上括號。
#define MICRO_FUNC(arg1, arg2) (statement1; statement2) #define MICRO_FUNC(arg1, arg2) (statement1; statement2;)   這種定義編譯會不通過，因為C的語法當中沒有在括號之間使用分號';'的情況。   2）其次：使用{}將兩條語句粘合在一起。 #define MICRO_FUNC(arg1, arg2) {statement1; statement2;}   這樣看起來的確解決了問題，但是在碰到if...else...語句的時候，又將出現問題。比如

1 if (true)
2     MICRO_FUNC(arg1, arg2); // C/C++當中規定分號作為一行語句的結束符號，所以一直以來的編碼習慣上，我們都會在每條語句後面加上分號。
3 else
4     ...

這個時候宏展開將會是這樣子的情況：

1 if (true)
2     {statement1; statement2;}; // 這裡將多了一個分號，這個分號便會承接if條件不滿足時的處理，也就意味著if語句的范圍到這裡結束
3 else
4     ...

此時，else語句掉空，無法通過編譯。

||=== Build: Debug in TestVariableDeclaration (compiler: GNU GCC Compiler) ===| F:\Coding\C\TestVariableDeclaration\main.c||In function 'main':| F:\Coding\C\TestVariableDeclaration\main.c|23|error:  'else' without a previous 'if'| ||=== Build failed: 1 error(s), 0 warning(s) (0 minute(s), 0 second(s)) ===|   當前這種情況的主要原因是多了一個分號，那麼在宏定義當中的statement2後面不要加分號不就行了？ 如果真想到這種改造方式該拍板子咯，其實挺不好意思，我當時就被拍了，因為這個行不通，是C/C++基本的語法概念。   到這裡，就會發現，將do...while(0)語句來對宏進行改造，來得多麼漂亮，又多麼順理成章！ #define MICRO_FUNC(arg1, arg2) do{statement1; statement2;}while(0)   場景三：消除空宏引起的警告

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。 

場景四：優化代碼組織結構，向C98兼容 C89規定了變量的聲明只能夠在語句塊的開頭聲明，因此對於當前一些舊的僅支持C89的編譯器而言，如下的方式是錯誤的。

 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)技巧的簡要歸納，自以為學有所得，也挺覺得心滿意足。予以分享，希望有用：）