Generic Algorithms in C++: Evolution from Linear Search
This content elaborates on the evolution of linear search in C++, showcasing improvements from sequential search to utilizing ranges, templates, and generic iterators for more versatile and efficient algorithm design. Explore the transformation of the search functionality, empowering programmers with enhanced flexibility and generality.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
E81 CSE 428S: Multi-Paradigm Programming in C++ Generic Algorithms Department of Computer Science & Engineering Washington University, St. Louis MO Chris Gill cdgill@wustl.edu 1
Motivating Example: Searching a String From Matt Austern, Generic Programming and the STL 1st Edition, Addison-Wesley 1999 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++
Improving Linear Search with Ranges First generalization (Austern, pp. 11): use a range (something that sequential containers give us!) char * find1 (char* first, char* last, char c){ while (first != last && *first != c) ++first; return first; } Assumes first is before last (can check how?) Gives an explicit range (can calculate length how?) How caller checks for success has changed - why?
Linear Search over Parameterized Types Second generalization (again from Austern): use templates to parameterize the function argument types template <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 ranges can t be traversed via simple pointers?
Linear Search with Generic Iterators Third generalization: use a separate iterator type parameter in the template 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 the algorithm depends on the iterators Notice how the refinements made it more abstract but it still essentially does the same thing i.e., algorithm structure (and time complexity) is the same
Key Ideas: Concepts and Models A concept collects a set of type requirements Classifies/categorizes types (e.g., random access iterators) Tells whether or not a type can be used with a particular algorithm (you will get a compiler error if it cannot) E.g., in the examples from last time, we could not use a linked list iterator in find1 or even find2, but we can use one in find Any specific type that meets the requirements is a model of that concept E.g., list<char>::iterator vs. char *in find Different abstractions (bi-linked list iterator vs. char pointer) No inheritance-based relationships are necessary But both model iterator concept necessary for find
Concepts and Models, Continued What very basic concept does the last statement of find, (the line return first;) assume? Asked another way, what must be able to happen to first when it s returned from function find? Same requirement imposed by by-value iterator parameters What other capabilities are required of the Iterator and T type parameters by the STL find algorithm ? template <typename Iterator, typename T> Iterator find (Iterator first, Iterator last, const T & value) { while (first != last && *first != value) ++first; return first; }
Match Algorithm to the Iterators it Needs Random Access Category/ Operation Output Input Forward Bidirectional =*p (r-value) =*p (r-value) =*p (r-value) =*p (r-value) Read -> [] Access -> -> -> *p= (l-value) *p= (l-value) *p= (l-value) *p= (l-value) Write ++ -- + - += -= Iteration ++ ++ ++ ++ -- == != < > <= >= Comparison == != == != == != What STL iterator category does findrequire?
Iterator Concept Hierarchy transient write to stream (ostream) destructive read at head of stream (istream) read or write a value (one-shot) Input Iterator Output Iterator is-a (refines) Singly-inked-list style access (forward_list) value persists after read/write values have locations can express distance between random access iterators Forward Iterator is-a (refines) Bi-linked-list style access (list) Bidirectional Iterator is-a (refines) Array/buffer style access (vector, deque) Random Access Iterator
What if Algorithm Has Multiple Versions? // Based on Austern, pp. 38, 39 template <class Iter, class Distance> void jump (Iter i, Distance d, fwd) { while (d>0) {--d; ++i;} // O(d) } concrete tag (empty struct type) Static dispatching Implementations provide different signatures Iterator type is evaluated at compile-time Links to the best implementation template <class Iter, class Distance> void jump (Iter i, Distance d, rand) { i += d; // O(1) } concrete tag (empty struct type) Notice how type tags are used template <class Iter, class Distance> void jump (Iter i, Distance d) { jump (i, d, iterator_traits<Iter>:: iterator_category() ) } default constructor (explicit call syntax)
Iterator Traits and Category Type Tags struct input {}; // empty structs for type tags struct output {}; struct fwd : public input {}; // note inheritance struct bidir : public fwd {}; struct rand : public bidir {}; (actually, random_access_iterator_tag) Need a few concrete types to use as tags Use empty structs E.g., input, output, fwd, bidir, and rand template <typename I> struct iterator_traits { ... typedef typename I::iterator_category iterator_category; }; Tags provide yet another associated type for iterators Iterator category Made available by using the traits idiom template <typename T> struct iterator_traits<T*> { ... typedef rand iterator_category; }; template <typename T> struct iterator_traits<const T*> { ... typedef rand iterator_category; };
Extend STL Algorithms with Callable Types Make the algorithms even more general Can be used parameterize policy E.g., the order produced by a sorting algorithm E.g., the order maintained by an associative containe Each callable object does a single, specific operation E.g., returns true if first value is less than second value Algorithms often have overloaded versions E.g., sort that takes two iterators (uses operator<) E.g., sort that takes two iterators and a binary predicate, uses the binary predicate to compare elements in range
Callable Types and Adapters Callable types support function call syntax A function or function pointer bool (*PF) (const string &, const string &); // func ptr bool string_func (const string &, const string &); // func A struct or class providing an overloaded operator() struct strings_ok { bool operator() (const string &s, const string &t) { return (s != quit ) && (t != quit ); } }; A lambda expression (unnamed inline function) [quit_string] (const string &s, const string &t) -> bool {return (s != quit_string) && (t != quit_string);} Adapters further extend callable objects E.g., bind any argument using bindand _1 _2 _3etc. E.g., wrap a member function using mem_fn E.g., wrap callable object with functiontemplate
Using Functions with an Algorithm heap object #include <iostream> #include <vector> #include <string> #include <iterator> #include <algorithm> using namespace std; struct Employee { Employee (const char * n, int i) : name_(n), id_(i) {} string name_; int id_; }; typedef Employee * EmployeePtr; ostream& operator<< (ostream & os, const EmployeePtr & e) { os << e->name_ << " " << e->id_ << " "; return os; } // function for comparing EmployeePtrs bool id_compare (const EmployeePtr & e, const EmployeePtr & f) { return e->id_< f->id_|| (e->id_ == f->id_ && e->name_ < f->name_); } delete *i; } return 0; } int main (int, char *[]) { vector<EmployeePtr> v; v.push_back(new Employee("Claire", 23451)); v.push_back(new Employee("Bob", 12345)); v.push_back(new Employee("Alice", 54321)); cout << "v: " ; copy (v.begin(), v.end(), ostream_iterator<EmployeePtr>(cout)); cout << endl; // "v: Claire 23451 Bob 12345 Alice 54321 " sort (v.begin(), v.end(), id_compare); cout << "v: " ; copy (v.begin(), v.end(), ostream_iterator<EmployeePtr>(cout)); cout << endl; // "v: Bob 12345 Claire 23451 Alice 54321 " // clean up: pointers "own" the heap objects for (vector<EmployeePtr>::iterator i = v.begin(); i != v.end(); ++i) { pass function name
Using Function Objects with an Algorithm count_if algorithm Generalizes the count algorithm Instead of comparing for equality to a value Applies a given predicate function object (functor) If functor s result is true, increases count v.push_back(3); v.push_back(2); #include <iostream> #include <vector> #include <algorithm> using namespace std; template <typename T> // covers many types struct odd { bool operator() (T t) const { return (t % 2) != 0; } }; int main (int, char * []) { vector<int> v; v.push_back(1); v.push_back(2); cout << "there are " << count_if(v.begin(), v.end(), odd<int>()) << " odd numbers in v" << endl; /* output is there are 2 odd numbers in v */ return 0; }
Concluding Remarks STL algorithms give you useful, generic functions Combine easily with a variety of containers/iterators Support many common data structure manipulations Finding and modifying values, re-ordering, numeric operations Reusing them saves you from writing/debugging code Many STL algorithms can be extended Especially by plugging callable objects (functors) into them C++11 lambdas & the bind function give new ways to do that Think about how iterators and algorithms combine Think about which category of iterator a container provides Think about the concept each iterator models Think about the type requirements an algorithm imposes Think about which combinations are valid, accordingly
Studio 18 Looks at how different algorithms can be applied to iterators over ranges in different containers Considers how pointers to array elements and iterators over random access sequential containers support similar behavior of algorithms Explores how algorithms can be made more general by passing in callable types that change how some of their operations are performed Studios 12 through 19 are due 11:59pm Wednesday November 29th (night before Exam 1) Submit as soon as each is done so you get feedback and can resubmit any that may be marked incomplete CSE 428S Multi-Paradigm Programming in C++ 17
