sidebar.htm

ARM编辑、编译软件

<P>As we noted in earlier sections, support for initializing containers using a pair of iterators requires a feature that is not yet widely supported by compilers.  While we document this form of constructor, it may not yet be available on your system.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar42"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG>Information on ...</STRONG>
<P><B>Information on Heaps.</B>  Details of the algorithms used in manipulating heaps will not be discussed here, however such information is readily available in almost any textbook on data structures.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar43"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Finding Smallest Elements</STRONG>
<P>We describe the priority queue as a structure for quickly discovering the <I>largest </I>element in a sequence.  If, instead, your problem requires the discovery of the <I>smallest</I> element, there are various possibilities.  One is to supply the inverse operator as either a template argument or the optional comparison function argument to the constructor.  If you are defining the comparison argument as a function, as in the example problem, another solution is to simply invert the comparison test.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar44"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Storing Pointers versus Storing Values</STRONG>
<P>Other example programs in this tutorial have all used containers to store values.  In this example the container will maintain pointers to values, not the values them-selves.  Note that a consequence of this is that the programmer is then responsible for managing the memory for the objects being manipulated.</P>

<BR><BR><BR><BR><BR><A NAME="sidebar45"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the sample program</STRONG>
<P>The complete event simulation is found in the file <SAMP>icecream.cpp</SAMP> on the distribution disk.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar46"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Strings and Wide Strings</STRONG>
<P>In the remainder of this section we will refer to the string data type, however all the operations we will introduce are equally applicable to wide strings.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar47"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Initializing from Iterators</STRONG>
<P>Remember, the ability to initialize a container using a pair of iterators requires the ability to declare a template member function using template arguments independent of those used to declare the container.  At present not all compilers support this feature.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar48"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Invalidating Iterators</STRONG>
<P>Note that the contents of an iterator are not guaranteed to be valid after any operation that might force a reallocation of the internal string buffer, such as an append or an insertion.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar49"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Comparing Strings</STRONG>
<P>Although the function is accessible, users will seldom invoke the member function <SAMP>compare() </SAMP>directly.  Instead, comparisons of strings are usually performed using the conventional comparison operators, which in turn make use of the function <SAMP>compare()</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar50"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Sample Program</STRONG>
<P>The split function can be found in the concordance program in file <SAMP>concord.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar51"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the source</STRONG>
<P>The sample programs described in this section can be found in the file <SAMP>alg1.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar52"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Different Initialization Algorithms</STRONG>
<P>The initialization algorithms all overwrite every element in a container.  The difference between the algorithms is the source for the values used in initialization.  The <SAMP>fill()</SAMP> algorithm repeats a single value, the <SAMP>copy()</SAMP> algorithm reads values from a second container, and the <SAMP>generate()</SAMP> algorithm invokes a function for each new value.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar53"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Appending Several Copies</STRONG>
<P>The result returned by the <SAMP>copy()</SAMP> function is a pointer to the end of the copied sequence.  To make a <I>catenation</I> of values, the result of one <SAMP>copy() </SAMP>operation can be used as a starting iterator in a subsequent <SAMP>copy().</SAMP></P>
<BR><BR><BR><BR><BR><A NAME="sidebar54"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> copy_backwards</STRONG>
<P>In the copy_backwards algorithm, note that it is the order of transfer, and not the elements themselves that is "backwards"; the relative placement of moved values in the target is the same as in the source.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar55"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Parallel Sequences</STRONG>
<P>A number of algorithms operate on two parallel sequences.  In most cases the second sequence is identified using only a starting iterator, not a starting and ending iterator pair.  It is assumed, but never verified, that the second sequence is at least as large as the first.  Errors will occur if this condition is not satisfied.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar56"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Source</STRONG>
<P>The example functions described in this section can be found in the file <SAMP>alg2.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar57"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Check Search Results</STRONG>
<P>The searching algorithms in the standard library all return the end-of-sequence iterator if no value is found that matches the search condition.  As it is generally illegal to dereference the end-of-sequence value, it is important to check for this condition before proceeding to use the result of a search.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar58"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Searching Sets and Maps</STRONG>
<P>These algorithms perform a linear sequential search through the associated structures.  The <B><I>set</I></B> and <B><I>map</I></B> data structures, which are ordered, provide their own <SAMP>find()</SAMP> member functions, which are more efficient.  Because of this, the generic <SAMP>find()</SAMP> algorithm should not be used with <B><I>set</I></B> and <B><I>map.</I></B></P>
<BR><BR><BR><BR><BR><A NAME="sidebar59"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Speed of Search</STRONG>
<P>In the worst case, the number of comparisons performed by the algorithm <SAMP>search()</SAMP> is the product of the number of elements in the two sequences.  Except in rare cases, however, this worst case behavior is highly unlikely.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar60"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Largest and Smallest Elements of a Set</STRONG>
<P>The maximum and minimum algorithms can be used with all the data types provided by the standard library.  However, for the ordered data types, <B><I>set</I></B> and <B><I>map</I></B>, the maximum or minimum values are more easily accessed as the first or last elements in the structure.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar61"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Source</STRONG>
<P>The example functions described in this section can be found in the file <SAMP>alg3.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar62"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Partitions</STRONG>
<P>While there is a unique <SAMP>stable_ partition()</SAMP> for any sequence, the <SAMP>partition()</SAMP> algorithm can return any number of values.  The following, for example, are all legal partitions of the example problem. </P>
<P>2 4 6 8 10 1 3 5 7 9</P>
<P>10 8 6 4 2 5 7 9 3 1</P>
<P>2 6 4 8 10 3 5 7 9 1</P>
<P>6 4 2 10 8 5 3 7 9 1.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar63"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Ordering Permutations</STRONG>
<P>Permutations can be ordered, with the smallest permutation being the one in which values are listed smallest to largest, and the largest being the sequence that lists values largest to smallest.  Consider, for example, the permutations of the integers 1 2 3.  The six permutations of these values are, in order: </P>
<P>1 2 3</P>
<P>1 3 2</P>
<P>2 1 3</P>
<P>2 3 1</P>
<P>3 1 2</P>
<P>3 2 1</P>
<P>Notice that in the first permutation the values are all ascending, while in the last permutation they are all descending.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar64"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> What is a Name?</STRONG>
<P>The algorithms in this section set up a sequence so that the desired elements are moved to the front.  The remaining values are not actually removed, but the starting location for these values is returned, making it possible to remove these values by means of a subsequent call on <SAMP>erase()</SAMP>.  <I>Remember</I>, the remove algorithms do not actually remove the unwanted elements.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar65"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Source</STRONG>
<P>The example functions described in this section can be found in the file <SAMP>alg4.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar66"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Source</STRONG>
<P>The example functions described in this section can be found in the file <SAMP>alg5.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar67"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> The Resulting Count</STRONG>
<P>Note that the <SAMP>count()</SAMP> algorithms do not return the sum as a function result, but instead simply add to the last argument in their parameter list, which is passed by reference.  This means successive calls on these functions can be used to produce a cumulative sum.  This also means that you must initialize the variable passed to this last argument location prior to calling one of these algorithms.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar68"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Equal and Mismatch</STRONG>
<P>By substituting another function for the binary predicate, the equal and mismatch algorithms can be put to a variety of different uses.  Use the <SAMP>equal()</SAMP> algorithm if you want a pairwise test that returns a <I>boolean </I>result.  Use the <SAMP>mismatch()</SAMP> algorithm if you want to discover the <I>location</I> of elements that fail the test.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar69"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Source</STRONG>
<P>The example functions described in this section can be found in the file <SAMP>alg6.cpp</SAMP>.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar70"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Results Produced by Side Effect</STRONG>
<P>The function passed as the third argument is not permitted to make any modifications to the sequence, so it can only achieve any result by means of a side effect, such as printing, assigning a value to a global or static variable, or invoking another function that produces a side effect.  If the argument function returns any result, it is ignored.  </P>
<BR><BR><BR><BR><BR><A NAME="sidebar71"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Sample Programs</STRONG>
<P>The example programs described in this section have been combined and are included in the file <SAMP>alg7.cpp</SAMP> in the tutorial distribution.  As we did in <a href="gen_9895.htm">Chapter 13</a>, we will generally omit output statements from the descriptions of the programs provided here, although they are included in the executable versions.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar72"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> More Sorts</STRONG>
<P>Yet another sorting algorithm is provided by the heap operations, to be described in <a href="hea_8081.htm">Chapter 14 (<i>Heap Operations</i></a>).</P>
<BR><BR><BR><BR><BR><A NAME="sidebar73"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Heaps and Ordered Collections</STRONG>
<P>Note that an ordered collection is a heap, but a heap need not necessarily be an ordered collection.  In fact, a heap can be constructed in a sequence much more quickly than the sequence  can be sorted.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar74"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Sample Program.</STRONG>
<P>This program can be found in the file<SAMP> exceptn.cpp</SAMP> in your code distribution.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar75"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Sample Program.</STRONG>
<P>You can find this program in the file autoptr.cpp in the turorial distribution.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar76"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Functions and Member Functions</STRONG>
<P>Note that, with the exception of the member functions <SAMP>real()</SAMP> and <SAMP>imag(),</SAMP> most operations on complex numbers are performed using ordinary functions, not member functions.</P>

<BR><BR><BR><BR><BR><A NAME="sidebar77"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Obtaining the Sample Program</STRONG>
<P>This program is found in the file <SAMP>complx.cpp</SAMP> in the distribution.</P>
<BR><BR><BR><BR><BR><A NAME="sidebar78"><IMG SRC="images/sail_bar.gif"></A> <BR><IMG SRC="images/note.gif"><STRONG> Two Mechanisms, One Purpose</STRONG>
<P>For reasons of compatibility, the numeric_limits mechanism is used as an addition to the symbolic constants used in older C++ libraries, rather than a strict replacement.  Thus both mechanisms will, for the present, exist in parallel.  However, as the numeric_limits technique is more uniform and extensible, it should be expected that over time the older symbolic constants will become outmoded.</P>
<BR><BR><BR><BR><BR></BODY></HTML>