泛型編程編出來的代碼,適用於任何「吻合某種條件限制」的資料型別。這已成為撰寫可復(fù)用代碼時(shí)的一個(gè)重要選擇。然而,總有一些時(shí)候,泛型不夠好 ─ 有時(shí)候是因?yàn)椴煌男蛣e差距過大,難以產(chǎn)生一致的泛化實(shí)作版本。這個(gè)時(shí)候 traits 技術(shù)就變得相當(dāng)重要。這種技術(shù)可以將那些需要被納入考量的型別性質(zhì)以一種 type by type 的原則,封裝於一個(gè) traits class 內(nèi),於是可以將「由於型別之間的差異,必須撰寫出來以備用」的代碼體積降至最低,并使泛用代碼的體積提升到最高。
考慮一個(gè)例子:當(dāng)我們處理字元字串(character strings)時(shí),常見的一個(gè)操作行為就是決定「以 null 為結(jié)束符號(hào)」的字串的長度。很明顯我們不可能寫出一份泛型代碼取代眾所周知原本就存在的極有效率的解法:是的,C 標(biāo)準(zhǔn)函式 strlen 和 wcslen 通常是以組合語言完成,如果再加上適量的硬體支援,就能夠比 C++ 泛型版本有明顯的速度優(yōu)勢。C++ 標(biāo)準(zhǔn)程式庫的作者了解這一點(diǎn),所以他們抽取出 char 和 wchar_t 的性質(zhì),置於 class char_traits 內(nèi)。於是,泛型代碼一旦處理字元字串,便可以簡單地使用 char_traits<>::length 來決定一個(gè)「以 null 為結(jié)束符號(hào)」的字串的長度,并且很安心地確知 char_traits 的特化版本將采用最適當(dāng)?shù)姆椒▉硗瓿扇蝿?wù)。
Type traits(型別特性)
Class char_traits 是「把一系列與型別相關(guān)的性質(zhì)包裹於單一 class 之內(nèi)」的典型例子,那正是 Nathan Myers 所謂的 baggage class [叁考資料1]。在 Boost type-traits library 中,我們 [叁考資料2] 完成了一組非常特別的 traits classes,其中每一個(gè) classes 都封裝了 C++ 型別系統(tǒng)中的一個(gè)(僅僅一個(gè))特性。所謂特性(trait)指的是,舉個(gè)例子,某型別是否為一個(gè) pointer,或是一個(gè) reference?某型別是否擁有一個(gè) trivial constructor,或是擁有一個(gè) const 修飾詞?這些 type-traits classes 共同享有一致性的設(shè)計(jì):每一個(gè) class 都有一個(gè) member value,那是一個(gè)編譯期常數(shù),如果某型別擁有某種特性,此一常數(shù)的值就是 true,否則就是 false。稍後我將為你展示,這些 classes 可以被使用於泛型編程之中,用來決定某個(gè)型別的特性,并導(dǎo)入對(duì)應(yīng)的最佳化措施。
Boost type-traits library 也內(nèi)含一組 classes,可以針對(duì)某個(gè)型別執(zhí)行專屬的特定的轉(zhuǎn)換。例如它們可以從某個(gè)型別身上移除一個(gè)上層的 const 或 volatile。每一個(gè)用來執(zhí)行轉(zhuǎn)換的 class 都定義有一個(gè) typedef-member type,那便是轉(zhuǎn)換結(jié)果。所有這些 type-traits classes 都被定義於 namespace boost 之中。為求簡化,本文的范例代碼大多省略命名空間的設(shè)定。
實(shí)作(Implementation)
要在這里顯示 type-traits library 的所有實(shí)作內(nèi)容,是不可能的,那真是太多太多了。如果你有這個(gè)需求,請看 Boost library 的源碼。大部份實(shí)作方法都是重復(fù)的,所以這里我只給你一種風(fēng)貌,為你示范這些 classes 如何實(shí)作出來。讓我們從程式庫中最簡單的一個(gè) class 開始。is_void<T> 有一個(gè) member value,如果 T 是 void,它就是 true。
template <typename T>
struct is_void
{ static const bool value = false; };
template <>
struct is_void<void>
{ static const bool value = true; };
在這里,我們定義了 template class is_void 的一個(gè)主版本,并針對(duì)「T 是 void」的情況提供了一個(gè)全特化( full-specialisation)版。雖然 template class 的全特化是一項(xiàng)重要技術(shù),但有時(shí)候我們需要的解決方案介於「完全泛化」和「完全特化」之間。這正是標(biāo)準(zhǔn)委員會(huì)之所以定義出偏特化(partial template-class specialisation)的原因。舉個(gè)例子,讓我們考慮 class boost::is_pointer<T>,這里我們需要一個(gè)主版本,用來處理「T 不為指標(biāo)」的所有情況,以及一個(gè)偏特化版本,用來處理「T 是指標(biāo)」的情況:
template <typename T>
struct is_pointer
{ static const bool value = false; };
template <typename T>
struct is_pointer<T*>
{ static const bool value = true; };
偏特化的語法帶了點(diǎn)不可思議的味道,而且一談到它很容易就耗掉一整篇文章。就像全特化的情形一樣,為了針對(duì)某個(gè) class 寫出一個(gè)偏特化版本,你首先必須宣告 template 主版本。偏特化版本在 class 名稱之後多出一個(gè) <┅> ,其中內(nèi)含偏特化叁數(shù);這些叁數(shù)定義出「將被系結(jié)於偏特化版」的某些型別。究竟什麼叁數(shù)會(huì)(或說能夠)出現(xiàn)於偏特化版本之中,規(guī)則頗為曲折,以下是一個(gè)簡略的規(guī)則。如果你能夠以此型式合法寫出兩個(gè)多載化函式:
void foo(T);
void foo(U);
那麼你就能夠以此型式寫出一個(gè)偏特化版本:
template <typename T>
class c{ /*details*/ };
template <typename T>
class c<U>{ /*details*/ };
這個(gè)簡則并非絕對(duì)成立,但它非常簡單,足以讓你牢牢記住并足夠接近精確的規(guī)則。
至於比較復(fù)雜的偏特化例子,讓我們考慮 class remove_bounds<T>。這個(gè) class 定義了唯一一個(gè) typedef-member type,其型別與 T 相同,但移除任何上層(top level)的 array 邊界;這是「traits class 對(duì)某個(gè)型別進(jìn)行轉(zhuǎn)換」的例子:
template <typename T>
struct remove_bounds
{ typedef T type; };
template <typename T, std::size_t N>
struct remove_bounds<T[N]>
{ typedef T type; };
remove_bounds 的目的是:想像一個(gè)泛型演算法,接受一個(gè) array 型別做為 template 叁數(shù),remove_bounds 會(huì)提供一個(gè)方法,讓你有辦法得知底部(underlying)的 array 型別。例如,remove_bounds<int[4][5]>::type 會(huì)被核定為型別 int[5]。這個(gè)例子也向你展示,在一個(gè)偏特化版本中,template 叁數(shù)的個(gè)數(shù)并不需要吻合 default template 中的個(gè)數(shù)。然而,出現(xiàn)於 class 名稱之後的叁數(shù)個(gè)數(shù)必須吻合 default template 的叁數(shù)個(gè)數(shù)和叁數(shù)型別。
copy 最佳化
現(xiàn)在我要舉一個(gè)例子,說明我們可以如何運(yùn)用 type traits classes。考慮標(biāo)準(zhǔn)程式庫所提供的 copy 演算法:
template<typename Iter1, typename Iter2>
Iter2 copy(Iter1 first, Iter1 last, Iter2 out);
很明顯,寫一個(gè)泛型版本的 copy 絕無問題,它可以處理任何型別的迭代器 Iter1和 Iter2。然而在某種情況下,copy 動(dòng)作可以透過 memcpy 完成。為了能夠以 memcpy 完成 copy,以下條件必須成立:
兩個(gè)迭代器 Iter1 和 Iter2 的型別都必須是指標(biāo)。
Iter1 和 Iter2 都必須指向相同的型別 - 但允許有不同的 const 和volatile 修飾詞。
Iter1 所指的型別必須有一個(gè) trivial assignment operator。
所謂 trivial assignment operator,我的意思是這個(gè)型別如果不是一個(gè)純量型別(scalar types)[叁考資料3],就是:
這個(gè)型別沒有使用者自定的 assignment operator。
這個(gè)型別沒有任何 data members 采用 reference 型式。
所有的 base classes,以及所有的 data member objects 都有 trivial assignment operators。
如果上述所有條件都獲得滿足,那麼這個(gè)型別就可以被 memcpy 直接拷貝,而不使用一個(gè)由編譯器產(chǎn)生的 assignment operator。type-traits library 提供了一個(gè) class has_trivial_assign,使得當(dāng) T 有一個(gè) trivial assignment operator 時(shí),has_trivial_assign<T>::value 為 true。這個(gè) class 只能對(duì)純量型別起作用,但你很輕易就可以將它特殊化,使它適用於那些也擁有 trivial assignment operator 的 class/struct。換一個(gè)角度說,如果 has_trivial_assign 給出錯(cuò)誤的答案,它會(huì)導(dǎo)致安全性方面的錯(cuò)誤。
列表一顯示一個(gè)最佳化(使用 memcpy)的 copy 代碼。代碼之中首先定義一個(gè) template class copier,接受唯一一個(gè) template 叁數(shù) Boolean,然後是一個(gè) static template member function do_copy,執(zhí)行 copy 的泛型版本(也就是比較慢但比較安全的版本)。接下來是一個(gè) copier<true> 特化版本,其中也定義了一個(gè) static template member function do_copy,這一次使用 memcpy 來執(zhí)行最佳化拷貝動(dòng)作。
為了完成整份實(shí)作代碼,現(xiàn)在我們需要一個(gè) copy 版本;如果可以安全使用 memcpy,就讓它呼叫 copier<true>::do_copy 執(zhí)行特化版本,否則就呼叫 copier<false>::do_copy 執(zhí)行泛化版本。這正是列表一的代碼的所作所為。為了了解這些代碼如何運(yùn)作,請看 copy 函式代碼,并首先注意最前面的兩個(gè) typedefs v1_t 和 v2_t。它們使用 std::iterator_traits<Iter1>::value_type 來得知兩個(gè)迭代器所指的是什麼型別,然後將其結(jié)果喂給另一個(gè) type-traits class remove_cv,用以移除上層的 const- 或 volatile-修飾詞,這使 copy 得以比較兩個(gè)型別而不在乎 const- 或 volatile- 修飾詞。接下來,copy 宣告一個(gè)列舉元 can_opt,它將成為 copier 的 template 叁數(shù) - 在這里,宣告為常數(shù)只是為了方便:數(shù)值可以被直接傳遞給 class copier(譯注:我無法理解這一段意思;代碼本身并未出現(xiàn)常數(shù)宣告)。can_opt 的值是根據(jù)「以下所有項(xiàng)目都驗(yàn)證為真」而計(jì)算出來:
首先,兩個(gè)迭代器必須指向相同型別 - 驗(yàn)證方法是透過 type-traits class is_same。
其次,兩個(gè)迭代器都必須是真正的指標(biāo) - 驗(yàn)證方法是透過先前描述過的 class is_pointer。
最後,被迭代器所指的型別必須有一個(gè) trivial assignment operator - 驗(yàn)證方法是透過 has_trivial_assign。
最後,我們可以使用 can_opt 的值做為 template 引數(shù),傳給 copier。這里所呈現(xiàn)的 copy 版本會(huì)根據(jù)它所獲得的叁數(shù)而調(diào)整,如果有可能使用 memcpy,它就會(huì)那麼做,否則就使用一個(gè)泛型的 copy。
值得如此嗎?
許多文章都會(huì)引用這句話:「貿(mào)然實(shí)施最佳化,是各種傷害的根源」("premature optimization is the root of all evil") [叁考資料4]。所以你一定會(huì)問這樣的問題:我們的最佳化是否太過貿(mào)然?是否太過唐突?為了透視這一點(diǎn),我把我們的 copy 版本拿來和一個(gè)傳統(tǒng)的泛型版本做比較 [叁考資料5],結(jié)果顯示於表一。
很明顯,最佳化與否,造成兩個(gè)截然不同的結(jié)果。但我也要持平地說,時(shí)間的量測并不含括「快取裝置誤擊效應(yīng)」(cache miss effects),因此這份結(jié)果并未能在兩個(gè)演算法之間展現(xiàn)精確的比較。然而,或許我們可以加上一些警告,放到「貿(mào)然最佳化」的規(guī)則里頭:
如果你一開始就使用正確的演算法,那麼最佳化就不再有必要。某些情況下,memcpy 是正確的演算法。
如果某個(gè)組件即將在許多地方被許多人使用,那麼最佳化是值得的 - 即使對(duì)少數(shù)使用者而言,最佳化可能是小題大作。
表一:以 copy<const T*, T*> 拷貝1000 個(gè)元素,所花費(fèi)的時(shí)間(微秒)
版本 型別 T 時(shí)間(微秒)
最佳化的 copy char 0.99
傳統(tǒng)的 copy char 8.07
最佳化的 copy int 2.52
傳統(tǒng)的 copy int 8.02
Pair of References
「copy 行為最佳化」這個(gè)實(shí)例告訴我們,type traits 如何被用來在編譯時(shí)期執(zhí)行最佳化策略。type traits 的另一個(gè)重要用途是允許某些「除非運(yùn)用極端的偏特化,否則無法通過編譯」的代碼得以被順利編譯。只要將偏特化行為授權(quán)(delegating)給type traits classes,便有可能做到。關(guān)於這種用法,我舉的例子是一個(gè)可以持有 references 的 pair [叁考資料6]。
首先讓我們檢驗(yàn) "std::pair" 的定義,為了簡化,我略去其中的 comparision operators, default constructor, 和 template copy constructor:
template <typename T1, typename T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(const T1 & nfirst, const T2 & nsecond)
:first(nfirst), second(nsecond) { }
};
此刻這個(gè) "pair" 無法持有 references,因?yàn)槿绱艘粊砥?span lang="EN-US"> constructor 將被迫接受一個(gè) reference to reference,而這種語法目前并不存在 [叁考資料7]。讓我們想想,為了允許 "pair" 得以持有 non-reference 型別、references 型別、constant references 型別,constructor 的叁數(shù)必須是什麼樣子:
"T1" 的型別 constructor 的叁數(shù)型別
T const T &
T & T &
const T & const T &
一個(gè)和 type traits classes 類似的技術(shù),允許我們建構(gòu)單一的對(duì)應(yīng)關(guān)系,使我們得以根據(jù) contained class 的型別決定叁數(shù)型別。type traits classes 提供了一個(gè) "add_reference" 轉(zhuǎn)換,可以為自身型別加上一個(gè) reference,除非它本身已經(jīng)是一個(gè) reference。
"T1" 的型別 "const T1" 的型別 "add_reference<const T1>::type" 的型別
T const T const T &
T & T & [注8] T &
const T & const T & const T &
這使我們得以建立一個(gè) template 主版本,定義一個(gè)可內(nèi)含 non-reference 型別、 reference 型別、constant reference 型別的 "pair" :
template <typename T1, typename T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(boost::add_reference<const T1>::type nfirst,
boost::add_reference<const T2>::type nsecond)
:first(nfirst), second(nsecond) { }
};
為它回添標(biāo)準(zhǔn)的 comparision operators, default constructor 和 template copy constructor 之後(它們都和原先版本相同),你就有了一個(gè)可以內(nèi)含 reference 型別的 std::pair。
當(dāng)然我們也可以使用偏特化技巧完成同樣的擴(kuò)充,但果真如此,我們需要三個(gè) "pair" 偏特化版本和一個(gè)主版本。Type traits 允許我們僅僅定義一個(gè)主版本,就可以自動(dòng)而神奇地將自己調(diào)整為任何偏特化版,取代一一偏特化的所謂「暴力法」。以此方式使用 type traits,可允許程式員將偏特化授權(quán)(delegate)給 type traits classes,使得代碼比較容易維護(hù),也比較容易被理解。
結(jié)論
希望這篇文章能夠給你一些想法,讓你大略知道 type-traits 是什麼。boost 說明文件中有更完整的 classes 列表,以及更進(jìn)一步的使用范例。Templates 使 C++ 有能力實(shí)現(xiàn)泛型編程所帶來的復(fù)用性;這篇文章還告訴你,templates 可以和 generic 一樣地美好。這都有賴 type traits 帶來的價(jià)值。
致謝
感謝 Beman Dawes 和 Howard Hinnant 對(duì)本文所提的意見。
叁考資料
Nathan C. Myers, C++ Report, June 1995.
這個(gè) type traits library 的完成,要感謝 Steve Cleary, Beman Dawes, Howard Hinnant 和 John Maddock。你可以在 http://www.boost.org/ 找到它。
所謂純量型別(scalar type)就是算術(shù)型別(例如內(nèi)建的整數(shù)或浮點(diǎn)數(shù))、列舉型別(enumeration)、指標(biāo)、函式指標(biāo)、或以上任何型別再加上 const- 或 volatile- 修飾詞。
此句引自 Donald Knuth, ACM Computing Surveys, December 1974, pg 268.
這一份測試代碼是 boost utility library 的一部份(見 algo_opt_examples.cpp),以 gcc 2.95 編譯完成,所有最佳化選項(xiàng)都打開。我的測試結(jié)果是在 400MHz Pentium II + Microsoft Windows 98 上獲得。
John Maddock 和 Howard Hinnant 已經(jīng)送出一個(gè) "compressed_pair" library 給 Boost,其中使用的一個(gè)技術(shù),和此處所描述的技術(shù)類似,也是用來持有 references。他們的 pair 也使用 type traits 來決定是否有任何型別是空的,并且采用 "derive" 而非 "contain" 的方式,用以保存空間 -- 這正是 "compressed" 的命名由來。
這其實(shí)是 C++ 核心語言工作小組的一個(gè)議題,由 Bjarne Stroustrup 提出。暫時(shí)的解決辦法是,允許 "a reference to a reference to T" 的意義等同於 "a reference to T",但是只能存在於 template 具現(xiàn)實(shí)體中,或是存在於一個(gè)「具備多個(gè) const-volatile 修飾詞」的 method 中。
為什麼這里不該有 const 修飾詞呢?對(duì)此感到驚訝的人,我要提醒你,請記住, references 永遠(yuǎn)是個(gè)隱晦常數(shù)(舉個(gè)例子,你不能夠重新對(duì)一個(gè) reference 賦值)。同時(shí)也請你記住,"const T &" 是完全不同的東西。因?yàn)檫@些理由,template 型別引數(shù)如果本身是個(gè) references 的話,其「const-volatile 修飾詞」都被忽略。
列表一
namespace detail{
template <bool b>
struct copier
{
template<typename I1, typename I2>
static I2 do_copy(I1 first,
I1 last, I2 out);
};
template <bool b>
template<typename I1, typename I2>
I2 copier<b>::do_copy(I1 first,
I1 last,
I2 out)
{
while(first != last)
{
*out = *first;
++out;
++first;
}
return out;
}
template <>
struct copier<true>
{
template<typename I1, typename I2>
static I2* do_copy(I1* first, I1* last, I2* out)
{
memcpy(out, first, (last-first)*sizeof(I2));
return out+(last-first); // 譯注:因?yàn)槭?span lang="EN-US"> RandomAccessIterator
}
};
}
template<typename I1, typename I2>
inline I2 copy(I1 first, I1 last, I2 out)
{
typedef typename
boost::remove_cv<
typename std::iterator_traits<I1>
::value_type>::type v1_t;
typedef typename
boost::remove_cv<
typename std::iterator_traits<I2>
::value_type>::type v2_t;
enum{ can_opt =
boost::is_same<v1_t, v2_t>::value
&& boost::is_pointer<I1>::value
&& boost::is_pointer<I2>::value
&& boost::has_trivial_assign<v1_t>::value
};
return detail::copier<can_opt>::do_copy(first, last, out);
}