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> 56It is important to note, however, that 57minimizing concepts does not mean simply 58reducing the number of valid expressions 59in the concept. 60For example, the 61<tt>std::stable_sort()</tt> function requires that the value type of 62the iterator be <a 63href="http://www.boost.org/sgi/stl/LessThanComparable.html"> 64LessThanComparable</a>, which not only 65includes <tt>operator<()</tt>, but also <tt>operator>()</tt>, 66<tt>operator<=()</tt>, and <tt>operator>=()</tt>. 67It turns out that <tt>std::stable_sort()</tt> only uses 68<tt>operator<()</tt>. The question then arises: should 69<tt>std::stable_sort()</tt> be specified in terms of the concept 70<a 71href="http://www.boost.org/sgi/stl/LessThanComparable.html"> 72LessThanComparable</a> or in terms of a concept that only 73requires <tt>operator<()</tt>? 74 75<p> 76We remark first that the use of <a 77href="http://www.boost.org/sgi/stl/LessThanComparable.html"> 78LessThanComparable</a> does not really violate the requirement 79minimization principle because all of the other operators can be 80trivially implemented in terms of <tt>operator<()</tt>. By 81``trivial'' we mean one line of code and a constant run-time cost. 82More fundamentally, however, the use of <a 83href="http://www.boost.org/sgi/stl/LessThanComparable.html"> 84LessThanComparable</a> does not violate the requirement minimization 85principle because all of the comparison operators (<tt><</tt>, 86<tt>></tt>, <tt><=</tt>, <tt>>=</tt>) are conceptually equivalent (in 87a mathematical sense). Adding conceptually equivalent valid 88expressions is not a violation of the requirement minimization 89principle because no new semantics are being added === only new 90syntax. The added syntax increases re-usability. 91 92<p> 93For example, 94the 95maintainer of the <tt>std::stable_sort()</tt> may some day change the 96implementation in places to use <tt>operator>()</tt> instead of 97<tt>operator<()</tt>, since, after all, they are equivalent. Since the 98requirements are part of the public interface, such a change could 99potentially break client code. If instead 100<a 101href="http://www.boost.org/sgi/stl/LessThanComparable.html"> 102LessThanComparable</a> is given as the requirement for 103<tt>std::stable_sort()</tt>, then the maintainer is given a reasonable 104amount 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 © 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> 145
