The C++ Algorithm LibrariesMotivating Example: Searching a StringImproving Linear Search with RangesLinear Search over Parameterized TypesLinear Search with Generic IteratorsOrganization of C++ Algorithm LibrariesExample of Using Non-Modifying AlgorithmsExample of Using Mutating AlgorithmsExample of Using Sorting AlgorithmsExample of Using Numeric AlgorithmsConcluding RemarksCSE 332: C++ Algorithms IThe C++ Algorithm Libraries•A standard collection of generic algorithms–Applicable to various types and containers•E.g., sorting integers (int) vs. intervals (pair<int, int>)•E.g., sorting elements in a vector vs. in a C-style array–Polymorphic even without inheritance relationships•Types substituted need not have a common base class•Must only provide the operators the algorithm needs•Significantly used with the sequence containers–To reorder elements within a container’s sequence–To store/fetch values into/from a container–To calculate various values and properties from itCSE 332: C++ Algorithms IMotivating Example: Searching a String•From Austern: “Generic Programming and the STL”•Sequential (linear) search: find char c in string s char * strchr (char* s, char c){ while (*s != 0 && *s != c){++s; } return *s == c ? s : (char *) 0; }•Problem: not very general–“Range” of iteration is always defined up to ‘\0’ character–Only works for a “zero terminated” string in C/C++CSE 332: C++ Algorithms IImproving Linear Search with Ranges•First generalization (Austern, pp. 11): use a range (something that sequential containers can give us!)char * find1 (char* first, char* last, char c){ while (first != last && *first != c) ++first; return first;}•Gives an explicit range (calculate its length – how?)•Assumes first is before last (can check – how?)•Note how caller checks for success changed: why?CSE 332: C++ Algorithms ILinear Search over Parameterized Types•Second generalization: use templates to parameterize the function argument typestemplate <typename T> T * find2(T * first, T * last, const T & value){ while (first != last && *first != value)++first; return first;}•How much did the find1 code need to change?•One last problem–What if we want to apply this to a container (e.g., list) whose range can’t be traversed via simple pointers?CSE 332: C++ Algorithms ILinear Search with Generic Iterators•Third generalization: separate iterator type parameter•We arrive at the find algorithm (Austern pp. 13): template <typename Iterator, typename T>Iterator find (Iterator first, Iterator last, const T & value) { while (first != last && *first != value) ++first; return first;}•Notice how algorithm depends on the iterators•Notice how refinements made algorithm more abstract–… but still essentially does the same thing–i.e., algorithm structure (and time complexity) is the sameCSE 332: C++ Algorithms IOrganization of C++ Algorithm Libraries•The <algorithm> header file contains–Non-modifying sequence operations•Do some calculation but don’t change sequence itself•Examples include count, count_if–Mutating sequence operations•Modify the order or values of the sequence elements•Examples include copy, random_shuffle–Sorting and related operations•Modify the order in which elements appear in a sequence•Examples include sort, next_permutation•The <numeric> header file contains–General numeric operations•Scalar and matrix algebra, especially used with vector<T>•Examples include accumulate, inner_productCSE 332: C++ Algorithms IExample of Using Non-Modifying Algorithms •count algorithm–Moves through iterator range–Checks each position for equality–Increases count if equal#include <iostream>#include <vector>#include <algorithm>using namespace std;int main (int, char * []) { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(2); int i = 7; cout << i << " appears " << count(v.begin(), v.end(), i) << " times in v" << endl; i = 2; cout << i << " appears " << count(v.begin(), v.end(), i) << " times in v" << endl; return 0;}/* output is7 appears 0 times in v2 appears 2 times in v */CSE 332: C++ Algorithms IExample of Using Mutating Algorithms•copy algorithm–Copies from an input iterator range into an output iterator–Note use of default constructor to get an “off-the-end” (here, “end-of-file”) input iterator–Note use of noskipws (need to make sure container behavior matches what you want to do) ifstream input_file (input_file_name.c_str()); ofstream output_file (output_file_name.c_str()); input_file >> noskipws; istream_iterator<char> i (input_file); ostream_iterator<char> o (output_file); copy (i, istream_iterator<char>(), o); cout << "copied input file: " << input_file_name << endl << " to output file: " << output_file_name << endl; return 0;}/* output:cdgill@hive> ./copytest Makefile Makefile2copied input file: Makefile to output file: Makefile2cdgill@hive> diff Makefile Makefile2cdgill@hive> */#include <iostream>#include <string>#include <fstream>#include <iterator>#include <algorithm>using namespace std;int main (int argc, char * argv[]) { if (argc != 3) {return 1;} string input_file_name (argv[1]); string output_file_name (argv[2]);CSE 332: C++ Algorithms IExample of Using Sorting Algorithms•sort algorithm–Reorders a given range–Can also plug in a functor to change the ordering function•next_permutation algorithm–Generates a specific kind of reordering, called a “permutation”–Can use to generate all possible orders of a given sequence#include <iostream>#include <string>#include <algorithm>using namespace std;int main (int, char * []) { string s = "asdf"; cout << "original: " << s << endl; sort (s.begin(), s.end()); cout << "sorted: " << s << endl; string t (s); cout << "permutations:" << endl; do { next_permutation (s.begin(), s.end()); cout << s << " "; } while (s != t); cout << endl; return 0;}/* output isoriginal: asdfsorted: adfspermutations:adsf afds afsd asdf asfddafs dasf dfas dfsa dsaf dsfa fads fasd fdas fdsa fsad fsda sadf safd sdaf sdfa sfad sfda adfs */CSE 332: C++ Algorithms IExample of Using Numeric Algorithms•accumulate algorithm–Sums up elements in a range (based on a starting sum value)•inner_product algorithm–Computes the inner (also known as “dot”) product of two matrixes: sum of the products of their respective elements#include <iostream>#include