ch10.htm

c++语言操作手册

  header file (see Table 10.3)</p>
<h4> Table 10.3 STL Iterators </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>&lt;iterator&gt;</tt></p>
    </td>
    <td colspan=1 align="left"> 
      <p>Various types of iterators and iterator support </p>
    </td>
  </tr>
</table>
<h3> <a name="Heading7"> Numeric Library</a></h3>
<p>STL provides several classes and algorithms that are specifically designed 
  for numeric computations (see Table 10.4).</p>
<h4> Table 10.4 Numeric Containers and 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>&lt;complex&gt;</tt></p>
    </td>
    <td colspan=1 align="left"> 
      <p>Complex numbers and their associated operations </p>
    </td>
  </tr>
  <tr valign="TOP" align="left"> 
    <td colspan=1 align="left"> 
      <p><tt>&lt;valarray&gt;</tt></p>
    </td>
    <td colspan=1 align="left"> 
      <p>Mathematical vectors and their associated operations </p>
    </td>
  </tr>
  <tr valign="TOP" align="left"> 
    <td colspan=1 align="left"> 
      <p><tt>&lt;numerics&gt;</tt></p>
    </td>
    <td colspan=1 align="left"> 
      <p>Generalized numeric operations </p>
    </td>
  </tr>
</table>
<h3> <a name="Heading8"> Utilities</a></h3>
<p>The following headers define auxiliary components that are used in STL containers 
  and algorithms (see Table 10.5). These include function adaptors, pairs, and 
  class <tt>auto_ptr</tt> (discussed later). </p>
<h4> Table 10.5 General Utilities </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>&lt;utility&gt;</tt></p>
    </td>
    <td colspan=1 align="left">
      <p>Operators and pairs </p>
    </td>
  </tr>
  <tr valign="TOP" align="left"> 
    <td colspan=1 align="left">
      <p><tt>&lt;functional&gt;</tt></p>
    </td>
    <td colspan=1 align="left">
      <p>Function objects </p>
    </td>
  </tr>
  <tr valign="TOP" align="left"> 
    <td colspan=1 align="left">
      <p><tt>&lt;memory&gt;</tt></p>
    </td>
    <td colspan=1 align="left">
      <p>Allocators and <tt>auto_ptr </tt></p>
    </td>
  </tr>
</table>
<h2> <a name="Heading9">Containers</a></h2>
<p>A container is an object that can hold other objects as its elements. A generic 
  container is not confined to a specific type it can store objects of any kind. 
  C supports one container type in the form of built-in arrays. Other languages 
  support other data models. Pascal, for example, has a built-in <tt>set</tt> 
  type, and Lisp supports lists (hence its name). C++ inherited from C its support 
  for arrays. Arrays have several properties that more or less correspond to the 
  mathematical notion of a vector: They can store any data type and they provide 
  random access that is, the time needed to access any element is identical, regardless 
  of the element's position.</p>
<p>Still, under some circumstances, arrays are less convenient than other data 
  models; it is impossible to insert a new element in the middle of an array. 
  Also, you cannot append new elements to the end of an array. With other data 
  models, (a list, for example), it is possible to insert new elements in the 
  middle of the container or to append elements to its end. A special type of 
  list, a <i>heterogenic list</i>, can hold elements of different types at the 
  same time.</p>
<h3> <a name="Heading10">Sequence Containers</a></h3>
<p>A sequence container organizes a collection of objects of the same type <tt>T</tt> 
  into a strictly linear arrangement. Following are examples of sequence containers:</p>
<ul>
  <li>
    <p> <b>T v[n]</b> A built-in array that stores a fixed number of <i>n</i> 
      elements and provides random access to them.</p>
  </li>
  <p></p>
  <li>
    <p> <b>std::vector&lt;T&gt;</b> An array-like container that stores a varying 
      number of n elements and provides random access to them. Insertions and 
      deletions at the end of a vector are constant time operations.</p>
  </li>
  <p></p>
  <li>
    <p> <b>std::deque&lt;T&gt;</b> A double-ended queue that provides random access 
      to a sequence of varying length, with constant time insertions and deletions 
      at the beginning and the end.</p>
  </li>
  <p></p>
  <li>
    <p> <b>std::list&lt;T&gt;</b> A list that provides linear time access to a 
      sequence of varying length, with constant time insertions and deletions 
      at any position.</p>
  </li>
</ul>
<p></p>
<p>Interestingly, built-in arrays are considered sequence containers because STL 
  algorithms are designed to work with them as they work with other sequence types.</p>
<h3> <a name="Heading11">Requirements for STL Containment</a></h3>
<p>Elements of STL containers must be<i> copy-constructible </i>and<i> assignable</i>. 
  Essentially, copy-constructible means that an object and a copy of that object 
  must be identical (although the formal definition in the Standard is somewhat 
  more complicated than that). Likewise, assignable means that assigning one object 
  to another results in two identical objects. These definitions might sound trivial 
  because objects in general are copy-constructible and assignable; later, however 
  (when class <tt>auto_ptr</tt> is discussed), you will see an example of an object 
  that does not meet these requirements and is, therefore, not to be stored in 
  STL containers.</p>
<p>An additional requirement is that container elements must have their copy constructor, 
  default constructor, assignment operator, and destructor publicly declared (either 
  explicitly or implicitly).</p>
<h3> <a name="Heading12"> The vector Container Class</a></h3>
<p>The standard containers share a common interface, but each container also defines 
  particular operations. Following is the interface of class <tt>vector&lt;T&gt;</tt>:</p>
<pre>
<tt>namespace std {</tt>
<tt>       template &lt;class T, class Allocator = allocator&lt;T&gt; &gt;</tt>
<tt>       class vector {</tt>
<tt>       public:</tt>
<tt>         // implementation-defined types</tt>
<tt>         typedef<cite> implementation defined</cite>                iterator;</tt>
<tt>         typedef <cite>implementation defined</cite>                const_iterator;</tt>
<tt>         typedef <cite>implementation defined</cite>                size_type;</tt>
<tt>         typedef <i>implementation defined</i>                difference_type;</tt>
<tt>         // additional types</tt>
<tt>         typedef typename Allocator::reference         reference;</tt>
<tt>         typedef typename Allocator::const_reference   const_reference;</tt>
<tt>         typedef T  value_type;</tt>
<tt>         typedef Allocator                             allocator_type;</tt>
<tt>         typedef typename Allocator::pointer           pointer;</tt>
<tt>         typedef typename Allocator::const_pointer     const_pointer</tt>
<tt>         typedef std::reverse_iterator&lt;iterator&gt;       reverse_iterator;</tt>
<tt>         typedef std::reverse_iterator&lt;const_iterator&gt; const_reverse_iterator;</tt>
<tt>         // construction, copying destruction and assignment operations</tt>
<tt>         explicit vector(const Allocator&amp; = Allocator());</tt>
<tt>         explicit vector(size_type n, const T&amp; value = T(),</tt>
<tt>                              const Allocator&amp; = Allocator());</tt>
<tt>         template &lt;class InputIterator&gt;</tt>
<tt>           vector(InputIterator first, InputIterator last,</tt>
<tt>             const Allocator&amp; = Allocator());</tt>
<tt>         vector(const vector&lt;T,Allocator&gt;&amp; x);</tt>
<tt>        ~vector();</tt>
<tt>         vector&lt;T,Allocator&gt;&amp; operator=(const vector&lt;T,Allocator&gt;&amp; x);</tt>
<tt>         template &lt;class InputIterator&gt;</tt>
<tt>           void assign(InputIterator first, InputIterator last);</tt>
<tt>         void assign(size_type n, const T&amp; u);</tt>
<tt>         allocator_type get_allocator() const;</tt>
<tt>         //iterators</tt>
<tt>         iterator               begin();</tt>
<tt>         const_iterator         begin() const;</tt>
<tt>         iterator               end();</tt>
<tt>         const_iterator         end() const;</tt>
<tt>         reverse_iterator       rbegin();</tt>
<tt>         const_reverse_iterator rbegin() const;</tt>
<tt>         reverse_iterator       rend();</tt>
<tt>         const_reverse_iterator rend() const;</tt>
<tt>         //capacity operations</tt>
<tt>         size_type size() const;</tt>
<tt>         size_type max_size() const;</tt>
<tt>         void      resize(size_type sz, T c = T());</tt>
<tt>         size_type capacity() const;</tt>
<tt>         bool      empty() const;</tt>
<tt>         void      reserve(size_type n);</tt>
<tt>         //element access operations</tt>
<tt>         reference       operator[](size_type n);</tt>
<tt>         const_reference operator[](size_type n) const;</tt>
<tt>         const_reference at(size_type n) const;</tt>
<tt>         reference       at(size_type n);</tt>
<tt>         reference       front();</tt>
<tt>         const_reference front() const;</tt>
<tt>         reference       back();</tt>
<tt>         const_reference back() const;</tt>
<tt>         // modifiers</tt>
<tt>         void push_back(const T&amp; x);</tt>
<tt>         void pop_back();</tt>
<tt>         iterator insert(iterator position, const T&amp; x);</tt>
<tt>         void     insert(iterator position, size_type n, const T&amp; x);</tt>
<tt>         template &lt;class InputIterator&gt;</tt>
<tt>             void insert(iterator position,</tt>
<tt>                         InputIterator first, InputIterator last);</tt>
<tt>         iterator erase(iterator position);</tt>
<tt>         iterator erase(iterator first, iterator last);</tt>
<tt>         void     swap(vector&lt;T,Allocator&gt;&amp;);</tt>
<tt>         void     clear();</tt>
<tt>       }; //class vector</tt>
<tt>       //non-member overloaded operators</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator==(const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator&lt; (const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator!=(const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator&gt; (const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator&gt;=(const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         bool operator&lt;=(const vector&lt;T,Allocator&gt;&amp; x,</tt>
<tt>                         const vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>       //specialized algorithms</tt>
<tt>       template &lt;class T, class Allocator&gt;</tt>
<tt>         void swap(vector&lt;T,Allocator&gt;&amp; x, vector&lt;T,Allocator&gt;&amp; y);</tt>
<tt>     }//namespace std</tt>
</pre>
<p>On most implementations, the parameterized types <tt>size_type</tt> and <tt>difference_type</tt> 
  have the default values <tt>size_t</tt> and <tt>ptrdiff_t</tt>, respectively. 
  However, they can be replaced by other types for particular specializations.</p>
<p>The storage of STL containers automatically grows as necessary, freeing the 
  programmer from this tedious and error-prone task. For example, a <tt>vector</tt> 
  can be used to read an unknown number of elements from the keyboard:</p>
<pre>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>