Lecture Notes for SE 598, Data Structures and Algorithms

16 August 2000 - STL Adaptors for Containers, Functions, and Iterators

1. iterator adaptors

   1. reverse iterators

      1. behave backwards from iterators - ++ moves one to the left

      2. don't program with reverse iterators - use generics

      3. pass to generic algorithms to change the meaning - ascending or descending sort

   2. stream iterators

      1. turn io-streams into iterators

      2. output iterators

         1. ostream_iterator<T>(ostream, sep) - T::operator <<() must be defined

         2. no default constructor

      3. input iterators

         1. istream_iterator<T>(istream) - T::operator >>() must be defined

         2. istream_iterator<T>() - default constructor; eof

   3. insert iterators

      1. what good are input stream iterators

         1. copy(istream_iterator<T>(istream), istream_iterator<T>(), tvec.end()) doesn't work

      2. what good are the generic algorithms for set operations?

      3. insert iterator adaptors turn iterator references into calls to insert operations

      4. back insert iterators

         1. an output iterator - l-side * and ++

         2. back_insert_iterator(C) creates an back-insert iterator for container C

         3. *back_insert_iterator(C) = v is equivalent to C.push_back(v)

         4. copy(istream_iterator(cin),
                 istream_iterator(), 
                 back_insert_iterator(svec));
            

         5. the container C must have the push_back() member function

      5. front insert iterators

         1. an output iterator

         2. front_insert_iterator(C) creates an front-insert iterator for container C

         3. *back_insert_iterator(C) = v is equivalent to C.push_front(v)

         4. copy(istream_iterator(cin),
                 istream_iterator(), 
                 front_insert_iterator(svec));
            

         5. the container C must have the push_front() member function

      6. insert iterators

         1. an output iterator

         2. front_insert_iterator(C, i) creates a insert iterator for container C starting at the iterator i

         3. *insert_iterator(C, i) = v is equivalent to i = C.insert(v, i)

         4. copy(istream_iterator(cin),
                 istream_iterator(), 
                 insert_iterator(svec, svec.end()));
            

         5. the container C must have the insert() member function

2. function adaptors

   1. function objects

      1. class operators - <, =, and so on

      2. the function call operator () can also be defined for a class.

         1. class callable {
              public:
                void operator()() { . . . }
              };
            
            int f() {
              callable c;
              c();
              }
            

      3. analagous to function pointers

      4. many amusing properties

         1. compile-time entities - no run-time overhead as with function pointers; can be in-lined

         2. enclosed scope makes side-effecting functions cleaner to write

         3. class nesting makes for a neater name space

         4. STL function adaptors work with callable classes, not function pointers

   2. converting function pointers to callable objects

      1. template<class Arg,class Result>ptr_fun(Result (*x) (Arg)) - converts x, a pointer to a unary function, into a callable function object

         1. example: ptr_fun(isalnum)

      2. template<class Arg1,class Arg2,class Result>ptr_fun(Result (*x) (Arg1, Arg2)) - converts x, a pointer to a binary function, into a callable function object

         1. example: ptr_fun(index)

   3. negating a predicate

      1. not1 inverts the sense of a unary predicate

         1. example - not1(ptr_fun(isalnum))

   4. not2 inverts the sense of a binary predicate

      1. example - not2(less<string>)

3. converting binary to unary functions

   1. many generic algorithms take only unary functions, which can be a pain

      1. example - find_if() accepts a unary prediate

   2. turn a binary function into a unary function by supplying an argument

   3. bind1st(callable_object, first_argument) - returns a unary callable object

      1. example - look for white space in a string

      2. char * msg = "hello world!";
         char * cp = find_if(msg, msg + strlen(msg), bind1st(ptr_fun(index), " \t\n"));
         

   4. bind1st(callable_object, first_argument) - returns a unary callable object

      1. example - find a command line argument containing an exclamation point

      2. char ** cp = find_if(argv, argv + argc, bind2nd(ptr_fun(index), '!'));