The Standard Template Library


Part of the C++ standard. The most important example for generic programming.
Generic programming: make more abstract routines without loosing efficiency
using parameterization (both data and algorithm).


Motivation:

    int t[] = { 1, 3, 5, ... };

    // find the first occurance of a value
    int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);

    if ( pi )
    {
        *pi = 56;
    }



A very specific implementation:


    int *find( int *begin, int *end, int x)
    {
        while ( begin != end )
        {
            if ( *begin == x )
            {
                return begin;
            }
            ++begin;
        }
        return 0;
    }


Step1: generalization on type    int -> T


    template <typename T>
    T *find( T *begin, T *end, const T& x)
    {
        while ( begin != end )
        {
            if ( *begin == x )
            {
                return begin;
            }
            ++begin;
        }
        return 0;
    }



Step2: Generalization on data structure


    template <typename It, typename T>
    It find( It begin, It end, const T& x)
    {
        while ( begin != end )
        {
            if ( *begin == x )
            {
                return begin;
            }
            ++begin;
        }
        return end;  // not 0
    }



Uniform usage


    int t[] = { 1, 3, 5, ... };

    int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);

    if ( pi )
    {
        *pi = 56;
    }

    vector<int> v;
    v.push_back(1); v.push_back(3); v.push_back(5); ...

    vector<int>::iterator vi = find( v.begin(), v.end(), 55);

    if ( vi != v.end() )
    {
        *vi = 56;
    }

    list<double> l;
    l.push_back(1.1); l.push_back(3.3); l.push_back(5.5); ...

    list<double>::iterator li = find( l.begin(), l.end(), 55.55);

    if ( li != l.end() )
    {
        *li = 56.66;
    }



Constant safety:


    const int t[] = { 1, 3, 5, ... };

    const int *pi = find( t, t+sizeof(t)/sizeof(t[0]), 55);

    if ( pi )
    {
        // *pi = 56;    Syntax error
        cout << *pi;
    }

    vector<int> v;
    v.push_back(1); v.push_back(3); v.push_back(5); ...

    const list<double> cl( v.begin(), v.end());

    list<double>::const_iterator cli = find( cl.begin(), cl.end(), 55.55);

    if ( cli != cl.end() )
    {
        // *cli = 56.66;    Syntax error
        cout << *cli;
    }


Be care: const_iterator != const iterator


More generalization. Find the 3rd occurance:


    list<double> l; ...
    list<double>::iterator li;

    li = find( l.begin(), l.end(), 3.14);
    li = find( li, l.end(), 3.14);
    li = find( li, l.end(), 3.14);

    // or:
    li = find(find(find(l.begin(),l.end(),3.14),l.end(),3.14),l.end(),3.14);


It is obvious that this way there is a limitation. We have to change our
strategy here. Find the third element whis is less than 55.


    template <typename It, typename Pred>
    It find_if( It begin, It end, Pred p)
    {
        while ( begin != end )
        {
            if ( p(*begin) )
            {
                return begin;
            }
            ++begin;
        }
        return end;
    }



    // Pred1: not too good
    bool less55_3rd( int x)
    {
        static int cnt = 0;
        if ( x < 55 )
            ++cnt;
        return 3 == cnt;
    }

    vector<int> v; ...
    vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd);
    vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd); // ??



    // Pred2
    struct less55_3rd
    {
        less55_3rd() : cnt(0) { }
        bool operator()(int x)
        {
            if ( x < 55 )
               ++cnt;
            return 3 == cnt;
        }
    private:
        int cnt;
    };


    vector<int> v; ...
    less55_3rd  pp;
    vector<int>::iterator = find_if( v.begin(), v.end(), pp);

    // or:
    vector<int>::iterator = find_if( v.begin(), v.end(), less55_3rd());



    // Pred3: more generic

    template <typename T>
    struct less_nth
    {
        less_nth( const T& t, int n) : t_(t), n_(n), cnt_(0) { }
        bool operator()(const T& t)
        {
            if ( t < t_ )
               ++cnt;
            return n_ == cnt;
        }
    private:
        T   t_;
        int n_;
        int cnt_;
    };


    vector<int> v; ...
    vector<int>::iterator = find_if(v.begin(),v.end(),less_nth<int>(55,3));


Bit in longer term, it is better to avoid predicates with state.