Squashed 'third_party/boostorg/concept_check/' content from commit ed0a0eb
Change-Id: Ib7230965334f9501601efc300242efde8352a380
git-subtree-dir: third_party/boostorg/concept_check
git-subtree-split: ed0a0ebd72f778cfa4931e0538ea34c28db3a42b
diff --git a/prog_with_concepts.htm b/prog_with_concepts.htm
new file mode 100644
index 0000000..fb04aed
--- /dev/null
+++ b/prog_with_concepts.htm
@@ -0,0 +1,144 @@
+<!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>