Lecture notes for CS 509, Advanced Programming II

Lecture Notes for CS 509

16 October 2003 - Introduction to Generic Algorithms

Generic Algorithms

Generic Algorithms
Containers vs. Data Sequences
Why Use Generic Algorithms?
Generic Algorithm Categories
- Non-Mutating Algorithms
- Generalized Numeric Algorithms
- Mutating Algorithms
- Order-Related Algorithms
Naming Conventions
Generic Algorithms vs. Member Functions

Generic Algorithms

"generic" means the algorithms can be used with any STL container.
Because C++ arrays are considered a container, you can apply these algorithms to arrays, ignoring the rest of the STL.
Because you can change containers without changing the algorithm, you don't need to think too hard about what container types to use, and you don't need to commit to your choice.
But - I lied - not all containers can be used with all algorithms.
Containers + iterators + algorithms = generic programming.

Containers vs. Data Sequences

Generic algorithms work on data sequences delimited by iterator ranges.
- Generic algorithms do not work on containers, only on data sequences defined by iterator ranges.
A data sequence may be, but doesn't have to be, from an STL container.
- Input and output stream iterators.
- Pointer T * iterators.
- String data types.

Why Use Generic Algorithms?

Find? I can write find!
Maybe so, but...
find() is easy, but how about find_rightmost_subsequence()?
Writing generic algorithms is neither obvious nor simple.
They're already there, and they're tested, debugged, and optimized.
A common vocabulary of functions.
- Use std:: to make it clear you're using generic algorithms.
They simplify your code.
- You're responsible for every line of code you write.
- Write less code.

Generic Algorithms and Iterator Categories

Generic algorithms obey the principle of least privilege.
- Lots of input and output iterators as arguments.
```
InputIterator min_element(
  InputIterator beg, InputIterator end);
```
However, sometimes "least privilege" is not "least powerful".
- Constraints on algorithm function or performance.
- replace(b, e, old, new) needs forward iterators.
- sort(b, e) uses random iterators.
Make sure you understand the iterator categories required by the generic algorithms.
- It's a compile-time error with horrendous error messages.
Also, don't confuse iterator categories with the iterator type.
- You can't declare an input iterator; it's a category, not a type.
- You can declare an iterator that's an input iterator.

Generic Algorithm Categories

Two categories, each with a major sub-category.
Non-mutating algorithms don't change the data sequence.
- Generalized numeric algorithms compute values over data sequences.
Mutating algorithms change the data sequence.
- Order-related algorithms, such as sorts.
Include <algorithm>.
Study Chapter 9 in Josuttis.
- Also study Chapter 22 in Musser, Derge, and Saini.

Non-Mutating Algorithms

Non-mutating algorithms don't change the input data sequence.
- Find a value in a sequence.
  find(v), find_first_of(v), adjacent_find()
- Find a sequence in another sequence.
  search(), search_n(), find_end()
- Test for sequence equality or inequality.
  mismatch(),equal()
- count(v) values in a sequence.
- for_each(f) applies a function to each value in a sequence.

Generalized Numeric Algorithms

Generalized numeric algorithms compute values over data sequences.
- Compute the sum of values in a data sequence.
  accumulate()
- Compute the dot product of two data sequences.
  inner_product()
- Compute the prefix sums of a sequence.
  partial_sum()
- Compute the differences between adjacent values in a sequence.
  adjacent_difference()
The generalized numeric algorithms are powerful, but they require some change of thinking to exploit their full power.
- They are akin to functional programming.

Mutating Algorithms

Mutating algorithms change the contents of a data sequence, but not the sequence itself.
- Copy values from one sequence to another.
- Swap values in two sequences.
- Change values in a sequence.
  transform(f), replace(v1, v2), fill(v), generate(f)
- Eliminate elements in a sequence.
  remove(v), unique()
  - "Eliminate" has an unexpected meaning.
- Move around elements in a sequence.
  reverse(), rotate(), random_shuffle(), partition()

The Mutating Algorithm Trap

Mutating algorithm do not change the input data sequences.
- They change only the contents of the sequences.
Mutating algorithms do not change the sequence size.
Yeah, yeah, yeah - what's next?
```
std::vector<int> iv1(10, 0);
std::vector<int> iv2;
std::copy(iv1.start(), iv1.end(), iv2.start);
```
This goes (or should go) boom. Why?
- As an aside, copy constructors do this better.
```
std::vector iv1(10, 0);
std::vector iv2(iv1);
```
  Know your tools.
- iv2 is properly sized; the data transfer optimized.
Insertion iterators avoid this trap.

Order-Related Algorithms

Order-related mutating algorithms either order or require ordered data sequences.
- Sorting into ascending order.
  sort(), stable_sort(), partial_sort()
- Bisection searching.
  nth_element(), binary_search(), lower_bound(), upper_bound(), ...
- merge() two sorted sequences into one.
- Set operations.
  set_union(), set_intersection(), ...
- Heap operations (priority queues).
  push_heap(), pop_heap(), make_heap(), ...
- Finding the minimum and maximum elements in a sequence.
- Lexicographic comparisons between two sequences.
- Permuting sequences.

Order-Related Algorithm Traps

Order-related algorithms accept unordered data sequence, but won't work correctly.
- Unordered data sequences may produce the wrong results, or do something terrible (run infinitely, often).
- This is done silently (assuming it doesn't explode).
The definition of the order predicate less() is not obvious.
- less() must be a trichotomy:
  If both a < b and b < a are false
  then (a == b).
- < is a trichotomy, <= is not.
  - If both a < b and b < a are false, then a == b.
  - Both a <= b and b <= a are never false,
    so a == b is never true.
- Using a non-trichotomous order predicate may produce incorrect or unpleasant results.

Naming Conventions

The _if convention distinguishes value-predicate algorithms.
- find(start, end, value)
  Return an iterator to the leftmost occurrence of value in the sequence, or end if there's no such value.
- find_if(start, end, predicate)
  Return an iterator to the leftmost occurrence of a value in the sequence that causes the predicate to return true, or end if there's no such value.
The _copy convention indicates non-mutating mutating algorithms.
- reverse(start, end)
  Reverse the order of the elements in the given sequence.
- reverse(start, end, new_start)
  Copy the reversed sequence into the sequence starting at new_start.

When to Use Generic Algorithms

Writing a loop with iterators or indices?
- That's a prime candidate for being replaced by a generic algorithm.

Examples:

Before:

iv_iter i = iv.begin()
while (i != iv.end()) and (iv[i] != 0)
  ++i

After:

iv_iter i = 
  std::find(iv.begin(), iv.end(), 0)

Before:

for(unsigned i = 0; i < s.size(); i++)
  s[i] = std::tolower(s[i])

After:

std::transform(
  s.begin(), s.end(), 
  s.begin(), std::tolower)

Generic Algorithms and Member Functions

Some containers don't have iterators acceptable to some generic algorithms.
- std::sort() requires random iterators for efficiency.
- Lists only support bidirectional iterators.
- How do you sort lists?
- Use the .sort() list member function.
Some containers duplicate function provided by generic algorithms.
- std::copy(s.begin(),s.end(),d.begin())
- v2.assign(s.begin(), s.end())
- v2.insert(d, s.begin(), s.end())
Generic Algorithms vs. Member Functions
- Favor member functions over generic algorithms.
- Less typing, no template problems.
- Member functions are better behaved than are generic algorithms.
  - Member functions can resize the container.
    v2.assign() changes v2's size; std::copy() can't (without help).
- Member functions can be more efficient than generic algorithms.
Points to Remember
- Generic algorithms - know them, use them, love them.
  - But favor member functions where possible.
- Don't write loops with iterators or indexes.
  - That smells like a generic algorithm.
- Understand the categories and respect them.
  - Iterator kinds and sorted data sequences.
- Mutating generic algorithms change the data, not the container.
  - Mutating algorithms don't change the container's size.
  - Avoid the mutating-algorithm trap.
This page last modified on 17 November 2003.