From Last Time: Search with Generic IteratorsKey Ideas: Concepts and ModelsConcepts and Models, ContinuedMatching an Algorithm to the Iterators it NeedsIterator Concept HierarchyWhat if an Algorithm Has Alternative Versions?Iterator Traits and Category Type TagsCan Extend STL Algorithms with Callable ObjectsCallable Objects and AdaptersUsing Functions with an AlgorithmUsing Function Objects with an AlgorithmConcluding RemarksCSE 332: C++ Algorithms IIFrom Last Time: 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;}•Which kinds of iterators will work with this algorithm?•How can we determine that from the algorithm itself?CSE 332: C++ Algorithms IIKey Ideas: Concepts and Models•A concept gives a set of type requirements–Classify/categorize types (e.g., random access iterators)–Tells whether or not a type can or cannot be used with a particular algorithm (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 array iterator)•No inheritance-based relationship between them •But both model iterator concept necessary for findCSE 332: C++ Algorithms IIConcepts 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;}CSE 332: C++ Algorithms IIMatching an Algorithm to the Iterators it NeedsCategory/ OperationOutput Input Forward BidirectionalRandomAccessRead=*p(r-value)=*p(r-value)=*p(r-value)=*p(r-value)Access-> -> ->->[]Write*p=(l-value)*p=(l-value)*p=(l-value)*p=(l-value)Iteration++ ++ ++ ++ --++ -- + - += -=Comparison== != == != == !=== != < > <= >=What STL iterator category does find require?CSE 332: C++ Algorithms IIIterator Concept HierarchyInput Iterator Output IteratorForward IteratorBidirectional IteratorRandom Access Iterator•value persists after read/write•values have locations•can express distance between two iterators•read or write a value (one-shot)Singly-inked-list style access (forward_list)Bi-linked-list style access (list)Array/buffer style access (vector, deque)“destructive” read at head of stream (istream)“transient” write to stream (ostream)is-a (refines)CSE 332: C++ Algorithms IIWhat if an Algorithm Has Alternative Versions?•Static dispatching–Implementations provide different signatures–Iterator type is evaluated at compile-time–Links to the best implementation•Notice how type tags are used// Based on Austern, pp. 38, 39template <class Iter, class Distance> void move (Iter i, Distance d, fwd) { while (d>0) {--d; ++i;} // O(d)}template <class Iter, class Distance> void move (Iter i, Distance d, rand) { i += d; // O(1)}template <class Iter, class Distance> void move (Iter i, Distance d) { move (i, d, iterator_traits<Iter>::iterator_category() )}concrete tag (empty struct) typedefault constructor (call syntax)concrete tag (empty struct) typeCSE 332: C++ Algorithms IIIterator Traits and Category Type Tags•Need a few concrete types to use as tags–E.g., empty structs–E.g., input, output, fwd, bidir, and rand •Tags provide yet another associated type for iterators–Iterator category–Again, made available by using the traits idiomstruct input {}; // empty structs for type tagsstruct output {};struct fwd : public input {}; // note inheritancestruct bidir : public fwd {};struct rand : public bidir {}; template <typename I> struct iterator_traits { ... typedef typename I::iterator_category iterator_category;};template <typename T> struct iterator_traits<T*> { ... typedef rand iterator_category;};template <typename T>struct iterator_traits<const T*> { ... typedef rand iterator_category;};(actually, random_access_iterator_tag)CSE 332: C++ Algorithms IICan Extend STL Algorithms with Callable Objects•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 rangeCSE 332: C++ Algorithms IICallable Objects and Adapters•Callable objects support function call syntax–A function or function pointer bool (*PF) (const string &, const string &); // function pointer bool string_func (const string &, const string &); // function–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 bind and _1 _2 _3 etc.–E.g., wrap a member function using mem_fn–E.g., wrap callable object with function (associates types)CSE 332: C++ Algorithms IIUsing Functions with an Algorithm#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_; };