?? stl_introduction.html
字號:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Author" CONTENT="Zafir Anjum">
<TITLE>MFC Programmer's SourceBook : STL Programmer's Guide</TITLE>
<META name="description"
content="A freely available implementation
of the C++ Standard Template Library, including
hypertext documentation.">
<META name="keywords"
content="generic programming, STL, standard template library">
</HEAD>
<SCRIPT LANGUAGE="JavaScript"><!--
var adcategory = "cpp";
// -->
</SCRIPT>
<body background="../../fancyhome/back.gif" bgcolor="#FFFFFF" >
<SCRIPT LANGUAGE="JavaScript"><!--
var nfrm = location.href.indexOf("_nfrm_");
var validframes = (top.frames.length > 0 && top.frames['ad'] && top.frames['logo'] );
var random = Math.random();
if( !validframes && nfrm == -1 )
{
var dclkPage = "www.codeguru.com/";
if( self.adcategory )
dclkPage += adcategory;
else
dclkPage += "mfc";
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>');
}
// top.location = "/show.cgi?" + adcategory + "=" + location.pathname;
// -->
</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>
<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" tppabs="http://www.sgi.com/Technology/STL/List.shtml">list</A></TT>, <TT><A href="Deque.html" tppabs="http://www.sgi.com/Technology/STL/Deque.shtml">deque</A></TT>, <TT><A href="set.html" tppabs="http://www.sgi.com/Technology/STL/set.shtml">set</A></TT>, <TT><A href="multiset.html" tppabs="http://www.sgi.com/Technology/STL/multiset.shtml">multiset</A></TT>, <TT><A href="Map.html" tppabs="http://www.sgi.com/Technology/STL/Map.shtml">map</A></TT>, <TT><A href="Multimap.html" tppabs="http://www.sgi.com/Technology/STL/Multimap.shtml">multimap</A></TT>, <TT><A href="hash_set.html" tppabs="http://www.sgi.com/Technology/STL/hash_set.shtml">hash_set</A></TT>, <TT><A href="hash_multiset.html" tppabs="http://www.sgi.com/Technology/STL/hash_multiset.shtml">hash_multiset</A></TT>, <TT><A href="hash_map.html" tppabs="http://www.sgi.com/Technology/STL/hash_map.shtml">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
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -