Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

Manipulating sequences

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
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, StrictWeakOrdering

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.


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

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire