Lesson 23. STL Algorithms
An important part of the Standard Template Library (STL) is a set of generic functions, supplied by the header <algorithm>, that help manipulate or work with the contents of a container. In this lesson, you learn the usage of algorithms that reduce boilerplate code in helping you:
Count, search, find, copy, and remove elements from a container
Set values in a range of elements to the return value of a generator function or a predefined constant
Sort or partition elements in a range
Insert elements at the correct position in a sorted range
What Are STL Algorithms?
Finding, searching, removing, and counting are some generic algorithmic activities that find application in a broad range of programs. STL solves these and many other requirements in the form of generic template functions that work on containers using iterators. To use STL algorithms, the programmer first has to include the header <algorithm>.
Note
Although most algorithms work via iterators on containers, not all algorithms necessarily work on containers and hence not all algorithms need iterators. Some, such as swap(), simply accept a pair of values to swap them. Similarly, min() and max() work directly on values, too.
Classification of STL Algorithms
STL algorithms can be broadly classified into two types: non-mutating and mutating algorithms.
Non-Mutating Algorithms
Algorithms that change neither the order nor the contents of a container are called non-mutating algorithms. Some of the prominent non-mutating algorithms are shown in Table 23.1.
Mutating Algorithms
Mutating algorithms are those that change the contents or the order of the sequence they are operating on. Some of the most useful mutating algorithms supplied by STL are shown in Table 23.2.
Usage of STL Algorithms
The usage of the STL algorithms mentioned in Tables 23.1 and 23.2 is best learned in a hands-on coding session. To that end, practice using the code examples that follow and start applying them to your programs.
Finding Elements Given a Value or a Condition
Given a container such as a vector, STL algorithms find() and find_if() help you find an element that matches a value or fulfills a condition, respectively. The usage of find() follows this pattern:
auto element = find (numsInVec.cbegin(), // Start of range
numsInVec.cend(), // End of range
numToFind); // Element to find
// Check if find() succeeded
if (element != numsInVec.cend ())
cout << "Result: Value found!" << endl;
find_if() is similar and requires you to supply a unary predicate (a unary function that returns true or false) as the third parameter.
auto evenNum = find_if (numsInVec.cbegin(), // Start of range
numsInVec.cend(), // End of range
[](int element) { return (element % 2) == 0; } );
if (evenNum != numsInVec.cend())
cout << "Result: Value found!" << endl;
Thus, both find functions return an iterator, which you need to compare against the end() or cend() of the container to verify the success of the find operation. If this check is successful, you can use this iterator further. Listing 23.1 demonstrates the usage of find() to locate a value in a vector, and find_if() to locate the first even value.
LISTING 23.1 Using find() to Locate an Integer Value in a vector, find_if to Locate the First Even Number Given an Unary Predicate in a Lambda Expression
0: #include <iostream>
1: #include <algorithm>
2: #include <vector>
3:
4: int main()
5: {
6: using namespace std;
7: vector<int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };
8:
9: cout << "Enter number to find in collection: ";
10: int numToFind = 0;
11: cin >> numToFind;
12:
13: auto element = find (numsInVec.cbegin (), // Start of range
14: numsInVec.cend (), // End of range
15: numToFind); // Element to find
16:
17: // Check if find succeeded
18: if (element != numsInVec.cend ())
19: cout << "Value " << *element << " found!" << endl;
20: else
21: cout << "No element contains value " << numToFind << endl;
22:
23: cout << "Finding the first even number using find_if: " << endl;
24:
25: auto evenNum = find_if (numsInVec.cbegin(), // Start range
26: numsInVec.cend(), // End range
27: [](int element) { return (element % 2) == 0; } );
28:
29: if (evenNum != numsInVec.cend ())
30: {
31: cout << "Number '" << *evenNum << "' found at position [";
32: cout << distance (numsInVec.cbegin (), evenNum) << "]" << endl;
33: }
34:
35: return 0;
36: }
Output 
Enter number to find in collection: 42
Value 42 found!
Finding the first even number using find_if:
Number '0' found at position [1]
Next run:
Enter number to find in collection: 2016
No element contains value 2016
Finding the first even number using find_if:
Number '0' found at position [1]
Analysis
main() starts with initializing a vector of integers to sample values in Line 7. You use find() in Lines 13–15 to find the number entered by the user. The use of find_if() to locate the first even number given the range is shown in Lines 25–27. Line 27 is the unary predicate supplied to find_if() as a lambda expression. This lambda expression returns true when element is divisible by 2, thereby indicating to the algorithm that the element satisfies the criteria being checked for. Note the usage of algorithm std::distance() in Line 32 to find the relative position of an element found against the start of the container.
Caution
Note how Listing 23.1 always checks the iterator returned by find() or find_if() for validity against cend(). This check should never be skipped, as it indicates the success of the find() operation, which should not be taken for granted.
Counting Elements Given a Value or a Condition
std::count() and count_if() are algorithms that help in counting elements given a range. std::count() helps you count the number of elements that match a value (tested via equality operator==):
size_t numZeroes = count (numsInVec.cbegin (), numsInVec.cend (), 0);
cout << "Number of instances of '0': " << numZeroes << endl;
std::count_if() helps you count the number of elements that fulfill a unary predicate supplied as a parameter (which can be a function object or a lambda expression):
// Unary predicate:
template <typename elementType>
bool IsEven (const elementType& number)
{
return ((number % 2) == 0); // true, if even
}
...
// Use the count_if algorithm with the unary predicate IsEven:
size_t numEvenNums = count_if (numsInVec.cbegin (),
numsInVec.cend (), IsEven <int> );
cout << "Number of even elements: " << numEvenNums << endl;
The code in Listing 23.2 demonstrates the usage of these functions.
LISTING 23.2 Demonstrates the Usage of std::count() to Determine Number of Elements with a Value and count_if() to Determine Number of Elements That Fulfill a Condition
0: #include <algorithm>
1: #include <vector>
2: #include <iostream>
3:
4: // unary predicate for *_if functions
5: template <typename elementType>
6: bool IsEven (const elementType& number)
7: {
8: return ((number % 2) == 0); // true, if even
9: }
10:
11: int main ()
12: {
13: using namespace std;
14: vector <int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };
15:
16: size_t numZeroes = count (numsInVec.cbegin(), numsInVec.cend(), 0);
17: cout << "Number of instances of '0': " << numZeroes << endl << endl;
18:
19: size_t numEvenNums = count_if (numsInVec.cbegin(),
20: numsInVec.cend(), IsEven <int> );
21:
22: cout << "Number of even elements: " << numEvenNums << endl;
23: cout << "Number of odd elements: ";
24: cout << numsInVec.size () - numEvenNums << endl;
25:
26: return 0;
27: }
Output
Number of instances of '0': 1
Number of even elements: 2
Number of odd elements: 4
Analysis
Line 16 uses count() to determine the number of instances of 0 in the vector. Similarly, Line 19 uses count_if() to determine the number of even elements in the vector. Note the third parameter, which is a unary predicate IsEven() defined in Lines 5–9. The number of elements in the vector that are odd is calculated by subtracting the return of count_if() with the total number of elements contained in the vector returned by size().
Note
Listing 23.2 uses predicate function IsEven() in count_if(), whereas Listing 23.1 used a lambda function doing the work of IsEven() in find_if().
The lambda version saves lines of code, but you should remember that if the two samples were merged, IsEven() could be used in both find_if() and count_if(), increasing opportunities for reuse.
Searching for an Element or a Range in a Collection
Listing 23.1 demonstrated how you can find an element in a container. Sometimes, you need to find a range of values or a pattern. In such situations, you should use search() or search_n(). search() can be used to check if one range is contained in another:
auto range = search (numsInVec.cbegin(), // Start range to search in
numsInVec.cend(), // End range to search in
numsInList.cbegin(), // start range to search
numsInList.cend() ); // End range to search for
search_n() can be used to check if n instances of a value placed consequently are to be found in a container:
auto partialRange = search_n (numsInVec.cbegin(), // Start range
numsInVec.cend(), // End range
3, // num items to be searched for
9); // value to search for
Both functions return an iterator to the first instance of the pattern found, and this iterator needs to be checked against end() before it can be used. Listing 23.3 demonstrates the usage of search() and search_n().
LISTING 23.3 Finding a Range in a Collection Using search() and search_n()
0: #include <algorithm>
1: #include <vector>
2: #include <list>
3: #include <iostream>
4: using namespace std;
5:
6: template <typename T>
7: void DisplayContents (const T& container)
8: {
9: for(auto element = container.cbegin();
10: element != container.cend();
11: ++ element)
12: cout << *element << ' ';
13:
14: cout << endl;
15: }
16:
17: int main()
18: {
19: vector <int> numsInVec{ 2017, 0, -1, 42, 10101, 25, 9, 9, 9 };
20: list <int> numsInList{ -1, 42, 10101 };
21:
22: cout << "The contents of the sample vector are: " << endl;
23: DisplayContents (numsInVec);
24:
25: cout << "The contents of the sample list are: " << endl;
26: DisplayContents (numsInList);
27:
28: cout << "search() for the contents of list in vector:" << endl;
29: auto range = search (numsInVec.cbegin(), // Start range to search in
30: numsInVec.cend(), // End range to search in
31: numsInList.cbegin(), // Start range to search for
32: numsInList.cend()); // End range to search for
33:
34: // Check if search found a match
35: if (range != numsInVec.end())
36: {
37: cout << "Sequence in list found in vector at position: ";
38: cout << distance (numsInVec.cbegin(), range) << endl;
39: }
40:
41: cout << "Searching {9, 9, 9} in vector using search_n(): " << endl;
42: auto partialRange = search_n (numsInVec.cbegin(), // Start range
43: numsInVec.cend(), // End range
44: 3, // Count of item to be searched for
45: 9 ); // Item to search for
46:
47: if (partialRange != numsInVec.end())
48: {
49: cout << "Sequence {9, 9, 9} found in vector at position: ";
50: cout << distance (numsInVec.cbegin(), partialRange) << endl;
51: }
52:
53: return 0;
54: }
Output
The contents of the sample vector are:
2017 0 -1 42 10101 25 9 9 9
The contents of the sample list are:
-1 42 10101
search() for the contents of list in vector:
Sequence in list found in vector at position: 2
Searching {9, 9, 9} in vector using search_n():
Sequence {9, 9, 9} found in vector at position: 6
Analysis
The sample starts with two sample containers, a vector and a list that are initially populated with sample integer values. search() is used to find the presence of the contents of the list in vector, as shown in Line 29. As you want to search in the entire vector for the contents of the entire list, you supply a range as returned by the iterators corresponding to cbegin() and cend() member methods of the two container classes. This actually demonstrates how well iterators connect the algorithms to the containers. The physical characteristics of the containers that supply those iterators are of no significance to algorithms, which search the contents of a list in a vector seamlessly as they only work with iterators. search_n() is used in Line 42 to find the first occurrence of series {9, 9, 9}in the vector.
Initializing Elements in a Container to a Specific Value
fill() and fill_n() are the STL algorithms that help set the contents of a given range to a specified value. fill() is used to overwrite the elements in a range given the bounds of the range and the value to be inserted:
vector <int> numsInVec (3);
// fill all elements in the container with value 9
fill (numsInVec.begin (), numsInVec.end (), 9);
As the name suggests, fill_n() resets a specified n number of values. It needs a starting position, a count, and the value to fill:
fill_n (numsInVec.begin () + 3, /*count*/ 3, /*fill value*/ -9);
Listing 23.4 demonstrates how these algorithms make initializing elements in a vector<int> easy.
LISTING 23.4 Using fill() and fill_n() to Set Initial Values in a Container
0: #include <algorithm>
1: #include <vector>
2: #include <iostream>
3:
4: int main ()
5: {
6: using namespace std;
7:
8: // Initialize a sample vector with 3 elements
9: vector <int> numsInVec (3);
10:
11: // fill all elements in the container with value 9
12: fill (numsInVec.begin (), numsInVec.end (), 9);
13:
14: // Increase the size of the vector to hold 6 elements
15: numsInVec.resize (6);
16:
17: // Fill the three elements starting at offset position 3 with value -9
18: fill_n (numsInVec.begin () + 3, 3, -9);
19:
20: cout << "Contents of the vector are: " << endl;
21: for (size_t index = 0; index < numsInVec.size (); ++ index)
22: {
23: cout << "Element [" << index << "] = ";
24: cout << numsInVec [index] << endl;
25: }
26:
27: return 0;
28: }
Output
Contents of the vector are:
Element [0] = 9
Element [1] = 9
Element [2] = 9
Element [3] = -9
Element [4] = -9
Element [5] = -9
Analysis
Listing 23.4 uses the fill() and fill_n() functions to initialize the contents of the container to two separate sets of values, as shown in Lines 12 and 18. Note the usage of the resize() function in Line 15 where the vector is asked to create space for a total number of 6 elements. The three new elements are later filled with the value -9 using fill_n() in Line 18. The fill() algorithm works on a complete range, whereas fill_n() has the potential to work on a partial range.
Tip
You may have noticed that code in Listings 23.1, 23.2, and 23.3 use the constant versions of the iterators; that is, cbegin() and cend() are used in defining the bounds of elements accessed in a container. However, Listing 23.4 is a deviation in that it uses begin() and end(). This is simply because the purpose of the algorithm fill() is to modify the elements in the container, and this cannot be achieved using constant iterators that don’t allow changes to the element they point to.
Using constant iterators is a good practice, and you may deviate from it when you are certain about the need to modify the elements they point to.
Using std::generate() to Initialize Elements to a Value Generated at Runtime
Just as fill() and fill_n() functions fill the collection with a specific value, STL algorithms, such as generate() and generate_n(), are used to initialize collections using values returned by a unary function.
You can use generate() to fill a range using the return value of a generator function:
generate (numsInVec.begin (), numsInVec.end (), // range
rand); // generator function
generate_n() is similar to generate() except that you supply the number of elements to be assigned instead of the closing bound of a range:
generate_n (numsInList.begin (), 5, rand);
Thus, you can use these two algorithms to initialize the contents of a container to the contents of a file, for example, or to random values, as shown in Listing 23.5.
LISTING 23.5 Using generate() and generate_n() to Initialize Collections to Random Values
0: #include <algorithm>
1: #include <vector>
2: #include <list>
3: #include <iostream>
4: #include <ctime>
5:
6: int main ()
7: {
8: using namespace std;
9: srand(time(NULL)); // seed random generator using time
10:
11: vector <int> numsInVec (5);
12: generate (numsInVec.begin (), numsInVec.end (), // range
13: rand); // generator function
14:
15: cout << "Elements in the vector are: ";
16: for (size_t index = 0; index < numsInVec.size (); ++ index)
17: cout << numsInVec [index] << " ";
18: cout << endl;
19:
20: list <int> numsInList (5);
21: generate_n (numsInList.begin (), 3, rand);
22:
23: cout << "Elements in the list are: ";
24: for (auto element = numsInList.begin();
25: element != numsInList.end();
26: ++ element )
27: cout << *element << ' ';
28:
29: return 0;
30: }
Output
Elements in the vector are: 41 18467 6334 26500 19169
Elements in the list are: 15724 11478 29358 0 0
Analysis
The usage of a random number generator seeded using the current time as seen in Line 9 means that the output is likely to be different on every run of the application. Listing 23.5 uses the generate() in Line 12 to populate all elements in the vector and uses generate_n() in Line 21 to populate the first three elements in the list with random values supplied by the generator function rand(). Note that the generate() function accepts a range as an input and consequently calls the specified function object rand() for every element in the range. generate_n(), in comparison, accepts only the starting position. It then invokes the specified function object, rand(), the number of times specified by the count parameter to overwrite the contents of that many elements. The elements in the container that are beyond the specified offset go untouched.
Processing Elements in a Range Using for_each()
The for_each() algorithm applies a specified unary function object to every element in the supplied range. The usage of for_each() is
fnObjType retValue = for_each (start_of_range,
end_of_range,
unaryFunctionObject);
This unary function object can also be a lambda expression that accepts one parameter.
The return value indicates that for_each() returns the function object (also called functor) used to process every element in the supplied range. The implication of this specification is that using a struct or a class as a function object can help in storing state information, which you can later query when for_each() is done. This is demonstrated by Listing 23.6, which uses the function object to display elements in a range and also uses it to count the number of elements displayed.
LISTING 23.6 Displaying the Contents of Sequences Using for_each()
0: #include <algorithm>
1: #include <iostream>
2: #include <vector>
3: #include <string>
4: using namespace std;
5:
6: template <typename elementType>
7: struct DisplayElementKeepcount
8: {
9: int count;
10: DisplayElementKeepcount (): count (0) {}
11:
12: void operator () (const elementType& element)
13: {
14: ++ count;
15: cout << element << ' ';
16: }
17: };
18:
19: int main ()
20: {
21: vector <int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };
22:
23: cout << "Elements in vector are: " << endl;
24: DisplayElementKeepcount<int> functor =
25: for_each (numsInVec.cbegin(), // Start of range
26: numsInVec.cend (), // End of range
27: DisplayElementKeepcount<int> ());// functor
28: cout << endl;
29:
30: // Use the state stored in the return value of for_each!
31: cout << "'" << functor.count << "' elements displayed" << endl;
32:
33: string str ("for_each and strings!");
34: cout << "Sample string: " << str << endl;
35:
36: cout << "Characters displayed using lambda:" << endl;
37: int numChars = 0;
38: for_each (str.cbegin(),
39: str.cend (),
40: [&numChars](char c) { cout << c << ' '; ++numChars; } );
41:
42: cout << endl;
43: cout << "'" << numChars << "' characters displayed" << endl;
44:
45: return 0;
46: }
Elements in vector are:
2017 0 -1 42 10101 25
'6' elements displayed
Sample string: for_each and strings!
Characters displayed using lambda:
f o r _ e a c h a n d s t r i n g s !
'21' characters displayed
Analysis
The code sample demonstrates the utility of for_each() invoked in Lines 25 and 38, and the function object functor returned by for_each() that is programmed to hold the number of times it was invoked in member count. The code features two sample ranges, one contained in a vector of integers, numsInVec, and the other a std::string object str. The first call to for_each() uses DisplayElementKeepCount as the unary predicate, and the second uses a lambda expression. for_each() invokes operator() for every element in the supplied range, which in turn prints the element on the screen and increments an internal counter. The function object is returned when for_each() is done, and the member count tells the number of times the object was used. This facility of storing information (or state) in the object that is returned by the algorithm can be useful in practical programming situations. for_each() in Line 38 does exactly the same as its previous counterpart in Line 25 for a std::string, using a lambda expression instead of a function object.
Performing Transformations on a Range Using std::transform()
std::for_each() and std::transform() are similar in that they both invoke a function object for every element in a source range. However, std::transform() has two versions. The first version accepts a unary function and is popularly used to convert a string to upper- or lowercase using functions toupper() or tolower():
string str ("THIS is a TEst string!");
transform (str.cbegin(), // start source range
str.cend(), // end source range
strLowerCaseCopy.begin(), // start destination range
::tolower); // unary function
The second version accepts a binary function allowing transform() to process a pair of elements taken from two different ranges:
// sum elements from two vectors and store result in a deque
transform (numsInVec1.cbegin(), // start of source range 1
numsInVec1.cend(), // end of source range 1
numsInVec2.cbegin(), // start of source range 2
sumInDeque.begin(), // store result in a deque
plus<int>()); // binary function plus
Both versions of the transform() always assign the result of the specified transformation function to a supplied destination range, unlike for_each(), which works on only a single range. The usage of std::transform() is demonstrated in Listing 23.7.
LISTING 23.7 Using std::transform() with Unary and Binary Functions
0: #include <algorithm>
1: #include <string>
2: #include <vector>
3: #include <deque>
4: #include <iostream>
5: #include <functional>
6:
7: int main()
8: {
9: using namespace std;
10:
11: string str ("THIS is a TEst string!");
12: cout << "The sample string is: " << str << endl;
13:
14: string strLowerCaseCopy;
15: strLowerCaseCopy.resize (str.size());
16:
17: transform (str.cbegin(), // start source range
18: str.cend(), // end source range
19: strLowerCaseCopy.begin(), // start dest range
20: ::tolower); // unary function
21:
22: cout << "Result of 'transform' on the string with 'tolower':" << endl;
23: cout << """ << strLowerCaseCopy << """ << endl << endl;
24:
25: // Two sample vectors of integers...
26: vector<int> numsInVec1{ 2017, 0, -1, 42, 10101, 25 };
27: vector<int> numsInVec2 (numsInVec1.size(), -1);
28:
29: // A destination range for holding the result of addition
30: deque <int> sumInDeque (numsInVec1.size());
31:
32: transform (numsInVec1.cbegin(), // start of source range 1
33: numsInVec1.cend(), // end of source range 1
34: numsInVec2.cbegin(), // start of source range 2
35: sumInDeque.begin(), // start of dest range
36: plus<int>()); // binary function
37:
38: cout << "Result of 'transform' using binary function 'plus': " << endl;
39: cout << "Index Vector1 + Vector2 = Result (in Deque)" << endl;
40: for (size_t index = 0; index < numsInVec1.size(); ++ index)
41: {
42: cout << index << " " << numsInVec1 [index] << " + ";
43: cout << numsInVec2 [index] << " = ";
44: cout << sumInDeque [index] << endl;
45: }
46:
47: return 0;
48: }
Output
The sample string is: THIS is a TEst string!
Result of 'transform' on the string with 'tolower':
"this is a test string!"
Result of 'transform' using binary function 'plus':
Index Vector1 + Vector2 = Result (in Deque)
0 2017 + -1 = 2016
1 0 + -1 = -1
2 -1 + -1 = -2
3 42 + -1 = 41
4 10101 + -1 = 10100
5 25 + -1 = 24
Analysis
The sample demonstrates both versions of std::transform(), one that works on a single range using a unary function tolower(), as shown in Line 20, and another that works on two ranges and uses a binary function plus(), as shown in Line 36. The first changes the case of a string, character by character, to lowercase. If you use toupper() instead of tolower(), you effect a case conversion to uppercase. The other version of std::transform(), shown in Lines 32–36, acts on elements taken from two input ranges (two vectors in this case) and uses a binary predicate in the form of the STL function plus() (supplied by the header <functional>) to add them. std::transform() takes one pair at a time, supplies it to the binary function plus, and assigns the result to an element in the destination range—one that happens to belong to an std::deque.
Note that the change in container used to hold the result is purely for demonstration purposes. It only displays how well iterators are used to abstract containers and their implementation from STL algorithms; transform(), being an algorithm, deals with ranges and really does not need to know details on the containers that implement these ranges. So, the input ranges happened to be in vector, and the output ranges happened to be a deque, and it all works fine—so long as the bounds that define the range (supplied as input parameters to transform) are valid.
Copy and Remove Operations
STL supplies three prominent copy functions: copy(), copy_if(), and copy_backward(). copy() can assign the contents of a source range into a destination range in the forward direction:
auto lastElement = copy (numsInList.cbegin(), // start source range
numsInList.cend(), // end source range
numsInVec.begin()); // start dest range
copy_if() is an addition to the standard library starting with C++11 and copies an element when a unary predicate supplied by you returns true:
// copy odd numbers from list into vector
copy_if (numsInList.cbegin(), numsInList.cend(),
lastElement, // copy position in dest range
[](int element){return ((element % 2) == 1);});
copy_backward() assigns the contents to the destination range in the backward direction:
copy_backward (numsInList.cbegin (),
numsInList.cend (),
numsInVec.end ());
remove(), on the other hand, deletes elements in a container that matches a specified value:
// Remove all instances of '0', resize vector using erase()
auto newEnd = remove (numsInVec.begin (), numsInVec.end (), 0);
numsInVec.erase (newEnd, numsInVec.end ());
remove_if() uses a unary predicate and removes from the container those elements for which the predicate evaluates to true:
// Remove all odd numbers from the vector using remove_if
newEnd = remove_if (numsInVec.begin (), numsInVec.end (),
[](int num) {return ((num % 2) == 1);} ); //predicate
numsInVec.erase (newEnd, numsInVec.end ()); // resizing
Listing 23.8 demonstrates the usage of the copy and removal functions.
LISTING 23.8 A Sample That Demonstrates copy(), copy_if(), remove(), and remove_if() to Copy a list into a vector, Remove 0s and Even Numbers
0: #include <algorithm>
1: #include <vector>
2: #include <list>
3: #include <iostream>
4: using namespace std;
5:
6: template <typename T>
7: void DisplayContents(const T& container)
8: {
9: for (auto element = container.cbegin();
10: element != container.cend();
11: ++ element)
12: cout << *element << ' ';
13:
14: cout << "| Number of elements: " << container.size() << endl;
15: }
16:
17: int main()
18: {
19: list <int> numsInList{ 2017, 0, -1, 42, 10101, 25 };
20:
21: cout << "Source (list) contains:" << endl;
22: DisplayContents(numsInList);
23:
24: // Initialize vector to hold 2x elements as the list
25: vector <int> numsInVec (numsInList.size() * 2);
26:
27: auto lastElement = copy (numsInList.cbegin(), // start source range
28: numsInList.cend(), // end source range
29: numsInVec.begin() );// start dest range
30:
31: // copy odd numbers from list into vector
32: copy_if (numsInList.cbegin(), numsInList.cend(),
33: lastElement,
34: [](int element){return ((element % 2) != 0);});
35:
36: cout << "Destination (vector) after copy and copy_if:" << endl;
37: DisplayContents(numsInVec);
38:
39: // Remove all instances of '0', resize vector using erase()
40: auto newEnd = remove (numsInVec.begin(), numsInVec.end(), 0);
41: numsInVec.erase (newEnd, numsInVec.end());
42:
43: // Remove all odd numbers from the vector using remove_if
44: newEnd = remove_if (numsInVec.begin(), numsInVec.end(),
45: [](int element) {return ((element % 2) != 0);} );
46: numsInVec.erase (newEnd , numsInVec.end()); // resizing
47:
48: cout << "Destination (vector) after remove, remove_if, erase:" << endl;
49: DisplayContents(numsInVec);
50:
51: return 0;
52: }
Output
Source (list) contains:
2017 0 -1 42 10101 25 | Number of elements: 6
Destination (vector) after copy and copy_if:
2017 0 -1 42 10101 25 2017 -1 10101 25 0 0 | Number of elements: 12
Destination (vector) after remove, remove_if, erase:
42 | Number of elements: 1
Analysis
The usage of copy() is shown in Line 27, where you copy the contents of the list into the vector. copy_if() is used in Line 32 and copies all but even numbers from the source range numsInList into the destination range numsInVec starting at the iterator position lastElement returned by copy(). remove() in Line 40 is used to rid numsInVec of all instances of 0. remove_if() in Line 44 removes all odd numbers.
Caution
Listing 23.8 demonstrates that both remove() and remove_if() return an iterator that points to the new end of the container. Yet the container numsInVec has not been resized yet. Elements have been deleted by the remove algorithms and other elements have been shifted forward, but the size() has remained unaltered, meaning there are values at the end of the vector. To resize the container (and this is important, else it has unwanted values at the end), you need to use the iterator returned by remove() or remove_if() in a subsequent call to erase(), as shown in Lines 41 and 46.
Replacing Values and Replacing Element Given a Condition
replace() and replace_if() are the STL algorithms that can replace elements in a collection that are equivalent to a supplied value or satisfy a given condition, respectively. replace() replaces elements based on the return value of the comparison operator (==):
cout << "Using 'std::replace' to replace value 5 by 8" << endl;
replace (numsInVec.begin (), numsInVec.end (), 5, 8);
replace_if() expects a user-specified unary predicate that returns true for every value that needs to be replaced:
cout << "Using 'std::replace_if' to replace even values by -1" << endl;
replace_if (numsInVec.begin (), numsInVec.end (),
[](int element) {return ((element % 2) == 0); }, -1);
The usage of these functions is demonstrated by Listing 23.9.
LISTING 23.9 Using replace() and replace_if() to Replace Values in a Specified Range
0: #include <iostream>
1: #include <algorithm>
2: #include <vector>
3: using namespace std;
4:
5: template <typename T>
6: void DisplayContents(const T& container)
7: {
8: for (auto element = container.cbegin();
9: element != container.cend();
10: ++ element)
11: cout << *element << ' ';
12:
13: cout << "| Number of elements: " << container.size() << endl;
14: }
15:
16: int main ()
17: {
18: vector <int> numsInVec (6);
19:
20: // fill first 3 elements with value 8, last 3 with 5
21: fill (numsInVec.begin (), numsInVec.begin () + 3, 8);
22: fill_n (numsInVec.begin () + 3, 3, 5);
23:
24: // shuffle the container
25: random_shuffle (numsInVec.begin (), numsInVec.end ());
26:
27: cout << "The initial contents of vector: " << endl;
28: DisplayContents(numsInVec);
29:
30: cout << endl << "'std::replace' value 5 by 8" << endl;
31: replace (numsInVec.begin (), numsInVec.end (), 5, 8);
32:
33: cout << "'std::replace_if' even values by -1" << endl;
34: replace_if (numsInVec.begin (), numsInVec.end (),
35: [](int element) {return ((element % 2) == 0); }, -1);
36:
37: cout << endl << "Vector after replacements:" << endl;
38: DisplayContents(numsInVec);
39:
40: return 0;
41: }
Output
The initial contents of vector:
5 8 5 8 8 5 | Number of elements: 6
'std::replace' value 5 by 8
'std::replace_if' even values by -1
Vector after replacements:
-1 -1 -1 -1 -1 -1 | Number of elements: 6
Analysis
The sample fills a vector<int> with sample values and then shuffles it using the STL algorithm std::random_shuffle() as shown in Line 25. Line 31 demonstrates the usage of replace() to replace all 5s by 8s. Hence, when replace_if(), in Line 34, replaces all even numbers with –1, the end result is that the collection has six elements, all containing an identical value of –1, as shown in the output.
Sorting and Searching in a Sorted Collection and Erasing Duplicates
Sorting and searching a sorted range (for sake of performance) are requirements that come up in practical applications. Very often you have an array of information that needs to be sorted, say for presentation’s sake. You can use STL’s sort() algorithm to sort a container:
sort (numsInVec.begin (), numsInVec.end ()); // ascending order
This version of sort() uses std::less<> as a binary predicate that uses operator< implemented by the type in the vector. You can supply your own predicate to change the sort order using an overloaded version:
sort (numsInVec.begin (), numsInVec.end (),
[](int lhs, int rhs) {return (lhs > rhs);} ); // descending order
Similarly, duplicates need to be deleted before the collection is displayed. To remove adjacently placed repeating values, use algorithm unique():
auto newEnd = unique (numsInVec.begin (), numsInVec.end ());
numsInVec.erase (newEnd, numsInVec.end ()); // to resize
To search fast, STL provides you with binary_search() that is effective only on a sorted container:
bool elementFound = binary_search (numsInVec.begin (), numsInVec.end (), 2011);
if (elementFound)
cout << "Element found in the vector!" << endl;
Listing 23.10 demonstrates STL algorithms std::sort() that can sort a range, std::binary_search() that can search a sorted range, and std::unique() that eliminates duplicate neighboring elements (that become neighbors after a sort() operation).
LISTING 23.10 Using sort(), binary_search(), and unique()
0: #include <algorithm>
1: #include <vector>
2: #include <string>
3: #include <iostream>
4: using namespace std;
5:
6: template <typename T>
7: void DisplayContents(const T& container)
8: {
9: for (auto element = container.cbegin();
10: element != container.cend();
11: ++ element)
12: cout << *element << endl;
13: }
14:
15: int main ()
16: {
17: vector<string> vecNames{"John", "jack", "sean", "Anna"};
18:
19: // insert a duplicate
20: vecNames.push_back ("jack");
21:
22: cout << "The initial contents of the vector are: " << endl;
23: DisplayContents(vecNames);
24:
25: cout << "The sorted vector contains names in the order:" << endl;
26: sort (vecNames.begin (), vecNames.end ());
27: DisplayContents(vecNames);
28:
29: cout << "Searching for "John" using 'binary_search':" << endl;
30: bool elementFound = binary_search (vecNames.begin (), vecNames.end (),
31: "John");
32:
33: if (elementFound)
34: cout << "Result: "John" was found in the vector!" << endl;
35: else
36: cout << "Element not found " << endl;
37:
38: // Erase adjacent duplicates
39: auto newEnd = unique (vecNames.begin (), vecNames.end ());
40: vecNames.erase (newEnd, vecNames.end ());
41:
42: cout << "The contents of the vector after using 'unique':" << endl;
43: DisplayContents(vecNames);
44:
45:_ return 0;
46: }
Output
The initial contents of the vector are:
John
jack
sean
Anna
jack
The sorted vector contains names in the order:
Anna
John
jack
jack
sean
Searching for "John" using 'binary_search':
Result: "John" was found in the vector!
The contents of the vector after using 'unique':
Anna
John
jack
sean
Analysis
The preceding code first sorts the sample vector, vecNames in Line 26, before using binary_search() in Line 30 to find "John" in it. Similarly, std::unique() is used in Line 39 to delete the second occurrence of an adjacent duplicate. Note that unique(), like remove(), does not resize the container. It results in values being shifted but not a reduction in the total number of elements. To ensure that you don’t have unwanted or unknown values at the tail end of the container, always follow a call to unique() with vector::erase() using the iterator returned by unique(), as demonstrated by Line 40.
Caution
Algorithms such as binary_search() are effective only in sorted containers. Use of this algorithm on an unsorted vector can have undesirable consequences.
Note
The usage of stable_sort() is the same as that of sort(), which you saw earlier. stable_sort() ensures that the relative order of the sorted elements is maintained. Maintaining relative order comes at the cost of performance—a factor that needs to be kept in mind, especially if the relative ordering of elements is not essential.
Partitioning a Range
std::partition() helps partition an input range into two sections: one that satisfies a unary predicate and another that doesn’t:
bool IsEven (const int& num) // unary predicate
{
return ((num % 2) == 0);
}
...
partition (numsInVec.begin(), numsInVec.end(), IsEven);
std::partition(), however, does not guarantee the relative order of elements within each partition. To maintain relative order, when that is important, you should use std::stable_partition():
stable_partition (numsInVec.begin(), numsInVec.end(), IsEven);
Listing 23.11 demonstrates the usage of these algorithms.
LISTING 23.11 Using partition() and stable_partition() to Partition a Range of Integers into Even and Odd Values
0: #include <algorithm>
1: #include <vector>
2: #include <iostream>
3: using namespace std;
4:
5: bool IsEven (const int& num) // unary predicate
6: {
7: return ((num % 2) == 0);
8: }
9:
10: template <typename T>
11: void DisplayContents(const T& container)
12: {
13: for (auto element = container.cbegin();
14: element != container.cend();
15: ++ element)
16: cout << *element << ' ';
17:
18: cout << "| Number of elements: " << container.size() << endl;
19: }
20:
21: int main ()
22: {
23: vector <int> numsInVec{ 2017, 0, -1, 42, 10101, 25 };
24:
25: cout << "The initial contents: " << endl;
26: DisplayContents(numsInVec);
27:
28: vector <int> vecCopy (numsInVec);
29:
30: cout << "The effect of using partition():" << endl;
31: partition (numsInVec.begin (), numsInVec.end (), IsEven);
32: DisplayContents(numsInVec);
33:
34: cout << "The effect of using stable_partition():" << endl;
35: stable_partition (vecCopy.begin (), vecCopy.end (), IsEven);
36: DisplayContents(vecCopy);
37:
38: return 0;
39: }
Output
The initial contents:
2017 0 -1 42 10101 25 | Number of elements: 6
The effect of using partition():
42 0 -1 2017 10101 25 | Number of elements: 6
The effect of using stable_partition():
0 42 2017 -1 10101 25 | Number of elements: 6
The code partitions a range of integers, as contained inside vector numsInVec, into even and odd values. This partitioning is first done using std::partition(), as shown in Line 31, and is repeated on a copy using stable_partition() in Line 35. For the sake of being able to compare, you copy the sample range numsInVec into vecCopy, the former partitioned using partition(), and the latter using stable_partition(). The effect of using stable_partition() rather than partition is apparent in the output. stable_partition() maintains the relative order of elements in each partition. Note that maintaining this order comes at the price of performance that might be small, as in this case, or significant depending on the type of object contained in the range.
Note
stable_partition() is slower than partition(), and therefore you should use it only when the relative order of elements in the container is important.
Inserting Elements in a Sorted Collection
It is important that elements inserted in a sorted collection be inserted at the correct positions. STL supplies functions, such as lower_bound() and upper_bound(), to assist in meeting that need:
auto minInsertPos = lower_bound (names.begin(), names.end(),
"Brad Pitt");
// alternatively:
auto maxInsertPos = upper_bound (names.begin(), names.end(),
"Brad Pitt");
Hence, lower_bound() and upper_bound() return iterators pointing to the minimal and the maximal positions in a sorted range where an element can be inserted without breaking the order of the sort.
Listing 23.12 demonstrates the usage of lower_bound() in inserting an element at the minimal position in a sorted list of names.
LISTING 23.12 Using lower_bound() and upper_bound() to Insert in a Sorted Collection
0: #include <algorithm>
1: #include <list>
2: #include <string>
3: #include <iostream>
4: using namespace std;
5:
6: template <typename T>
7: void DisplayContents(const T& container)
8: {
9: for (auto element = container.cbegin();
10: element != container.cend();
11: ++ element)
12: cout << *element << endl;
13: }
14:
15: int main ()
16: {
17: list<string> names{ "John", "Brad", "jack", "sean", "Anna" };
18:
19: cout << "Sorted contents of the list are: " << endl;
20: names.sort ();
21: DisplayContents(names);
22:
23: cout << "Lowest index where "Brad" can be inserted is: ";
24: auto minPos = lower_bound (names.begin (), names.end (), "Brad");
25: cout << distance (names.begin (), minPos) << endl;
26:
27: cout << "The highest index where "Brad" can be inserted is: ";
28: auto maxPos = upper_bound (names.begin (), names.end (), "Brad");
29: cout << distance (names.begin (), maxPos) << endl;
30:
31: cout << endl;
32:
33: cout << "List after inserting Brad in sorted order: " << endl;
34: names.insert (minPos, "Brad");
35: DisplayContents(names);
36:
37: return 0;
38: }
Output
Sorted contents of the list are:
Anna
Brad
John
jack
sean
Lowest index where "Brad" can be inserted is: 1
The highest index where "Brad" can be inserted is: 2
List after inserting Brad in sorted order:
Anna
Brad
Brad
John
jack
sean
An element can be inserted into a sorted collection at two potential positions: one is returned by lower_bound() and is the lowest (the closest to the beginning of the collection) and another is the iterator returned by upper_bound() that is the highest (the farthest away from the beginning of the collection). In the case of Listing 23.12, where the string "Brad" that is inserted into the sorted collection already exists in it, the lower and upper bounds are different (else, they would’ve been identical). The usage of these functions is shown in Lines 24 and 29, respectively. As the output demonstrates, the iterator returned by lower_bound(), when used in inserting the string into the list as shown in Line 35, results in the list keeping its sorted state. Thus, these algorithms help you make an insertion at a point in the collection without breaking the sorted nature of the contents. Using the iterator returned by upper_bound() would have worked fine as well.
Summary
In this lesson, you learned one of the most important and powerful aspects of STL: algorithms. You gained an insight into the different types of algorithms, and the samples should have given you a clearer understanding of the algorithms application.
Q&A
Q Would I use a mutating algorithm, such as std::transform(), on an associative container, such as std::set?
A Even if it were possible, this should not be done. The contents of an associative container should be treated as constants. This is because associative containers sort their elements on insertion, and the relative positions of the elements play an important role in functions such as find() and also in the efficiency of the container. For this reason, mutating algorithms, such as std::transform(), should not be used on STL sets.
Q I need to set the content of every element of a sequential container to a particular value. Would I use std::transform() for this activity?
A Although std::transform() could be used for this activity, fill() or fill_n() is more suited to the task.
Q Does copy_backward()reverse the contents of the elements in the destination container?
A No, it doesn’t. The STL algorithm copy_backward() reverses the order in which elements are copied but not the order in which elements are stored; that is, it starts with the end of the range and reaches the top. To reverse the contents of a collection, you should use std::reverse().
Q Should I use std::sort()on a list?
A std::sort() can be used on a list in the same way it can be used on any sequential container. However, the list needs to maintain a special property that an operation on the list does not invalidate existing iterators—a property that std::sort() cannot guarantee to upkeep. So, for this reason, STL list supplies the sort() algorithm in the form of the member function list::sort(), which should be used because it guarantees that iterators to elements in the list are not invalidated even if their relative positions in the list have changed.
Q Why is it important to use functions such as lower_bound()or upper_bound()while inserting into a sorted range?
A These functions supply the first and the last positions, respectively, where an element can be inserted into a sorted collection without disturbing the sort.
Workshop
The Workshop contains quiz questions to help solidify your understanding of the material covered and exercises to provide you with experience in using what you’ve learned. Try to answer the quiz and exercise questions before checking the answers in Appendix E, and be certain you understand the answers before going to the next lesson.
Quiz
1. You need to remove items that meet a specific condition from a list. Would you use std::remove_if() or list::remove_if()?
2. You have a list of a class type ContactItem. How does the list::sort() function sort items of this type in the absence of an explicitly specified binary predicate?
3. How often does the generate() STL algorithm invoke the generator() function?
4. What differentiates std::transform() from std::for_each()?
Exercises
1. Write a binary predicate that accepts strings as input arguments and returns a value based on case-insensitive comparison.
2. Demonstrate how STL algorithms such as copy() use iterators to do their functions without needing to know the nature of the destination collections by copying between two sequences held in two dissimilar containers.
3. You are writing an application that records the characteristics of stars that come up on the horizon in the order in which they rise. In astronomy, the size of the star—as well as information on their relative rise and set sequences—is important. If you’re sorting this collection of stars on the basis of their sizes, would you use std::sort or std::stable_sort?