Mastering STL Algorithms and Function Objects

The remove() family of functions is stable in that it maintains the order of elements remaining in the container even while moving the removed elements to the end.

Unique

The unique() algorithm is a special case of remove() that removes all duplicate contiguous elements. You may recall from Chapter 21 that the list container provides a unique() method that implements the same semantics. You should generally use unique() on sorted sequences, but nothing prevents you from running it on unsorted sequences.

The basic form of unique() runs in place, but there is also a version of the algorithm called unique_copy() that copies its results to a new destination range.

Chapter 21 showed an example of the list unique() algorithm, so we omit an example of the general form here.

Reverse

The reverse() algorithms simply reverses the order of the elements in a range. The first element in the range is swapped with the last, the second with the second-to-last, and so on.

The basic form of reverse() runs in place, but there is also a version of the algorithm called reverse_copy() that copies its results to a new destination range.

Other Modifying Algorithms

There are several other modifying algorithms described in the Standard Library Reference resource on the Web site, including iter_swap(), swap_ranges(), fill(), generate(), rotate(), next_permutation(), and prev_permutation(). We have found these algorithms to be less useful on a day-to-day basis than those shown earlier. However, if you ever need to use them, the Standard Library Reference resource on the Web site contains all the details.

Sorting Algorithms

The STL provides several variations of sorting algorithms. These algorithms don’t apply to associative containers, which always sort their elements internally. Additionally, the list container supplies its own version of sort(), which is more efficient than the general algorithm. Thus, most of these sorting algorithms are useful only for vectors and deques.

Basic Sorting and Merging

The sort() function uses a quicksort-like algorithm to sort a range of elements in O(N log N) time in the general case. Following the application of sort() to a range, the elements in the range are in nondecreasing order (lowest to highest), according to operator<. If you don’t like that order, you can specify a different comparison callback such as greater.

A variant of sort(), called stable_sort(), maintains the relative order of equal elements in the range. stable_sort() uses a mergesort-like algorithm.

643

Chapter 22

Once you have sorted the elements in a range, you can apply the binary_search() algorithm to find elements in logarithmic instead of linear time.

The merge() function allows you to merge two sorted ranges together, while maintaining the sorted order. The result is a sorted range containing all the elements of the two source ranges. merge() works in linear time. Without merge(), you could still achieve the same effect by concatenating the two ranges and applying sort() to the result, but that would be less efficient (O(N log N) instead of linear).

Always ensure that you supply a big enough range to store the result of the merge!

Here is an example of sorting and merging:

#include <algorithm> #include <vector> #include <iostream> using namespace std;

//The populateContainer() and print() functions are identical to those

//in the example above, so they are omitted here.

int main(int argc, char** argv)

{

vector<int> vectorOne, vectorTwo, vectorMerged; cout << “Enter values for first vector:\n”; populateContainer(vectorOne);

cout << “Enter values for second vector:\n”; populateContainer(vectorTwo);

sort(vectorOne.begin(), vectorOne.end()); sort(vectorTwo.begin(), vectorTwo.end());

//Make sure the vector is large enough to hold the values

//from both source vectors. vectorMerged.resize(vectorOne.size() + vectorTwo.size()); merge(vectorOne.begin(), vectorOne.end(), vectorTwo.begin(),

vectorTwo.end(), vectorMerged.begin());

cout << “Merged vector: “;

for_each(vectorMerged.begin(), vectorMerged.end(), &print); cout << endl;

while (true) { int num;

cout << “Enter a number to find (0 to quit): “; cin >> num;

if (num == 0) { break;

}

if (binary_search(vectorMerged.begin(), vectorMerged.end(), num)) { cout << “That number is in the vector.\n”;

} else {

cout << “That number is not in the vector\n”;

644

Mastering STL Algorithms and Function Objects

}

}

return (0);

}

Heapsort

A heap structure stores elements in a semi-sorted order so that finding the highest element is a constant time operation. Removing the highest element and adding a new element both take logarithmic time. For general information on heap data structures, consult one of the data structures books listed in Appendix B.

The STL provides four algorithms for manipulating a heap structure.

make_heap() turns a range of elements into a heap in linear time. The highest element is the first element in the range.

push_heap() adds a new element to the heap by incorporating the element in the previous end position of the range. That is, push_heap() takes an iterator range [first,last) and expects that [first,last-1) is a valid heap and that the element at position last – 1 is a new element to be added to the heap. In terms of containers, if you have a heap in a deque container, you can use push_back() to add a new element to the deque, then call push_heap() on the deque beginning and end iterators. push_heap() runs in logarithmic time.

pop_heap() removes the highest element from the heap and reorders the remaining elements to keep the heap structure. It reduces the range representing the heap by one element. If the range before the call was [first,last), the new range is [first,last-1). As usual, the algorithm can’t actually remove the element from the container. If you want to remove it you must call erase() or pop_back() after calling pop_heap(). pop_heap() runs in logarithmic time.

sort_heap() turns a heap range into a fully sorted range in O(N log N) time.

Heaps are useful for implementing priority queues. In fact, the priority_queue container presented in Chapter 21 is implemented with these heap algorithms. If you are ever tempted to use the heap algorithms directly, you should first make sure that the priority_queue interface does not meet with your satisfaction. We don’t show an example of the heap functions here, but the Standard Library Reference resource on the Web site contains the details in case you ever need to use them.

Other Sorting Routines

There are several other sorting routines, including partition(), partial_sort(), and nth_element(). They are mostly useful as building blocks for a quicksort-like algorithm. Given that sort() already provides a quicksort-like algorithm, you usually shouldn’t need to use these other sorting routines. However, the Standard Library Reference resource on the Web site contains the details in case the need arises.

random_shuffle()

The final “sorting” algorithm is technically more of an “anti-sorting” algorithm. random_shuffle() rearranges the elements of a range in a random order. It’s useful for implementing tasks like sorting a deck of cards.

645

Chapter 22

Set Algorithms

The final class of algorithms in the STL is five functions for performing set operations. Although these algorithms work on any sorted iterator range, they are obviously aimed at ranges from the set container.

The includes() function implements standard subset determination, checking if all the elements of one sorted range are included in another sorted range, in any order.

The set_union(), set_intersection(), set_difference(), and set_symmetric_difference() functions implement the standard semantics of those operations. In case you haven’t studied set theory recently, here’s a rundown. The result of union is all the elements in either set. The result of intersection is all the elements in both sets. The result of difference is all the elements in the first set but not the second. The result of symmetric difference is the “exclusive or” of sets: all the elements in one, but not both, sets.

As usual, make sure that your result range is large enough to hold the result of the operations. For set_union() and set_symmetric_difference(), the result is at most the sum of the sizes of the two input ranges. For set_intersection() and set_difference() it’s at most the maximum of the two sizes.

Remember that you can’t use iterator ranges from associative containers, including sets, to store the results.

Here is an example of these algorithms:

#include <algorithm> #include <iostream> #include <vector> using namespace std;

//The populateContainer() and print() functions are identical to those

//in the example above, so are omitted here.

int main(int argc, char** argv)

{

vector<int> setOne, setTwo, setThree;

cout << “Enter set one:\n”; populateContainer(setOne); cout << “Enter set two:\n”; populateContainer(setTwo);

// set algorithms work on sorted ranges sort(setOne.begin(), setOne.end()); sort(setTwo.begin(), setTwo.end());

if (includes(setOne.begin(), setOne.end(), setTwo.begin(), setTwo.end())) { cout << “The second set is a subset of the first\n”;

646

Mastering STL Algorithms and Function Objects

}

if (includes(setTwo.begin(), setTwo.end(), setOne.begin(), setOne.end())) { cout << “The first set is a subset of the second\n”;

}

setThree.resize(setOne.size() + setTwo.size()); vector<int>::iterator newEnd;

newEnd = set_union(setOne.begin(), setOne.end(), setTwo.begin(), setTwo.end(), setThree.begin());

cout << “The union is: “; for_each(setThree.begin(), newEnd, &print); cout << endl;

newEnd = set_intersection(setOne.begin(), setOne.end(), setTwo.begin(), setTwo.end(), setThree.begin());

cout << “The intersection is: “; for_each(setThree.begin(), newEnd, &print); cout << endl;

newEnd = set_difference(setOne.begin(), setOne.end(), setTwo.begin(), setTwo.end(), setThree.begin());

cout << “The difference between set one and set two is: “; for_each(setThree.begin(), newEnd, &print);

cout << endl;

newEnd = set_symmetric_difference(setOne.begin(), setOne.end(), setTwo.begin(), setTwo.end(), setThree.begin());

cout << “The symmetric difference is: “; for_each(setThree.begin(), newEnd, &print); cout << endl;

return (0);

}

Here is a sample run of the program:

Enter set one:

Enter a number (0 to quit): 5

Enter a number (0 to quit): 6

Enter a number (0 to quit): 7

Enter a number (0 to quit): 8

Enter a number (0 to quit): 0

Enter set two:

Enter a number (0 to quit): 8

Enter a number (0 to quit): 9

Enter a number (0 to quit): 10

Enter a number (0 to quit): 0

The union is: 5 6 7 8 9 10

The intersection is: 8

The difference between set one and set two is: 5 6 7

The symmetric difference is: 5 6 7 9 10

647