STL中的Concept和Boost庫的Concept_Check

在Generic Programming當中，一個重要的概念就是Concept（滑稽的是，如果把這個Concept也翻譯成“概念”，那就狗屁不通了。我傾向于說它是“操作集”）。Concept就是一組操作，如果一個type具有這些操作，那麼就說這個type是這個Concept的一個model。

這其中的思想有那麼一丁點像是OO當中的interface，一個class如果實作了一個interface，那麼它就可以被當作這個interface來用。同樣，如果一個type是一個Concept的model，那麼所有接受這個Concept的操作也就可以接受這個type。

例如，在STL中，stable_sort這個算法必須接受RandomAccessIterator，這裡RandomAccessIterator就是一個Concept，它規定自己的model必須可以進行下标運算，那麼不滿足這個Concept的type就無法被編譯器接受（搞笑的是我在VC71裡面把list<int> 的iterator傳給stable_sort，它居然欣然接受，要知道list的iterator應該隻是一個BidirectionalIterator 啊，比RandomAccessIterator弱多了。不過仔細看看代碼，發現VC71的stable_sort接受BidirectionalIterator就夠了，不知道是好還是壞）。在gcc下面如果傳遞一個BidirectionalIterator給stable_sort，會得到一堆不知所雲的錯誤提示，讓人摸不着頭腦。

C++語言本身并沒有對于Concept的直接支援，STL解決這個問題的辦法是用了一些traits來限制iterator的特性，以達到在編譯時期檢查Concept的目的。但是traits導緻的編譯錯誤提示實在是太可怕了，我非常懷疑有哪個正常人可以從這些錯誤提示推測出自己錯在哪裡。

在boost庫裡面，提供了一個ConceptCheck庫，它可以幫助我們寫出帶有Concept檢查的代碼，而且沒有運作時的開銷，一旦使用者違反Concept限制，輸出的錯誤提示也比較好懂。舉個例子先，如果STL裡面有ConceptCheck，那麼它的stable_sort大約會這樣：

#include <boost/concept_check.hpp>

template <class RandomAccessIter>

void stable_sort(RandomAccessIter first, RandomAccessIter last)

{

function_requires< RandomAccessIteratorConcept<RandomAccessIter> >();

//... bla bla bla......

}

有了這個 function_requires ，如果再傳遞給它list的iterator，編譯器（VC71）就會報這樣的錯：

c:\boost_1_31_0\boost\concept_check.hpp(642): error C2676: 二進制“+=” : “std::list<_Ty>::iterator”不定義該運算符或到預定義運算符可接收的類型的轉換

with

[

_Ty=int

]

當然還有很多别的，但是至少它說了一點：傳入的iterator不滿足某個運算。這對于使用者來說，應當是一個很有用的提示。

使用Concept Check還有一個額外的好處，那就是調用一個 function_requires可遠比寫一些traits容易，而且代碼也清晰好維護。

這個好用的 function_requires 就定義在concept_check.hpp當中：

template <class Concept>

inline void function_requires(mpl::identity<Concept>* = 0)

{

#if !defined(NDEBUG)

void (Concept::*x)() = BOOST_FPTR Concept::constraints;

ignore_unused_variable_warning(x);

#endif

}

換句話說，function_requires隻在Debug中起作用，那麼是不是在Debug當中它就添加了overhead呢？其實也沒有，仔細看看代碼：

void (Concept::*x)() = BOOST_FPTR Concept::constraints;

這一句取constraints的位址。妙就妙在它讓編譯器“注意到”constraints，但又沒有真正調用constraints，而constraints是一個虛函數，做實際的check。例如在RandomAccessIteratorConcept（檢查iterator是否符合RandomAccessIterator的Concept）當中，constraint是這個樣子：

template <class TT>

struct RandomAccessIteratorConcept

{

void constraints() {

function_requires< BidirectionalIteratorConcept<TT> >();

function_requires< ComparableConcept<TT> >();

#ifndef BOOST_NO_STD_ITERATOR_TRAITS

typedef typename std::iterator_traits<TT>::iterator_category C;

function_requires< ConvertibleConcept< C,

std::random_access_iterator_tag> >();

typedef typename std::iterator_traits<TT>::reference R;

#endif

i += n; // require assignment addition operator

i = i + n; i = n + i; // require addition with difference type

i -= n; // require assignment subtraction operator

i = i - n; // require subtraction with difference type

n = i - j; // require difference operator

(void)i[n]; // require element access operator

}

TT a, b;

TT i, j;

#ifndef BOOST_NO_STD_ITERATOR_TRAITS

typename std::iterator_traits<TT>::difference_type n;

#else

std::ptrdiff_t n;

#endif

};

從這個實作中我們完全可以讀出RandomAccessIterator的具體含義：

1. 它必須是一個BidirectionalIterator

2. 它必須滿足“可比較 (Comparable)”的Concept

3. 它還必須滿足“可轉換 (Convertible)”的Concept，而且是轉換成自己的iterator_category類别

4. 它必須定義了reference這個type

5. 這是最重要的，它必須有difference_type，而且可以進行 +, -, +=, -= 的運算

還要記得，由于這個函數沒有真正的被調用過，是以無論你怎麼寫，它都不會變成實際的代碼，是以也不會影響運作效率的！

boost庫除了提供了一系列的Concept Check以外，也鼓勵我們自己寫Concept Check，至于寫法，從這個RandomAccessIteratorConcept的寫法，大家也可以看出些端倪了：很簡單的。