📄 index.html
字号:
<!-- -*-html-*-
$Source: /usr/local/cvsroot/BigC++/23/index.html,v $
$Revision: 1.4 $
Big C++, chptr 23
editor: cols=80, tabstop=2
(c) 2005 John Wiley & Sons
Kurt Schmidt, kschmidt@cs.drexel.edu
NOTES
- 3 spaces are used for each indent in examples
REVISIONS:
$Log: index.html,v $
Revision 1.4 2004/04/20 22:03:01 kurt
Made slides smaller (view %150, on 1024x768 display)
Revision 1.3 2004/02/23 16:47:28 kurt
pared verbage, put image in
Revision 1.2 2004/02/01 16:47:43 kurt
Pared language, split long slides
Revision 1.1 2004/01/31 22:36:09 kurt
Creation
-->
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="Copyright" content="2005 John Wiley & Sons">
<meta name="Author" content="Kurt Schmidt">
<script language="JavaScript" src="./config.js"></script>
<script language="JavaScript" src="./pageFormat.js"></script>
<script><!-- // Set title on page
title()
//--></script>
</head>
<body>
<hr><h2><font color="#009999" size="+3">Chapter 23 - The Standard Template
Library - Containers</font></h2>
<font size="+1">
<script><!--
image( "cover.png" )
//--></script>
</font>
<hr><h2><font color="#009999" size="+2">Chapter Goals</font></h2>
</font>
<hr noshade size="4" color="#009999">
<font size="+1">
<ul>
<li>To understand the purpose and use of the containers in the Standard
Template Library</li>
<ul>
<li>The fundamental sequential containers - vector, list, deque</li>
<li>The adapter containers - stack, queue, and priority queue</li>
<li>The ordered container - set</li>
<li>The associative container - map</li>
</ul>
</li>
</ul>
</font>
<hr><h2><font color="#009999">23.1 The Standard Template Library
(STL)</font></h2>
<font size="+1">
<ul>
<li>Library of collection classes and associated functions</li>
<li>Found in most nontrivial applications</li>
<li>Simplifies creation of new applications</li>
<li>Promote reliability and portability</li>
<li>Containers represented by class templates w/small interfaces</li>
<li>Functionality extended by generic algorithms, used w/many
types of containers</li>
</ul>
</font>
<hr><h2><font color="#009999">23.1.1 STL Container Categories</font></h2>
<font size="+1">
<p>3 categories of containers:</p>
<ol>
<li>Fundamental (or <i>sequential</i>)
<ul>
<li>vector, list, deque (pronounced "deck")</li>
</ul>
</li>
<li>Adapters
<ul>
<li>Layered on top of the fundamental containers</li>
<li>stack, queue, priority queue</li>
</ul>
</li>
<li>Associative
<ul>
<li>set, map</li>
</ul>
</li>
</ol>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers</font></h2>
<font size="+1">
<ul>
<li>Overlap of operations among these containers (see table, next slide)</li>
<li>The 3 containers often interchangeable:
<blockquote>
<pre>vector<int>::iterator current
= a_container.begin();
while (current != a_container.end())
{
<font color="#0000cc">// Number is even if remainder is
// zero after division by two</font>
if (0 == *current % 2)
current = a_container.erase(current);
else
++current;
}</pre>
</blockquote>
</li>
</ul>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<table width="80%" border="1">
<tr bgcolor="#00ffff">
<th>Operation</th>
<th>Vector</th>
<th>List</th>
<th>Queue</th>
</tr>
<tr align="center">
<td><tt>container()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>container(<i>size</i>)</tt></td>
<td>O(1)</td>
<td>O(<i>n</i>)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>container(<i>size</i>, <i>value</i>)</tt></td>
<td>O(<i>n</i>)</td>
<td>O(<i>n</i>)</td>
<td>O(<i>n</i>)</td>
</tr>
<tr align="center">
<td><tt>at(int)</tt></td>
<td>O(1)</td>
<td> </td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>back()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>begin()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>capacity()</tt></td>
<td>O(1)</td>
<td> </td>
<td> </td>
</tr>
<tr align="center">
<td><tt>clear()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>empty()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
</table>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<table width="80%" border="1">
<tr bgcolor="#00ffff">
<th>Operation</th>
<th>Vector</th>
<th>List</th>
<th>Queue</th>
</tr>
<tr align="center">
<td><tt>end()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>erase(<i>iterator</i>)</tt></td>
<td>O(<i>n</i>)</td>
<td>O(1)</td>
<td>O(<i>n</i>)</td>
</tr>
<tr align="center">
<td><tt>erase(<i>iterator</i>, <i>iterator</i>)</tt></td>
<td>O(<i>n</i>)</td>
<td>O(1)</td>
<td>O(<i>n</i>)</td>
</tr>
<tr align="center">
<td><tt>front()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>insert( <i>iterator</i>, <i>value</i>)</tt></td>
<td>O(<i>n</i>)</td>
<td>O(1)</td>
<td>O(<i>n</i>)</td>
</tr>
<tr align="center">
<td><tt>pop_back()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>pop_front()</tt></td>
<td> </td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>push_back(<i>value</i>)</tt></td>
<td>O(1)+</td>
<td>O(1)</td>
<td>O(1)+</td>
</tr>
<tr align="center">
<td><tt>push_front(<i>value</i>)</tt></td>
<td> </td>
<td>O(1)</td>
<td>O(1)+</td>
</tr>
</table>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<table width="80%" border="1">
<tr bgcolor="#00ffff">
<th>Operation</th>
<th>Vector</th>
<th>List</th>
<th>Queue</th>
</tr>
<tr align="center">
<td><tt>rbegin()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>rend()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>resize()</tt></td>
<td>O(<i>n</i>)</td>
<td> </td>
<td>O(<i>n</i>)</td>
</tr>
<tr align="center">
<td><tt>size()</tt></td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>operator[]()</tt></td>
<td>O(1)</td>
<td> </td>
<td>O(1)</td>
</tr>
<tr align="center">
<td><tt>operator=(<i>container</i>)</tt></td>
<td>O(<i>n</i>)</td>
<td>O(<i>n</i>)</td>
<td>O(<i>n</i>)</td>
</tr>
</table>
<p><b>O(1)+</b> - means <i>amortized</i> constant time
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<dl>
<dt><b>C'tors</b></dt>
<dd>Default creates an empty container</dd>
<dd>Integer arg. creates container with <i>size</i> elements,
initialized to default value
<ul>
<li>2nd form allows explicit initialization. Same for all
elements</li>
</ul>
</dd>
<dd>Can be initialized with another collection</dd>
<dt><b><tt>at</tt></b></dt>
<dd>checks for index validity, unlike <tt>operator[]</tt></dd>
<dt><b><tt>front</tt>, <tt>back</tt></b></dt>
<dd>return the first and last elements</dd>
<dt><b><tt>empty</tt></b></dt>
<dd>returns <tt>true</tt> if container has no elements</dd>
</dl>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<dl>
<dt><b><tt>erase</tt></b></dt>
<dd>removes specified element(s), returns iterator to next element</dd>
<dt><b><tt>insert</tt></b></dt>
<dd>inserts element prior to the iterator</dd>
<dt><b><tt>push_front</tt>, <tt>push_back</tt></b></dt>
<dd>insert values at the front and back</dd>
<dt><b><tt>pop_front</tt>, <tt>pop_back</tt></b></dt>
<dd>remove them</dd>
<dt><b><tt>rbegin</tt>, <tt>rend</tt></b></dt>
<dd>return <tt>reverse_iterator</tt>s</dd>
</dl>
</font>
<hr><h2><font color="#009999">23.2 The Fundamental Containers (cont.)
</font></h2>
<font size="+1">
<ul>
<li>Generic algorithms extend classes (next chapter)</li>
<li>Similar, not identical, behavior</li>
<li>Not all operations are supported in all containers</li>
<li>Common operations may have different complexity (see chptr. 15)</li>
<li>To choose an appropriate container:
<ul>
<li>Which operations are req'd?</li>
<li>How often each operation will be performed (relatively)?</li>
</ul>
</li>
</ul>
</font>
<hr><h2><font color="#009999">23.2.1 Vectors</font></h2>
<font size="+1">
<ul>
<li>Indexed container</li>
<li>Declared in <tt><vector></tt>
<li>Subscripting (<tt>operator[]</tt>) is the fundamental operation</li>
<li><tt>push_back</tt> - adds elements at back (resizing as needed)</li>
<li>E.g., the Sieve of Eratosthenes, to discover prime numbers
(ex. P16.15)
<ul>
<li>Start w/a vector of <tt>bool</tt>s, initialized to <tt>true</tt></li>
<li>Increasing from 2, for each that is still <tt>true</tt>, strike out
all multiples of that number</li>
</ul>
</li>
</ul>
</font>
<hr><h2><font color="#009999">23.2.1 Vectors - Sieve of Eratosthenes
</font></h2>
<font size="+1">
<script><!--
iframeWrapCode( "sieve.cpp", "90%", "80%" )
//--></script>
</font>
<hr><h2><font color="#009999">Advanced Topic 23.1</font></h2>
<font size="+1">
<hr color="#00ffff" size="6">
<p><font color="#009999">Implementation of Vector</font></p>
<ul>
<li>Built on an array, allocated from the heap</li>
<li>Store a pointer, the size and the capacity</li>
<li>Usually larger than needed</li>
<li>When needed <tt>vector</tt> will
<ul>
<li>get a new buffer, at least double the previous size</li>
<li>copy elements over</li>
</ul>
</li>
<li><tt>push_front</tt> and <tt>pop_front</tt> would be O(<i>n</i>) tasks,
so, not implemented</li>
</ul>
</font>
<hr><h2><font color="#009999">23.2.2 Lists</font></h2>
<font size="+1">
<ul>
<li>Declared in <tt><list></tt></li>
<li>Implemented as linked lists (see chptr. 16)</li>
<li>Not indexed</li>
<li>Allows O(1) insertion/removal from front and back</li>
<li>Supports insertion into the middle via iterators</li>
<li>The only container of the three that does it in constant time</li>
</ul>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -