C++ Standard Algorithm Libraries and Usage Examples

E81 CSE 428S: Multi-Paradigm Programming in C++ Standard Generic Algorithms Department of Computer Science & Engineering Washington University, St. Louis MO Chris Gill cdgill@wustl.edu 1

The C++ Standard Algorithm Libraries A collection of generic algorithms Applicable to a wide range of 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 it

Organization of the 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_product

Example Using Non-Modifying Algorithms count algorithm Moves through iterator range Checks each position for equality Increases count if equal v.push_back(3); v.push_back(2); #include <iostream> #include <vector> #include <algorithm> using namespace std; int main (int, char * []) { vector<int> v; v.push_back(1); v.push_back(2); int i = 7; cout << i << " appears " << count(v.begin(), v.end(), i) << " times in v" << endl; /* output is 7 appears 0 times in v 2 appears 2 times in v */ i = 2; cout << i << " appears " << count(v.begin(), v.end(), i) << " times in v" << endl; return 0; }

Example 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); #include <iostream> #include <string> #include <fstream> #include <iterator> #include <algorithm> cout << "copied input file: " << input_file_name << endl << " to output file: " << output_file_name << endl; return 0; } using namespace std; /* output: cdgill@hive> ./copytest Makefile Makefile2 copied input file: Makefile to output file: Makefile2 cdgill@hive> diff Makefile Makefile2 cdgill@hive> */ int main (int argc, char * argv[]) { if (argc != 3) {return 1;} string input_file_name (argv[1]); string output_file_name (argv[2]);

Example 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 sort (s.begin(), s.end()); cout << "sorted: " << s << endl; #include <iostream> #include <string> #include <algorithm> using namespace std; int main (int, char * []) { string s = "asdf"; cout << "original: " << s << endl; string t (s); cout << "permutations:" << endl; /* output is original: asdf sorted: adfs permutations: adsf afds afsd asdf asfd dafs dasf dfas dfsa dsaf dsfa fads fasd fdas fdsa fsad fsda sadf safd sdaf sdfa sfad sfda adfs */ do { next_permutation (s.begin(), s.end()); cout << s << " "; } while (s != t); cout << endl; return 0; }

Example 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 cout << "the sum of the elements in v is " << accumulate (v.begin(), v.end(), 0) << endl; cout << "the inner product of v and itself is " << inner_product (v.begin(), v.end(), v.begin(), 0) << endl; the sum of the elements in v is 8 the inner product of v and itself is 18 */ #include <iostream> #include <vector> #include <numeric> 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); cout << "v contains "; for (size_t s = 0; s < v.size(); ++s) { cout << v[s] << " "; } cout << endl; /* output is: v contains 1 2 3 2 return 0; }

Concluding Remarks C++ standard libraries offer useful, generic algorithms They combine easily with different containers and iterators They support many common coding tasks including finding and modifying values, re-ordering elements, and performing numeric operations over different ranges of elements Using (and reusing) them lets you write less code, which is both efficient and potentially less error-prone Many STL algorithms can be extended further Especially by plugging variables of callable types into them But also through specialization for particular iterator types, etc.

No Studio Exercises Assigned Today Studios 12 through 19 are due 11:59pm Wednesday November 29th (the night before Exam 1) Submit as soon as each is done so you get feedback and so you can resubmit any of them that may have been marked incomplete before the deadline CSE 428S Multi-Paradigm Programming in C++ 9