inp_4704.htm

ARM编辑、编译软件

{
       // first make the vector 1 2 3 ... 10
   vector<int> numbers(10);
   generate(numbers.begin(), numbers.end(), iotaGen(1));

      // now put the even values low, odd high
   vector<int>::iterator result = 
      partition(numbers.begin(), numbers.end(), isEven);
   cout << "middle location " << result - numbers.begin() << endl;

      // now do a stable partition
   generate (numbers.begin(), numbers.end(), iotaGen(1));
   stable_partition (numbers.begin(), numbers.end(), isEven);
}
</PRE>
<P>The relative order of the elements within a partition in the resulting vector may not be the same as the values in the original vector.  For example, the value 4 preceded the element 8 in the original, yet in the result it may follow the element 8.  A second version of partition, named <SAMP>stable_partition(),</SAMP> guarantees the ordering of the resulting values.  For the sample input shown in the example, the stable partition would result in the sequence 2 4 6 8 10 1 3 5 7 9.  The <SAMP>stable_partition()</SAMP> algorithm is slightly slower and uses more memory than the <SAMP>partition()</SAMP> algorithm, so when the order of elements is not important you should use <SAMP>partition().</SAMP></P>

<A NAME="generatepermutationsinsequence"><H3>Generate Permutations in Sequence</H3></A>
<A HREF="sidebar.htm#sidebar63"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Ordering Permutations</STRONG></A>

<P>A permutation is a rearrangement of values.  If values can be compared against each other (such as integers, characters, or words) then it is possible to systematically construct all permutations of a sequence.  There are 2 permutations of two values, for example, and six permutations of three values, and 24 permutations of four values.  </P>
<P>The permutation generating algorithms have the following definition:</P>
<PRE>bool next_permutation (BidirectionalIterator first, 
      BidirectionalIterator last, [ Compare ] );

bool prev_permutation (BidirectionalIterator first, 
      BidirectionalIterator last, [ Compare ] );
</PRE>
<P>The second example in the sample program illustrates the same idea, only using pointers to character arrays instead of integers.  In this case a different comparison function must be supplied, since the default operator would simply compare pointer addresses.  </P>
<PRE>bool nameCompare (char * a, char * b) { return strcmp(a, b) &#60;= 0; }

void permutation_example ()
   // illustrate the use of the next_permutation algorithm
{
      // example 1, permute the values 1 2 3
   int start [] = { 1, 2, 3};
   do
      copy (start, start + 3, 
            ostream_iterator&#60;int> (cout, " ")), cout &#60;&#60; endl;
   while (next_permutation(start, start + 3));

      // example 2, permute words
   char * words = {"Alpha", "Beta", "Gamma"};
   do
      copy (words, words + 3, 
         ostream_iterator&#60;char *> (cout, " ")), cout &#60;&#60; endl;
   while (next_permutation(words, words + 3, nameCompare));

      // example 3, permute characters backwards
   char * word = "bela";
   do
      cout &#60;&#60; word &#60;&#60; ' ';
   while (prev_permutation (word, &#38;word[4]));
   cout &#60;&#60; endl;
}
</PRE>
<P>Example 3 in the sample program illustrates the use of the reverse permutation algorithm, which generates values in reverse sequence.  This example also begins in the middle of a sequence, rather than at the beginning.  The remaining permutations of the word "bela," are <SAMP>beal, bale, bael, aleb, albe, aelb, aebl, able</SAMP>,  and finally,<SAMP> abel.</SAMP></P>

<A NAME="mergetwoadjacentsequencesintoone"><H3>Merge Two Adjacent Sequences into One</H3></A>
<P>A <I>merge</I> takes two ordered sequences and combines them into a single ordered sequence, interleaving elements from each collection as necessary to generate the new list.  The <SAMP>inplace_merge()</SAMP> algorithm assumes a sequence is divided into two adjacent sections, each of which is ordered.  The merge combines the two sections into one, moving elements as necessary.  (The alternative <SAMP>merge()</SAMP> algorithm, described elsewhere, can be used to merge two separate sequences into one.)  The arguments to <SAMP>inplace_merge()</SAMP> must be bidirectional iterators.</P>
<PRE>void inplace_merge (BidirectionalIterator first, 
   BidirectionalIterator middle,
   BidirectionalIterator last [, BinaryFunction ] );
</PRE>
<P>The example program illustrates the use of the <SAMP>inplace_merge()</SAMP> algorithm with a vector and with a list.  The sequence 0 2 4 6 8 1 3 5 7 9 is placed into a vector.  A <SAMP>find()</SAMP> call (<i><a href="sea_9743.htm#findanelementsatisfyingacondition">Find an Element Satisfying a Condition</a></i>) is used to locate the beginning of the odd number sequence.  The two calls on <SAMP>inplace_merge()</SAMP> then combine the two sequences into one.</P>
<PRE>void inplace_merge_example ()
      // illustrate the use of the inplace_merge algorithm
{
      // first generate the sequence 0 2 4 6 8 1 3 5 7 9
   vector&#60;int> numbers(10);
   for (int i = 0; i &#60; 10; i++)
      numbers[i] = i &#60; 5 ? 2 * i : 2 * (i - 5) + 1;

      // then find the middle location
   vector&#60;int>::iterator midvec = 
      find(numbers.begin(), numbers.end(), 1);

      // copy them into a list
   list&#60;int> numList;
   copy (numbers.begin(), numbers.end(),
         inserter (numList, numList.begin()));
   list&#60;int>::iterator midList = 
         find(numList.begin(), numList.end, 1);

      // now merge the lists into one
   inplace_merge (numbers.begin(), midvec, numbers.end());
   inplace_merge (numList.begin(), midList, numList.end());
}
</PRE>

<A NAME="randomlyrearrangeelementsinasequence"><H3>Randomly Rearrange Elements in a Sequence</H3></A>
<P>The algorithm <SAMP>random_shuffle()</SAMP> randomly rearranges the elements in a sequence.  Exactly <I>n</I> swaps are performed, where <I>n</I> represents the number of elements in the sequence.  The results are, of course, unpredictable.  Because the arguments must be random access iterators, this algorithm can only be used with vectors, deques, or ordinary pointers.  It cannot be used with lists, sets, or maps.</P>
<PRE>void random_shuffle (RandomAccessIterator first, 
   RandomAccessIterator last [, Generator ] );
</PRE>
<P>An alternative version of the algorithm uses the optional third argument.  This value must be a random number generator. This generator must take as an argument a positive value <SAMP>m</SAMP> and return a value between <SAMP>0</SAMP> and <SAMP>m-1</SAMP>.  As with the <SAMP>generate()</SAMP> algorithm, this random number function can be any type of object that will respond to the function invocation operator.</P>
<PRE>void random_shuffle_example ()
   // illustrate the use of the random_shuffle algorithm
{
   // first make the vector containing 1 2 3 ... 10
   vector&#60;int> numbers;
   generate(numbers.begin(), numbers.end(), iotaGen(1));

   // then randomly shuffle the elements
   random_shuffle (numbers.begin(), numbers.end());

   // do it again, with explicit random number generator
   struct RandomInteger {
   {
      operator() (int m) { return rand() % m; }
   } random;

   random_shuffle (numbers.begin(), numbers.end(), random);
}
</PRE>

<HR>
<A HREF="sea_9743.htm"><IMG SRC="images/prev.gif"></A> <A HREF="booktoc.htm"><IMG SRC="images/toc.gif"></A> <A HREF="rem_8388.htm"><IMG SRC="images/next.gif"></A></BODY></HTML>