📄 inp_4704.htm
字号:
<HTML><HEAD><TITLE>In-Place Transformations</TITLE></HEAD>
<BODY>
<A HREF="ug.htm"><IMG SRC="images/banner.gif"></A>
<P><STRONG>Click on the banner to return to the user guide home page.</STRONG></P>
<P>©Copyright 1996 Rogue Wave Software</P>
<H2>In-Place Transformations</H2>
<A HREF="sidebar.htm#sidebar61"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Obtaining the Source</STRONG></A>
<P>The next category of algorithms in the standard library that we examine are those used to modify and transform sequences without moving them from their original storage locations. A few of these routines, such as <SAMP>replace(),</SAMP> include a <I>copy</I> version as well as the original in-place transformation algorithms. For the others, should it be necessary to preserve the original, a copy of the sequence should be created before the transformations are applied. For example, the following illustrates how one can place the reversal of one vector into another newly allocated vector.</P>
<PRE> vector<int> newVec(aVec.size());
copy (aVec.begin(), aVec.end(), newVec.begin()); // first copy
reverse (newVec.begin(), newVec.end()); // then reverse
</PRE>
<P>Many of the algorithms described as sequence generating operations, such as<SAMP> transform()</SAMP> (<i><a href="seq_4302.htm#transformoneortwosequences">Transform One or Two Sequences</i></a>), or <SAMP>partial_sum()</SAMP>, can also be used to modify a value in place by simply using the same iterator as both input and output specification.</P>
<A NAME="reverseelementsinasequence"><H3>Reverse Elements in a Sequence</H3></A>
<P>The algorithm <SAMP>reverse()</SAMP> reverses the elements in a sequence, so that the last element becomes the new first, and the first element the new last. The arguments are assumed to be bidirectional iterators, and no value is returned.</P>
<PRE> void reverse (BidirectionalIterator first,
BidirectionalIterator last);
</PRE>
<P>The example program illustrates two uses of this algorithm. In the first, an array of characters values is reversed. The algorithm <SAMP>reverse()</SAMP> can also be used with list values, as shown in the second example. In this example, a list is initialized with the values 2 to 11 in increasing order. (This is accomplished using the <B><I>iotaGen</I></B> function object introduced in <i><a href="fun_0476.htm">Chapter 3: Functions Objects</a></i>). The list is then reversed, which results in the list holding the values 11 to 2 in decreasing order. Note, however, that the list data structure also provides its own <SAMP>reverse()</SAMP> member function.</P>
<PRE>void reverse_example ()
// illustrate the use of the reverse algorithm
{
// example 1, reversing a string
char * text = "Rats live on no evil star";
reverse (text, text + strlen(text));
cout << text << endl;
// example 2, reversing a list
list<int> iList;
generate_n (inserter(iList, iList.begin()), 10, iotaGen(2));
reverse (iList.begin(), iList.end());
}
</PRE>
<A NAME="replacecertainelementswithfixedvalue"><H3>Replace Certain Elements With Fixed Value</H3></A>
<P>The algorithms <SAMP>replace()</SAMP> and <SAMP>replace_if()</SAMP> are used to replace occurrences of certain elements with a new value. In both cases the new value is the same, no matter how many replacements are performed. Using the algorithm <SAMP>replace(),</SAMP> all occurrences of a particular test value are replaced with the new value. In the case of <SAMP>replace_if(),</SAMP> all elements that satisfy a predicate function are replaced by a new value. The iterator arguments must be forward iterators.</P>
<P>The algorithms <SAMP>replace_copy()</SAMP> and <SAMP>replace_copy_if()</SAMP> are similar to <SAMP>replace()</SAMP> and <SAMP>replace_if()</SAMP>, however they leave the original sequence intact and place the revised values into a new sequence, which may be a different type.</P>
<PRE>void replace (ForwardIterator first, ForwardIterator last,
const T&, const T&);</PRE>
<!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE>void replace_if (ForwardIterator first, ForwardIterator last,
Predicate, const T&);</PRE><!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE>OutputIterator replace_copy (InputIterator, InputIterator,
OutputIterator, const T&, const T&);</PRE><!--ASQ-1 The style "teletype gap" is not associated; its content follows: --><PRE>OutputIterator replace_copy (InputIterator, InputIterator,
OutputIterator, Predicate, const T&);
</PRE><P>In the example program, a vector is initially assigned the values 0 1 2 3 4 5 4 3 2 1 0. A call on <SAMP>replace()</SAMP> replaces the value 3 with the value 7, resulting in the vector 0 1 2 7 4 5 4 7 2 1 0. The invocation of <SAMP>replace_if()</SAMP> replaces all even numbers with the value 9, resulting in the vector 9 1 9 7 9 5 9 7 9 1 9.</P>
<PRE>void replace_example ()
// illustrate the use of the replace algorithm
{
// make vector 0 1 2 3 4 5 4 3 2 1 0
vector<int> numbers(11);
for (int i = 0; i < 11; i++)
numbers[i] = i < 5 ? i : 10 - i;
// replace 3 by 7
replace (numbers.begin(), numbers.end(), 3, 7);
// replace even numbers by 9
replace_if (numbers.begin(), numbers.end(), isEven, 9);
// illustrate copy versions of replace
int aList[] = {2, 1, 4, 3, 2, 5};
int bList[6], cList[6], j;
replace_copy (aList, aList+6, &bList[0], 2, 7);
replace_copy_if (bList, bList+6, &cList[0],
bind2nd(greater<int>(), 3), 8);
}
</PRE>
<P>The example program also illustrates the use of the <SAMP>replace_copy</SAMP> algorithms. First, an array containing the values 2 1 4 3 2 5 is created. This is modified by replacing the 2 values with 7, resulting in the array 7 1 4 3 7 5. Next, all values larger than 3 are replaced with the value 8, resulting in the array values 8 1 8 3 8 8. In the latter case the <SAMP>bind2nd()</SAMP> adaptor is used, to modify the binary greater-than function by binding the 2nd argument to the constant value 3, thereby creating the unary function<SAMP> x > 3</SAMP>.</P>
<A NAME="rotateelementsaroundamidpoint"><H3>Rotate Elements Around a Midpoint</H3></A>
<P>A rotation of a sequence divides the sequence into two sections, then swaps the order of the sections, maintaining the relative ordering of the elements within the two sections. Suppose, for example, that we have the values 1 to 10 in sequence.</P>
<P>1 2 3 4 5 6 7 8 9 10</P>
<P>If we were to rotate around the element 7, the values 7 to 10 would be moved to the beginning, while the elements 1 to 6 would be moved to the end. This would result in the following sequence.</P>
<P>7 8 9 10 1 2 3 4 5 6 </P>
<P>When you invoke the algorithm <SAMP>rotate()</SAMP>, the starting point, midpoint, and past-the-end location are all denoted by forward iterators:</P>
<PRE>void rotate (ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
</PRE>
<P>The prefix portion, the set of elements following the start and not including the midpoint, is swapped with the suffix, the set of elements between the midpoint and the past-the-end location. Note, as in the illustration presented earlier, that these two segments need not be the same length.</P>
<PRE>void rotate_example()
// illustrate the use of the rotate algorithm
{
// create the list 1 2 3 ... 10
list<int> iList;
generate_n(inserter(iList, iList.begin()), 10, iotaGen(1));
// find the location of the seven
list<int>::iterator & middle =
find(iList.begin(), iList.end(), 7);
// now rotate around that location
rotate (iList.begin(), middle, iList.end());
// rotate again around the same location
list<int> cList;
rotate_copy (iList.begin(), middle, iList.end(),
inserter(cList, cList.begin()));
}
</PRE>
<P>The example program first creates a list of the integers in order from 1 to 10. Next, the <SAMP>find()</SAMP> algorithm (<i><a href="sea_9743.htm#findanelementsatisfyingacondition">Find an Element Satisfying a Condition</a></i>) is used to find the location of the element 7. This is used as the midpoint for the rotation.</P>
<P>A second form of <SAMP>rotate()</SAMP> copies the elements into a new sequence, rather than rotating the values in place. This is also shown in the example program, which once again rotates around the middle position (now containing a 3). The resulting list is 3 4 5 6 7 8 9 10 1 2. The values held in <SAMP>iList</SAMP> remain unchanged.</P>
<A NAME="partitionasequenceintotwogroups"><H3>Partition a Sequence into Two Groups</H3></A>
<P>A <I>partition </I>is formed by moving all the elements that satisfy a predicate to one end of a sequence, and all the elements that fail to satisfy the predicate to the other end. Partitioning elements is a fundamental step in certain sorting algorithms, such as "quicksort."</P>
<PRE>BidirectionalIterator partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
BidirectionalIterator stable_partition
(BidirectionalIterator, BidirectionalIterator, Predicate);
</PRE>
<P>There are two forms of partition supported in the standard library. The first, provided by the algorithm <SAMP>partition(),</SAMP> guarantees only that the elements will be divided into two groups. The result value is an iterator that describes the final midpoint between the two groups; it is one past the end of the first group. </P>
<A HREF="sidebar.htm#sidebar62"><IMG SRC="images/note.gif" BORDER=0> <STRONG>Partitions</STRONG></A>
<P>In the example program the initial vector contains the values 1 to 10 in order. The partition moves the even elements to the front, and the odd elements to the end. This results in the vector holding the values 10 2 8 4 6 5 7 3 9 1, and the midpoint iterator pointing to the element 5.</P>
<PRE>void partition_example ()
// illustrate the use of the partition algorithm
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -