📄 index.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META NAME="Author" Content="Steph Mineart">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html;CHARSET=iso-8859-1">
<TITLE>ANSI/ISO C++ Professional Programmer's Handbook - Chapter 10 - STL and Generic Programming</TITLE>
<link rel="stylesheet" TYPE="text/css" href="/includes/stylesheets/ebooks.css">
</head>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF">
<CENTER>
<H1><img src="/publishers/que/series/professional/0789720221/button/que.gif" WIDTH="171" HEIGHT="66" ALIGN="BOTTOM" BORDER="0"><BR>
ANSI/ISO C++ Professional Programmer's Handbook</H1>
</CENTER>
<CENTER>
<P><A HREF="/publishers/que/series/professional/0789720221/index.htm"><img src="/publishers/que/series/professional/0789720221/button/contents.gif" WIDTH="128"
HEIGHT="28" ALIGN="BOTTOM" ALT="Contents" BORDER="0"></A>
<HR>
</CENTER>
<H1 align="center">10</H1>
<h1 align="center"> STL and Generic Programming</h1>
<address>by Danny Kalev</address>
<ul>
<li><a href="#Heading1">Introduction</a>
<li><a href="#Heading2">Generic Programming</a>
<li><a href="#Heading3">Organization of STL Header Files</a>
<ul>
<li><a href="#Heading4">Containers</a>
<li><a href="#Heading5">Algorithms</a>
<li><a href="#Heading6"> Iterators</a>
<li><a href="#Heading7"> Numeric Library</a>
<li><a href="#Heading8"> Utilities</a>
</ul>
<li><a href="#Heading9">Containers</a>
<ul>
<li><a href="#Heading10">Sequence Containers</a>
<li><a href="#Heading11">Requirements for STL Containment</a>
<li><a href="#Heading12"> The vector Container Class</a>
<li><a href="#Heading13">Container Reallocation</a>
<li><a href="#Heading14">capacity() and size()</a>
<li><a href="#Heading15">Specifying the Container's Capacity During Construction</a>
<li><a href="#Heading16">Accessing a Single Element</a>
<li><a href="#Heading17">Front and Back Operations</a>
<li><a href="#Heading18">Container Assignment</a>
<li><a href="#Heading19">Contiguity of Vectors</a>
<li><a href="#Heading20">A vector<Base> Should not Store Derived Objects</a>
<li><a href="#Heading21">FIFO Data Models</a>
</ul>
<li><a href="#Heading22">Iterators</a>
<ul>
<li><a href="#Heading23">begin() and end()</a>
<li><a href="#Heading24">The Underlying Representation of Iterators</a>
<li><a href="#Heading25">"const Correctness" of Iterators</a>
<li><a href="#Heading26"> Initializing a Vector with the Contents of a Built-in
Array</a>
<li><a href="#Heading27">Iterator Invalidation</a><a href="#Heading28">
</a>
</ul>
<li><a href="#Heading29"> Algorithms</a>
<ul>
<li><a href="#Heading30">Non-Modifying Sequence Operations</a>
<li><a href="#Heading31">Mutating Sequence Operations</a>
<li><a href="#Heading32">Sort Operations</a>
</ul>
<li><a href="#Heading33">Function Objects</a>
<ul>
<li><a href="#Heading34">Implementation of Function Objects</a>
<li><a href="#Heading35">Uses of Function Objects</a>
<li><a href="#Heading36">Predicate Objects</a>
</ul>
<li><a href="#Heading37">Adaptors</a>
<ul>
<li><a href="#Heading38">Sequence Adaptors</a>
<li><a href="#Heading39">Iterator Adaptors</a>
<li><a href="#Heading40">Function Adaptors</a>
</ul>
<li><a href="#Heading41">Allocators</a>
<li><a href="#Heading42">Specialized Containers</a>
<li><a href="#Heading43">Associative Containers</a>
<li><a href="#Heading44">Class auto_ptr</a>
<ul>
<li><a href="#Heading45">STL Containers Should not Store auto_ptr Elements</a>
</ul>
<li><a href="#Heading46">Nearly Containers</a>
<li><a href="#Heading47">Class string</a>
<ul>
<li><a href="#Heading48">Constructors</a>
<li><a href="#Heading49">Conversion to a C-string</a>
<li><a href="#Heading50">Accessing a Single Element</a>
<li><a href="#Heading51">Clearing the Contents of A string</a>
<li><a href="#Heading52">Comparison</a>
<li><a href="#Heading53">Additional Overloaded Operators</a>
<li><a href="#Heading54">Performance Issues</a>
</ul>
<li><a href="#Heading55">Conclusions</a>
</ul>
<hr size=4>
<h2><a name="Heading1">Introduction</a></h2>
<p>Object-oriented design offers a limited form of code reuse inheritance and
polymorphism. The generic programming paradigm is designed to enable a higher
level of reusability. Instead of data hiding, it relies on data independence.
C++ has two features that support data independence: templates and operator
overloading. A combination of these features allows a generic algorithm to assume
very little about the actual object to which it is applied, whether it is a
fundamental type or a user-defined type. Consequently, such an algorithm is
not confined to a specific data type, and it has a higher reusability potential
than does a type-dependent algorithm.</p>
<p>The <i>Standard Template Library</i> (<i>STL</i>) is an exemplary framework
that is built on the foundations of generic programming. STL is a collection
of generic algorithms and containers that communicate through iterators. This
chapter explores the principles of generic programming, focusing on STL. A complete
account of every STL container and algorithm can fill a book of its own, so
this chapter only discusses the basic concepts of generic programming. It starts
with an overview of STL header files. STL components are discussed next: containers,
iterators, algorithms, function objects, adaptors, and allocators. This discussion
presents some of the most widely used containers and algorithms of STL. Finally,
class <tt>string</tt> is described in detail.</p>
<h2> <a name="Heading2">Generic Programming</a></h2>
<p>Generic software is primarily reusable software. Reusability is characterized
by two key features: adaptability and efficiency. It is not difficult to imagine
highly adaptive software components that are too inefficient to become widely
used (these are usually implemented by complex inheritance hierarchies, virtual
functions, and extensive use of runtime type information). Conversely, efficient
components are generally written in low-level, platform-dependent code that
is both nonportable and hard to maintain. Templates overcome these difficulties
because they are checked at compile time rather than at runtime, because they
do not require any inheritance relation among objects, and because they are
applicable to fundamental types. The most useful generic components are containers
and algorithms. For years, programmers were implementing their own lists, queues,
sets, and other container types to make up for the lack of language support;
however, homemade containers suffer from significant drawbacks. They are not
portable, they are sometimes less than 100% bug free, their interfaces vary
from one implementation to another, and they can be less than optimal in terms
of runtime performance and memory usage.</p>
<p>In the latest phases of the standardization of C++, Alex Stepanov suggested
adding a generic library of containers and algorithms to C++. He based his proposal
on a similar generic library that he had previously designed for Ada. At that
time (November 1993), the committee was under pressure to complete the ongoing
standardization process as fast as possible. Consequently, suggestions for language
extensions were rejected one after another. However, Stepanov's proposal was
too good to be forsaken the committee adopted it unanimously.</p>
<p>The proposed generic library was a collection of containers based on mathematical
data models such as vector, queue, list, and stack. It also contained a set
of generic algorithms such as <tt>sort</tt>, <tt>merge</tt>, <tt>find</tt>,
<tt>replace</tt>, and so on. These library constituents were implemented with
templates. Still, templates alone are insufficient because fundamental types,
pointers, user-defined types, and single bits are manipulated by different language
constructs and operators. Operator overloading provides the necessary uniform
interface that abstracts the actual data type of a container or an algorithm.
The following section examines these components in greater detail.</p>
<h2> <a name="Heading3">Organization of STL Header Files</a></h2>
<p>STL components are grouped under namespace <tt>std</tt>. They are defined in
the following header files. Note that prestandardized implementations of STL
might use different header names, as indicated below.</p>
<h3> <a name="Heading4">Containers</a></h3>
<p>Container classes are defined in the following header files (see Table 10.1).
The associative containers multimap and <tt>multiset</tt> are defined in <tt><map></tt>
and <tt><set></tt>, respectively. Similarly, priority_queue and deque
are defined in <tt><queue></tt>. (On some prestandardized implementations,
the container adaptors stack, <tt>queue</tt>, and priority_queue are in <tt><stack.h></tt>).</p>
<p> </p>
<h4> Table 10.1 STL Containers </h4>
<table border>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><b>Header</b></p>
</td>
<td colspan=1 align="left">
<p><b>Contents</b></p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><vector></tt></p>
</td>
<td colspan=1 align="left">
<p>An array of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><list></tt></p>
</td>
<td colspan=1 align="left">
<p>A doubly-linked list of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><deque></tt></p>
</td>
<td colspan=1 align="left">
<p>A double-ended queue of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><queue></tt></p>
</td>
<td colspan=1 align="left">
<p>A queue of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><stack></tt></p>
</td>
<td colspan=1 align="left">
<p>A stack of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><map></tt></p>
</td>
<td colspan=1 align="left">
<p>An associative array of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><set></tt></p>
</td>
<td colspan=1 align="left">
<p>A set of T </p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><bitset></tt></p>
</td>
<td colspan=1 align="left">
<p>A set of Boolean values </p>
</td>
</tr>
</table>
<p></p>
<h3> <a name="Heading5">Algorithms</a></h3>
<p>STL generic algorithms can be applied to a sequence of elements. They are defined
in the following header file (see Table 10.2). (On prestandardized implementations,
generic algorithms are defined in <tt><algo.h></tt>).</p>
<h4> Table 10.2 STL Algorithms </h4>
<table border>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><b>Header</b></p>
</td>
<td colspan=1 align="left">
<p><b>Contents</b></p>
</td>
</tr>
<tr valign="TOP" align="left">
<td colspan=1 align="left">
<p><tt><algorithm></tt></p>
</td>
<td colspan=1 align="left">
<p>A collection of generic algorithms </p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -