Ch. 11 STL Algorithms

11.2 Algorithm Overview

Non-modifying Algorithms

find()  // Searches for 1st elt with passed value   pg. 528
find()  // string function, find first occurrence of one elt
rfind() // string function, last occurence of one elt
        STL: find() w/ reverse iterators
search_n() // STL: first occurrence of n consecutive elts

Modifying Algorithms

copy() // copies a range starting w/ 1st elt    pg. 557
copy_n()  // copies n elts
copy_backward()  // copies a range starting with last elt   pg. 561
move()  // moves elts of a range starting with 1st elt    pg. 557
merge()  // merge 2 ranges           pg. 614
iota()   // replaces each elt with a sequence of incremented values    pg. 571
swap()??// I added this, should be O(1)

Removing Algorithms

remove()   // removes elts with given value

Mutating Algorithms

reverse()  // reverses the order of the elts
reverse_copy()   // copies the elts while reversing their order
partition()    // changes the order of the elts so that elts that match a criterion are at the front
stable_partition()  // partition() but stable

Sorting Algorithms

STL Sorting Algorithms

SORT
sort(coll.begin(), coll.end());
    // based on quicksort  n log n, or n^2
PARTIAL_SORT
partial_sort(coll.begin(), coll.end(), coll.end());
    // based on heapsort, better complexity in theory, but slower runtime in practice
    // never reaches quadratic complexity, always n log n
STABLE_SORT
stable_sort(coll.begin(), coll.end());
    // based on mergesort
    // n log n, or n log n log n
    // STABLE: preserves the order of equal elements

• sort() uses introsort: operates like quicksort, but switches to heapsort when it is in worse-case condition
• You can always pass the sorting criterion to all sorting algorithms as an optional argument
  • The default sorting argument is functor less<>, sorting elts in ascending order according to their values
  • Sorting criterion has to be strict weak ordering: < or >, no >= or <= allowed
• Lists and forward lists have member function sort() to sort elts, but no sorting algorithms for either

STL Heap Algorithms

MAKE HEAP
make_heap(coll.begin(), coll.end());
    // n + n log n 
    // makes a heap from a begin and end iterator
SORT_HEAP
sort_heap(coll.begin(), coll.end());
    // n + n log n
    // sorts a heap given a begin and end iterator

STL nth Element Algorithms

NTH ELEMENT
nth_element(coll.begin(),     // beginning of range
            coll.begin() + 3, // position between 1st and 2nd part
            coll.end());      // end of range
PARTITION
partition(coll1.begin(), 
          coll1.end(),   // range
          [] (int elt) {  // criterion
                 return elt<7;   // action
             }
          );
STABLE PARTITION
stable_partition(...)
// same as partition(...), but guarantees stability

Sorted Ranges