diff options
| author | Dave Abrahams <dave@boostpro.com> | 2004-08-18 13:49:45 +0000 |
|---|---|---|
| committer | Dave Abrahams <dave@boostpro.com> | 2004-08-18 13:49:45 +0000 |
| commit | a4f4dd146f4df089fcbf87e77d0583937fcd1197 (patch) | |
| tree | 525dc766135d34405ed44d7fba9a5576058811a8 /more/generic_programming.html | |
| parent | fc92fdfed98acce03c661b538ea8e00b86b31696 (diff) | |
| download | boost-a4f4dd146f4df089fcbf87e77d0583937fcd1197.tar.gz | |
Fixed links; updated.
[SVN r24557]
Diffstat (limited to 'more/generic_programming.html')
| -rw-r--r-- | more/generic_programming.html | 277 |
1 files changed, 152 insertions, 125 deletions
diff --git a/more/generic_programming.html b/more/generic_programming.html index 9cd5d80342..b9fb6031ce 100644 --- a/more/generic_programming.html +++ b/more/generic_programming.html @@ -1,40 +1,44 @@ <!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"> +<html> + <head> + <meta name="generator" content= + "HTML Tidy for Cygwin (vers 1st April 2002), 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> + </head> + <body bgcolor="#FFFFFF" text="#000000"> <img src="../c++boost.gif" alt="c++boost.gif (8819 bytes)" align="center" width="277" height="86"> - <body bgcolor="#FFFFFF" text="#000000"> - <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. + techniques used in the <a href="../index.htm">boost</a> libraries.</p> <h2>Table of Contents</h2> <ul> - <li><a href="#introduction">Introduction</a> + <li><a href="#introduction">Introduction</a></li> - <li><a href="#concept">The Anatomy of a Concept</a> + <li><a href="#concept">The Anatomy of a Concept</a></li> - <li><a href="#traits">Traits</a> + <li><a href="#traits">Traits</a></li> - <li><a href="#tag_dispatching">Tag Dispatching</a> + <li><a href="#tag_dispatching">Tag Dispatching</a></li> - <li><a href="#adaptors">Adaptors</a> + <li><a href="#adaptors">Adaptors</a></li> - <li><a href="#type_generator">Type Generators</a> + <li><a href="#type_generator">Type Generators</a></li> - <li><a href="#object_generator">Object Generators</a> + <li><a href="#object_generator">Object Generators</a></li> - <li><a href="#policy">Policy Classes</a> + <li><a href="#policy">Policy Classes</a></li> </ul> <h2><a name="introduction">Introduction</a></h2> @@ -43,13 +47,14 @@ 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. + sacrificing efficiency.</p> <p>As a simple example of generic programming, we will look at how one - might generalize the <tt>memcpy()</tt> function of the C standard library. - An implementation of <tt>memcpy()</tt> might look like the following: - <br> + might generalize the <tt>memcpy()</tt> function of the C standard + library. An implementation of <tt>memcpy()</tt> might look like the + following:<br> <br> + </p> <blockquote> <pre> @@ -64,30 +69,31 @@ void* memcpy(void* region1, const void* region2, size_t n) } </pre> </blockquote> - The <tt>memcpy()</tt> function is already generalized to some extent by the - use of <tt>void*</tt> 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 + The <tt>memcpy()</tt> function is already generalized to some extent by + the use of <tt>void*</tt> 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 <tt>memcpy()</tt>, the function's <b><i>minimal requirements</i></b> are - that it needs to to <i>traverse</i> through the sequence using some sort of - pointer, <i>access</i> elements pointed to, <i>write</i> the elements to - the destination, and <i>compare</i> pointers to know when to stop. The C++ - standard library groups requirements such as these into + that it needs to to <i>traverse</i> through the sequence using some sort + of pointer, <i>access</i> elements pointed to, <i>write</i> the elements + to the destination, and <i>compare</i> pointers to know when to stop. The + C++ standard library groups requirements such as these into <b><i>concepts</i></b>, in this case the <a href= - "http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a> concept - (for <tt>region2</tt>) and the <a href= + "http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a> + concept (for <tt>region2</tt>) and the <a href= "http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a> concept (for <tt>region1</tt>). - <p>If we rewrite the <tt>memcpy()</tt> as a function template, and use the - <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input Iterator</a> - and <a href="http://www.sgi.com/tech/stl/OutputIterator.html">Output - Iterator</a> concepts to describe the requirements on the template - parameters, we can implement a highly reusable <tt>copy()</tt> function in - the following way: - <br> + <p>If we rewrite the <tt>memcpy()</tt> as a function template, and use + the <a href="http://www.sgi.com/tech/stl/InputIterator.html">Input + Iterator</a> and <a href= + "http://www.sgi.com/tech/stl/OutputIterator.html">Output Iterator</a> + concepts to describe the requirements on the template parameters, we can + implement a highly reusable <tt>copy()</tt> function in the following + way:<br> <br> + </p> <blockquote> <pre> @@ -105,9 +111,9 @@ copy(InputIterator first, InputIterator last, OutputIterator result) <p>Using the generic <tt>copy()</tt> function, we can now copy elements from any kind of sequence, including a linked list that exports iterators such as <tt>std::<a href= - "http://www.sgi.com/tech/stl/List.html">list</a></tt>. - <br> + "http://www.sgi.com/tech/stl/List.html">list</a></tt>.<br> <br> + </p> <blockquote> <pre> @@ -136,34 +142,37 @@ int main() <h2><a name="concept">Anatomy of a Concept</a></h2> A <b><i>concept</i></b> 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 - <b><i>model</i></b> the concept. A concept can extend the requirements of - another concept, which is called <b><i>refinement</i></b>. + consist of valid expressions, associated types, invariants, and + complexity guarantees. A type that satisfies the set of requirements is + said to <b><i>model</i></b> the concept. A concept can extend the + requirements of another concept, which is called + <b><i>refinement</i></b>. <ul> <li><a name="valid_expression"><b>Valid Expressions</b></a> are C++ expressions which must compile successfully for the objects involved in - the expression to be considered <i>models</i> of the concept. + the expression to be considered <i>models</i> of the concept.</li> - <li><a name="associated_type"><b>Associated Types</b></a> 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 <a href="#traits">traits class</a>. + <li><a name="associated_type"><b>Associated Types</b></a> 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 <a href= + "#traits">traits class</a>.</li> <li><b>Invariants</b> 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. + pre-conditions and post-conditions.</li> <li><b>Complexity Guarantees</b> 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. + various resources its computation will use.</li> </ul> <p>The concepts used in the C++ Standard Library are documented at the <a - href="http://www.sgi.com/tech/stl/table_of_contents.html">SGI STL site</a>. + href="http://www.sgi.com/tech/stl/table_of_contents.html">SGI STL + site</a>.</p> <h2><a name="traits">Traits</a></h2> @@ -171,7 +180,7 @@ int main() compile-time entity (a type, integral constant, or address). 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: + looks something like this:</p> <blockquote> <pre> @@ -186,46 +195,46 @@ struct iterator_traits { </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 + 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>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> <p>For an in-depth description of <tt>std::iterator_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. + constants describing the range and capabilities of numeric types.</p> <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= + 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 + 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. Other iterators must be + <tt>advance()</tt> function can simply be implemented with <tt>i += + n</tt>, and is very efficient: constant time. Other iterators must be <tt>advance</tt>d in steps, making the operation linear in n. 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, so we must decide whether - to increment or decrement the iterator. + then it makes sense for <tt>n</tt> to be negative, so we must decide + whether to increment or decrement the iterator.</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 often accessed through a traits class. The main <tt>advance()</tt> function - uses the <a href= + property used for dispatching (in this case the + <tt>iterator_category</tt>) is often 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 @@ -236,10 +245,10 @@ struct iterator_traits { "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. + 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> @@ -288,23 +297,31 @@ namespace std { 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. + container to provide a simple stack interface.</p> - <p>A more comprehensive review of the adaptors in the standard can be found - <a href= + <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>. + here</a>.</p> <h2><a name="type_generator">Type Generators</a></h2> + <p><b>Note:</b> The <i>type generator</i> concept has largely been + superseded by the more-refined notion of a <a href= + "../libs/mpl/doc/ref/Metafunction.html"><i>metafunction</i></a>. See + <i><a href="http://www.boost-consulting.com/mplbook">C++ Template + Metaprogramming</a></i> for an in-depth discussion of metafunctions.</p> + <p>A <i>type generator</i> is a template whose only purpose is to synthesize a new type or types based on its template argument(s)<a href= "#1">[1]</a>. 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.htm">filter_iterator_generator</a></tt>, - which looks something like this: + consolidate a complicated type expression into a simple one. This example + uses an old version of <tt><a href= + "../libs/iterator/doc/iterator_adaptor.html">iterator_adaptor</a></tt> + whose design didn't allow derived iterator types. As a result, every + adapted iterator had to be a specialization of <tt>iterator_adaptor</tt> + itself and generators were a convenient way to produce those types.</p> <blockquote> <pre> @@ -317,14 +334,15 @@ template <class Predicate, class Iterator, > 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: + <p>Now, that's complicated, but producing an adapted filter iterator + using the generator is much easier. You can usually just write:</p> <blockquote> <pre> @@ -334,16 +352,17 @@ boost::filter_iterator_generator<my_predicate,my_base_iterator>::type <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 Boost 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>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 Boost + 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> - <p>For example, given: + <p>For example, given:</p> <blockquote> <pre> @@ -369,7 +388,8 @@ void tweak_all_widgets1(int arg) </pre> </blockquote> - <p>Without using object generators the example above would look like this: + <p>Without using object generators the example above would look like + this:</p> <blockquote> <pre> @@ -382,8 +402,8 @@ void tweak_all_widgets2(int arg) </pre> </blockquote> - <p>As expressions get more complicated the need to reduce the verbosity of - type specification gets more compelling. + <p>As expressions get more complicated the need to reduce the verbosity + of type specification gets more compelling.</p> <h2><a name="policy">Policy Classes</a></h2> @@ -391,58 +411,65 @@ void tweak_all_widgets2(int arg) example from the standard library is <tt>std::<a href= "http://www.dinkumware.com/htm_cpl/memory.html#allocator">allocator</a></tt>, which supplies memory management behaviors to standard <a href= - "http://www.sgi.com/tech/stl/Container.html">containers</a>. + "http://www.sgi.com/tech/stl/Container.html">containers</a>.</p> <p>Policy classes have been explored in detail by <a href= - "mailto:andrewalex@hotmail.com">Andrei Alexandrescu</a> in <a href= + "http://www.moderncppdesign.com/">Andrei Alexandrescu</a> in <a href= "http://www.cs.ualberta.ca/~hoover/cmput401/XP-Notes/xp-conf/Papers/7_3_Alexandrescu.pdf"> - this paper</a>. He writes: + this paper</a>. He writes:</p> <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. + uses. This allows the user to select the policies needed.</p> <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. + amount of code.</p> </blockquote> - <p>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 <a href= - "../libs/utility/iterator_adaptors.htm">Iterator Adaptors</a> library, - where we transmit all of an adapted iterator's behavior in a single policy - class. There is precedent for this, however: <tt><a href= + <p>Andrei's description of policy classes suggests that their power is + derived from granularity and orthogonality. Less-granular policy + interfaces have been shown to work well in practice, though. <a href= + "http://cvs.sourceforge.net/viewcvs.py/*checkout*/boost/boost/libs/utility/Attic/iterator_adaptors.pdf"> + This paper</a> describes an old version of <tt><a href= + "../libs/iterator/doc/iterator_adaptor.html">iterator_adaptor</a></tt> + that used non-orthogonal policies. There is also precedent in the + standard library: <tt><a href= "http://www.dinkumware.com/htm_cpl/string2.html#char_traits">std::char_traits</a></tt>, - despite its name, acts as a policies class that determines the behaviors of - <a href= - "http://www.dinkumware.com/htm_cpl/string2.html#basic_string">std::basic_string</a>. + despite its name, acts as a policies class that determines the behaviors + of <a href= + "http://www.dinkumware.com/htm_cpl/string2.html#basic_string">std::basic_string</a>.</p> <h2>Notes</h2> - <a name="1">[1]</a> Type generators are a workaround for the lack of - ``templated typedefs'' in C++. + <a name="1">[1]</a> Type generators are sometimes viewed as a workaround + for the lack of ``templated typedefs'' in C++. <hr> <p>Revised - <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->14 Mar 2001<!--webbot bot="Timestamp" endspan i-checksum="14885" --> - + <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %b %Y" startspan -->18 + August 2004<!--webbot bot="Timestamp" endspan i-checksum="14885" --> + </p> <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. + 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 memcpy int - --> - - <!-- LocalWords: const OutputIterator iostream pre cpl - --> + --> + <!-- LocalWords: const OutputIterator iostream pre cpl + --> + </p> + </body> +</html> - </body> |