Lecture Notes for CS 509

8 October 2002 - 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.

• 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 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 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.

• 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 either produce the wrong results, or do something terrible (run infinitely, often).

  • This is, of course, all done silently (assuming it doesn't explode).

• The definition of the order predicate less() is not obvious.

  • less() must be a trichotomy.

  • < is a trichotomy, <= is not.

  • Using a non-trichotomous order predicate produces incorrect or unpleasant results.

  • Trichotomy:

    If both a < b and b < b are false
    then (a == b).

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.

• Example:

  • Before:

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

  • After:

    std::transform(str.begin(), str.end(), str.begin(), std::tolower);
    

Generic Algorithms vs. Member Functions

• Some containers duplicate function provided by generic algorithms.

  • std::copy(v1.begin(), v1.end(), v2.begin())

  • v2.assign(v1.begin(), v2.end())

  • v2.insert(v2.end(), v1.begin(), v1,end())

• Favor member functions over generic algorithms.

  • Less typing, non template.

  • Member functions provide better behaving function.

    • 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 16 October 2002.