| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" |
| "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| |
| <html xmlns="http://www.w3.org/1999/xhtml"> |
| <!-- Copyright (c) Jeremy Siek and Andrew Lumsdaine 2000 --> |
| <!-- Distributed under the Boost --> |
| <!-- Software License, Version 1.0. (See accompanying --> |
| <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> |
| |
| <head> |
| <meta name="generator" content= |
| "HTML Tidy for Linux/x86 (vers 1 September 2005), see www.w3.org" /> |
| |
| <title>Programming With Concepts</title> |
| <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" /> |
| <link rel="stylesheet" href="../../rst.css" type="text/css" /> |
| </head> |
| |
| <body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink= |
| "#FF0000"> |
| <img src="../../boost.png" alt="C++ Boost" width="277" height= |
| "86" /><br clear="none" /> |
| |
| <h2><a name="programming-with-concepts" id= |
| "programming-with-concepts">Programming with Concepts</a></h2> |
| |
| <p>The process of deciding how to group requirements into concepts and |
| deciding which concepts to use in each algorithm is perhaps the most |
| difficult (yet most important) part of building a generic library. A |
| guiding principle to use during this process is one we call the |
| <i>requirement minimization principle</i>.</p> |
| |
| <p><b>Requirement Minimization Principle:</b> Minimize the requirements on |
| the input parameters of a component to increase its reusability.</p> |
| |
| <p>There is natural tension in this statement. By definition, the input |
| parameters must be used by the component in order for the component to |
| accomplish its task (by ``component'' we mean a function or class |
| template). The challenge then is to implement the component in such a way |
| that makes the fewest assumptions (the minimum requirements) about the |
| inputs while still accomplishing the task.</p> |
| |
| <p>The traditional notions of <i>abstraction</i> tie in directly to the |
| idea of minimal requirements. The more abstract the input, the fewer the |
| requirements. Thus, concepts are simply the embodiment of generic abstract |
| data types in C++ template programming.</p> |
| |
| <p>When designing the concepts for some problem domain it is important to |
| keep in mind their purpose, namely to express the requirements for the |
| input to the components. With respect to the requirement minimization |
| principle, this means we want to minimize concepts. |
| <!-- the following discussion does not match the Standard definition |
| of LessThanComparable and needs to be changed -Jeremy |
| |
| <p> |
| It is important to note, however, that |
| minimizing concepts does not mean simply |
| reducing the number of valid expressions |
| in the concept. |
| For example, the |
| <tt>std::stable_sort()</tt> function requires that the value type of |
| the iterator be <a |
| href="http://www.sgi.com/tech/stl/LessThanComparable.html"> |
| LessThanComparable</a>, which not only |
| includes <tt>operator<()</tt>, but also <tt>operator>()</tt>, |
| <tt>operator<=()</tt>, and <tt>operator>=()</tt>. |
| It turns out that <tt>std::stable_sort()</tt> only uses |
| <tt>operator<()</tt>. The question then arises: should |
| <tt>std::stable_sort()</tt> be specified in terms of the concept |
| <a |
| href="http://www.sgi.com/tech/stl/LessThanComparable.html"> |
| LessThanComparable</a> or in terms of a concept that only |
| requires <tt>operator<()</tt>? |
| |
| <p> |
| We remark first that the use of <a |
| href="http://www.sgi.com/tech/stl/LessThanComparable.html"> |
| LessThanComparable</a> does not really violate the requirement |
| minimization principle because all of the other operators can be |
| trivially implemented in terms of <tt>operator<()</tt>. By |
| ``trivial'' we mean one line of code and a constant run-time cost. |
| More fundamentally, however, the use of <a |
| href="http://www.sgi.com/tech/stl/LessThanComparable.html"> |
| LessThanComparable</a> does not violate the requirement minimization |
| principle because all of the comparison operators (<tt><</tt>, |
| <tt>></tt>, <tt><=</tt>, <tt>>=</tt>) are conceptually equivalent (in |
| a mathematical sense). Adding conceptually equivalent valid |
| expressions is not a violation of the requirement minimization |
| principle because no new semantics are being added === only new |
| syntax. The added syntax increases re-usability. |
| |
| <p> |
| For example, |
| the |
| maintainer of the <tt>std::stable_sort()</tt> may some day change the |
| implementation in places to use <tt>operator>()</tt> instead of |
| <tt>operator<()</tt>, since, after all, they are equivalent. Since the |
| requirements are part of the public interface, such a change could |
| potentially break client code. If instead |
| <a |
| href="http://www.sgi.com/tech/stl/LessThanComparable.html"> |
| LessThanComparable</a> is given as the requirement for |
| <tt>std::stable_sort()</tt>, then the maintainer is given a reasonable |
| amount of flexibility within which to work. |
| |
| --></p> |
| |
| <p>Minimality in concepts is a property associated with the underlying |
| semantics of the problem domain being represented. In the problem domain of |
| basic containers, requiring traversal in a single direction is a smaller |
| requirement than requiring traversal in both directions (hence the |
| distinction between <a href= |
| "http://www.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a> and |
| <a href= |
| "http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>). |
| The semantic difference can be easily seen in the difference between the |
| set of concrete data structures that have forward iterators versus the set |
| that has bidirectional iterators. For example, singly-linked lists would |
| fall in the set of data structures having forward iterators, but not |
| bidirectional iterators. In addition, the set of algorithms that one can |
| implement using only forward iterators is quite different than the set that |
| can be implemented with bidirectional iterators. Because of this, it is |
| important to factor families of requirements into rather fine-grained |
| concepts. For example, the requirements for iterators are factored into the |
| six STL iterator concepts (trivial, output, input, forward, bidirectional, |
| and random access).</p> |
| |
| <p><a href="./implementation.htm">Next: Implementation</a><br /> |
| <a href="./concept_covering.htm">Prev: Concept Covering and |
| Archetypes</a><br /></p> |
| <hr /> |
| |
| <table> |
| <tr valign="top"> |
| <td nowrap="nowrap">Copyright © 2000</td> |
| |
| <td><a href="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</a>(<a href= |
| "mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>) Andrew |
| Lumsdaine(<a href="mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>), |
| 2007 <a href="mailto:dave@boost-consulting.com">David Abrahams</a>. |
| </tr> |
| </table> |
| </body> |
| </html> |