index.html

C程序员手册(英文)

<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>
<tt>  vi.push_back(19);</tt>
<tt>  sort(vi.begin(), vi.end() );   // sort vi; default is ascending order</tt>
<tt>  cout&lt;&lt; vi[0]  &lt;&lt;", "&lt;&lt; vi[1] &lt;&lt;", "&lt;&lt; vi[2] &lt;&lt;endl;  // output: 1, 7, 19</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>One way to force a descending order is to use reverse iterators:</p>
<pre>
<tt>sort(vi.rbegin(), vi.rend() ); // now sort in descending order</tt>
<tt>cout&lt;&lt; vi[0] &lt;&lt;", "&lt;&lt;vi[1]&lt;&lt;", "&lt;&lt;vi[2]&lt;&lt;endl; // output: 19, 7, 1</tt>
</pre>
<h4> Requirements for Sorting Containers</h4>
<p>When <tt>sort()</tt> operates on a container, it uses the relational operators 
  <tt>==</tt> and <tt>&lt;</tt> of the container's elements. User-defined types 
  that do not support these operators can still be stored in a container, but 
  such a container cannot be sorted.</p>
<h2> <a name="Heading33">Function Objects</a></h2>
<p>It is customary to use a function pointer to invoke a callback routine. In 
  an object-oriented environment, nonetheless, a function can be encapsulated 
  in a <i>function object</i> (see also Chapter 3, "Operator Overloading"). There 
  are several advantages to using a function object, or <i>functor</i>, instead 
  of a pointer. Function objects are more resilient because the object that contains 
  the function can be modified without affecting its users. In addition, compilers 
  can inline a function object, which is nearly impossible when function pointers 
  are used. But perhaps the most compelling argument in favor of function objects 
  is their genericity a function object can embody a generic algorithm by means 
  of a member template.</p>
<h3> <a name="Heading34">Implementation of Function Objects</a></h3>
<p>A function object overloads the function call operator. A generic function 
  object defines the overloaded function call operator as a member function template. 
  Consequently, the object can be used like a function call. Remember that the 
  overloaded operator <tt>()</tt> can have a varying number of arguments, and 
  any return value. In the following example, a function object implements a generic 
  negation operator:</p>
<pre>
<tt>#include &lt;iostream&gt;</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>using namespace std;</tt>
<tt>class negate</tt>
<tt>{</tt>
<tt>public : //generic negation operator</tt>
<tt>  template &lt; class T &gt; T operator()  (T t) const { return -t;}</tt>
<tt>};</tt>
<tt>void callback(int n, const negate&amp; neg) //pass a function object rather </tt>
<tt>                                        //than a function pointer</tt>
<tt>{</tt>
<tt>  n = neg(n);  //invoke the overloaded () operator to negate n</tt>
<tt>  cout &lt;&lt; n;</tt>
<tt>}</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  callback(5, negate() ); //output: -5</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading35">Uses of Function Objects</a></h3>
<p>Some container operations use function objects. For example, a <tt>priority_queue</tt> 
  uses the <tt>less</tt> function object to sort its elements internally. The 
  following example demonstrates a scheduler that stores tasks with different 
  priorities in a <tt>priority_queue</tt>. Tasks that have higher priority are 
  located at the top. Tasks with identical priority are located according to the 
  order of their insertion, as in an ordinary queue:</p>
<pre>
<tt>#include &lt;functional&gt; // definition of less</tt>
<tt>#include &lt;queue&gt;  // definition of priority_queue</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>struct Task</tt>
<tt>{</tt>
<tt>  int priority;</tt>
<tt>  friend bool operator &lt; (const Task&amp; t1, const Task&amp; t2);</tt>
<tt>  Task(int p=0) : priority(p) {}</tt>
<tt>};</tt>
<tt>bool operator &lt; (const Task&amp; t1, const Task&amp; t2)</tt>
<tt>{</tt>
<tt>  return t1.priority &lt; t2.priority;</tt>
<tt>}</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  priority_queue&lt;Task&gt; scheduler;</tt>
<tt>  scheduler.push(Task(3));</tt>
<tt>  scheduler.push(Task(5));</tt>
<tt>  scheduler.push(Task(1));</tt>
<tt>  scheduler.push(Task(1));</tt>
<tt>  cout&lt;&lt; scheduler.top().priority &lt;&lt;endl;   // output 5</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading36">Predicate Objects</a></h3>
<p>A predicate is an expression that returns a Boolean value. Similarly, a function 
  object that returns a Boolean value is a <i>predicate object</i>. STL defines 
  several predicate objects that can be used to alter the computation of a generic 
  algorithm. These predicate objects are defined in the header <tt>&lt;functional&gt;</tt>. 
  In a previous example, you saw the operation of the algorithm <tt>sort()</tt>. 
  The third argument of <tt>sort()</tt> is a predicate that alters the computation 
  of this algorithm. For example, the predicate <tt>greater&lt;int&gt;</tt> can 
  be used to override the default ascending order. Likewise, the predicate <tt>less&lt;int&gt;</tt> 
  restores the original ascending order:</p>
<pre>
<tt>#include &lt;functional&gt; //definitions of STL predicates</tt>
<tt>#include &lt;algorithm&gt; //definition of sort</tt>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  vector &lt;int&gt; vi;</tt>
<tt>  vi.push_back(9);</tt>
<tt>  vi.push_back(5);</tt>
<tt>  vi.push_back(10);</tt>
<tt>  sort(vi.begin(), vi.end(), greater&lt;int&gt; () );  // descending order</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: 10  9  5</tt>
<tt>  sort(vi.begin(), vi.end(), less&lt;int&gt; () );   // now in ascending order</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: 5  9  10</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<h2> <a name="Heading37">Adaptors</a></h2>
<p>An adaptor is a component that modifies the interface of another component. 
  STL uses several types of adaptors: sequence adaptors, iterator adaptors, and 
  function adaptors.</p>
<h3> <a name="Heading38">Sequence Adaptors</a></h3>
<p>A sequence adaptor is a container that is built upon another container and 
  that modifies its interface. For example, the container <tt>stack</tt> is usually 
  implemented as a <tt>deque</tt>, whose non-<tt>stack</tt> operations are hidden. 
  In addition, <tt>stack</tt> uses the operations <tt>back()</tt>, <tt>push_back()</tt>, 
  and <tt>pop_back()</tt> of a <tt>deque</tt> to implement the operations <tt>top()</tt>, 
  <tt>push()</tt>, and <tt>pop()</tt>, respectively. For example</p>
<pre>
<tt>#include &lt;string&gt;</tt>
<tt>#include &lt;stack&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  stack &lt;string&gt; strstack;</tt>
<tt>  strstack.push("Bjarne");</tt>
<tt>  strstack.push("Stroustrup");</tt>
<tt>  string topmost = strstack.top();</tt>
<tt>  cout&lt;&lt; "topmost element is: "&lt;&lt; topmost &lt;&lt; endl; // "Stroustrup"</tt>
<tt>  strstack.pop();</tt>
<tt>  cout&lt;&lt; "topmost element is: "&lt;&lt; strstack.top() &lt;&lt; endl; // "Bjarne"</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>Calling the member function <tt>pop()</tt> on an empty stack is an error. If 
  you are not sure whether a stack contains any elements, you can use the member 
  function <tt>empty()</tt> to check it first. For example</p>
<pre>
<tt>stack&lt;int&gt; stk;</tt>
<tt>//...many lines of code</tt>
<tt>if (!stk.empty() ) //test stack before popping it</tt>
<tt>{</tt>
<tt>    stk.pop();</tt>
<tt>}</tt>
</pre>
<h3> <a name="Heading39">Iterator Adaptors</a></h3>
<p>The interface of an iterator can be altered by an <i>iterator adaptor</i>. 
  The member functions <tt>rend()</tt> and <tt>rbegin()</tt> return reverse iterators, 
  which are iterators that have the meanings of operators <tt>++</tt> and <tt>--</tt> 
  exchanged. Using a reverse iterator is more convenient in some computations.</p>
<h3> <a name="Heading40">Function Adaptors</a></h3>
<p>Earlier you saw the use of <tt>greater</tt> as a function adaptor for changing 
  the computation of <tt>sort()</tt>. STL also provides <i>negators</i>, which 
  are used to reverse the result of certain Boolean operations. <i>Binders</i> 
  are another type of adaptors, which convert a binary function object into a 
  unary function object by binding an argument to a specific value.</p>
<h2> <a name="Heading41">Allocators</a></h2>
<p>Every STL container uses an allocator that encapsulates the memory model that 
  the program uses. Allocators hide the platform-dependent details such as the 
  size of pointers, memory organization, reallocation model, and memory page size. 
  Because a container can work with different allocator types, it can easily work 
  in different environments simply by plugging a different allocator into it. 
  An implementation provides a suitable allocator for every container. Normally, 
  users should not override the default allocator.</p>
<h2> <a name="Heading42">Specialized Containers</a></h2>
<p>Chapter 9, "Templates," discussed the benefits of defining template specializations 
  to optimize and rectify the behavior of a primary template for a particular 
  type. <tt>vector</tt> has a specialized form that manipulates Boolean values 
  optimally, namely <tt>vector&lt;bool&gt;</tt>. This specialization is implemented 
  in a way that squeezes each element into a single bit, rather than a <tt>bool</tt> 
  variable, albeit with the familiar <tt>vector</tt> interface. For example</p>
<pre>
<tt>#include &lt;vector&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std</tt>
<tt>void transmit(vector &lt;bool&gt; &amp;binarystream)</tt>
<tt>{</tt>
<tt>  cout&lt;&lt;binarystream[0]; // subscript operator provided</tt>
<tt>  vector&lt;bool&gt;::const_iterator bit_iter = binarystream.begin(); //iterators</tt>
<tt>  if (binarystream[0] == true)</tt>
<tt>  {/* do something */ }</tt>
<tt>}</tt>
</pre>
<h2> <a name="Heading43">Associative Containers</a></h2>
<p>An <i>associative array</i> is one for which the index need not be an integer. 
  An associative array is also called <i>map</i> or <i>dictionary</i>. STL defines 
  several associative containers. A <tt>map</tt>, for instance, stores pairs of 
  values; one serves as the key, and the other is the associated value. The template 
  <tt>pair&lt;class Key, class Value&gt;</tt> serves as a <tt>map</tt> element. 
  In the following example, a <tt>map</tt> is used to translate the string value 
  of an enumerator into its corresponding integral value. The string is the key 
  whose associated value is an <tt>int</tt>:</p>
<pre>
<tt>#include &lt;map&gt;</tt>
<tt>#include &lt;string&gt;</tt>
<tt>#include &lt;iostream&gt;</tt>
<tt>using namespace std;</tt>
<tt>enum directions {up, down};</tt>
<tt>int main()</tt>
<tt>{</tt>
<tt>  pair&lt;string, int&gt; Enumerator(string("down"), down); //create a pair</tt>
<tt>  map&lt;string, int&gt; mi; //create a map</tt>
<tt>  mi.insert(Enumerator); //insert the pair</tt>
<tt>  int n = mi["down"]; //n = 1 //string used as subscript</tt>
<tt>  return 0;</tt>
<tt>}</tt>
</pre>
<p>A <tt>map</tt> can store only unique keys. A <tt>multimap</tt> is a <tt>map</tt> 
  that can store duplicate keys.</p>
<p><tt>set</tt> is similar to a <tt>map</tt> except that the associated values 
  are irrelevant in this case. A <tt>set</tt> is used when only the keys are important: 
  to ensure that a database transaction does not attempt to insert a record with 
  a unique key that already exists in a table, for example. <tt>multiset</tt> 
  is a <tt>set</tt> that allows duplicate keys.</p>
<h2> <a name="Heading44">Class auto_ptr</a></h2>
<p>The class template <tt>auto_ptr</tt> implements the "resource acquisition is 
  initialization" idiom (discussed in Chapter 5, "Object-Oriented Programming 
  Design"). It is initialized by a pointer to an object allocated on the free 
  store (<tt>auto_ptr</tt> has a default constructor so you can instantiate an 
  empty <tt>auto_ptr</tt> and assign a pointer to it later). The destructor of 
  <tt>auto_ptr</tt> destroys the object that is bound to the pointer. This technique 
  can avoid memory leakage in the case of exceptions (see also Chapter 6, "Exception 
  Handling"), or it can simplify programming by sparing the hassle of explicitly 
  deleting every object allocated on the free store. Class <tt>auto_ptr</tt> is 
  declared in the standard header <tt