Gitiles
Code Review Sign In
realtimeroboticsgroup.org / RealtimeRoboticsGroup / test / bca6d25af494f6ecfb6ecab60094dae251570c14 / . / prog_with_concepts.htm
blob: fb04aed3ba2d0effaa5f3610b2ed8076f10a54a2 [file] [log] [blame]
Brian Silvermanbca6d252018-08-04 23:36:16 -0700[diff] [blame^]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.sgi.com/tech/stl/LessThanComparable.html">
64LessThanComparable</a>, which not only
65includes <tt>operator&lt;()</tt>, but also <tt>operator&gt;()</tt>,
66<tt>operator&lt;=()</tt>, and <tt>operator&gt;=()</tt>.
67It 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
71href="http://www.sgi.com/tech/stl/LessThanComparable.html">
72LessThanComparable</a> or in terms of a concept that only
73requires <tt>operator&lt;()</tt>?
74
75<p>
76We remark first that the use of <a
77href="http://www.sgi.com/tech/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&lt;()</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.sgi.com/tech/stl/LessThanComparable.html">
84LessThanComparable</a> does not violate the requirement minimization
85principle because all of the comparison operators (<tt>&lt;</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.sgi.com/tech/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.sgi.com/tech/stl/ForwardIterator.html">ForwardIterator</a> and
114 <a href=
115 "http://www.sgi.com/tech/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>