Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/more/generic_programming.html @ 18

Last change on this file since 18 was 12, checked in by landauf, 17 years ago

added boost
File size: 18.9 KB
Line 
1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
2
3<html>
4  <head>
5    <meta name="generator" content=
6    "HTML Tidy for Cygwin (vers 1st April 2002), see www.w3.org">
7    <meta http-equiv="Content-Type" content=
8    "text/html; charset=windows-1252">
9    <meta name="GENERATOR" content="Microsoft FrontPage 4.0">
10    <meta name="ProgId" content="FrontPage.Editor.Document">
11
12    <title>Generic Programming Techniques</title>
13  </head>
14
15  <body bgcolor="#FFFFFF" text="#000000">
16    <img src="../boost.png" alt="boost.png (6897 bytes)" align="center"
17    width="277" height="86"> 
18
19    <h1>Generic Programming Techniques</h1>
20
21    <p>This is an incomplete survey of some of the generic programming
22    techniques used in the <a href="../index.htm">boost</a> libraries.</p>
23
24    <h2>Table of Contents</h2>
25
26    <ul>
27      <li><a href="#introduction">Introduction</a></li>
28
29      <li><a href="#concept">The Anatomy of a Concept</a></li>
30
31      <li><a href="#traits">Traits</a></li>
32
33      <li><a href="#tag_dispatching">Tag Dispatching</a></li>
34
35      <li><a href="#adaptors">Adaptors</a></li>
36
37      <li><a href="#type_generator">Type Generators</a></li>
38
39      <li><a href="#object_generator">Object Generators</a></li>
40
41      <li><a href="#policy">Policy Classes</a></li>
42    </ul>
43
44    <h2><a name="introduction">Introduction</a></h2>
45
46    <p>Generic programming is about generalizing software components so that
47    they can be easily reused in a wide variety of situations. In C++, class
48    and function templates are particularly effective mechanisms for generic
49    programming because they make the generalization possible without
50    sacrificing efficiency.</p>
51
52    <p>As a simple example of generic programming, we will look at how one
53    might generalize the <tt>memcpy()</tt> function of the C standard
54    library. An implementation of <tt>memcpy()</tt> might look like the
55    following:<br>
56    <br>
57    </p>
58
59    <blockquote>
60<pre>
61void* memcpy(void* region1, const void* region2, size_t n)
62{
63  const char* first = (const char*)region2;
64  const char* last = ((const char*)region2) + n;
65  char* result = (char*)region1;
66  while (first != last)
67    *result++ = *first++;
68  return result;
69}
70</pre>
71    </blockquote>
72    The <tt>memcpy()</tt> function is already generalized to some extent by
73    the use of <tt>void*</tt> so that the function can be used to copy arrays
74    of different kinds of data. But what if the data we would like to copy is
75    not in an array? Perhaps it is in a linked list. Can we generalize the
76    notion of copy to any sequence of elements? Looking at the body of
77    <tt>memcpy()</tt>, the function's <b><i>minimal requirements</i></b> are
78    that it needs to <i>traverse</i> through the sequence using some sort
79    of pointer, <i>access</i> elements pointed to, <i>write</i> the elements
80    to the destination, and <i>compare</i> pointers to know when to stop. The
81    C++ standard library groups requirements such as these into
82    <b><i>concepts</i></b>, in this case the <a href=
83    "http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a>
84    concept (for <tt>region2</tt>) and the <a href=
85    "http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>
86    concept (for <tt>region1</tt>).
87
88    <p>If we rewrite the <tt>memcpy()</tt> as a function template, and use
89    the <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input
90    Iterator</a> and <a href=
91    "http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a>
92    concepts to describe the requirements on the template parameters, we can
93    implement a highly reusable <tt>copy()</tt> function in the following
94    way:<br>
95    <br>
96    </p>
97
98    <blockquote>
99<pre>
100template &lt;typename InputIterator, typename OutputIterator&gt;
101OutputIterator
102copy(InputIterator first, InputIterator last, OutputIterator result)
103{
104  while (first != last)
105    *result++ = *first++;
106  return result;
107}
108</pre>
109    </blockquote>
110
111    <p>Using the generic <tt>copy()</tt> function, we can now copy elements
112    from any kind of sequence, including a linked list that exports iterators
113    such as <tt>std::<a href=
114    "http://www.sgi.com/tech/stl/List.html">list</a></tt>.<br>
115    <br>
116    </p>
117
118    <blockquote>
119<pre>
120#include &lt;list&gt;
121#include &lt;vector&gt;
122#include &lt;iostream&gt;
123
124int main()
125{
126  const int N = 3;
127  std::vector&lt;int&gt; region1(N);
128  std::list&lt;int&gt; region2;
129
130  region2.push_back(1);
131  region2.push_back(0);
132  region2.push_back(3);
133 
134  std::copy(region2.begin(), region2.end(), region1.begin());
135
136  for (int i = 0; i &lt; N; ++i)
137    std::cout &lt;&lt; region1[i] &lt;&lt; " ";
138  std::cout &lt;&lt; std::endl;
139}
140</pre>
141    </blockquote>
142
143    <h2><a name="concept">Anatomy of a Concept</a></h2>
144    A <b><i>concept</i></b> is a set requirements, where the requirements
145    consist of valid expressions, associated types, invariants, and
146    complexity guarantees. A type that satisfies the set of requirements is
147    said to <b><i>model</i></b> the concept. A concept can extend the
148    requirements of another concept, which is called
149    <b><i>refinement</i></b>.
150
151    <ul>
152      <li><a name="valid_expression"><b>Valid Expressions</b></a> are C++
153      expressions which must compile successfully for the objects involved in
154      the expression to be considered <i>models</i> of the concept.</li>
155
156      <li><a name="associated_type"><b>Associated Types</b></a> are types
157      that are related to the modeling type in that they participate in one
158      or more of the valid expressions. Typically associated types can be
159      accessed either through typedefs nested within a class definition for
160      the modeling type, or they are accessed through a <a href=
161      "#traits">traits class</a>.</li>
162
163      <li><b>Invariants</b> are run-time characteristics of the objects that
164      must always be true, that is, the functions involving the objects must
165      preserve these characteristics. The invariants often take the form of
166      pre-conditions and post-conditions.</li>
167
168      <li><b>Complexity Guarantees</b> are maximum limits on how long the
169      execution of one of the valid expressions will take, or how much of
170      various resources its computation will use.</li>
171    </ul>
172
173    <p>The concepts used in the C++ Standard Library are documented at the <a
174    href="http://www.sgi.com/tech/stl/table_of_contents.html">SGI STL
175    site</a>.</p>
176
177    <h2><a name="traits">Traits</a></h2>
178
179    <p>A traits class provides a way of associating information with a
180    compile-time entity (a type, integral constant, or address). For example,
181    the class template <tt><a href=
182    "http://www.sgi.com/tech/stl/iterator_traits.html">std::iterator_traits&lt;T&gt;</a></tt>
183    looks something like this:</p>
184
185    <blockquote>
186<pre>
187template &lt;class Iterator&gt;
188struct iterator_traits {
189  typedef ... iterator_category;
190  typedef ... value_type;
191  typedef ... difference_type;
192  typedef ... pointer;
193  typedef ... reference;
194};
195</pre>
196    </blockquote>
197    The traits' <tt>value_type</tt> gives generic code the type which the
198    iterator is "pointing at", while the <tt>iterator_category</tt> can be
199    used to select more efficient algorithms depending on the iterator's
200    capabilities.
201
202    <p>A key feature of traits templates is that they're
203    <i>non-intrusive</i>: they allow us to associate information with
204    arbitrary types, including built-in types and types defined in
205    third-party libraries, Normally, traits are specified for a particular
206    type by (partially) specializing the traits template.</p>
207
208    <p>For an in-depth description of <tt>std::iterator_traits</tt>, see <a
209    href="http://www.sgi.com/tech/stl/iterator_traits.html">this page</a>
210    provided by SGI. Another very different expression of the traits idiom in
211    the standard is <tt>std::numeric_limits&lt;T&gt;</tt> which provides
212    constants describing the range and capabilities of numeric types.</p>
213
214    <h2><a name="tag_dispatching">Tag Dispatching</a></h2>
215
216    <p>Tag dispatching is a way of using function overloading to
217    dispatch based on properties of a type, and is often used hand in
218    hand with traits classes. A good example of this synergy is the
219    implementation of the <a href=
220    "http://www.sgi.com/tech/stl/advance.html"><tt>std::advance()</tt></a>
221    function in the C++ Standard Library, which increments an iterator
222    <tt>n</tt> times. Depending on the kind of iterator, there are different
223    optimizations that can be applied in the implementation. If the iterator
224    is <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">random
225    access</a> (can jump forward and backward arbitrary distances), then the
226    <tt>advance()</tt> function can simply be implemented with <tt>i +=
227    n</tt>, and is very efficient: constant time. Other iterators must be
228    <tt>advance</tt>d in steps, making the operation linear in n. If the
229    iterator is <a href=
230    "http://www.sgi.com/tech/stl/BidirectionalIterator.html">bidirectional</a>,
231    then it makes sense for <tt>n</tt> to be negative, so we must decide
232    whether to increment or decrement the iterator.</p>
233
234    <p>The relation between tag dispatching and traits classes is that the
235    property used for dispatching (in this case the
236    <tt>iterator_category</tt>) is often accessed through a traits class. The
237    main <tt>advance()</tt> function uses the <a href=
238    "http://www.sgi.com/tech/stl/iterator_traits.html"><tt>iterator_traits</tt></a>
239    class to get the <tt>iterator_category</tt>. It then makes a call the the
240    overloaded <tt>advance_dispatch()</tt> function. The appropriate
241    <tt>advance_dispatch()</tt> is selected by the compiler based on whatever
242    type the <tt>iterator_category</tt> resolves to, either <a href=
243    "http://www.sgi.com/tech/stl/input_iterator_tag.html"><tt>input_iterator_tag</tt></a>,
244    <a href=
245    "http://www.sgi.com/tech/stl/bidirectional_iterator_tag.html"><tt>bidirectional_iterator_tag</tt></a>,
246    or <a href=
247    "http://www.sgi.com/tech/stl/random_access_iterator_tag.html"><tt>random_access_iterator_tag</tt></a>.
248    A <b><i>tag</i></b> is simply a class whose only purpose is to convey
249    some property for use in tag dispatching and similar techniques. Refer to
250    <a href="http://www.sgi.com/tech/stl/iterator_tags.html">this page</a>
251    for a more detailed description of iterator tags.</p>
252
253    <blockquote>
254<pre>
255namespace std {
256  struct input_iterator_tag { };
257  struct bidirectional_iterator_tag { };
258  struct random_access_iterator_tag { };
259
260  namespace detail {
261    template &lt;class InputIterator, class Distance&gt;
262    void advance_dispatch(InputIterator&amp; i, Distance n, <b>input_iterator_tag</b>) {
263      while (n--) ++i;
264    }
265
266    template &lt;class BidirectionalIterator, class Distance&gt;
267    void advance_dispatch(BidirectionalIterator&amp; i, Distance n,
268       <b>bidirectional_iterator_tag</b>) {
269      if (n &gt;= 0)
270        while (n--) ++i;
271      else
272        while (n++) --i;
273    }
274
275    template &lt;class RandomAccessIterator, class Distance&gt;
276    void advance_dispatch(RandomAccessIterator&amp; i, Distance n,
277       <b>random_access_iterator_tag</b>) {
278      i += n;
279    }
280  }
281
282  template &lt;class InputIterator, class Distance&gt;
283  void advance(InputIterator&amp; i, Distance n) {
284    typename <b>iterator_traits&lt;InputIterator&gt;::iterator_category</b> category;
285    detail::advance_dispatch(i, n, <b>category</b>);
286  }
287}
288</pre>
289    </blockquote>
290
291    <h2><a name="adaptors">Adaptors</a></h2>
292
293    <p>An <i>adaptor</i> is a class template which builds on another type or
294    types to provide a new interface or behavioral variant. Examples of
295    standard adaptors are <a href=
296    "http://www.sgi.com/tech/stl/ReverseIterator.html">std::reverse_iterator</a>,
297    which adapts an iterator type by reversing its motion upon
298    increment/decrement, and <a href=
299    "http://www.sgi.com/tech/stl/stack.html">std::stack</a>, which adapts a
300    container to provide a simple stack interface.</p>
301
302    <p>A more comprehensive review of the adaptors in the standard can be
303    found <a href="http://portal.acm.org/citation.cfm?id=249118.249120">
304    here</a>.</p>
305
306    <h2><a name="type_generator">Type Generators</a></h2>
307
308    <p><b>Note:</b> The <i>type generator</i> concept has largely been
309    superseded by the more refined notion of a <a href=
310    "../libs/mpl/doc/refmanual/metafunction.html"><i>metafunction</i></a>. See
311    <i><a href="http://www.boost-consulting.com/mplbook">C++ Template
312    Metaprogramming</a></i> for an in-depth discussion of metafunctions.</p>
313
314    <p>A <i>type generator</i> is a template whose only purpose is to
315    synthesize a new type or types based on its template argument(s)<a href=
316    "#1">[1]</a>. The generated type is usually expressed as a nested typedef
317    named, appropriately <tt>type</tt>. A type generator is usually used to
318    consolidate a complicated type expression into a simple one. This example
319    uses an old version of <tt><a href=
320    "../libs/iterator/doc/iterator_adaptor.html">iterator_adaptor</a></tt>
321    whose design didn't allow derived iterator types. As a result, every
322    adapted iterator had to be a specialization of <tt>iterator_adaptor</tt>
323    itself and generators were a convenient way to produce those types.</p>
324
325    <blockquote>
326<pre>
327template &lt;class Predicate, class Iterator,
328    class Value = <i>complicated default</i>,
329    class Reference = <i>complicated default</i>,
330    class Pointer = <i>complicated default</i>,
331    class Category = <i>complicated default</i>,
332    class Distance = <i>complicated default</i>
333         &gt;
334struct filter_iterator_generator {
335    typedef iterator_adaptor&lt;
336       
337        Iterator,filter_iterator_policies&lt;Predicate,Iterator&gt;,
338        Value,Reference,Pointer,Category,Distance&gt; <b>type</b>;
339};
340</pre>
341    </blockquote>
342
343    <p>Now, that's complicated, but producing an adapted filter iterator
344    using the generator is much easier. You can usually just write:</p>
345
346    <blockquote>
347<pre>
348boost::filter_iterator_generator&lt;my_predicate,my_base_iterator&gt;::type
349</pre>
350    </blockquote>
351
352    <h2><a name="object_generator">Object Generators</a></h2>
353
354    <p>An <i>object generator</i> is a function template whose only purpose
355    is to construct a new object out of its arguments. Think of it as a kind
356    of generic constructor. An object generator may be more useful than a
357    plain constructor when the exact type to be generated is difficult or
358    impossible to express and the result of the generator can be passed
359    directly to a function rather than stored in a variable. Most Boost
360    object generators are named with the prefix "<tt>make_</tt>", after
361    <tt>std::<a href=
362    "http://www.sgi.com/tech/stl/pair.html">make_pair</a>(const&nbsp;T&amp;,&nbsp;const&nbsp;U&amp;)</tt>.</p>
363
364    <p>For example, given:</p>
365
366    <blockquote>
367<pre>
368struct widget {
369  void tweak(int);
370};
371std::vector&lt;widget *&gt; widget_ptrs;
372</pre>
373    </blockquote>
374    By chaining two standard object generators, <tt>std::<a href=
375    "http://www.dinkumware.com/htm_cpl/functio2.html#bind2nd">bind2nd</a>()</tt>
376    and <tt>std::<a href=
377    "http://www.dinkumware.com/htm_cpl/functio2.html#mem_fun">mem_fun</a>()</tt>,
378    we can easily tweak all widgets:
379
380    <blockquote>
381<pre>
382void tweak_all_widgets1(int arg)
383{
384   for_each(widget_ptrs.begin(), widget_ptrs.end(),
385      <b>bind2nd</b>(std::<b>mem_fun</b>(&amp;widget::tweak), arg));
386}
387</pre>
388    </blockquote>
389
390    <p>Without using object generators the example above would look like
391    this:</p>
392
393    <blockquote>
394<pre>
395void tweak_all_widgets2(int arg)
396{
397   for_each(struct_ptrs.begin(), struct_ptrs.end(),
398      <b>std::binder2nd&lt;std::mem_fun1_t&lt;void, widget, int&gt; &gt;</b>(
399          std::<b>mem_fun1_t&lt;void, widget, int&gt;</b>(&amp;widget::tweak), arg));
400}
401</pre>
402    </blockquote>
403
404    <p>As expressions get more complicated the need to reduce the verbosity
405    of type specification gets more compelling.</p>
406
407    <h2><a name="policy">Policy Classes</a></h2>
408
409    <p>A policy class is a template parameter used to transmit behavior. An
410    example from the standard library is <tt>std::<a href=
411    "http://www.dinkumware.com/htm_cpl/memory.html#allocator">allocator</a></tt>,
412    which supplies memory management behaviors to standard <a href=
413    "http://www.sgi.com/tech/stl/Container.html">containers</a>.</p>
414
415    <p>Policy classes have been explored in detail by <a href=
416    "http://www.moderncppdesign.com/">Andrei Alexandrescu</a> in <a href=
417    "http://www.informit.com/articles/article.asp?p=167842">this chapter</a>
418    of his book, <i>Modern C++ Design</i>. He writes:</p>
419
420    <blockquote>
421      <p>In brief, policy-based class design fosters assembling a class with
422      complex behavior out of many little classes (called policies), each of
423      which takes care of only one behavioral or structural aspect. As the
424      name suggests, a policy establishes an interface pertaining to a
425      specific issue. You can implement policies in various ways as long as
426      you respect the policy interface.</p>
427
428      <p>Because you can mix and match policies, you can achieve a
429      combinatorial set of behaviors by using a small core of elementary
430      components.</p>
431    </blockquote>
432
433    <p>Andrei's description of policy classes suggests that their power is
434    derived from granularity and orthogonality. Less-granular policy
435    interfaces have been shown to work well in practice, though. <a href=
436    "http://cvs.sourceforge.net/viewcvs.py/*checkout*/boost/boost/libs/utility/Attic/iterator_adaptors.pdf">
437    This paper</a> describes an old version of <tt><a href=
438    "../libs/iterator/doc/iterator_adaptor.html">iterator_adaptor</a></tt>
439    that used non-orthogonal policies. There is also precedent in the
440    standard library: <tt><a href=
441    "http://www.dinkumware.com/htm_cpl/string2.html#char_traits">std::char_traits</a></tt>,
442    despite its name, acts as a policies class that determines the behaviors
443    of <a href=
444    "http://www.dinkumware.com/htm_cpl/string2.html#basic_string">std::basic_string</a>.</p>
445
446    <h2>Notes</h2>
447    <a name="1">[1]</a> Type generators are sometimes viewed as a workaround
448    for the lack of ``templated typedefs'' in C++.
449    <hr>
450
451    <p>Revised
452    <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->18
453    August 2004<!--webbot bot="Timestamp" endspan i-checksum="14885" -->
454    </p>
455
456    <p>&copy; Copyright David Abrahams 2001. Permission to copy, use, modify,
457    sell and distribute this document is granted provided this copyright
458    notice appears in all copies. This document is provided "as is" without
459    express or implied warranty, and with no claim as to its suitability for
460    any purpose.
461    <!--  LocalWords:  HTML html charset gif alt htm struct SGI namespace std libs
462                     -->
463     
464    <!--  LocalWords:  InputIterator BidirectionalIterator RandomAccessIterator pdf
465                     -->
466     
467    <!--  LocalWords:  typename Alexandrescu templated Andrei's Abrahams memcpy int
468                     -->
469     <!--  LocalWords:  const OutputIterator iostream pre cpl
470                     -->
471    </p>
472  </body>
473</html>
474
Note: See TracBrowser for help on using the repository browser.