ch10.htm

c++语言操作手册

<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;int&gt; v(1);  //room for a single element</tt>
<tt>  v[0] = 10;</tt>
<tt>  vector&lt;int&gt;::iterator p  = v.begin();   // p points to the first element of v</tt>
<tt>  *p = 11; //assign a new value to v[0] through p</tt>
<tt>  cout &lt;&lt; *p;  //output 11</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>The member function <tt>end()</tt>, on the other hand, returns an iterator 
  that points one position <i>past</i> the last valid element of the container. 
  This sounds surprising at first, but there's nothing really unusual about it 
  if you consider how C-strings are represented: An additional null character 
  is automatically appended one position past the final element of the <tt>char</tt> 
  array. The additional element in STL has a similar role it indicates the end 
  of the container. Having <tt>end()</tt> return an iterator that points one position 
  past the container's elements is useful in <tt>for</tt> and <tt>while</tt> loops. 
  For example</p>
<pre>
<tt>  vector &lt;int&gt; v(10);</tt>
<tt>  int n=0;</tt>
<tt>  for (vector&lt;int&gt;::iterator p = v.begin(); p&lt;v.end(); p++)</tt>
<tt>    *p = n++;</tt>
</pre>
<p><tt>begin()</tt> and <tt>end()</tt> come in two versions: <tt>const</tt> and 
  non-<tt>const</tt>. The non-<tt>const</tt> version returns a <i>non-const iterator</i>, 
  which enables the user to modify the values of the container's element, as you 
  just saw. The <tt>const</tt> version returns a <i>const iterator</i>, which 
  cannot modify its container. </p>
<p>For example</p>
<pre>
<tt>  const vector &lt;char&gt; v(10);</tt>
<tt>  vector&lt;char&gt;::iterator p  = v.begin(); //error, must use a const_iterator</tt>
<tt>  vector&lt;char&gt;::const_iterator cp  = v.begin(); //OK</tt>
<tt>  *cp = 'a'; //error, attempt to modify a const object</tt>
<tt>  cout &lt;&lt; *cp;  //OK</tt>
</pre>
<p>The member functions <tt>rbegin()</tt> and <tt>rend()</tt> (reverse <tt>begin()</tt> 
  and reverse <tt>end()</tt>) are similar to <tt>begin()</tt> and <tt>end()</tt>, 
  except that they return <i>reverse iterators</i>, which apply to reverse sequences. 
  Essentially, reverse iterators are ordinary iterators, except that they invert 
  the semantics of the overloaded <tt>++</tt> and <tt>--</tt> operators. They 
  are useful when the elements of a container are accessed in reverse order. </p>
<p>For example</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;string&gt;</tt>
<tt>using namespace std;</tt>
<tt>void ascending_order()</tt>
<tt>{</tt>
<tt>  vector &lt;double&gt; v(10);</tt>
<tt>  double d = 0.1;</tt>
<tt>  for (vector&lt;double&gt;::iterator p = v.begin(); p&lt;v.end(); p++) //initialize</tt>
<tt>  {</tt>
<tt>    *p = d;</tt>
<tt>    d+= 0.1;</tt>
<tt>  }</tt>
<tt>   //display elements of v in ascending order</tt>
<tt>  for (vector&lt;double&gt;::reverse_iterator rp = v.rbegin(); rp &lt; v.rend(); rp++)</tt>
<tt>  {</tt>
<tt>    cout&lt;&lt; *rp&lt;&lt;endl;</tt>
<tt>  }</tt>
<tt>}</tt>
</pre>
<p>Like <tt>begin()</tt> and <tt>end()</tt>, <tt>rbegin()</tt> and <tt>rend()</tt> 
  have a <tt>const</tt> and a non-<tt>const</tt> version.</p>
<h3> <a name="Heading24">The Underlying Representation of Iterators</a></h3>
<p>Most implementations of STL use pointers as the underlying representation of 
  iterators. However, an iterator need not be a pointer, and there's a good reason 
  for that. Consider a huge vector of scanned images that are stored on a 6GB 
  disk; the built-in pointer on most machines has only 32 bits, which is not large 
  enough to iterate through this large vector. Instead of a bare pointer, an implementation 
  can use a 64-bit integer as the underlying iterator in this case. Likewise, 
  a container that holds elements such as bits and nibbles (to which built-in 
  pointers cannot refer) can be implemented with a different underlying type for 
  iterators and still provide the same interface. However, bare pointers can sometimes 
  be used to iterate through the elements of a container on certain implementations; 
  for example</p>
<pre>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>void hack()</tt>
<tt>{</tt>
<tt>  vector&lt;int&gt; vi;</tt>
<tt>  vi.push_back(5);</tt>
<tt>  int *p = vi.begin();//bad programming practice, although it may work</tt>
<tt>  *p = 6; //assign vi[0]</tt>
<tt>  cout&lt;&lt;vi[0]; //output 6 (maybe)</tt>
<tt>}</tt>
</pre>
<p>Using bare pointers instead of iterators is a bad programming practice avoid 
  it.</p>
<h3> <a name="Heading25">"const Correctness" of Iterators</a></h3>
<p>Use the <tt>const</tt> iterator of a container when the elements that are accessed 
  through it are not to be modified. As with ordinary pointer types, using a non-<tt>const</tt> 
  iterator implies that the contents of the container are to be changed. A <tt>const</tt> 
  iterator enables the compiler to detect simple mistakes, and it is more readable.</p>
<h3> <a name="Heading26"> Initializing a Vector with the Contents of a Built-in 
  Array</a></h3>
<p>As was previously noted, built-in arrays are valid sequence containers. Thus, 
  the addresses of array ends can be used as iterators to initialize a vector 
  with the contents of a built-in array. For example</p>
<pre>
<tt>#include&lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  int arr[3];</tt>
<tt>  arr[0] = 4; arr[1] = 8;  arr[2] = 16;</tt>
<tt>   vector &lt;int&gt; vi ( &amp;arr[0], //address of  the array's beginning</tt>
<tt>                     &amp;arr[3] ); // must point one element <cite>past</cite> the array's end</tt>
<tt>  cout&lt;&lt; vi[0] &lt;&lt; '\t' &lt;&lt; vi[1] &lt;&lt; '\t' &lt;&lt; vi[2] &lt;&lt;endl;  // output: 4  8  16</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading27">Iterator Invalidation</a></h3>
<p>Reallocation can occur when a member function modifies its container. Modifying 
  member functions are <tt>reserve()</tt> and <tt>resize()</tt>, <tt>push_back()</tt> 
  and <tt>pop_back()</tt>, <tt>erase()</tt>, <tt>clear()</tt>, <tt>insert()</tt>, 
  and others. In addition, assignment operations and modifying algorithms can 
  also cause reallocation. When a container reallocates its elements, their addresses 
  change. Consequently, the values of existing iterators are invalidated. </p>
<p>For example</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;list&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  list &lt;double&gt; payroll;</tt>
<tt>  payroll.push_back(5000.00);</tt>
<tt>  list&lt;double&gt;::const_iterator p = payroll.begin(); //points to first element</tt>
<tt>  for (int i = 0 ; i &lt; 10; i++)</tt>
<tt>  {</tt>
<tt>      payroll.push_back(4500.00); //insert 10 more elements to payroll; </tt>
<tt>                                   //reallocation may occur</tt>
<tt>  }</tt>
<tt>      // DANGEROUS</tt>
<tt>  cout &lt;&lt; "first element in payroll: "&lt;&lt; *p &lt;&lt;endl; // p may have </tt>
<tt>                                                    //been invalidated</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>In the preceding example, <tt>payroll</tt> might have reallocated itself during 
  the insertion of ten additional elements, thereby invalidating the value of 
  <tt>p</tt>. Using an invalid iterator is similar to using a pointer with the 
  address of a deleted object both result in undefined behavior. To be on the 
  safe side, it is recommended that you reassign the iterator's value after calling 
  a modifying member function. For example</p>
<pre>
<tt>list&lt;double&gt;::const_iterator p = payroll.begin();//points to the first element</tt>
<tt>for (int i = 0 ; i &lt; 10; i++)</tt>
<tt>{</tt>
<tt>  payroll.push_back(4500.00); // reallocation may occur here</tt>
<tt>}</tt>
<tt>  p = payroll.begin(); // reassign p</tt>
<tt>  cout &lt;&lt;"first element in payroll: "&lt;&lt;*p&lt;&lt;endl;  // now safe</tt>
<tt>}</tt>
</pre>
<p>Alternatively, you can prevent reallocation by preallocating sufficient storage 
  before the instantiation of an iterator. For example</p>
<pre>
<tt>int main()</tt>
<tt>{</tt>
<tt>  list &lt;double&gt; payroll;</tt>
<tt>  payroll.reserve(11);</tt>
<tt>  payroll.push_back(5000.00);</tt>
<tt>  list&lt;double&gt;::const_iterator p = payroll.begin();  </tt>
<tt>  for (int i = 0 ; i &lt; 10; i++)</tt>
<tt>  {</tt>
<tt>    payroll.push_back(4500.00); //no reallocation</tt>
<tt>  }</tt>
<tt>  cout &lt;&lt; "first element in payroll: "&lt;&lt; *p &lt;&lt;endl; // OK</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h2> <a name="Heading29"> Algorithms</a></h2>
<p>STL defines a rich collection of generic algorithms that can be applied to 
  containers and other sequences. There are three major categories of algorithms: 
  non-modifying sequence operations, mutating sequence operations, and algorithms 
  for sorting.</p>
<h3> <a name="Heading30">Non-Modifying Sequence Operations</a></h3>
<p>Non-modifying sequence operations are algorithms that do not directly modify 
  the sequence on which they operate. They include operations such as search, 
  checking for equality, and counting.</p>
<h4> The find() Algorithm</h4>
<p>The generic algorithm <tt>find()</tt> locates an element within a sequence. 
  <tt>find()</tt> takes three arguments. The first two are iterators that point 
  to the beginning and the end of the sequence, respectively. </p>
<p>The third argument is the sought-after value. <tt>find()</tt> returns an iterator 
  that points to the first element that is identical to the sought-after value. 
  If <tt>find()</tt> cannot locate the requested value, it returns an iterator 
  that points one element past the final element in the sequence (that is, it 
  returns the same value as <tt>end()</tt> does). For example</p>
<pre>
<tt>#include &lt;algorithm&gt; // definition of find()</tt>
<tt>#include &lt;list&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  list&lt;char&gt; lc;</tt>
<tt>  lc.push_back('A');</tt>
<tt>  lc.push_back('T');</tt>
<tt>  lc.push_back('L');</tt>
<tt>  list&lt;char&gt;::iterator p = find(lc.begin(), lc.end(), 'A');   // find 'A'</tt>
<tt>  if (p != lc.end())     // was 'A' found?</tt>
<tt>     *p = 'S';    // then replace it with 'S'</tt>
<tt>  while (p != lc.end())   //display the modified list</tt>
<tt>    cout&lt;&lt;*p++;</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading31">Mutating Sequence Operations</a></h3>
<p>Mutating sequence algorithms modify the sequence on which they operate. They 
  include operations such as copy, fill, replace, and transform.</p>
<h4> The copy() Algorithm</h4>
<p>The Standard Library provides a generic copy function, which can be used to 
  copy a sequence of objects to a specified target. The first and the second arguments 
  of <tt>copy()</tt> are <tt>const</tt> iterators that mark the sequence's beginning 
  and its end, respectively. The third argument points to a container into which 
  the sequence is copied. The following example demonstrates how to copy the elements 
  of a <tt>list</tt> into a <tt>vector</tt>:</p>
<pre>
<tt>#include &lt;algorithm&gt;</tt>
<tt>#include&lt;list&gt;</tt>
<tt>#include&lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  list&lt;int&gt; li; vector &lt;int&gt; vi;</tt>
<tt>  li.push_back(1);</tt>
<tt>  li.push_back(2);</tt>
<tt>  vi.reserve( li.size() );  //must make room for copied elements in advance</tt>
<tt>  //copy list elements into vector, starting at vector's beginning</tt>
<tt>  copy (li.begin(), li.end(), vi.begin() );</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading32">Sort Operations</a></h3>
<p>This category contains algorithms for sorting and merging sequences and set-like 
  algorithms that operate on sorted sequences. These include <tt>sort()</tt>, 
  <tt>partial_sort()</tt>, <tt>binary_search()</tt>, <tt>lower_bound()</tt>, and 
  many others.</p>
<h4> The sort() Algorithm</h4>
<p><tt>sort()</tt> takes two arguments of type <tt>const</tt> iterator that point 
  to the beginning and the end of the sequence, respectively. An optional third 
  algorithm is a <i>predicate object</i>, which alters the computation of <tt>sort</tt> 
  (predicate objects and adaptors are discussed shortly). For example</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;algorithm&gt; //definition of sort()</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;int&gt; vi;</tt>
<tt>  vi.push_back(7);</tt>
<tt>  vi.push_back(1);</tt>