Lecture Notes for CS 509

21 February 2002 - Introduction to Generic Algorithms

1. generic algorithms

   1. "generic" means the algorithms can be applied to any type of container

   2. because C++ arrays are considered an stl container, you can apply these algorithms to arrays, ignoring the rest of the stl

   3. because you can easily 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

   4. but - I lied - not all containers can be used for with algorithms

   5. containers, iterators, and generic algorithms

2. why use them

   1. they're already there - tested, debugged, and optimized

   2. a common vocabulary of functions - use std:: to make it clear

   3. simplifies your code

3. kinds of generic algorithms

   1. non-mutating algorithms - don't change the containers; find()

      1. generalized numeric algorithms - compute values over containers

   2. mutating algorithms - change the containers; random_shuffle()

      1. sorting-related algorithms

4. non-mutating algorithms - don't change containers or their contents

   1. vp = find(start, end, v) - search the container delimited by start and end for the value v; return a reference to the value in the container if found, or else return end

      char str1[13] = "Hello World!";
      char *cp = find(&str1[0], &str1[12], 'o');
      cout << (cp == &str1[12] ? "didn't find it.\n" : "found it.\n");
      
      cp = find(&str1[0], &str1[12], 'x');
      cout << (cp == &str1[12] ? "didn't find it.\n" : "found it.\n");
      

   2. sp = search(start1, end1, start2, end2) - search the container delimited by start1 and end1 for the contents of the container delimited by start2 and end2; return a reference to the start of the match if found, or else return end1

      char str1[13] = "Hello World!";
      char pat[4] = "o W";
      char *cp = search(&str1[0], &str1[12], &pat[0], &pat[3]);
      cout << (cp == &str1[12] ? "didn't find it.\n" : "found it.\n");
      
      pat[2] = 'w';
      cp = search(&str1[0], &str1[12], &pat[0], &pat[3]);
      cout << (cp == &str1[12] ? "didn't find it.\n" : "found it.\n");
      

5. mutating algorithms - change the container, or its contents, or both

   1. copy(start1, end1, start2) - copy the contents of the container delimited by start1 and end1 to the container location start2

      char str1[13] = "Hello World!";
      char str2[13];
      copy(&str1[0], &str1[12], &str2[0]);
      cout << "str1 = " << str1 << ", str2 = " << str2 << ".\n";
      

   2. random_shuffle(start, end) - randomly shuffle the contents of the container delimited by start and end

      char str[13] = "Hello World!";
      cout << "str = \"" << str;
      random_shuffle(&str[0], &str[12]);
      cout << "\", str shuffled = \"" << str << "\".\n";
      

6. sorting-related algorithms - useful mutating algorithms

   1. sort(start, end) - sort the contents of the container delimited by start and end in ascending order by <

      char str[13] = "Hello World!";
      cout << "str = \"" << str;
      sort(&str[0], &str[12]);
      cout << "\", str sorted = \"" << str << "\".\n";
      

   2. end3 = set_union(start1, end1, start2, end2, start3) - form the set union of the contents of the container delimited by start1 and end1) and the contents of the container delimited by start2 and end2; store the union in the container starting at start3, and return a reference to the end of the union

      char a[] = "12a";
      char b[] = "abc";
      char c[7];
      char *end = set_union(&a[0], &a[3], &b[0], &b[3], &c[0]);
      *end = 0;
      cout << "the union of " << a << " and " << b << " is " << c << ".\n";
      

7. generalized numeric algorithms - non-mutating algorithms (accumulate, inner-product, partial_sum, and adjacent_difference)

   1. v = accumulate(start, end, i) - compute the sum of the container contents delimited by start and end, using i as the initial value of the sum; return the sum

      int ivals[] = {1, 2, 3};
      int sum = accumulate(&ivals[0], &ivals[3], 0);
      cout << "the sum is " << sum << ".\n";
      

   2. the generalized numeric algorithms are powerful, but they require some change of thinking to exploit their full power

8. naming conventions

   1. the _if convention - distinguishes value-predicate algorithms; find()-find_if() vs. equal/3-equal/4

   2. the _copy convention - indicates non-mutating mutating algorithms; reverse() and reverse_copy()

This page last modified on 21 February 2002.