ch10.htm

c++语言操作手册

<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;int&gt; vi;</tt>
<tt>  for (;;) //read numbers from a user's console until 0 is input</tt>
<tt>  {</tt>
<tt>    int temp;</tt>
<tt>    cout&lt;&lt;"enter a number; press 0 to terminate" &lt;&lt;endl;</tt>
<tt>    cin&gt;&gt;temp;</tt>
<tt>    if (temp == 0 ) break; //exit from loop?</tt>
<tt>    vi.push_back(temp); //insert int into the buffer</tt>
<tt>  }</tt>
<tt>  cout&lt;&lt; "you entered "&lt;&lt; vi.size() &lt;&lt;" elements" &lt;&lt;endl;</tt>
<tt>  return 0;</tt>
<tt>}//end main</tt>
</pre>
<h3> <a name="Heading13">Container Reallocation</a></h3>
<p>The memory allocation scheme of STL containers must address two conflicting 
  demands. On the one hand, a container should not preallocate large amounts of 
  memory because it can impair the system's performance. On the other hand, it 
  is inefficient to allow a container reallocate memory whenever it stores a few 
  more elements. The allocation strategy has to walk a thin line. On many implementations, 
  a container initially allocates a small memory buffer, which grows exponentially 
  with every reallocation. Sometimes, however, it is possible to estimate in advance 
  how many elements the container will have to store. In this case, the user can 
  preallocate a sufficient amount of memory in advance so that the recurrent reallocation 
  process can be avoided. Imagine a mail server of some Internet Service Provider: 
  The server is almost idle at 4 a.m. At 9 a.m., however, it has to transfer thousands 
  of emails every minute. The incoming emails are first stored in a <tt>vector</tt> 
  before they are routed to other mail servers across the Web. Allowing the container 
  to reallocate itself little by little with every few dozen emails can degrade 
  performance.</p>
<h4> What Happens During Reallocation?</h4>
<p>The reallocation process consists of four steps. First, a new memory buffer 
  that is large enough to store the container is allocated. Second, the existing 
  elements are copied to the new memory location. Third, the destructors of the 
  elements in their previous location are successively invoked. Finally, the original 
  memory buffer is released. Obviously, reallocation is a costly operation. You 
  can avert reallocation by calling the member function <tt>reserve()</tt>. <tt>reserve(</tt><cite>n</cite><tt>)</tt> 
  ensures that the container reserves sufficient memory for at least <cite>n</cite> 
  elements in advance, as in the following example:</p>
<pre>
<tt>class Message { /*...*/};</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>int FillWithMessages(vector&lt;Message&gt;&amp; msg_que); //severe time constraints</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;Message&gt; msgs;</tt>
<tt>  // before entering a time-critical section, make room for 1000 Messages</tt>
<tt>  msgs.reserve(1000);</tt>
<tt>//no re-allocation should occur before 1000 objects have been stored in vector</tt>
<tt>  FillWithMessages(msgs);</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading14">capacity() and size()</a></h3>
<p><tt>capacity()</tt> returns the total number of elements that the container 
  can hold without requiring reallocation. <tt>size()</tt> returns the number 
  of elements that are currently stored in the container. In other words, <tt>capacity() 
  - size()</tt> is the number of available "free slots" that can be filled with 
  additional elements without reallocating. The capacity of a container can be 
  resized explicitly by calling either <tt>reserve()</tt> or <tt>resize()</tt>. 
  These member functions differ in two respects. <tt>resize(</tt><cite>n</cite><tt>)</tt> 
  allocates memory for <cite>n</cite> objects and default-initializes them (you 
  can provide a different initializer value as the second optional argument). 
</p>
<p><tt>reserve()</tt> allocates raw memory without initializing it. In addition, 
  <tt>reserve()</tt> does not change the value that is returned from <tt>size()</tt> 
  it only changes the value that is returned from <tt>capacity</tt>(). <tt>resize()</tt> 
  changes both these values. 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>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;string&gt; vs;</tt>
<tt>  vs.reserve(10);  //make room for at least 10 more strings</tt>
<tt>  vs.push_back(string()); //insert an element   </tt>
<tt>  cout&lt;&lt;"size: "&lt;&lt; vs.size()&lt;&lt;endl; //output: 1</tt>
<tt>  cout&lt;&lt;"capacity: "&lt;&lt;vs.capacity()&lt;&lt;endl; //output: 10</tt>
<tt>  cout&lt;&lt;"there's room for "&lt;&lt;vs.capacity() - vs.size()</tt>
<tt>      &lt;&lt;" elements before reallocation"&lt;&lt;endl;</tt>
<tt>  //allocate 10 more elements, initialized each with string::string()</tt>
<tt>  vs.resize(20);</tt>
<tt>  cout&lt;&lt;"size: "&lt;&lt; vs.size()&lt;&lt;endl; //output 20</tt>
<tt>  cout&lt;&lt;"capacity: "&lt;&lt;vs.capacity()&lt;&lt;endl; //output 20;</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading15">Specifying the Container's Capacity During Construction</a></h3>
<p>Up until now, the examples in this chapter have used explicit operations to 
  preallocate storage by calling either <tt>reserve()</tt> or <tt>resize()</tt>. 
  However, it is possible to specify the requested storage size during construction. 
  For example</p>
<pre>
<tt>#include &lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector&lt;int&gt;  vi(1000); //initial storage for 1000 int's</tt>
<tt>  //vi contains 1000 elements initialized by int::int()</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>Remember that <tt>reserve()</tt> allocates raw memory without initializing 
  it. The constructor, on the other hand, initializes the allocated elements by 
  invoking their default constructor. It is possible to specify a different initializer 
  value, though:</p>
<pre>
<tt>vector&lt;int&gt;  vi(1000, 4); //initial  all 1000 int's with 4</tt>
</pre>
<h3> <a name="Heading16">Accessing a Single Element</a></h3>
<p>The overloaded operator <tt>[]</tt> and the member function <tt>at()</tt> enable 
  direct access to a vector's element. Both have a <tt>const</tt> and a non-<tt>const</tt> 
  version, so they can be used to access an element of a <tt>const</tt> and a 
  non-<tt>const</tt> vector, respectively.</p>
<p>The overloaded <tt>[]</tt> operator was designed to be as efficient as its 
  built-in counterpart. Therefore, <tt>[]</tt> does not check to see if its argument 
  actually refers to a valid element. The lack of runtime checks ensures the fastest 
  access time (an operator <tt>[]</tt> call is usually inlined). However, using 
  operator <tt>[]</tt> with an illegal subscript yields undefined behavior. When 
  performance is paramount, and when the code is written carefully so that only 
  legal subscripts are accessed, use the <tt>[]</tt> operator. The <tt>[]</tt> 
  notation is also more readable and intuitive. Nonetheless, runtime checks are 
  unavoidable in some circumstances for instance, when the subscript value is 
  received from an external source such as a function, a database record, or a 
  human operator. In such cases you should use the member function <tt>at()</tt> 
  instead of operator <tt>[]</tt>. <tt>at()</tt> performs range checking and, 
  in case of an attempt to access an out of range member, it throws an exception 
  of type <tt>std::out_of_range</tt>. Here is an example:</p>
<pre>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;string&gt;</tt>
<tt>#include &lt;stdexcept&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector&lt;string&gt; vs; // vs has no elements currently</tt>
<tt>  vs.push_back("string"); //add first element</tt>
<tt>  vs[0] = "overriding string"; //override it using []</tt>
<tt>  try</tt>
<tt>  {</tt>
<tt>    cout&lt;&lt; vs.at(10) &lt;&lt;endl; //out of range element, exception thrown</tt>
<tt>  }</tt>
<tt>  catch(std::out_of_range &amp; except)</tt>
<tt>  {</tt>
<tt>    // handle out-of-range subscript</tt>
<tt>  }</tt>
<tt>}//end main</tt>
</pre>
<h3> <a name="Heading17">Front and Back Operations</a></h3>
<p>Front and back operations refer to the beginning and the end of a container, 
  respectively. The member function <tt>push_back()</tt> appends a single element 
  to the end of the container. When the container has exhausted its free storage, 
  it reallocates additional storage, and then appends the element. The member 
  function <tt>pop_back()</tt> removes the last element from the container. The 
  member functions <tt>front()</tt> and <tt>back()</tt> access a single element 
  at the container's beginning and end, respectively. <tt>front()</tt> and <tt>back()</tt> 
  both have a <tt>const</tt> and a non-<tt>const</tt> version. For example</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;short&gt; v;</tt>
<tt>  v.push_back(5);</tt>
<tt>  v.push_back(10);</tt>
<tt>  cout&lt;&lt;"front: " &lt;&lt; v.front() &lt;&lt; endl; //5</tt>
<tt>  cout&lt;&lt;"back: " &lt;&lt; v.back() &lt;&lt; endl; //10</tt>
<tt>  v.pop_back(); //remove v[1]</tt>
<tt>  cout&lt;&lt;"back: " &lt;&lt; v.back() &lt;&lt; endl; //now 5</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading18">Container Assignment</a></h3>
<p>STL containers overload the assignment operator, thereby allowing containers 
  of the same type to be assigned easily. For example</p>
<pre>
<tt>#include &lt;iostream&gt;</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(1);</tt>
<tt>  vi.push_back(2);</tt>
<tt>  vector &lt;int&gt; new_vector;</tt>
<tt>  //copy the contents of vi to new_vector, which automatically grows as needed</tt>
<tt>  new_vector = vi;</tt>
<tt>  cout &lt;&lt; new_vector[0] &lt;&lt; new_vector[1] &lt;&lt; endl;   // display 1 and 2</tt>
<tt>  return 0; </tt>
<tt>} </tt>
</pre>
<h3> <a name="Heading19">Contiguity of Vectors</a></h3>
<p>Built-in arrays in C++ reside in contiguous chunks of memory. The Standard, 
  however, does not require that vector elements occupy contiguous memory. When 
  STL was added to the Standard, it seemed intuitive that vectors should store 
  their elements contiguously, so contiguity never became an explicit requirement. 
  Indeed, all current STL implementations follow this convention. The current 
  specification, however, permits implementations that do not use contiguous memory. 
  This loophole will probably be fixed by the Standardization committee in the 
  future, and vector contiguity will become a Standard requirement.</p>
<h3> <a name="Heading20">A vector&lt;Base&gt; Should not Store Derived Objects</a></h3>
<p>Each element in a vector must have the same size. Because a derived object 
  can have additional members, its size might be larger than the size of its base 
  class. Avoid storing a derived object in a <tt>vector&lt;Base&gt;</tt> because 
  it can cause object slicing with undefined results. You can, however, achieve 
  the desired polymorphic behavior by storing a pointer to a derived object in 
  a <tt>vector&lt;Base*&gt;.</tt></p>
<h3> <a name="Heading21">FIFO Data Models</a></h3>
<p>In a queue data model (a queue is also called FIFO first in first out), the 
  first element that is inserted is located at the topmost position, and any subsequent 
  elements are located at lower positions. The two basic operations in a queue 
  are <tt>pop()</tt> and <tt>push()</tt>. A <tt>push()</tt> operation inserts 
  an element into the bottom of the queue. A <tt>pop()</tt> operation removes 
  the element at the topmost position, which was the first to be inserted; consequently, 
  the element that is located one position lower becomes the topmost element. 
  The STL <tt>queue</tt> container can be used as follows:</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;queue&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt> queue &lt;int&gt; iq;</tt>
<tt> iq.push(93); //insert the first element, it is the top-most one</tt>
<tt> iq.push(250);</tt>
<tt> iq.push(10); //last element inserted is located at the bottom</tt>
<tt> cout&lt;&lt;"currently there are "&lt;&lt; iq.size() &lt;&lt; " elements" &lt;&lt; endl;</tt>
<tt> while (!iq.empty() )</tt>
<tt> {</tt>
<tt>   cout &lt;&lt;"the last element is: "&lt;&lt; iq.front() &lt;&lt; endl; //front() returns </tt>
<tt>                                                        //the top-most element</tt>
<tt>  iq.pop(); //remove the top-most element</tt>
<tt> }</tt>
<tt> return 0;</tt>
<tt>}</tt>
</pre>
<p>STL also defines a double-ended queue, or <i>deque</i> (pronounced "deck") 
  container. A <tt>deque</tt> is a queue that is optimized to support operations 
  at both ends efficiently. Another type of queue is a <cite>priority_queue</cite>. 
  A <tt>priority_queue</tt> has all its elements internally sorted according to 
  their priority. The element with the highest priority is located at the top. 
  To qualify as an element of <tt>priority_queue</tt>, an object has to define 
  the <tt>&lt;</tt> operator (<tt>priority_queue</tt> is discussed in detail later, 
  in the section titled "Function Objects").</p>
<h2> <a name="Heading22">Iterators</a></h2>
<p><i>Iterators</i> can be thought of as generic pointers. They are used to navigate 
  a container without having to know the actual type of its elements. Several 
  member functions such as <tt>begin()</tt> and <tt>end()</tt> return iterators 
  that point to the ends of a container.</p>
<h3> <a name="Heading23">begin() and end()</a></h3>
<p>All STL containers provide the <tt>begin()</tt> and <tt>end()</tt> pair of 
  member functions. <tt>begin()</tt> returns an iterator that points to the first 
  element of the container. For example</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;string&gt;</tt>