The Standard Template Library
=============================



The STL is 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:


We want to find an element in an array of integers:


    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());  // init const list

    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);   // first 
    if ( li != l.end() )  li = find( ++li, l.end(), 3.14);  // second
    if ( li != l.end() )  li = find( ++li, l.end(), 3.14);  // third



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.




STL components
==============


- Containers

  - Sequential containers: vector, deque, list
  - Associative containers: map, multimap, set, multiset
  - C++0X: unsorted associative containers (hash)



- Algorithms

  - Nonmodifying sequential algorithms
  - Modifying sequential algorithms
  - Sorted container algorithms



- Adaptors
  - Container adaptors: stack, queue, priority_queue
  - Others: iterator adaptors, inserters, etc.



- Functors, binders, ...


- Allocators



Sequential containers
=====================


  - vector
  - deque
  - list



Types defined in a container:


template <class T, class A = allocator<T> > class std::vector {
public:
    // types:

    typedef T value_type;           // type of element
    typedef A allocator_type;       // type of memory manager
    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;

    typedef implementation_dependent1 iterator;         // T*
    typedef implementation_dependent2 const_iterator;   // const T*
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    typedef typename A::pointer pointer;        // pointer to element
    typedef typename A::const_pointer const_pointer;
    typedef typename A::reference reference;    // reference to element
    typedef typename A::const_reference const_reference;

    // ...
};


Usage of types declared in a container
makes you be able to write generic code


template<class C> typename C::value_type sum(const C& c)
{
    typename C::value_type s = 0;
    typename C::const_iterator p = c.begin();   // start at the beginning
    while (p!=c.end()) {                        // continue until the end
        s += *p;        // get value of element
        ++p;            // make p point to next element
    }
    return s;
}



Iterators and references


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // iterators:

    iterator begin();           // points to first element
    const_iterator begin() const;
    iterator end();             // points to one-past-last element
    const_iterator end() const;

    reverse_iterator rbegin();  // points to first element of reverse sequence
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();    // points to one-past-last element
    const_reverse_iterator rend() const;

    // ...
};



Usage of reverse iterator


template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::reverse_iterator ri = find(c.rbegin(),c.rend(),v);
    if (ri == c.rend()) return c.end(); // use c.end() to indicate "not found"
    typename C::iterator i = ri.base();
    return --i;
}



template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::iterator p = c.end();   // search backwards from end
    while (p!=c.begin())
        if (*--p==v) return p;
    return c.end();             // use c.end() to indicate "not found"
}



template<class C> typename C::iterator find_last(C& c, typename C::value_type v)
{
    typename C::reverse_iterator p = c.rbegin();    // view sequence in reverse
    while (p!=c.rend()) {
        if (*p==v) {
            typename C::iterator i = p.base();
            return --i;
        }
        ++p;            // note: increment, not decrement (--)
    }
    return c.end(); // use c.end() to indicate "not found"
}



  i = ri.base();


         rend()      ri   rbegin()
           |          |       |
           V          V       V
              -------------------
             | 1 | 2 | 3 | 4 | 5 |
              -------------------
               ^           ^       ^
               |           |       |
             begin()       i     end()





Constructors and assignments


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // constructors, etc.:

    explicit vector(const A& = A());
    explicit vector(size_type n, const T& val = T(), const A& = A());   // n copies of val
    template <class In>     // In must be an input iterator
    vector(In first, In last, const A& = A());  // copy from [first:last[
    vector(const vector& x);

    ~vector();  // destructor

    vector& operator=(const vector& x); // assignment operator

    template <class In>                 // In must be an input iterator (_iter.oper_)
    void assign(In first, In last);     // copy from [first:last[
    void assign(size_type n, const T& val); // n copies of val

    // ...
};



Use of constructors

vector<Record> vr(10000);

void f(int s1, int s2)
{
    vector<int> vi(s1);
    vector<double>* p = new vector<double>(s2);
}


void f(const list<X>& lst)
{
    vector<X> v1(lst.begin(),lst.end());    // copy elements from list
    char p[] = "despair";
    vector<char> v2(p,&p[sizeof(p)-1]);     // copy characters from C-style string
}



vector<int> v1(10);         // ok: vector of 10 ints
vector<int> v2 = vector<int>(10);   // ok: vector of 10 ints
vector<int> v3 = v2;            // ok: v3 is a copy of v2
vector<int> v4 = 10;            // error: attempted implicit conversion of 10 to vector<int>



void f1(vector<int>&);      // common style
void f2(const vector<int>&);// common style
void f3(vector<int>);       // rare style

void h()
{
    vector<int> v(10000);
    // ...
    f1(v);  // pass a reference
    f2(v);  // pass a reference
    f3(v);  // copy the 10000 elements into a new vector for f3() to use
}



Direct access for sequential containers


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // element access:

    // only for vector and dequeue
    reference operator[](size_type n);  // unchecked access
    const_reference operator[](size_type n) const;

    // only for vector and dequeue
    reference at(size_type n);          // checked access
    const_reference at(size_type n) const;

    reference front();      // first element
    const_reference front() const;
    reference back();       // last element
    const_reference back() const;

    // ...
};



Stack operations


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // stack operations:

    // not for vector
    void push_front(const T& x); // add to the beginning
    void pop_front();            // remove first element

    void push_back(const T& x); // add to end
    void pop_back();            // remove last element
    // ...
};



void f()
{
    vector<int> v;
    v.pop_back();   // undefined effect: the state of v becomes undefined
    v.push_back(7); // undefined effect (the state of v is undefined), bad
}


List operations


template <class T, class A = allocator<T> > class vector {
public:
    // list operations:

    iterator insert(iterator pos, const T& x);          // add x before pos
    void insert(iterator pos, size_type n, const T& x); // add n copies of x before pos
    template <class In>                       // In must be an input iterator
    void insert(iterator pos, In first, In last);   // insert elements from sequence

    iterator erase(iterator pos);   // remove element at pos
    iterator erase(iterator first, iterator last);  // erase sequence
    void clear();                   // erase all elements

    // ...
};



Usage of list operations


void duplicate_elements(vector<string>& f)
{
    for(vector<string>::iterator p = f.begin(); p!=f.end(); ++p) f.insert(p,*p);    // No!
}

template<class C> void f(C& c)
{
    c.erase(c.begin()+7);   // ok (if c's iterators support + )
    c.erase(&c[7]);         // not general
    c.erase(c+7);           // error: adding 7 to a container makes no sense

    c.erase(c.back());      // error: c.back() is a reference, not an iterator
    c.erase(c.end()-2);     // ok (second to last element)
    c.erase(c.rbegin()+2);  // error: vector::reverse_iterator and vector::iterator
                            //  are different types
    c.erase((c.rbegin()+2).base()); // obscure, but ok 
}



Size and Capacity


template <class T, class A = allocator<T> > class vector {
public:
    // ...
    // capacity: only for vector

    size_type size() const;         // number of elements
    bool empty() const { return size()==0; }
    size_type max_size() const;     // size of the largest possible vector
    void resize(size_type sz, T val = T()); // added elements initialized by val

    size_type capacity() const; // size of the memory (in number of elements) allocated
    void reserve(size_type n);  // make room for a total of n elements; don't initialize
                                // throw a length_error if n>max_size()
    // ...
};



Different containers have different memory usage characteristics:



                          ______________________________________
                         |
                         |
                         |
               __________|
              |
            __|
vector   __|
                           ________
                          |        |
                  ________|        |____
                 |                      |
             ____|                      |______      ______
            |                                  |    |      |
          _ |                                  |____|      |_____
         |
dequeue  |                      _
                             __| |_
                           _|      |_
                    __   _|          |_
                  _|  |_|              |_
                _|                       |____
             __|                              |_     _______
           _|                                   |___|       |_____
list     _|






The swap() trick for reduce vector's memory:


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

    vector<int>(v).swap(v);


In C++11:

    v.shrink_to_fit();



template <class T, class A = allocator<T> > class vector {
public:
    // ...

    void swap(vector&);
};

template <class T, class A> void std::swap(vector<T,A>& x, vector<T,A>& y)
{
    x.swap(y);
}

template <class T, class A>
bool std::operator==(const vector<T,A>& x, const vector<T,A>& y);

template <class T, class A>
inline bool std::operator<(const vector<T,A>& x, const vector<T,A>& y)
{
    return lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
}



Container adaptors:


template <class T, class C = deque<T> > class std::stack {
protected:
    C c;
public:
    typedef typename C::value_type value_type;
    typedef typename C::size_type size_type;
    typedef C container_type;

    explicit stack(const C& a = C()) : c(a) { }

    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }

    value_type& top() { return c.back(); }
    const value_type& top() const { return c.back(); }

    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};


Queue and priority_queue are similar.





Associative containers
======================





Types defined in Map


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class std::map {
public:
    // types:

    typedef Key key_type;
    typedef T mapped_type;

    typedef pair<const Key, T> value_type;

    typedef Cmp key_compare;
    typedef A allocator_type;

    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;

    typedef implementation_defined1 iterator;
    typedef implementation_defined2 const_iterator;

    typedef typename A::size_type size_type;
    typedef typename A::difference_type difference_type;

    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    // ...
};


/*
 *  Iterators of map
 *
 */

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > > class map {
public:
    // ...
    // iterators:

    iterator begin();
    const_iterator begin() const;

    iterator end();
    const_iterator end() const;

    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;

    reverse_iterator rend();
    const_reverse_iterator rend() const;

    // ...
};


/*
 *  Usage of map
 *
 */

void f(map<string,number>& phone_book)
{
    typedef map<string,number>::const_iterator CI;
    for (CI p = phone_book.begin(); p!=phone_book.end(); ++p)
        cout << p->first << '\et' << p->second << '\en';
}


/*
 *  Pair
 *
 */

template <class T1, class T2> struct std::pair {
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;

    pair() :first(T1()), second(T2()) { }
    pair(const T1& x, const T2& y) :first(x), second(y) { }
    template<class U, class V>
        pair(const pair<U, V>& p) :first(p.first), second(p.second) { }
};


template <class Key, class T, class Cmp =less<Key>,
        class A =allocator<pair<const Key,T> > >
class map {
public:
    // ...
    // construct/copy/destroy:

    explicit map(const Cmp& = Cmp(), const A& = A());
    template <class In> map(In first, In last, const Cmp& = Cmp(), const A& = A());
    map(const map&);

    ~map();

    map& operator=(const map&);

    // ...
};


//  Using compare for associative containers

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...

    typedef Cmp key_compare;

    class value_compare : public binary_function<value_type,value_type,bool>
    {
    friend class map;
    protected:
    Cmp cmp;
        value_compare(Cmp c) : cmp(c) {}
    public:
    bool operator()(const value_type& x, const value_type& y) const
        { return cmp(x.first, y.first); }
    };

    key_compare key_comp() const;
    value_compare value_comp() const;
    // ...
};


/*
 *  Usage of comparison
 *
 */

map<string,int> m1;
map<string,int,Nocase> m2;      // specify comparison type (_cont.comp_)
map<string,int,String_cmp> m3;  // specify comparison type (_cont.comp_)
map<string,int,String_cmp> m4(String_cmp(literary));// pass comparison object


void f(map<string,int>& m)
{
    map<string,int> mm;         // compare using < by default
    map<string,int> mmm(m.key_comp());  // compare the way m does
    // ...
}


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    mapped_type& operator[](const key_type& k); // access element with key k
    // ...
};


void f()
{
    map<string,int> m;  // map starting out empty
    int x = m["Henry"]; // create new entry for "Henry", initialize to 0, return 0
    m["Harry"] = 7;     // create new entry for "Harry", initialize to 0, and assign 7
    int y = m["Henry"]; // return the value from "Henry"'s entry
    m["Harry"] = 9;     // change the value from "Harry"'s entry to 9
}


template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    // list operations:

    pair<iterator, bool> insert(const value_type& val);     // insert (key,value) pair
    iterator insert(iterator pos, const value_type& val);   // pos is just a hint
    template <class In> void insert(In first, In last);     // insert elements from sequence

    void erase(iterator pos);           // erase the element pointed to
    size_type erase(const key_type& k); // erase element with key k (if present)
    void erase(iterator first, iterator last);  // erase range
    void clear();               // Erase all elements

    // ...
};


void f(map<string,int>& m)
{
    pair<string,int> p99("Paul",99);

    pair<map<string,int>::iterator,bool> p = m.insert(p99);
    if (p.second) {
        // "Paul" was inserted
    }
    else {
        // "Paul" was there already
    }
    map<string,int>::iterator i = p.first;  // points to m["Paul"]
    // ...
}

template <class Key, class T, class Cmp = less<Key>,
        class A = allocator< pair<const Key,T> > >
class map {
public:
    // ...
    // map operations:

    iterator find(const key_type& k);           // find element with key k
    const_iterator find(const key_type& k) const;

    size_type count(const key_type& k) const;   // find number of elements with key k

    iterator lower_bound(const key_type& k);    // find first element with key k
    const_iterator lower_bound(const key_type& k) const;
    iterator upper_bound(const key_type& k);    // find first element with key greater than k
    const_iterator upper_bound(const key_type& k) const;

    pair<iterator,iterator> equal_range(const key_type& k);
    pair<const_iterator,const_iterator> equal_range(const key_type& k) const;

    // ...
};

void f(map<string,int>& m)
{
    map<string,int>::iterator p = m.find("Gold");
    if (p!=m.end()) {               // if "Gold" was found
        // ...
    }
    else if (m.find("Silver")!=m.end()) {   // look for "Silver"
    // ...
    }
    // ...
}

void f(multimap<string,int>& m)
{
    multimap<string,int>::iterator lb = m.lower_bound("Gold");
    multimap<string,int>::iterator ub = m.upper_bound("Gold");

    for (multimap<string,int>::iterator p = lb; p!=ub; ++p) {
        // ...
    }
}






A detailed sample: merge two containers
=======================================





#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// simple merge
int main()
{
    string s1, s2;

    ifstream f1("file1.txt");
    ifstream f2("file2.txt");

    f1 >> s1;
    f2 >> s2;

    // the usual way:
    while (f1 || f2)
    {
        if (f1 && ((s1 <= s2) || !f2))
        {
            cout << s1 << endl;
            f1 >> s1;
        }
        if (f2 && ((s1 >= s2) || !f1))
        {
            cout << s2 << endl;
            f2 >> s2;
        }
    }
    return 0;
}



#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>    // merge( b1, e1, b2, e2, b3 [,opc_rend])
#include <vector>

using namespace std;

int main()
{
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    string s;

    vector<string> v1;
    while ( if1 >> s ) v1.push_back(s);

    vector<string> v2;
    while ( if2 >> s ) v2.push_back(s);

    // allocate the spacefor the result
    vector<string> v3(v1.size() + v2.size());   // very expensive...

    merge( v1.begin(), v1.end(),
           v2.begin(), v2.end(),
           v3.begin());             // v3[i] = *current 

    for ( int i = 0; i < v3.size(); ++i)
        cout << v3[i] << endl;

    return 0;
}



#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    string s;

    vector<string> v1;
    while ( if1 >> s ) v1.push_back(s);

    vector<string> v2;
    while ( if2 >> s ) v2.push_back(s);

    vector<string> v3;
    v3.reserve( v1.size() + v2.size() );    // allocates but not construct
                                            // size == 0
    merge( v1.begin(), v1.end(),
           v2.begin(), v2.end(),
           back_inserter(v3));      // v3.push_back(*current)

    for ( int i = 0; i < v3.size(); ++i)
        cout << v3[i] << endl;

    return 0;
}



#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>     // input- and output-iterators

using namespace std;

int main()
{
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    // istream_iterator(if1) -> if1 >> *current
    // istream_iterator() -> EOF
    // ostream_iterator(of,x) -> of << *current << x 
    merge( istream_iterator<string>(if1), istream_iterator<string>(),
           istream_iterator<string>(if2), istream_iterator<string>(),
           ostream_iterator<string>(cout,"\n") );
    return 0;
}



#include <iostream>
#include <fstream>
#include <string>
#include <cctype>
#include <algorithm>
#include <iterator>

// function object: "functor"
struct my_less
{
    bool operator()(const std::string& s1, const std::string& s2)
    {
        std::string us1 = s1;
        std::string us2 = s2;

    // TODO: use locale object 
        transform( s1.begin(), s1.end(), us1.begin(), toupper);
        transform( s2.begin(), s2.end(), us2.begin(), toupper);

        return us1 < us2;
    }
};

using namespace std;

int main()
{
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    merge( istream_iterator<string>(if1), istream_iterator<string>(),
           istream_iterator<string>(if2), istream_iterator<string>(),
           ostream_iterator<string>(cout,"\n"), my_less() );
    return 0;
}


#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

// one from left, one from right:
struct zipp
{
    zipp() : flag(true) { }
    bool operator()(const string& s1, const string& s2)
    {
        flag = !flag;
        return flag;
    }
    bool flag;
};

int main()
{
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    merge( istream_iterator<string>(if1), istream_iterator<string>(),
           istream_iterator<string>(if2), istream_iterator<string>(),
           ostream_iterator<string>(cout,"\n"), zipp() );
    return 0;
}



#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

template <typename T>
class distr
{
public:
    distr(int l, int r, bool fl = true) :
                       left(l), right(r), from_left(fl), cnt(0) { }
    // formal reasons: "compare" has two parameters of type T
    bool operator()( const T&, const T&)
    {
        bool ret = from_left;
        const int  max = from_left ? left : right;
        if ( ++cnt == max )
        {
            cnt = 0;
            from_left = ! from_left;
        }
        return ret;
    }
private:
    const int left;
    const int right;
    int from_left;
    int cnt;
};

int main()
{
    int left, right;
    cin >> left >> right;
    ifstream if1("file1.txt");
    ifstream if2("file2.txt");

    merge( istream_iterator<string>(if1), istream_iterator<string>(),
           istream_iterator<string>(if2), istream_iterator<string>(),
           ostream_iterator<string>(cout,"\n"),
                                    distr<std::string>(left,right) );
    return 0;
}