1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
|
<HTML VERSION="2.0">
<HEAD>
<TITLE>The Standard Template Library: Introduction</TITLE>
<meta http-equiv="Job" content="pressrelease">
<meta http-equiv="Keywords" content="">
<meta http-equiv="Owner" content="John Cristofano/Ujesh Desai">
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="SGI" HEIGHT="43" WIDTH="151">
<!--end header-->
<CENTER><H1 ALIGN="CENTER">
Introduction to the Standard Template Library</H1>
</CENTER><P>
The Standard Template Library, or <I>STL</I>, is a C++ library of
container classes, algorithms, and iterators; it provides many of the
basic algorithms and data structures of computer science. The STL is a <I>generic</I>
library, meaning that its components are heavily parameterized: almost
every component in the STL is a template. You should make sure that you
understand how templates work in C++ before you use the STL.</P>
<H2>
Containers and algorithms</H2>
<P>
Like many class libraries, the STL includes <I>container</I> classes:
classes whose purpose is to contain other objects. The STL includes the
classes <TT><A href="Vector.html">vector</A></TT>, <TT><A href="List.html">list</A></TT>, <TT><A href="Deque.html">deque</A></TT>, <TT><A href="set.html">set</A></TT>, <TT><A href="multiset.html">multiset</A></TT>, <TT><A href="Map.html">map</A></TT>, <TT><A href="Multimap.html">multimap</A></TT>, <TT><A href="hash_set.html">hash_set</A></TT>, <TT><A href="hash_multiset.html">hash_multiset</A></TT>, <TT><A href="hash_map.html">hash_map</A></TT>,
and <TT><A href="hash_multimap.html">hash_multimap</A></TT>. Each of these classes is a template,
and can be instantiated to contain any type of object. You can, for
example, use a <TT>vector<int></TT> in much the same way as you
would use an ordinary C array, except that <TT>vector</TT> eliminates
the chore of managing dynamic memory allocation by hand.</P>
<PRE>
vector<int> v(3); // Declare a vector of 3 elements.
v[0] = 7;
v[1] = v[0] + 3;
v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
</PRE>
<P>
The STL also includes a large collection of <I>algorithms</I> that
manipulate the data stored in containers. You can reverse the order of
elements in a <TT>vector</TT>, for example, by using the <TT><A href="reverse.html">reverse</A></TT>
algorithm. </P>
<PRE>
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
</PRE>
<P>
There are two important points to notice about this call to <TT>reverse</TT>.
First, it is a global function, not a member function. Second, it takes
two arguments rather than one: it operates on a <I>range</I> of
elements, rather than on a container. In this particular case the range
happens to be the entire container <TT>v.</TT></P>
<P>
The reason for both of these facts is the same: <TT>reverse</TT>, like
other STL algorithms, is decoupled from the STL container classes. This
means that <TT>reverse</TT> can be used not only to reverse elements in
vectors, but also to reverse elements in lists, and even elements in C
arrays. The following program is also valid.</P>
<PRE>
double A[6] = { 1.2, 1.3, 1.4, 1.5, 1.6, 1.7 };
reverse(A, A + 6);
for (int i = 0; i < 6; ++i)
cout << "A[" << i << "] = " << A[i];
</PRE>
<P>
This example uses a <I>range</I>, just like the example of reversing a <TT>vector</TT>:
the first argument to reverse is a pointer to the beginning of the
range, and the second argument points one element past the end of the
range. This range is denoted <TT>[A, A + 6)</TT>; the asymmetrical
notation is a reminder that the two endpoints are different, that the
first is the beginning of the range and the second is <I>one past</I>
the end of the range. </P>
<H2>
Iterators</H2>
<P>
In the example of reversing a C array, the arguments to <TT>reverse</TT>
are clearly of type <TT>double*</TT>. What are the arguments to
reverse if you are reversing a <TT>vector</TT>, though, or a <TT>list</TT>?
That is, what exactly does <TT>reverse</TT> declare its arguments to
be, and what exactly do <TT>v.begin()</TT> and <TT>v.end()</TT> return? </P>
<P>
The answer is that the arguments to <TT>reverse</TT> are <I>iterators</I>,
which are a generalization of pointers. Pointers themselves are
iterators, which is why it is possible to reverse the elements of a C
array. Similarly, <TT>vector</TT> declares the nested types <TT>iterator</TT>
and <TT>const_iterator</TT>. In the example above, the type returned
by <TT>v.begin()</TT> and <TT>v.end()</TT> is <TT>vector<int>::iterator</TT>.
There are also some iterators, such as <TT><A href="istream_iterator.html">istream_iterator</A></TT>
and <TT><A href="ostream_iterator.html">ostream_iterator</A></TT>, that aren't associated with
containers at all. </P>
<P>
Iterators are the mechanism that makes it possible to decouple
algorithms from containers: algorithms are templates, and are
parameterized by the type of iterator, so they are not restricted to a
single type of container. Consider, for example, how to write an
algorithm that performs linear search through a range. This is the
STL's <TT><A href="find.html">find</A></TT> algorithm. </P>
<PRE>
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
while (first != last && *first != value) ++first;
return first;
}
</PRE>
<P>
<TT>Find</TT> takes three arguments: two iterators that define a range,
and a value to search for in that range. It examines each iterator in
the range <TT>[first, last)</TT>, proceeding from the beginning
to the end, and stops either when it finds an iterator that points to <TT>value</TT>
or when it reaches the end of the range. </P>
<P>
<TT>First</TT> and <TT>last</TT> are declared to be of type <TT>InputIterator</TT>,
and <TT>InputIterator</TT> is a template parameter. That is, there
isn't actually any type called <TT>InputIterator</TT>: when you call <TT>find</TT>,
the compiler substitutes the actual type of the arguments for the
formal type parameters <TT>InputIterator</TT> and <TT>T</TT>. If
the first two arguments to <TT>find</TT> are of type <TT>int*</TT> and
the third is of type <TT>int</TT>, then it is as if you had called the
following function.</P>
<PRE>
int* find(int* first, int* last, const int& value) {
while (first != last && *first != value) ++first;
return first;
}
</PRE>
<H2>
Concepts and Modeling</H2>
<P>
One very important question to ask about any template function, not
just about STL algorithms, is what the set of types is that may
correctly be substituted for the formal template parameters. Clearly,
for example, <TT>int*</TT> or <TT>double*</TT> may be substituted for <TT>find</TT>'s
formal template parameter <TT>InputIterator</TT>. Equally clearly, <TT>int</TT>
or <TT>double</TT> may not: <TT>find</TT> uses the expression <TT>*first</TT>,
and the dereference operator makes no sense for an object of type <TT>int</TT>
or of type <TT>double</TT>. The basic answer, then, is that <TT>find</TT>
implicitly defines a set of requirements on types, and that it may be
instantiated with any type that satisfies those requirements. Whatever
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">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 "inheritance", 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-->
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54"
ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif"
HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright ©
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>
|