1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
<meta name="generator" content="HTML Tidy, see www.w3.org">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>Generic Programming Techniques</title>
<img src="../c++boost.gif" alt="c++boost.gif (8819 bytes)" align="center"
width="277" height="86">
<h1>Generic Programming Techniques</h1>
<p>This is an incomplete survey of some of the generic programming
techniques used in the <a href="../index.htm">boost</a> libraries.
<h2>Table of Contents</h2>
<ul>
<li><a href="#traits">Traits</a>
<li><a href="#tag_dispatching">Tag Dispatching</a>
<li><a href="#type_generator">Type Generators</a>
<li><a href="#object_generator">Object Generators</a>
<li><a href="#policies">Policies Classes</a>
<li><a href="#adaptors">Adaptors</a>
</ul>
<h2><a name="traits">Traits</a></h2>
<p>A traits class provides a way of associating information with another
type. For example, the class template <tt><a href=
"http://www.sgi.com/tech/stl/iterator_traits.html">std::iterator_traits<T></a></tt>
looks something like this:
<blockquote>
<pre>
template <class Iterator>
struct iterator_traits {
typedef ... iterator_category;
typedef ... value_type;
typedef ... difference_type;
typedef ... pointer;
typedef ... reference;
};
</pre>
</blockquote>
The traits' <tt>value_type</tt> gives generic code the type which the
iterator is "pointing at", while the <tt>iterator_category</tt> can be used
to select more efficient algorithms depending on the iterator's
capabilities.
<p>A key feature of traits templates is that they're <i>non-intrusive</i>:
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.
<p>For an in-depth description of <tt>std::type_traits</tt>, see <a href=
"http://www.sgi.com/tech/stl/iterator_traits.html">this page</a> provided
by SGI. Another very different expression of the traits idiom in the
standard is <tt>std::numeric_limits<T></tt> which provides constants
describing the range and capabilities of numeric types.
<h2><a name="tag_dispatching">Tag Dispatching</a></h2>
<p>
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 <a
href="http://www.sgi.com/tech/stl/advance.html"><tt>std::advance()</tt></a>
function in the C++ Standard Library, which increments an
iterator <tt>n</tt> times. Depending on the kind of iterator,
there are different optimizations that can be applied in the
implementation. If the iterator is <a
href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">random
access</a> (can jump forward and backward arbitrary distances),
then the <tt>advance()</tt> function can simply be implemented
with <tt>i += n</tt>, and is very efficient: constant time. If
the iterator is <a
href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">bidirectional</a>,
then it makes sense for <tt>n</tt> to be negative, we can
decrement the iterator <tt>n</tt> times.
</p>
<p>
The relation between tag dispatching and traits classes is
that the property used for dispatching (in this case the
<tt>iterator_category</tt>) is accessed through a traits class.
The main <tt>advance()</tt> function uses the <a
href="http://www.sgi.com/tech/stl/iterator_traits.html"><tt>iterator_traits</tt></a>
class to get the <tt>iterator_category</tt>. It then makes a call
the the overloaded <tt>advance_dispatch()</tt> function.
The
appropriate <tt>advance_dispatch()</tt> is selected by the
compiler based on whatever type the <tt>iterator_category</tt>
resolves to, either <a
href="http://www.sgi.com/tech/stl/input_iterator_tag.html">
<tt>input_iterator_tag</tt></a>, <a
href="http://www.sgi.com/tech/stl/bidirectional_iterator_tag.html">
<tt>bidirectional_iterator_tag</tt></a>, or <a
href="http://www.sgi.com/tech/stl/random_access_iterator_tag.html">
<tt>random_access_iterator_tag</tt></a>. A <b><i>tag</i></b> is
simply a class whose only purpose is to convey some property for
use in tag dispatching and similar techniques. Refer to <a
href="http://www.sgi.com/tech/stl/iterator_tags.html">this
page</a> for a more detailed description of iterator tags.
</p>
<blockquote>
<pre>
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, <b>input_iterator_tag</b>) {
while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
void advance_dispatch(BidirectionalIterator& i, Distance n,
<b>bidirectional_iterator_tag</b>) {
if (n >= 0)
while (n--) ++i;
else
while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
void advance_dispatch(RandomAccessIterator& i, Distance n,
<b>random_access_iterator_tag</b>) {
i += n;
}
}
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
typename <b>iterator_traits<InputIterator>::iterator_category</b> category;
detail::advance_dispatch(i, n, <b>category</b>);
}
}
</pre>
</blockquote>
<h2><a name="type_generator">Type Generators</a></h2>
<p>A <i>type generator</i> is a template whose only purpose is to
synthesize a single new type based on its template argument(s). The
generated type is usually expressed as a nested typedef named,
appropriately <tt>type</tt>. A type generator is usually used to
consolidate a complicated type expression into a simple one, as in
<tt>boost::<a href=
"../libs/utility/filter_iterator.hpp">filter_iterator_generator</a></tt>,
which looks something like this:
<blockquote>
<pre>
template <class Predicate, class Iterator,
class Value = <i>complicated default</i>,
class Reference = <i>complicated default</i>,
class Pointer = <i>complicated default</i>,
class Category = <i>complicated default</i>,
class Distance = <i>complicated default</i>
>
struct filter_iterator_generator {
typedef iterator_adaptor<
Iterator,filter_iterator_policies<Predicate,Iterator>,
Value,Reference,Pointer,Category,Distance> <b>type</b>;
};
</pre>
</blockquote>
<p>Now, that's complicated, but producing an adapted filter iterator is
much easier. You can usually just write:
<blockquote>
<pre>
boost::filter_iterator_generator<my_predicate,my_base_iterator>::type
</pre>
</blockquote>
<h2><a name="object_generator">Object Generators</a></h2>
<p>An <i>object generator</i> 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 object generators are named
with the prefix "<tt>make_</tt>", after <tt>std::<a href=
"http://www.sgi.com/tech/stl/pair.html">make_pair</a>(const T&, const U&)</tt>.
<p>Here is an example, using another standard object generator, <tt>std::<a
href=
"http://www.sgi.com/tech/stl/back_insert_iterator.html">back_inserter</a>()</tt>:
<blockquote>
<pre>
// Append the items in [start, finish) to c
template <class Container, class Iterator>
void append_sequence(Container& c, Iterator start, Iterator finish)
{
std::copy(start, finish, <b>std::back_inserter</b>(c));
}
</pre>
</blockquote>
<p>Without using the object generator the example above would look like:
write:
<blockquote>
<pre>
// Append the items in [start, finish) to c
template <class Container, class Iterator>
void append_sequence(Container& c, Iterator start, Iterator finish)
{
std::copy(start, finish, <b>std::back_insert_iterator<Container></b>(c));
}
</pre>
</blockquote>
<p>As expressions get more complicated the need to reduce the verbosity of
type specification gets more compelling.
<h2><a name="policies">Policies Classes</a></h2>
<p>Policies classes are a simple idea we first saw described by <a href=
"mailto:andrewalex@hotmail.com">Andrei Alexandrescu</a>, but which we
snapped up and quickly applied in the <a href=
"../libs/utility/iterator_adaptors.htm">Iterator Adaptors</a> library. A
policies class is a template parameter used to transmit behaviors. A
detailed description by Andrei is available in <a href=
"http://www.cs.ualberta.ca/~hoover/cmput401/XP-Notes/xp-conf/Papers/7_3_Alexandrescu.pdf">
this paper</a>. He writes:
<blockquote>
<p>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.
<p>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.
</blockquote>
<p>Andrei's description of policies describe their power as being derived
from their granularity and orthogonality. Boost has probably diluted the
distinction in the <a href="../libs/utility/iterator_adaptors.htm">Iterator
Adaptors</a> library, where we transmit all of an adapted iterator's
behavior in a single policies class.
<h2><a name="adaptors">Adaptors</a></h2>
<p>An <i>adaptor</i> is a class template which builds on another type or
types to provide a new interface or behavioral variant. Examples of
standard adaptors are <a href=
"http://www.sgi.com/tech/stl/ReverseIterator.html">std::reverse_iterator</a>,
which adapts an iterator type by reversing its motion upon
increment/decrement, and <a href=
"http://www.sgi.com/tech/stl/stack.html">std::stack</a>, which adapts a
container to provide a simple stack interface.
<p>A more comprehensive review of the adaptors in the standard can be found
<a href=
"http://www.cs.rpi.edu/~wiseb/xrds/ovp2-3b.html#SECTION00015000000000000000">
here</a>.
<hr>
<p>Revised
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->11
Feb 2001<!--webbot bot="Timestamp" endspan i-checksum="14373" -->
<p>© Copyright David Abrahams 2001. Permission to copy, use, modify,
sell and distribute this document is granted provided this copyright notice
appears in all copies. This document is provided "as is" without express or
implied warranty, and with no claim as to its suitability for any purpose.
<!-- LocalWords: HTML html charset gif alt htm struct SGI namespace std libs
-->
<!-- LocalWords: InputIterator BidirectionalIterator RandomAccessIterator pdf
-->
<!-- LocalWords: typename Alexandrescu templated Andrei's Abrahams
-->
|
