stl_introduction.html

Standard Template Library (SOURCE + COMPLETE html man document)

requirements; the arguments to <TT><A href="for_each.html">for_each</A></TT> and <TT><A href="count.html">count</A></TT>, 
and other algorithms, must satisfy the same requirements. These requirements are 
sufficiently important that we give them a name: we call such a set of 
type requirements a <I>concept</I>, and we call this particular 
concept <B><A href="InputIterator.html">Input Iterator</A></B>. We say that a type <I>conforms to a concept</I>, or that 
it <I>is a model of a concept</I>, if it satisfies all of those 
requirements.  We say that <TT>int*</TT> is a model of <B>Input 
Iterator</B> because <TT>int*</TT> provides all of the operations that 
are specified by the <B>Input Iterator</B> requirements. </P>
<P>
Concepts are not a part of the C++ language; there is no way to declare 
a concept in a program, or to declare that a particular type is a model 
of a concept. Nevertheless, concepts are an extremely important part of 
the STL. Using concepts makes it possible to write programs that 
cleanly separate interface from implementation: the author of <TT>find</TT>
 only has to consider the interface specified by the concept <B>Input 
Iterator</B>, rather than the implementation of every possible type 
that conforms to that concept. Similarly, if you want to use <TT>find</TT>, 
you need only to ensure that the arguments you pass to it are models 
of <B>Input Iterator. </B>This is the reason why <TT>find</TT> and <TT>reverse</TT>
 can be used with <TT>list</TT>s, <TT>vector</TT>s, C arrays, and many 
other types: programming in terms of concepts, rather than in terms of 
specific types, makes it possible to reuse software components and to 
combine components together. </P>
<H2>
Refinement</H2>
<P>
<B>Input Iterator</B> is, in fact, a rather weak concept: that is, it 
imposes very few requirements. An <B>Input Iterator</B> must support a 
subset of pointer arithmetic (it must be possible to increment an <B>Input 
Iterator</B> using prefix and postfix <TT>operator++</TT>), but need 
not support all operations of pointer arithmetic. This is sufficient 
for <TT><A href="find.html">find</A></TT>, but some other algorithms require that their 
arguments satisfy additional requirements. <TT><A href="reverse.html">Reverse</A></TT>, for 
example, must be able to decrement its arguments as well as increment 
them; it uses the expression <TT>--last</TT>. In terms of concepts, we 
say that <TT>reverse</TT>'s arguments must be models of <B><A href="BidirectionalIterator.html">Bidirectional Iterator</A></B> 
rather than <B>Input Iterator</B>. </P>
<P>
The <B>Bidirectional Iterator</B> concept is very similar to the <B>Input
 Iterator</B> concept: it simply imposes some additional requirements. 
The types that are models of <B>Bidirectional Iterator</B> are a subset 
of the types that are models of<B> Input Iterator</B>: every type that 
is a model of <B>Bidirectional Iterator</B> is also a model of <B>Input 
Iterator</B>. <TT>Int*</TT>, for example, is both a model of <B>Bidirectional 
Iterator</B> and a model of <B>Input Iterator</B>, but <TT><A href="istream_iterator.html">istream_iterator</A></TT>, 
is only a model of  <B>Input Iterator</B>: it does not conform to the 
more stringent <B>Bidirectional Iterator</B> requirements. </P>
<P>
We describe the relationship between <B>Input Iterator</B> and <B>Bidirectional 
Iterator</B> by saying that <B>Bidirectional Iterator</B> is a <I>refinement</I>
 of <B>Input Iterator</B>. Refinement of concepts is very much like 
inheritance of C++ classes; the main reason we use a different word, 
instead of just calling it &quot;inheritance&quot;, is to emphasize 
that refinement applies to concepts rather than to actual types.</P>
<P>
There are actually three more iterator concepts in addition to the two 
that we have already discussed:  the five iterator concepts are 
<B><A href="OutputIterator.html">Output Iterator</A></B>, <B><A href="InputIterator.html">Input Iterator</A></B>, 
<B><A href="ForwardIterator.html">Forward Iterator</A></B>, <B><A href="BidirectionalIterator.html">Bidirectional Iterator</A></B>, and 
<B><A href="RandomAccessIterator.html">Random Access Iterator</A>;</B> <B>Forward Iterator</B> is a 
refinement of <B>Input Iterator</B>, <B>Bidirectional Iterator</B> 
is a refinement of <B>Forward Iterator</B>, and <B>Random Access Iterator</B>
is a refinement of <B>Bidirectional Iterator</B>.   (<B><A href="OutputIterator.html">Output Iterator</A></B>
is related to the other four concepts, but it is not part of the hierarchy
of refinement: it is not a refinement of any of the other iterator concepts,
and none of the other iterator concepts are refinements of it.)

The <I><A href="Iterators.html">Iterator Overview</A></I> has more information about iterators 
in general. </P>
<P>
Container classes, like iterators, are organized into a hierarchy of 
concepts. All containers are models of the concept <B><A href="Container.html">Container</A></B>; 
more refined concepts, such as <B><A href="Sequence.html">Sequence</A></B> and 
<B><A href="AssociativeContainer.html">Associative Container</A></B>, describe specific types of containers. 
</P>
<H2>
Other parts of the STL</H2>
<P>
If you understand algorithms, iterators, and containers, then you 
understand almost everything there is to know about the STL. The STL 
does, however, include several other types of components. </P>
<P>
First, the STL includes several  <I>utilities</I>: very basic concepts 
and functions that are used in many different parts of the library. The 
concept<B> <A href="Assignable.html">Assignable</A></B>, for example, describes types that have 
assignment operators and copy constructors; almost all STL classes are 
models of <B>Assignable</B>, and almost all STL algorithms require 
their arguments to be models of <B>Assignable</B>. </P>
<P>
Second, the STL includes some low-level mechanisms for allocating and 
deallocating memory. <I><A href="Allocators.html">Allocators</A></I> are very specialized, and 
you can safely ignore them for almost all purposes. </P>
<P>
Finally, the STL includes a large collection of <I><A href="functors.html">function objects</A></I>, 
also known as <I>functors</I>. Just as iterators are a generalization 
of pointers, function objects are a generalization of functions: a 
function object is anything that you can call using the ordinary 
function call syntax. There are several different concepts relating to 
function objects, including <B><A href="UnaryFunction.html">Unary Function</A></B> (a function 
object that takes a single argument, <I>i.e.</I> one that is called as <TT>f(x)</TT>) 
and <B><A href="BinaryFunction.html">Binary Function</A></B> (a function object that takes two 
arguments, <I>i.e.</I> one that is called as <TT>f(x, y)</TT>). Function 
objects are an important part of generic programming because they allow 
abstraction not only over the types of objects, but also over the 
operations that are being performed. </P>

<!-- start footer -->
<!-- Footer Begins -->

<STYLE TYPE="text/css">
<!--
TD.footer, TD.footer A{
		font-family: Arial, helvetica, sans-serif;
        	font-size: 8pt;

}

A.home {
font-family: Arial, helvetica, sans-serif;
}
-->
</STYLE>
<P>
<A CLASS="home" HREF="index.html">STL Home</A>
<P>
<TABLE WIDTH="600" CELLPADDING="0" CELLPADDING="0" BORDER="0">
	<TR>
	    <TD ALIGN="RIGHT" CLASS="footer"><A HREF="/company_info/terms.html" TARGET="_top">terms of use</A> | <A HREF="/company_info/privacy.html" TARGET="_top">privacy policy</A></TD>
	    <TD ALIGN="CENTER" CLASS="footer">&nbsp;|&nbsp;</TD>
	    <TD ALIGN="LEFT" CLASS="footer"><A HREF="/cgi-bin/feedback/" TARGET="_top">contact us</A></TD>
	</TR><TR>
	    <TD ALIGN="RIGHT" CLASS="footer">Copyright &copy; 1993-2003 Silicon Graphics, Inc. All rights reserved.</TD>
	    <TD ALIGN="CENTER" CLASS="footer">&nbsp;|&nbsp;</TD>
	    <TD ALIGN="LEFT" CLASS="footer"><A HREF="/company_info/trademarks/" TARGET="_top">Trademark Information</A></TD>
	</TR>
</TABLE>

<!-- Footer Ends -->

<!-- end footer -->
<P>
</BODY>
</HTML>