COMP6771 Advanced C++ Programming
Week 2.3 STL Algorithms
1
STL: Algorithms
STL Algorithms are functions that execute an algorithm on an abstract notion of an iterator.
In this way, they can work on a number of containers as long as those containers can be represented via a relevant iterator.
2
Simple Example
What’s the best way to sum a vector of numbers? C-style?
1 #include
2 #include
3
4 int main() {
5 std::vector
6
7 int sum = 0;
8 for (int i = 0; i <= nums.size(); ++i) {
9 sum += i;
10 }
11 std::cout << sum << "\n";
12 };
3.1
Simple Example
What's the best way to sum a vector of numbers? Via an iterator? Or for-range?
1 #include
2 #include
3
4 int main() {
5 std::vector
6
7 auto sum = 0;
8 for (auto it = nums.begin(); it != nums.end(); ++it) {
9 sum += *it;
10 }
11 std::cout << sum << "\n";
12 }
1 #include
2 #include
3
4 int main() {
5 std::vector
6
7 int sum = 0; 8
9 // Internally, this uses begin and end,
10 // but it abstracts it away.
11 for (const auto& i : nums) {
12 sum += i;
13 }
14
15 std::cout << sum << "\n";
16 }
demo207-simple-sum.cpp
demo208-simple-sum.cpp
3.2
Simple Example
What's the best way to sum a vector of numbers? Via use of an STL Algorithm
1
2
3
4
5
6
7
8 9}
#include
#include
#include
int main() {
std::vector
int sum = std::accumulate(nums.begin(), nums.end(), 0);
std::cout << sum << "\n";
1
2
3
4
5
6
7}
8 return total 9}
// What type of iterator is required here?
template
T sum(iterator_t
T total;
for (; first != last; ++first) {
total += *first;
demo209-accum.cpp
(This is the underlying mechanics)
3.3
More examples
We can also use algorithms to:
Find the product instead of the sum Sum only the first half of elements
1 #include
2 #include
3 #include
4
5 int main() {
6 std::vector
7 int sum = std::accumulate(v.begin(), v.end(), 0);
8
9 // What is the type of std::multiplies
10 int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies
11
12 auto midpoint = v.begin() + (v.size() / 2);
13 // This looks a lot harder to read. Why might it be better?
14 auto midpoint11 = std::next(v.begin(), std::distance(v.begin(), v.end()) / 2);
15
16 int sum2 = std::accumulate(v.begin(), midpoint, 0); 17
18 std::cout << sum << "\n";
19 }
demo211-algos.cpp
4.1
More examples
We can also use algorithms to: Check if an element exists
1 2 3 4 5 6 7 8 9
10 11 12
#include
#include
int main() {
std::vector
auto it = std::find(nums.begin(), nums.end(), 4);
if (it != nums.end()) {
std::cout << "Found it!" << "\n";
} }
demo212-find.cpp
4.2
Performance & Portability
Consider:
Number of comparisons for binary search on a vector is O(log N) Number of comparisons for binary search on a linked list is O(N log N) The two implementations are completely different
We can call the same function on both of them
It will end up calling a function have two different overloads, one for a forward iterator, and one for a random access iterator
Trivial to read
Trivial to change the type of a container
1 #include
2 #include
3 #include
4 #include
5
6 int main() {
7 // Lower bound does a binary search, and returns the first value >= the argument.
8 std::vector
9 std::lower_bound(sortedVec.begin(), sortedVec.end(), 5);
10
11 std::list
12 std::lower_bound(sortedLinkedList.begin(), sortedLinkedList.end(), 5);
13 }
demo213-bound.cpp
4.3
Algorithms with output sequences
1 #include
2 #include
3
4 char to_upper(unsigned char value) {
5
6}
7
8 int main() { 9
return static_cast
10 std::string s = “hello world”;
11 // Algorithms like transform, which have output iterators,
12 // use the other iterator as an output.
13 auto upper = std::string(s.size(), ‘\0’);
14 std::transform(s.begin(), s.end(), upper.begin(), to_upper);
15 }
demo214-transform.cpp
4.4
Back Inserter
Gives you an output iterator for a container that adds to the end of it
1 #include
2 #include
3
4 char to_upper(char value) {
5
6}
7
8 int main() { 9
return static_cast
10 std::string s = “hello world”;
11 // std::for_each modifies each element
12 std::for_each(s.begin(), s.end(), toupper);
13
14 std::string upper;
15 // std::transform adds to third iterator.
16 std::transform(s.begin(), s.end(), std::back_inserter(upper), to_upper);
17 }
demo215-inserter.cpp
4.5
Lambda Functions
A function that can be defined inside other functions
Can be used with std::function
It can be used as a parameter or variable No need to use function pointers anymore
1
2
3
4
5
6
7 8}
#include
#include
int main() {
std::string s = “hello world”;
// std::for_each modifies each element
std::for_each(s.begin(), s.end(), [] (char& value) { value = std::toupper(value); });
demo216-lambda1.cpp
5.1
Lambda Functions
Anatomy of a lambda function
Lambdas can be defined anonymously, or they can be stored in a variable
1 [](card const c) -> bool { 2 return c.colour == 4; 3}
1 [capture] (parameters) -> return { 2 body
3}
5.2
Lambda Captures
This doesn’t compile
The lambda function can get access to the scope, but does not by default The scope is accessed via the capture []
10 11
1 #include
2 #include
3
4 void add_n(std::vector
std::for_each(v.begin(), v.end(), [n] (int& val) { val = val + n; });
int main() {
std::vector
add_n(v, 3);
}
5 6} 7
8
9
demo217-lambda2.cpp
5.3
Iterator Categories
Operation
Read
Access
Write
Iteration
Compare
Output
*p=
++
Input
=*p
->
++
== !=
Forward
=*p
->
*p=
++
== !=
Bidirectional
=*p
->
*p=
++ —
== !=
Random Access
=*p
-> []
*p=
++ — + – += -=
== != < > <= >=
Random
More powerful
Forward Bidir.
“->” no longer specified as of C++20
6.1
An algorithm requires certain kinds of iterators for their operations
input: find(), equal()
output: copy()
forward: replace(), binary_search() bi-directional: reverse()
random: sort()
A container’s iterator falls into a certain category
forward: forward_list bi-directional: map, list random: vector, deque
Iterator Categories
stack, queue are container adapters, and do not have iterators
6.2