Public static void: 4. Iterators and functionobjects

Container classes, Iterators, Function objects and their algorithms

First class containers and adapter classes

Container classes are another word for builtin abstract datatypes. They live in the C++ Standard Template Library (STL). When we talk about sequential container classes we talk about vector, deque (double ended queue) and list.

template <class T> class vector
template <class T> class deque
template <class T> class list

And then we have the asscociative container classes map, multimap, set and multiset. The difference between the two classes map and set and their corresponding multi-counterparts is that in the single case, a stored key must be unique and in their multi-counterpart the class can store the same key multiple times.

template <class Key, class T, class Cmp=less<Key> > class map
template <class Key, class T, class Cmp=less<Key> > class multimap
template <class T, class Cmp=less<T> > class set
template <class T, class Cmp=less<T> > class multiset

These classes are all builtin template classes and can therefore be instantiated with different class types, they are therefore referred to as container classes. For example vector can be instantiated like:

vector<int> intvec;
vector<Person> persvec;                
// Assuming we have a Person class

And a set can be instantiated like:

set<string, int> set1;                 
// sorted by ascending alphabetic keys
set<string, greater<key> > set2;       
// sorted by descending alphabetic keys

And map:

map<string, int> map1;                 
// sorted by ascending key
map<string, int, greater<key> > map2;  
// sorted by descending key

They all represent data in different ways, why they have different methods for access and modification.
Then lastly we have the container adaptors. They are constructed by using one of the sequential containers (vector or deque) and adapting its interface to provide the desired behaviour.

template <class T, class Container = deque<T> > class stack
template <class T, class Container = deque<T> > class queue
template <class T, class Container = vector<T>, class Cmp=less<T> > class priority_queue

The Container type deque and vector are only default for the adaptors and if you want to change the underlying container type, you can.

Iterators and Functionsobjects

Iterators

The concept of an iterator is fundamental to understanding the C++ Standard Template Library (STL) because iterators provide a means for accessing data stored in container classes such a vector, map and list. Since all containers have different representations C++ provides iterators for all the container classes that act as pointers do when used together with arrays. You should know by now that you instead of using array[3] can use *(array+3) and iterate through an array using the idiom array++ and array--. This functionality is what iterators provide for all the containerclasses. You use iterators the same way you use pointers to an a array when iterating over it.
All containers supports the function called begin(), which will return an iterator pointing to the beginning of the container (the first element), and the function end(), that returns an iterator corresponding to having reached the end of the container. You access the element by "dereferencing" the iterator with a *, just as you would dereference a pointer. In fact, because of the similarities between pointers to arrays and iterators you can use pointers to arrays in the same functions that require an iterator to a collection.
Example usage of an iterator over vector:

using namespace std;

vector<int> myIntVector;
vector<int>::iterator myIntVectorIterator;  // Declare the iterator

// Add some elements to myIntVector
myIntVector.push_back(1);
myIntVector.push_back(4);
myIntVector.push_back(8);

for(myIntVectorIterator = myIntVector.begin(); 
    myIntVectorIterator != myIntVector.end();
    myIntVectorIterator++)
{
    cout<<*myIntVectorIterator<<" ";
    //Should output 1 4 8
}

Example usage of an iterator over map:

#include <iostream>
#include <map>
#include <algorithm>
#include <string>

int main()
{
  string word;
  map<string, int> wmap;

  // Add some word and increase the counter associated to it
  while (cin >> word) wmap[word]++;

  for( map<string,int>::iterator i=wmap.begin(); i!=wmap.end(); ++i)
    cout << i->first << " " << i->second << endl; // first=key, second=value

}

Many of the algorithms in the STL expect iterators as arguments. Here we use the function reverse from the STL.

vector<char> vec(string str)
{
    const char *s = str.c_str();              // returns a (char *) 
    vector<char> x;
    while (*s != '\0')
        x.push_back(*s++);                    // put the char at the end of the vector
    return x;
}

int main()
{
    vector<char> vector1 = vec("mark twain");
    reverse(vector1.begin(), vector1.end());  // reverse uses iterators
    for(int i=0; i<vector1.size(); i++) 
        cout << vector1[i];                   // outputs "niawt kram"
    cout << endl;
}

The function reverse requires iterator pointers to reverse the container, what ever it might be, and like we stated before, you could instead of using an container use an array with the same function that requires an iterator like reverse(array, array+7) if the array was of size 7, or reverse(array, array+4) if you only want to reverse the first 4 elements.
To end this section we illustrate the power of iterators when used together with streams. Here we introduce the isteam_iterator and the ostream_iterator.

#include <iostream>
#include <fstream>
#include <list>
#include <vector>

#include <algorithm>

class BookEntry {
private:
  char name[32]; // let's skip dynamic allocation for once
  int num;
public:
  BookEntry() { strcpy(name,""); num = 0; }
  BookEntry( char *nam, int nu ) : num(nu) { strcpy(name,nam); }
  const int number() const { return num; }

  friend ostream& operator<<(ostream &os, const BookEntry &be )
    { return os << be.num << " " << be.name;  }

  friend istream& operator>>(istream &is, BookEntry &be )
    { return is >> be.num >> be.name; }
};

bool lessthan( const BookEntry &b1, const BookEntry &b2 )
{
  return b1.number() < b2.number();
}

int main()
{

  ifstream is1("book1");
  ifstream is2("book2");
  ofstream os("book1and2");

  istream_iterator<BookEntry> in1(is1);
  istream_iterator<BookEntry> in2(is2);
  ostream_iterator<BookEntry> out(os,"\n");
  istream_iterator<BookEntry> eofin;

  list<BookEntry> lbe( in1, eofin );
  vector<BookEntry> vbe( in2, eofin );
  sort( vbe.begin(), vbe.end(), lessthan );
  lbe.sort( lessthan );
  merge( lbe.begin(), lbe.end(), vbe.begin(), vbe.end(),
         out, lessthan);
}

So if book1 has the following content:

150919 Andersson
451209 Eriksson
560912 Johansson
401210 Karlsson
132816 Nordin
110111 Persson
331122 Svensson

And book:

567891 Alfredsson
120912 Edvardson
121212 Lundberg
119991 Nilsson
811111 Olsson
980912 Zaric

Then book1andbook2 will look like:

110111 Persson
119991 Nilsson
120912 Edvardson
121212 Lundberg
132816 Nordin
150919 Andersson
331122 Svensson
401210 Karlsson
451209 Eriksson
560912 Johansson
567891 Alfredsson
811111 Olsson
980912 Zaric

Functionobjects

Imagine we want to iterate through an vector of ints until we find an element greater than 4, and return a corresponding vector that starts with this value, so that if we give [1,2,3,4,5,6,7] we get [5,6,7]. For this we could use find_if that takes two iterators and a predicate (a function that returns either true or false given a certain input).

bool GreaterThan4( double v )
{
  return v > 4.0;
}

void myfunc( vector<double>& v )
{
  vector<double>::iterator f = find_if(v.begin(),v.end(), GreaterThan4);
  // do something with f
}

But what if we now want to find an element greater than 5 or 6. We would now need to write GreaterThan5 and GreaterThan6. This is what functionobjects alleviate us from. Functionobjects are objects whose classes have overloaded the ()-operator (the function call operator). Now when the object is called with the ()-operator it does something with its data or anything it wishes. This is sometimes more practical than passing a function to a function which you also can do, in a typical functional style.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

template <class T>
class GreaterThan {                                      // our function class
    public:
        GreaterThan( T cv ) : compValue ( cv ) {}        // set the value to compare with
        bool operator()( T v ) { return v > compValue; } // function call operator
    private:
        T compValue;
};

template <class T>
void myfunc( vector<T>& v, T val)
{
    GreaterThan<T> gt(val);                              // our function object
    typename vector<T>::iterator f = find_if(v.begin(), v.end(), gt);
    // do something
    cout << *f << endl;
}

int main()
{
    int arr[] = {1,2,3,4,5,5,6,7};
    vector<int> vec(arr, arr+7);
    myfunc<int>(vec, 4);
}

Algorithms

We have now seen the the power of algorithms such as find_if from the STL that takes iterators and functions/functionobjects as parameters. There are ofcourse many more algorithms that provides similar functionality for us to take advantage of. We will loke briefly at foreach that helps us do something "foreach" element in the container.

template <class In, class Function>
Function for_each (In first, In last, Function f)
{
    while (first != last) 
        f(*first++);
    return f;
}

You maye will find the class In and Function confusing. Function only implies that the function requires a class that has overloaded the ()-operator (a functionobject) or get passed a function (not a member function) to use over the elements. In specifies that the parameter in the actual call expects an Iterator. Here are the typical meanings of the parameters in C++ built in algorithms:

In - InputIterator
Out - OutputIterator
For - ForwardIterator
Bi - Bidirectional iterator
Ran - Random-access-iterator
T - element type
Op - function/functionobject
Pred - predicate (function/functionobject) (true/false)
BinOp - binary operation
BinPred - binary predicate
Cmp - compare like binary predicate
Gen - function that takes no parameters with returntype T
Size - int

Here are some examples of algorithms from the <algorithm> file:

For search(For,For,For2,For2); - serches for the sequence For2 in the sequence For.
bool equal(In,In,In2); - true if all elements in the sequence In is pairwise equal to In2.
Out transform(In,In,Out,Op); - apply Op on all elements.
For remove_if(For,For,Pred p); - delete all elements in sequence that fulfills the predicate.
bool binary_search(For,For,T& v); - return true if v is in sequence.
Out merge(In,In,In2,In2,Out); - merges 2 sorted sequences.
void sort(Ran,Ran,Cmp); - sorts the elements with Cmp.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Sum {                   // Functionobject class for summing
    public:
        Sum(int i=0)  { sum = 0; }
        void operator()( int x ) { sum += x; }
        int operator()(void) const { return sum; }
    private:
        int sum;
};

class Printer {               // Functionobject class for printing
    public:
        Printer(ostream& oss) : os(oss) {}
        void operator()( int x ) { os << " " << x; }
    private:
        ostream& os;
};

int main()
{
    int arr[] = { 1, 3, 4, 2, 9, 7, 8, 6, 5 };
    vector<int> vec( arr, arr+9 );        // vec = arr

    Printer printer(cout);
    for_each( arr, arr+9, printer );
    cout << endl;

    sort(arr,arr+9);
    for_each( arr, arr+9, Printer(cout) );
    cout << endl;
    Sum sum = for_each( vec.begin(), vec.end(), Sum() );
    //The function object is passed by-value! 
    // we must use the return value!
    cout << sum() << endl;
}

In the include file <functional> there are builtin function objects that we can use with the algorithms in the inlclude file <algorithm>. Here is an example of the usage of multiplies and greater. Yes, greater also exists, so what we did before was indeed unnecessary.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

template <class T> class printer
{
    public:
          void operator()( T v ) { cout << v << endl; }
};

int main()
{
    vector<int> ivec;
    ivec.push_back(2);
    ivec.push_back(1);
    ivec.push_back(5);
    ivec.push_back(10);
    ivec.push_back(4);

    multiplies<int> mul;
    cout << accumulate( ivec.begin(), ivec.end(), 1, mul ) << endl;
    cout << accumulate( ivec.begin(), ivec.end(), 1, multiplies<int>() ) << endl;

    sort(ivec.begin(), ivec.end(), greater<int>() );

    for_each( ivec.begin(), ivec.end(), printer<int>() );

}

Here is a summary of some common and useful function objects

plus<T>
minus<T>
multiplies<T>
divides<T>
modulus<T>
equal_to<T>
not_equal_to<T>
greater<T>
less<T>
greate_equal<T>
less_equal<T>
logcal_and<T>
logical_or<T>

You can ofcourse write your own template functions that can either take functions or functionobjects as parameters. Here is an example of how you can make a function like this. We have called the function compare for simplicity, which is used for making a comparison between usage of this function together with functionobjects and functions.
With functions:

#include <cctype> // for toupper!
#include <iostream>
#include <string>

using namespace std;

template <class LT, class EQ>      // LT and EQ are either functions or functionobjects
int compare( string &str1, string &str2, LT lt, EQ eq )
{
    for (int i=0; i < str1.length() && i < str2.length(); i++)
        if ( !eq(str1[i],str2[i]) ) return lt(str1[i], str2[i]);
    return str2.length()-str1.length();
}

//template <class T> int lt(T a, T b) { return a<b; }
//template <class T> int eq(T a, T b) { return a==b; }

int eqcss( char a, char b) { return a==b; }
int ltcss( char a, char b) { return a<b; }

int eqcis( char a, char b) { return toupper(a)==toupper(b); }
int ltcis( char a, char b) { return toupper(a) < toupper(b); }


int main()
{
    string a = "Big", b = "bigiiie";
    cout << compare(a,b, ltcss, eqcss ) << endl;
    cout << compare(a,b, ltcis, eqcis ) << endl;
    return 0;
}

With functionobjects:

#include <cctype> // for toupper!
#include <string>
using namespace std;

template <class LT, class EQ>
int compare( string &str1, string &str2, LT lt, EQ eq )
{
      for (int i=0; i < str1.length() && i < str2.length(); i++)
              if ( !eq(str1[i],str2[i]) ) return lt(str1[i], str2[i]);
        return str2.length()-str1.length();
}

template <class T> class ltcss {
    public:
          int operator()( T a, T b) { return a<b;}
};

template <class T> class eqcss {
    public:
          int operator()( T a, T b) { return a==b;}
};

template <class T> class ltcis {
    public:
          int operator()( T a, T b) { return toupper(a)<toupper(b);}
};

template <class T> class eqcis {
    public:
          int operator()( T a, T b) { return toupper(a)==toupper(b);}
};

int main()
{
    string a = "Apple", b = "aple";
    cout << compare(a,b, ltcss<char>(), eqcss<char>() ) << endl;
    cout << compare(a,b, ltcis<char>(), eqcis<char>() ) << endl;
}

Public static void

onsdag 2 juli 2014

4. Iterators and functionobjects