0381c5fc54
Some documentation links currently point to pages that HP retired along with the rest of the SGI STL website. These links now point to the Boost mirror site.
145 lines
6.6 KiB
HTML
145 lines
6.6 KiB
HTML
<!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.boost.org/sgi/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.boost.org/sgi/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.boost.org/sgi/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.boost.org/sgi/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.boost.org/sgi/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.boost.org/sgi/stl/ForwardIterator.html">ForwardIterator</a> and
|
|
<a href=
|
|
"http://www.boost.org/sgi/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>
|