2019獨角獸企業重金招聘Python工程師標準>>>

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

讓swap函數支持迭代器

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

//?version?0.1版本，問題版本 template?<class?IN> void?swap_my(IN?left,?IN?right) {//?如何完成？ } template?<class?IN> void?reverse_my(IN?begin,?IN?end) {while?((begin?!=?end)?&&?(begin?!=?--end)){swap_my(begin,?end);++begin;} }

這是一個沒有完工的版本。在編寫swap_my的時候寫不下去了，這個時候盡管可以通過IN知道迭代器的類型，也能夠通過*IN實現對迭代器所指向元素的訪問，但這個時候我需要知道迭代器所指向的元素的類型（這里將迭代器所指向的元素的類型稱為其value type，下文其他地方沿用此稱謂），以便于申請一局部變量來協助完成兩個變量值的對換，這便是第一個問題。思前想后沒有想出答案，隨即更換了一種思路，使用引用來完成其功能，但這隨之而來也需要修改revers現中對于swap_my的調用方式，如下：

//?version?1.0版本，swap僅支持引用參數 template?<class?IN> void?swap_my(IN&?left,?IN&?right) {IN?tmp?=?left;left?=?right;right?=?tmp; } template?<class?IN> void?reverse_my(IN?begin,?IN?end) {while?((begin?!=?end)?&&?(begin?!=?--end)){swap_my(*begin,?*end);++begin;} }

version1.0版本通過"引用"的方式實現了swap_my函數，這的確是一個可以正常運作的reverse版本，但并不完美（在后文可見即便reverse實現上使用了支持迭代器的swap_my版本也仍舊有其不足）。回到最初的問題上面，上面的swap_my版本僅僅引用參數，如果想讓swap_my也支持迭代器參數，是不是沒有其他辦法了？畢竟這要求也不高，STL當中的庫函數不都要求要支持迭代器參數嘛。

苦思冥想仍舊不得其解。于是開始查找資料，之后在翻看《STL源碼剖析》的過程當中找到了一種方法，也就是借助編譯器的參數推導功能，來完成swap對于迭代器的支持。

//?version?1.1版本，swap僅支持迭代器參數 template?<class?IN,?class?T> void?swap_my(IN?begin,?IN?end,?T?t) {T?tmp?=?*begin;*begin?=?*end;*end?=?tmp; } template?<class?IN> void?swap_iter(IN?begin,?IN?end) {swap_my(begin,?end,?*begin); } template?<class?IN> void?reverse_my(IN?begin,?IN?end) {while?((begin?!=?end)?&&?(begin?!=?--end)){swap_iter(begin,?end);++begin;} }

將此版本與version1.0版本相比較，其實也就是在reverse與swap_my之間多了一次轉換，這次轉換通過對迭代器的“解引用(dereference)”操作，將迭代器指向元素的類型活脫脫的剝離了出來，大妙哉！

省思錄：作為一名程序員，心中雖然明白一些被業界精靈共同推崇的一些編程書籍，應該早日研讀，并借此進階技術并修得畢業。但是實際當中并沒有做好。這一點是自己需要立即加以改進的地方。

不完整的reverse

原本以為version1.1版本已經是一個很OK的實現版本。但在對比參照了STL當中reverse模板的實現之后發現完全不如自己所想的那樣，非但如此，源碼當中的實現似乎還藏有不少高深的技法，自己反倒被弄得愈加糊涂。下面一起看下STL當中是如何制造經典的reverse：）

template?<class?_ForwardIter1,?class?_ForwardIter2,?class?_Tp> inline?void?__iter_swap(_ForwardIter1?__a,?_ForwardIter2?__b,?_Tp*)?{_Tp?__tmp?=?*__a;*__a?=?*__b;*__b?=?__tmp; } template?<class?_ForwardIter1,?class?_ForwardIter2> inline?void?iter_swap(_ForwardIter1?__a,?_ForwardIter2?__b)?{__STL_REQUIRES(_ForwardIter1,?_Mutable_ForwardIterator);__STL_REQUIRES(_ForwardIter2,?_Mutable_ForwardIterator);__STL_CONVERTIBLE(typename?iterator_traits<_ForwardIter1>::value_type,typename?iterator_traits<_ForwardIter2>::value_type);__STL_CONVERTIBLE(typename?iterator_traits<_ForwardIter2>::value_type,typename?iterator_traits<_ForwardIter1>::value_type);__iter_swap(__a,?__b,?__VALUE_TYPE(__a)); }? //?以上為swap支持迭代器參數的實現，STL中的reverse實現并未使用支持引用參數的swap。支持引用參數的swap作為單獨的庫函數出現。 //?如下為reverse的主體實現 template?<class?_BidirectionalIter> void?__reverse(_BidirectionalIter?__first,?_BidirectionalIter?__last,bidirectional_iterator_tag)?{while?(true)if?(__first?==?__last?||?__first?==?--__last)return;elseiter_swap(__first++,?__last); } template?<class?_RandomAccessIter> void?__reverse(_RandomAccessIter?__first,?_RandomAccessIter?__last,random_access_iterator_tag)?{while?(__first?<?__last)iter_swap(__first++,?--__last); } template?<class?_BidirectionalIter> inline?void?reverse(_BidirectionalIter?__first,?_BidirectionalIter?__last)?{__STL_REQUIRES(_BidirectionalIter,?_Mutable_BidirectionalIterator);__reverse(__first,?__last,?__ITERATOR_CATEGORY(__first)); }

回憶起在打開STL源碼當時，恰如同小學時候解決完一道題之后去對照參考答案一樣，本是懷著自信滿滿的喜悅之情，可參看答案之后喜悅之情蕩然無存：“kao，又沒有做對！”。在自己閱讀STL當中reverse實現之后反生諸多疑惑：那個__STL_REQUIRES是什么東西？為什么要把reverse分成兩層架構，之前自己的那個版本不行嘛？__ITERATOR_CATEGORY是干什么的？還有，那個__STL_CONVERTIBLE站在那里干嘛啊？天啦！還有一個__VALUE_TYPE!!!

省思錄：生活似乎總是喜歡和人開玩笑，現實當中往往自己表現得非常樂觀的時候，往往就是失望的前奏。真是應了鬼腳七常說的那句話：“沒有期望，一切都是驚喜。”

對于上面幾個問題，自己按照它們所映射的知識進行了簡單劃分，分別分成了I，II和III這三個問題，并分別進行解答。

問題I:?為什么STL中reverse的實現要進行分層實現？我寫的version1.1版本不行嗎？

對比兩個版本當中的主要邏輯，似乎沒有什么不一樣的地方。對于隨機迭代器的處理部分，完全可以復用雙向迭代器的處理，為什么要一分為二？

//?針對雙向迭代器的處理while?(true)if?(__first?==?__last?||?__first?==?--__last)return;elseiter_swap(__first++,?__last);?//?針對隨機訪問迭代器的處理while?(__first?<?__last)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的源代碼吧：

#define?__STL_REQUIRES(__type_var,?__concept)?\ do?{?\void?(*__x)(?__type_var?)?=?__concept##_concept_specification<?__type_var?>\::__concept##_requirement_violation;?__x?=?__x;?}?while?(0) //?Use?this?to?check?whether?type?X?is?convertible?to?type?Y #define?__STL_CONVERTIBLE(__type_x,?__type_y)?\ do?{?\void?(*__x)(?__type_x?,?__type_y?)?=?_STL_CONVERT_ERROR<?__type_x?,?\__type_y?>::__type_X_is_not_convertible_to_type_Y;?\__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() {somestruct?*ptr?=?malloc?(...);...if?(error){free(ptr?);return?-1;}...if?(error){free(ptr?);return?-1;}...free(ptr?);return?0; }

如上，代碼中涉及到對多個函數調用的處理，當函數調用返回失敗并且需要進行一些相同的操作，常見如釋放內存。在這種情況下，如果針對每一個函數調用進行單獨的處理就會顯得冗余、臃腫不堪，這時可以對其略微改進。

int?TestFunc() {somestruct?*ptr?=?malloc?(...);...if?(error)goto?ErrorCatch;...if?(error)goto?ErrorCatch;...free(ptr?);return?0;ErrorCatch:free(ptr?);return?-1; }

盡管上述的代碼在結構上面顯得工整和整潔，但不幸的是，它使用了goto語句，而goto語句在軟件工程學當中是一直被眾人所詬病、不建議使用的（盡管我都還沒有爽過-_-）。而這個時候使用do...while(0)語句進行優化就顯得那么的“柳暗花明”了。

int?TestFunc() {somestruct?*ptr?=?malloc?(...);...do{if?(error)break;...if?(error)break;...free(ptr?);return?0;}while(0)free(ptr?);return?-1; }

2. 定義復雜的宏

提到宏，在我們腦海里面立即浮現出來的可能更多的是將之與typedef，函數相比較之類的面試題目；在平常項目當中使用的可能也是非常簡單的宏定義。而在STL源碼當中、linux內核等開源項目當中如下的用法著實會讓人眼前一亮。

#define?__STL_REQUIRES(__type_var,?__concept)?\ do?{?\void?(*__x)(?__type_var?)?=?__concept##_concept_specification<?__type_var?>\::__concept##_requirement_violation;?__x?=?__x;?}?while?(0)

如前所說，平時使用到的宏，通常只見單個語句，而如上的宏定義當中則包括了兩條執行語句。這里先撇開do...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...語句的時候，又將出現問題。比如

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

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

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

此時，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)

3. 避免空宏引起的警告

?SGI-STL3.3當中的代碼片段 //?Some?compilers?lack?the?features?that?are?necessary?for?concept?checks. //?On?those?compilers?we?define?the?concept?check?macros?to?do?nothing. #define?__STL_REQUIRES(__type_var,?__concept)?do?{}?while(0) linux-3.3.1?當中的代碼片段 static?void?check_spinlock_acquired_node(struct?kmem_cache?*cachep,?int?node) { #ifdef?CONFIG_SMPcheck_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。

4. 優化代碼塊，使代碼的組織更清晰

C89規定了變量的聲明只能夠在語句塊的開頭聲明，因此對于當前一些舊的僅支持C89的編譯器而言，如下的方式是錯誤的。

int?main()? {int?ret?=?TEST_INIT_VALUE;printf("ret?=?%d\n",?ret);?int?val?=?0;?//?錯誤。DoSomethingToY(&val);ret?=?ret?+?val;?return?ret;? }

C99時代，標準中新增了對混合變量的聲明（有關C99新增特性的介紹，這篇文章介紹得比較通俗），盡管如此，如果需要考慮到移植性或者在特定的情況需要如此（比如當前編譯器版本僅支持C89），使用do...while(0)進行修改是一個不錯的方法。

int?main()? {int?ret?=?TEST_INIT_VALUE;printf("ret?=?%d\n",?ret);do{int?val?=?0;DoSomethingToY(&val);ret?=?ret?+?val;}while(0);return?ret; }

?

正文完。筆記從一個reverse函數的實現開始，先后涉及到了C++當中的traits機制和concept checking機制，再到對do...while(0)技巧的簡要歸納，自以為學有所得，也挺覺得心滿意足。予以分享，希望有用：）

?

轉載于:https://my.oschina.net/peter87/blog/343743

總結

以上是生活随笔為你收集整理的疑惑即新知——记一次reverse模板实现过程的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。