ceph/src/boost/libs/concept_check/prog_with_concepts.htm

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   2     "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3
   4 <html xmlns="http://www.w3.org/1999/xhtml">
   5 <!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 -->
   6 <!-- Distributed under the Boost -->
   7 <!-- Software License, Version 1.0. (See accompanying -->
   8 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
   9
  10 <head>
  11   <meta name="generator" content=
  12   "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" />
  13
  14   <title>Programming With Concepts</title>
  15   <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
  16   <link rel="stylesheet" href="../../rst.css" type="text/css" />
  17 </head>
  18
  19 <body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
  20 "#FF0000">
  21   <img src="../../boost.png" alt="C++ Boost" width="277" height=
  22   "86" /><br clear="none" />
  23
  24   <h2><a name="programming-with-concepts" id=
  25   "programming-with-concepts">Programming with Concepts</a></h2>
  26
  27   <p>The process of deciding how to group requirements into concepts and
  28   deciding which concepts to use in each algorithm is perhaps the most
  29   difficult (yet most important) part of building a generic library. A
  30   guiding principle to use during this process is one we call the
  31   <i>requirement minimization principle</i>.</p>
  32
  33   <p><b>Requirement Minimization Principle:</b> Minimize the requirements on
  34   the input parameters of a component to increase its reusability.</p>
  35
  36   <p>There is natural tension in this statement. By definition, the input
  37   parameters must be used by the component in order for the component to
  38   accomplish its task (by ``component'' we mean a function or class
  39   template). The challenge then is to implement the component in such a way
  40   that makes the fewest assumptions (the minimum requirements) about the
  41   inputs while still accomplishing the task.</p>
  42
  43   <p>The traditional notions of <i>abstraction</i> tie in directly to the
  44   idea of minimal requirements. The more abstract the input, the fewer the
  45   requirements. Thus, concepts are simply the embodiment of generic abstract
  46   data types in C++ template programming.</p>
  47
  48   <p>When designing the concepts for some problem domain it is important to
  49   keep in mind their purpose, namely to express the requirements for the
  50   input to the components. With respect to the requirement minimization
  51   principle, this means we want to minimize concepts.
  52   <!-- the following discussion does not match the Standard definition
  53  of LessThanComparable and needs to be changed -Jeremy
  54
  55 <p>
  56 It is important to note, however, that
  57 minimizing concepts does not mean simply
  58 reducing the number of valid expressions
  59 in the concept.
  60 For example, the
  61 <tt>std::stable_sort()</tt> function requires that the value type of
  62 the iterator be <a
  63 href="http://www.boost.org/sgi/stl/LessThanComparable.html">
  64 LessThanComparable</a>, which not only
  65 includes <tt>operator&lt;()</tt>, but also <tt>operator&gt;()</tt>,
  66 <tt>operator&lt;=()</tt>, and <tt>operator&gt;=()</tt>.
  67 It turns out that <tt>std::stable_sort()</tt> only uses
  68 <tt>operator&lt;()</tt>.  The question then arises: should
  69 <tt>std::stable_sort()</tt> be specified in terms of the concept
  70 <a
  71 href="http://www.boost.org/sgi/stl/LessThanComparable.html">
  72 LessThanComparable</a> or in terms of a concept that only
  73 requires <tt>operator&lt;()</tt>?
  74
  75 <p>
  76 We remark first that the use of <a
  77 href="http://www.boost.org/sgi/stl/LessThanComparable.html">
  78 LessThanComparable</a> does not really violate the requirement
  79 minimization principle because all of the other operators can be
  80 trivially implemented in terms of <tt>operator&lt;()</tt>. By
  81 ``trivial'' we mean one line of code and a constant run-time cost.
  82 More fundamentally, however, the use of <a
  83 href="http://www.boost.org/sgi/stl/LessThanComparable.html">
  84 LessThanComparable</a> does not violate the requirement minimization
  85 principle because all of the comparison operators (<tt>&lt;</tt>,
  86 <tt>></tt>, <tt><=</tt>, <tt>>=</tt>) are conceptually equivalent (in
  87 a mathematical sense).  Adding conceptually equivalent valid
  88 expressions is not a violation of the requirement minimization
  89 principle because no new semantics are being added === only new
  90 syntax. The added syntax increases re-usability.
  91
  92 <p>
  93 For example,
  94 the
  95 maintainer of the <tt>std::stable_sort()</tt> may some day change the
  96 implementation in places to use <tt>operator>()</tt> instead of
  97 <tt>operator<()</tt>, since, after all, they are equivalent.  Since the
  98 requirements are part of the public interface, such a change could
  99 potentially break client code.  If instead
 100 <a
 101 href="http://www.boost.org/sgi/stl/LessThanComparable.html">
 102 LessThanComparable</a> is given as the requirement for
 103 <tt>std::stable_sort()</tt>, then the maintainer is given a reasonable
 104 amount of flexibility within which to work.
 105
 106 --></p>
 107
 108   <p>Minimality in concepts is a property associated with the underlying
 109   semantics of the problem domain being represented. In the problem domain of
 110   basic containers, requiring traversal in a single direction is a smaller
 111   requirement than requiring traversal in both directions (hence the
 112   distinction between <a href=
 113   "http://www.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a> and
 114   <a href=
 115   "http://www.boost.org/sgi/stl/BidirectionalIterator.html">BidirectionalIterator</a>).
 116   The semantic difference can be easily seen in the difference between the
 117   set of concrete data structures that have forward iterators versus the set
 118   that has bidirectional iterators. For example, singly-linked lists would
 119   fall in the set of data structures having forward iterators, but not
 120   bidirectional iterators. In addition, the set of algorithms that one can
 121   implement using only forward iterators is quite different than the set that
 122   can be implemented with bidirectional iterators. Because of this, it is
 123   important to factor families of requirements into rather fine-grained
 124   concepts. For example, the requirements for iterators are factored into the
 125   six STL iterator concepts (trivial, output, input, forward, bidirectional,
 126   and random access).</p>
 127
 128   <p><a href="./implementation.htm">Next: Implementation</a><br />
 129   <a href="./concept_covering.htm">Prev: Concept Covering and
 130   Archetypes</a><br /></p>
 131   <hr />
 132
 133   <table>
 134     <tr valign="top">
 135       <td nowrap="nowrap">Copyright &copy; 2000</td>
 136
 137       <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href=
 138       "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew
 139       Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>),
 140         2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>.
 141     </tr>
 142   </table>
 143 </body>
 144 </html>