1. mutating generic algorithms, sorting related

   1. generic algorithms that either sort or rely on sorted containers

   2. the sorting order

      1. a Compare functional parameter determines sorting order

      2. exactly one of Compare(v1, v2), Compare(v2, v1), or v2 == v1 must be true for any v1 and v2 - tricotomy

      3. < is acceptable, <= is not

      4. the default is <

   3. sorts - stable, partial, and nth value

      1. a stable sort preserves order among equal values

      2. a partial sort only sorts part of the container - sort the first n

      3. an nth-value sort only sorts until the nth value is known - median

   4. binary search, lower bound, upper bound, equal range

      1. binary search - a faster search than find()

      2. lower bound - the first (leftmost) value of a span of equal values

      3. upper bound - the first (leftmost) value after a span of equal values

      4. equal range - the pair (lower bound, upper bound)

   5. merge - combine sorted sequences into a sorted sequence

   6. other amusements

      1. heap algorithms - not related to dynamic storage

      2. minimum and maximum

      3. lexicographical comparison

      4. permutations

   7. set operations

      1. includes(b1, e1, b2, e2) returns true if and only if every value in the iterator range (b2, e2) is also in the iterator range (b1, e1) - the subset predicate

      2. set_union(b1, e1, b2, e2, i) stores into the container referenced by iterator i the values that appear either in iterator range (b1, e1) or iterator range (b2, e2)

         1. returns an iterator to the value one past the end of the new range

         2. the new range is sorted

         3. identical values in each set are merged into one value in the union set - multiset union contains the larger number of values between the two sets

      3. set_intersection(b1, e1, b2, e2, i) stores into the container referenced by iterator i the values that appear both in iterator range (b1, e1) and iterator range (b2, e2)

         1. returns an iterator to the value one past the end of the new range

         2. the new range is sorted

         3. multiset intersection contains the smaller number of values between the two sets

      4. set_difference(b1, e1, b2, e2, i) stores into the container referenced by iterator i the values that appear in iterator range (b1, e1) but not in iterator range (b2, e2)

      5. set_symmetric_difference(b1, e1, b2, e2, i) stores into the container referenced by iterator i the values that appear in either iterator range (b1, e1) or iterator range (b2, e2) but not in both

2. generalized numeric algorithms

   1. accumulate(b, e, v, f)

      1. given the sequence of values v₁, v₂, ..., v_n defined by the iterator range b,e, compute the value f(...f(f(v, v1), v2), ..., vn)

      2. f defaults to plus, computing v + v1 + v2 + ... + vn

      3. example - unparsing words back into a sentence

         1. #include <string>
            #include <vector>
            #include <numeric>
            
            static string concat(const string str1, const string str2) {
              return str1 + (str1.length() == 0 ? "" : " ") + str2;
              }
            
            int main(void) {
              string words[] = {"time", "flies", "like", "an", "arrow"};
              vector<string> wordv(words, words + 5);
              cout << accumulate(wordv.begin(), wordv.end(), string(""), concat) 
                   << "\n";
              return 0;
              }
            

   2. partial_sum(b, e, v, f)

   3. adjacent_difference(b, e, i, f)

   4. inner_product(b1, e1, b2, v, f1, f2)

      1. let the iterator range (b1, e1) be represented by the sequence of values v₁, v₂, ..., v_n f(...f(f(v, v1), v2), ..., vn)

      2. let the corresponding iterator range (b1, e1) be represented by the sequence of values v₁, v₂, ..., v_n f(...f(f(v, v1), v2), ..., vn)

      3. f defaults to plus, computing v + v1 + v2 + ... + vn

      4. example - combining two lists of values into a single list of paired values

         1. #include <string>
            #include <numeric>
            #include <list>
            
            typedef pair<string, int> grade;
            
            static grade pair_them(string & s, int i) {
              return grade(s, i);
              }
            
            static list<grade> append_them(list<grade> l, grade g) {
              l.push_back(g);
              return l;
              }
            
            int main(void) {
              string names[] = {"clinton", "bush", "regan", "carter"};
              int numbers[] = {11, 12, 13, 14};
              list<grade> roster;
              roster =
                inner_product(names, names + 4, numbers, roster, append_them, pair_them);
              for (list<grade>::iterator i = roster.begin(); i != roster.end(); i++)
                cout << (*i).first << " " << (*i).second << "\n";
            
              return 0;
              }
            

This page last modified on 21 July 2000.