Generic Programming Techniques 泛型編程技術(shù)
This is an incomplete survey of some of the generic programming techniques used in the boost libraries.
這是對在boost庫中使用的某些泛型編程技術(shù)的不完整的觀察。
Table of Contents
目錄
- Introduction
- The Anatomy of a Concept
- Traits
- Tag Dispatching
- Adaptors
- Type Generators
- Object Generators
- Policy Classes
Introduction
介紹
Generic programming is about generalizing software components so that they can be easily reused in a wide variety of situations. In C++, class and function templates are particularly effective mechanisms for generic programming because they make the generalization possible without sacrificing efficiency.
泛型編程是關(guān)于一般化（generalizing）軟件組件使得他們那可以在廣泛的情況下得到重用的編程技術(shù)。在C++中，類和函數(shù)模板對泛型編程是尤其有效率的機制因為他們在無需犧牲效率的情況下實現(xiàn)這種一般化（generalizing）。
As a simple example of generic programming, we will look at how one might generalize the memcpy() function of the C standard library. An implementation of memcpy() might look like the following:
作為泛型編程的一個簡單的例子，我們將來看看如何一般化c標準庫中的memcpy函數(shù)。memcpy的一個實現(xiàn)可能看上去就像這樣：
void* memcpy(void* region1, const void* region2, size_t n)
{
const char* first = (const char*)region2;
const char* last = ((const char*)region2) + n;
char* result = (char*)region1;
while (first != last)
*result++ = *first++;
return result;
}
The memcpy() function is already generalized to some extent by the use of void* so that the function can be used to copy arrays of different kinds of data. But what if the data we would like to copy is not in an array? Perhaps it is in a linked list. Can we generalize the notion of copy to any sequence of elements? Looking at the body of memcpy(), the function's minimal requirements are that it needs to to traverse through the sequence using some sort of pointer, access elements pointed to, write the elements to the destination, and compare pointers to know when to stop. The C++ standard library groups requirements such as these into concepts, in this case the Input Iterator concept (for region2) and the Output Iterator concept (for region1).
memcpy函數(shù)已經(jīng)在某種程度上通過void*的使用實現(xiàn)了一般化。函數(shù)可以用來拷貝任何類型數(shù)據(jù)的數(shù)組。但是如果我們想要拷貝的數(shù)據(jù)不在一個數(shù)組中呢？可能它在一個鏈表中。我們可以一般化拷貝任何元素序列這個概念嗎？看看memcpy的函數(shù)體，函數(shù)所需要的最低要求是使用某種指針遍歷序列，存取指向的元素，并比較指針來得知何時停止。C++標準庫把類似這樣的需求歸類為概念，在這例中是，Input Iterator概念Output Iterator概念。
If we rewrite the memcpy() as a function template, and use the Input Iterator and Output Iterator concepts to describe the requirements on the template parameters, we can implement a highly reusable copy() function in the following way:
如果我們把memcpy重寫為一個函數(shù)模板，并使用Input Iterator和Output Iterator概念來描述對于模板參數(shù)的要求，我們可以用一下方式實現(xiàn)一個有很高重用性的copy函數(shù)：
template <typename InputIterator, typename OutputIterator>
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last)
*result++ = *first++;
return result;
}
Using the generic copy() function, we can now copy elements from any kind of sequence, including a linked list that exports iterators such as std::list.
使用泛型的copy函數(shù)，我們現(xiàn)在可以拷貝來自任何種類的序列的元素，包括提供了iterators的鏈表，像std::list。
#include <list>
#include <vector>
#include <iostream>
int main()
{
const int N = 3;
std::vector<int> region1(N);
std::list<int> region2;
region2.push_back(1);
region2.push_back(0);
region2.push_back(3);
std::copy(region2.begin(), region2.end(), region1.begin());
for (int i = 0; i < N; ++i)
std::cout << region1[i] << " ";
std::cout << std::endl;
}
Anatomy of a Concept
概念剖析
A concept is a set requirements, where the requirements consist of valid expressions, associated types, invariants, and complexity guarantees. A type that satisfies the set of requirements is said to model the concept. A concept can extend the requirements of another concept, which is called refinement.
一個概念是數(shù)個要求（requirements）的集合，其中要求包括有效的表達式，相關(guān)的類型，不變量，和復雜度的保證。一個滿足這樣一套要求的類型被稱為模塑這個概念。一個概念可以擴展另外一個概念的要求，這個稱為refinement。
- Valid Expressions are C++ expressions which must compile successfully for the objects involved in the expression to be considered models of the concept.
- 有效的表達式是必須成功編譯的C++表達式。對于表達式中包括的對象稱為概念的模型。
- Associated Types are types that are related to the modeling type in that they participate in one or more of the valid expressions. Typically associated types can be accessed either through typedefs nested within a class definition for the modeling type, or they are accessed through a traits class.
- 相關(guān)的類型是和modeling相關(guān)的類型，其中的類型在一個或者多個有效的表達式中出現(xiàn)。典型的相關(guān)類型既可以通過內(nèi)蘊在模塑類型的class定義中的typedef也可以通過traits class。
- Invariants are run-time characteristics of the objects that must always be true, that is, the functions involving the objects must preserve these characteristics. The invariants often take the form of pre-conditions and post-conditions.
- 不變量是對象運行時的性質(zhì)，必須永遠為真。也就是說，對象中的函數(shù)必須保有這些性質(zhì)。不變量經(jīng)常以pre-condition和post-condition的形式出現(xiàn)
- Complexity Guarantees are maximum limits on how long the execution of one of the valid expressions will take, or how much of various resources its computation will use.
- 復雜度保證是有效表達式中的一個的執(zhí)行時間的，或者它計算所消耗的各種資源的多少的最大上限
The concepts used in the C++ Standard Library are documented at the SGI STL site.
在C++標準庫中使用的概念在SGI STL 網(wǎng)站上存有文檔。
Traits
A traits class provides a way of associating information with a compile-time entity (a type, integral constant, or address). For example, the class template std::iterator_traits<T> looks something like this:
一個traits class提供了一種把信息和一個編譯時實體關(guān)聯(lián)起來的方法。例如，類模板std::iterator_traits看上去有些像這樣：
template <class Iterator>
struct iterator_traits {
typedef ... iterator_category;
typedef ... value_type;
typedef ... difference_type;
typedef ... pointer;
typedef ... reference;
};
The traits' value_type gives generic code the type which the iterator is "pointing at", while the iterator_category can be used to select more efficient algorithms depending on the iterator's capabilities.
traits的“值類型（value_type）”提供iterator當前指向的類型的泛型代碼，當“iterator_category”可以被用來根據(jù)iterator的能力選擇更有效率的算法。
A key feature of traits templates is that they're non-intrusive: they allow us to associate information with arbitrary types, including built-in types and types defined in third-party libraries, Normally, traits are specified for a particular type by (partially) specializing the traits template.
traits模板的一個關(guān)鍵特性是他們是非插入性的：他們使得我們可以把信息和任意類型關(guān)聯(lián)到一起，包括內(nèi)建的類型和定義在第三方庫中定義的類型，一般的，traits通過（部分）指定traits template來指定用于特定的類型
For an in-depth description of std::iterator_traits, see this page provided by SGI. Another very different expression of the traits idiom in the standard is std::numeric_limits<T> which provides constants describing the range and capabilities of numeric types.
要查看std::iterator_traits的深度描述，參考這個SGI提供的頁面。另外一個標準中的traits idiom的非常不同的表達式是std::numeric_limits<T>，它提供了描述數(shù)值類型的范圍和能力的常數(shù)。
Tag Dispatching
A technique that often goes hand in hand with traits classes is tag dispatching, which is a way of using function overloading to dispatch based on properties of a type. A good example of this is the implementation of the std::advance() function in the C++ Standard Library, which increments an iterator n times. Depending on the kind of iterator, there are different optimizations that can be applied in the implementation. If the iterator is random access (can jump forward and backward arbitrary distances), then the advance() function can simply be implemented with i += n, and is very efficient: constant time. Other iterators must be advanced in steps, making the operation linear in n. If the iterator is bidirectional, then it makes sense for n to be negative, so we must decide whether to increment or decrement the iterator.
一個經(jīng)常和traits類并用的技術(shù)是tag dispatching。它是一種使用函數(shù)重載來分派調(diào)用基于同一屬性的不同類型。這項技術(shù)的一個很好哦實現(xiàn)是C++標準函數(shù)庫中的std::advance函數(shù)，它使一個迭代器步進n次。根據(jù)迭代器的種類，可以對迭代器施以不同的優(yōu)化。如果迭代器是random access（可以向前和向后跳躍任意距離），那么advance函數(shù)可以簡單的用i+=n來實現(xiàn)，而且是非常有效率的：常量時間。其他的迭代器必須分n步前進，使得操作表現(xiàn)為線性的。如果迭代器是bidirectional，那么它使得n可以為負數(shù)，因此我們必須決定是否使迭代器步進或者步退。
The relation between tag dispatching and traits classes is that the property used for dispatching (in this case the iterator_category) is often accessed through a traits class. The main advance() function uses the iterator_traits class to get the iterator_category. It then makes a call the the overloaded advance_dispatch() function. The appropriate advance_dispatch() is selected by the compiler based on whatever type the iterator_category resolves to, either input_iterator_tag, bidirectional_iterator_tag, or random_access_iterator_tag. A tag is simply a class whose only purpose is to convey some property for use in tag dispatching and similar techniques. Refer to this page for a more detailed description of iterator tags.
tag dispatching和traits類之間的關(guān)系是用來分派調(diào)用的屬性（在此例中是iterator_category）經(jīng)常由一個traits類來取得。advance()的主函數(shù)使用iterator_traits類來獲得iterator_category。然后它調(diào)用一個重載了的advance_dispatch，由編譯器根據(jù)iterator_category解析（resolve）為的類型來決定具體的重載版本。iterator_category要么是input_iterator_tag要么是bidirectional_iterator_tag要么是random_access_iterator_tag。tag是一個僅僅用來傳達tag dispatching或者類似技術(shù)中用到的一些屬性的類。參考這個頁面來獲得關(guān)于iterator tags的更具體的描述。
namespace std {
struct input_iterator_tag { };
struct bidirectional_iterator_tag { };
struct random_access_iterator_tag { };
namespace detail {
template <class InputIterator, class Distance>
void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag) {
while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
void advance_dispatch(BidirectionalIterator& i, Distance n,
bidirectional_iterator_tag) {
if (n >= 0)
while (n--) ++i;
else
while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
void advance_dispatch(RandomAccessIterator& i, Distance n,
random_access_iterator_tag) {
i += n;
}
}
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
typename iterator_traits<InputIterator>::iterator_category category;
detail::advance_dispatch(i, n, category);
}
}
Adaptors
配接器
An adaptor is a class template which builds on another type or types to provide a new interface or behavioral variant. Examples of standard adaptors are std::reverse_iterator, which adapts an iterator type by reversing its motion upon increment/decrement, and std::stack, which adapts a container to provide a simple stack interface.
配接器是一個建立在其他一個類型或者多個類型之上類模板，以提供一個新的接口或者不同的行為。標準配接器的例子是std::reverse_iterator和std::stack。std::reverse_iterator它通過在步增和步退上反轉(zhuǎn)它的運動來配接一個迭代器。std::stack配接一個容器來提供一個簡單的棧的接口。
A more comprehensive review of the adaptors in the standard can be found here.
對于標準中的配接器的一個更深入的評述可以在這里找到
Type Generators
A type generator is a template whose only purpose is to synthesize a new type or types based on its template argument(s)[1]. The generated type is usually expressed as a nested typedef named, appropriately type. A type generator is usually used to consolidate a complicated type expression into a simple one, as in boost::filter_iterator_generator, which looks something like this:
type generator是一個僅僅用來基于它的模板參數(shù)來合成一個或者多個新的類型的模板。合成的類型經(jīng)常以嵌套的typedef恰當命名的類型來表示。一個type generator經(jīng)常用來把一個復雜的類型表達式變成一個簡單的東西，就像boost::filter_iterator_generator中的表現(xiàn)的一樣。它大概是這樣作的：
template <class Predicate, class Iterator,
class Value = complicated default,
class Reference = complicated default,
class Pointer = complicated default,
class Category = complicated default,
class Distance = complicated default
>
struct filter_iterator_generator {
typedef iterator_adaptor<
Iterator,filter_iterator_policies<Predicate,Iterator>,
Value,Reference,Pointer,Category,Distance> type;
};
Now, that's complicated, but producing an adapted filter iterator is much easier. You can usually just write:
現(xiàn)在，雖然generator本身是復雜的但是創(chuàng)建一個配接了的filter iterator更加容易了。你通常可以僅僅這么寫：
boost::filter_iterator_generator<my_predicate,my_base_iterator>::type
Object Generators
An object generator is a function template whose only purpose is to construct a new object out of its arguments. Think of it as a kind of generic constructor. An object generator may be more useful than a plain constructor when the exact type to be generated is difficult or impossible to express and the result of the generator can be passed directly to a function rather than stored in a variable. Most Boost object generators are named with the prefix "make_", after std::make_pair(const T&, const U&).
object generator是一個單純用來根據(jù)它的參數(shù)創(chuàng)建對象的函數(shù)模板。把它考慮為一種泛型的構(gòu)造函數(shù)。當要產(chǎn)生的確切類型很難或者是完全不可能表達而generator的結(jié)構(gòu)可以直接傳遞給一個函數(shù)而不是存儲于一個變量中的時候，一個object generator可能比一個普通的構(gòu)造函數(shù)更有用。大部分boos的object generators被以make_前綴命名，就如std::make_pairt(const T&, const U&)。
For example, given:
例如，給出：
struct widget {
void tweak(int);
};
std::vector<widget *> widget_ptrs;
通過把兩個標準object generator，std::bind2nd和std::mem_fun，鏈在一塊，我們可以輕易地擰上所有的widgets：
void tweak_all_widgets1(int arg)
{
for_each(widget_ptrs.begin(), widget_ptrs.end(),
bind2nd(std::mem_fun(&widget::tweak), arg));
}
Without using object generators the example above would look like this:
不使用object generator，上面的例子可能看上去是這樣：
void tweak_all_widgets2(int arg)
{
for_each(struct_ptrs.begin(), struct_ptrs.end(),
std::binder2nd<std::mem_fun1_t<void, widget, int> >(
std::mem_fun1_t<void, widget, int>(&widget::tweak), arg));
}
As expressions get more complicated the need to reduce the verbosity of type specification gets more compelling.
當表達式變得更加復雜，減輕類型說明的冗長的要求變得更加迫切。
Policy Classes
A policy class is a template parameter used to transmit behavior. An example from the standard library is std::allocator, which supplies memory management behaviors to standard containers.
一個policy類時一個用來傳播行為的模板參數(shù)。來自標準庫的一個例子是std::allocator，它給標準容器提供內(nèi)存管理的行為。
Policy classes have been explored in detail by Andrei Alexandrescu in this paper. He writes:
policy類在Andrei Alexandrescu的這篇文章中被深度探究。他寫道：
Policy classes are implementations of punctual design choices. They are inherited from, or contained within, other classes. They provide different strategies under the same syntactic interface. A class using policies is templated having one template parameter for each policy it uses. This allows the user to select the policies needed.
policy類是嚴格設(shè)計的一個是實現(xiàn)。他們從其他類繼承或者包含于其他類。他們在同樣的句法接口的基礎(chǔ)上提供不同的策略。一個使用策略的類為每個它使用的策略提供一個模板參數(shù)。這使得用戶選擇他們需要的策略。
The power of policy classes comes from their ability to combine freely. By combining several policy classes in a template class with multiple parameters, one achieves combinatorial behaviors with a linear amount of code.
policy類的威力來自于他們自由組合的能力。通過在一個模板類中用多個參數(shù)組合好幾個policy類，實現(xiàn)了在線性數(shù)量的代碼中提供組合的行為。
Andrei's description of policy classes describe their power as being derived from their granularity and orthogonality. Boost has probably diluted the distinction in the Iterator Adaptors library, where we transmit all of an adapted iterator's behavior in a single policy class. There is precedent for this, however: std::char_traits, despite its name, acts as a policies class that determines the behaviors of std::basic_string.
Andrei對于policy類的描述說明他們的威力來自于他們的顆粒性和正交性。Boost可能已經(jīng)沖淡了在Iterator Adaptor庫中的區(qū)別，我們在一個policy類中傳播所有adapted iterator的行為。然而這有一個先例：std::char_traits，不管它的名字，就像一個policy class一樣行為決定std::basic_string的行為。
Notes
[1] Type generators are a workaround for the lack of ``templated typedefs'' in C++.type generators是為了彌補C++中缺乏"參數(shù)化的typedef"的缺陷而做的補充。
浙公網(wǎng)安備 33010602011771號