Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |

These algorithms let you move sequences around.

OutputIterator **copy**(InputIterator
first, InputIterator

last, OutputIterator destination);

Using assignment, copies from **[first, last)** to **destination**,
incrementing **destination** after each assignment. This is essentially a
shuffle-left operation, and so the source sequence must not contain the
destination. Because assignment is used, you cannot directly insert elements
into an empty container or at the end of a container, but instead you must wrap
the **destination** iterator in an **insert_iterator** (typically by using **back_inserter( )** or by using **inserter( )** in the case of an associative container).

BidirectionalIterator2 **copy_backward**(BidirectionalIterator1

first, BidirectionalIterator1 last,

BidirectionalIterator2 destinationEnd);

Like **copy( )**, but copies the elements in reverse
order. This is essentially a shuffle-right operation, and, like **copy( )**,
the source sequence must not contain the destination. The source range **[first,
last)** is copied to the destination, but the first destination element is **destinationEnd
- 1**. This iterator is then decremented after each assignment. The space in
the destination range must already exist (to allow assignment), and the
destination range cannot be within the source range.

void **reverse**(BidirectionalIterator
first,

BidirectionalIterator last);

OutputIterator **reverse_copy**(BidirectionalIterator first,

BidirectionalIterator last, OutputIterator destination);

Both forms of this function reverse the range **[first,
last)**. **reverse( )** reverses the range in place, and **reverse_copy****( )** leaves the original range alone and copies the reversed elements
into **destination**, returning the past-the-end iterator of the resulting
range.

ForwardIterator2 **swap_ranges**(ForwardIterator1
first1,

ForwardIterator1 last1, ForwardIterator2 first2);

Exchanges the contents of two ranges of equal size by
swapping corresponding elements.

void **rotate**(ForwardIterator
first, ForwardIterator middle,

ForwardIterator last);

OutputIterator **rotate_copy**(ForwardIterator first,

ForwardIterator middle, ForwardIterator last,

OutputIterator destination);

Moves the contents of **[first, middle)** to the end of
the sequence, and the contents of **[middle, last)** to the beginning. With **rotate( )**,
the swap is performed in place; and with **rotate_copy****( )** the original range is untouched, and the rotated version is copied into **destination**,
returning the past-the-end iterator of the resulting range. Note that while **swap_ranges( )**
requires that the two ranges be exactly the same size, the rotate functions do
not.

bool **next_permutation**(BidirectionalIterator
first,

BidirectionalIterator last);

bool **next_permutation**(BidirectionalIterator first,

BidirectionalIterator last, StrictWeakOrdering

binary_pred);

bool **prev_permutation**(BidirectionalIterator first,

BidirectionalIterator last);

bool **prev_permutation**(BidirectionalIterator first,

BidirectionalIterator last, StrictWeakOrdering

binary_pred);

A *permutation* is one unique ordering of a set of
elements. If you have **n** unique elements, there are **n!** (**n**
factorial) distinct possible combinations of those elements. All these
combinations can be conceptually sorted into a sequence using a lexicographical
(dictionary-like) ordering and thus produce a concept of a next and
previous permutation. So whatever the current ordering of elements in the
range, there is a distinct next and previous permutation in the sequence of
permutations.

The **next_permutation****( )** and **prev_permutation( )** functions rearrange the elements into their next or previous
permutation and, if successful, return **true**. If there are no more next
permutations, the elements are in sorted order so **next_permutation( )**
returns **false**. If there are no more previous permutations, the
elements are in descending sorted order so **previous_permutation( )**
returns **false**.

The versions of the functions that have a **StrictWeakOrdering** argument perform the comparisons using **binary_pred** instead of **operator<**.

void **random_shuffle**(RandomAccessIterator
first,

RandomAccessIterator last);

void **random_shuffle**(RandomAccessIterator first,

RandomAccessIterator last RandomNumberGenerator& rand);

This function randomly rearranges the elements in the range.
It yields uniformly distributed results if the random-number generator does.
The first form uses an internal random number generator, and the second uses a
user-supplied random-number generator. The generator must return a value in the
range **[0, n)** for some positive **n**.

BidirectionalIterator **partition**(BidirectionalIterator

first, BidirectionalIterator last, Predicate pred);

BidirectionalIterator **stable_partition**(BidirectionalIterator first,

BidirectionalIterator last, Predicate pred);

The partition functions move elements that satisfy **pred**
to the beginning of the sequence. An iterator pointing one past the last of
those elements is returned (which is, in effect, an end iterator for the
initial subsequence of elements that satisfy **pred**). This location is
often called the partition point.

With **partition****( )**, the order of the elements in each resulting subsequence after the function call is not specified, but with
**stable_partition****( )**, the relative order of the elements
before and after the partition point will be the same as before the
partitioning process.

#### Example

This gives a basic demonstration of sequence manipulation:

//: C06:Manipulations.cpp

// Shows basic manipulations.

//{L} Generators

// NString

#include <vector>

#include <string>

#include <algorithm>

#include "PrintSequence.h"

#include "NString.h"

#include "Generators.h"

using namespace std;

int main() {

vector<int> v1(10);

// Simple counting:

generate(v1.begin(), v1.end(), SkipGen());

print(v1.begin(), v1.end(), "v1", "
");

vector<int> v2(v1.size());

copy_backward(v1.begin(), v1.end(), v2.end());

print(v2.begin(), v2.end(),
"copy_backward", " ");

reverse_copy(v1.begin(), v1.end(), v2.begin());

print(v2.begin(), v2.end(), "reverse_copy",
" ");

reverse(v1.begin(), v1.end());

print(v1.begin(), v1.end(), "reverse",
" ");

int half = v1.size() / 2;

// Ranges must be exactly the same size:

swap_ranges(v1.begin(), v1.begin() + half,

v1.begin() + half);

print(v1.begin(), v1.end(), "swap_ranges",
" ");

// Start with a fresh sequence:

generate(v1.begin(), v1.end(), SkipGen());

print(v1.begin(), v1.end(), "v1", "
");

int third = v1.size() / 3;

for(int i = 0; i < 10; i++) {

rotate(v1.begin(), v1.begin() + third, v1.end());

print(v1.begin(), v1.end(), "rotate",
" ");

}

cout << "Second rotate example:"
<< endl;

char c[] = "aabbccddeeffgghhiijj";

const char CSZ = strlen(c);

for(int i = 0; i < 10; i++) {

rotate(c, c + 2, c + CSZ);

print(c, c + CSZ, "", "");

}

cout << "All n! permutations of abcd:"
<< endl;

int nf = 4 * 3 * 2 * 1;

char p[] = "abcd";

for(int i = 0; i < nf; i++) {

next_permutation(p, p + 4);

print(p, p + 4, "", "");

}

cout << "Using prev_permutation:"
<< endl;

for(int i = 0; i < nf; i++) {

prev_permutation(p, p + 4);

print(p, p + 4, "", "");

}

cout << "random_shuffling a word:"
<< endl;

string s("hello");

cout << s << endl;

for(int i = 0; i < 5; i++) {

random_shuffle(s.begin(), s.end());

cout << s << endl;

}

NString sa[] = { "a", "b",
"c", "d", "a", "b",

"c", "d", "a",
"b", "c", "d", "a", "b",
"c"};

const int SASZ = sizeof sa / sizeof *sa;

vector<NString> ns(sa, sa + SASZ);

print(ns.begin(), ns.end(),
"ns", " ");

vector<NString>::iterator it =

partition(ns.begin(), ns.end(),

bind2nd(greater<NString>(),
"b"));

cout << "Partition point: " <<
*it << endl;

print(ns.begin(), ns.end(), "", "
");

// Reload vector:

copy(sa, sa + SASZ, ns.begin());

it = stable_partition(ns.begin(), ns.end(),

bind2nd(greater<NString>(), "b"));

cout << "Stable partition" <<
endl;

cout << "Partition point: " <<
*it << endl;

print(ns.begin(), ns.end(), "", "
");

} ///:~

The best way to see the results of this program is to run
it. (You ll probably want to redirect the output to a file.)

The **vector<int> v1** is initially loaded with a
simple ascending sequence and printed. You ll see that the effect of **copy_backward( )**
(which copies into **v2**, which is the same size as **v1**) is the same
as an ordinary copy. Again, **copy_backward( )** does the same thing as
**copy( )** it just performs the operations in reverse order.

**reverse_copy( )** actually does create a reversed
copy, and **reverse( )** performs the reversal in place. Next, **swap_ranges( )**
swaps the upper half of the reversed sequence with the lower half. The ranges
could be smaller subsets of the entire **vector**, as long as they are of
equivalent size.

After re-creating the ascending sequence, **rotate( )**
is demonstrated by rotating one third of **v1** multiple times. A second **rotate( )**
example uses characters and just rotates two characters at a time. This also
demonstrates the flexibility of both the STL algorithms and the **print( )**
template, since they can both be used with arrays of **char** as easily as
with anything else.

To demonstrate **next_permutation( )** and **prev_permutation( )**,
a set of four characters abcd is permuted through all **n!** (**n**
factorial) possible combinations. You ll see from the output that the
permutations move through a strictly defined order (that is, permuting is a
deterministic process).

A quick-and-dirty demonstration of **random_shuffle( )**
is to apply it to a **string** and see what words result. Because a **string**
object has **begin( )** and **end( )** member functions that
return the appropriate iterators, it too can be easily used with many of the
STL algorithms. An array of **char** could also have been used.

Finally, the **partition( )** and **stable_partition( )**
are demonstrated, using an array of **NString**. You ll note that the
aggregate initialization expression uses **char** arrays, but **NString**
has a **char*** constructor that is automatically used.

You ll see from the output that with the unstable partition,
the objects are correctly above and below the partition point, but in no
particular order; whereas with the stable partition, their original order is maintained.

Thinking in C++ Vol 2 - Practical Programming |

Prev |
Home |
Next |