type is substituted for <TT>InputIterator</TT> must provide certain 
operations: it must be possible to compare two objects of that type for 
equality, it must be possible to increment an object of that type, it 
must be possible to dereference an object of that type to obtain the 
object that it points to, and so on. </P>
<P>
<TT>Find</TT> isn't the only STL algorithm that has such a set of 
requirements; the arguments to <TT><A href="for_each.html">for_each</A></TT> and <TT><A href="count.html" tppabs="http://www.sgi.com/Technology/STL/count.shtml">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" tppabs="http://www.sgi.com/Technology/STL/InputIterator.shtml">Input Iterator</A></B>, 
<B><A href="ForwardIterator.html">Forward Iterator</A></B>, <B><A href="BidirectionalIterator.html" tppabs="http://www.sgi.com/Technology/STL/BidirectionalIterator.shtml">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>

<HR SIZE="6"> <FONT SIZE="-2"> Copyright &copy; 1996 Silicon Graphics, Inc.
<HR>
<TABLE BORDER=0 WIDTH="100%" >
<TR>
<TD WIDTH="33%"><FONT SIZE=-1><A HREF="index.html" >
STL</A></FONT></TD>

<TD WIDTH="33%">
<CENTER><FONT SIZE=-2>&copy; Copyright 1997-1998 CodeGuru</FONT>&nbsp;</CENTER>
</TD>

<TD WIDTH="34%">
<DIV ALIGN=right><FONT SIZE=-1>Contact : <A HREF="mailto:webmaster@codeguru.com">webmaster@codeguru.com</A>&nbsp;</FONT></DIV>
</TD>
</TR>
</TABLE>
<SCRIPT LANGUAGE="JavaScript" ><!--
var adurl = "/cgi-bin/doubleclick.cgi?";

if( self.adcategory )
	adurl += adcategory;
else
	adurl += "mfc";

if( self.parent.norefreshad )
	parent.norefreshad = false;
else if( validframes )
	parent.frames['ad'].location = adurl;



if( !validframes && nfrm == -1)
{
	var dclkPage = "www.codeguru.com/";
	if( self.adcategory )
		dclkPage += adcategory;
	else 
		dclkPage += "mfc";
//	var random = Math.random();
	document.write('<nolayer><center>');
	document.write('<iframe src="http://ad.doubleclick.net/adi/' + dclkPage + ';ord='
	 + random + '" width=470 height=62 marginwidth=0 marginheight=0 hspace=0 vspace=0 '
	 + 'frameborder=0 scrolling=no bordercolor="#000000">');
	document.write('<a href="http://ad.doubleclick.net/jump/' + dclkPage + ';ord='
	 + random + '">');
	document.write('<img src="http://ad.doubleclick.net/ad/' + dclkPage + ';ord='
	 + random + '" height=60 width=468>' + '</a>');
	document.write('</iframe>');
	document.write('</center></nolayer>');
	document.write('<layer  src="http://ad.doubleclick.net/adl/' + dclkPage + 
	 ';ord=' + random + '"></layer>');
	document.write('<ilayer visibility=hide width=468 height=83></ilayer>');
}

// -->
</SCRIPT> 
<!-- SCRIPT LANGUAGE="JavaScript" SRC="/global/fscript.js">
//
</SCRIPT --> 

<noscript>
<p align="center">
<a href="http://ad.doubleclick.net/jump/www.codeguru.com/cpp;ord=NupaBNFCY34AAHa7US4">
<img src="http://ad.doubleclick.net/ad/www.codeguru.com/cpp;ord=NupaBNFCY34AAHa7US4"></a>
</p>
</noscript>





</BODY>
</HTML>