📄 ch10.htm
字号:
<!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> </td> </tr></table><h3> <a name="Heading6"> Iterators</a></h3><p>Iterators are used to navigate sequences. They are defined in the following ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -