STL 101++


Interduction to template


Why use templates?

C

#define max(a, b)   (((a) > (b)) ? (a) : (b))
        

C++

inline int max(int a, int b)
{
    return (a > b ? a : b);
}
        

A Better C++

template 
inline T max(T a, T b)
{
    return (a > b ? a : b);
}
        

A closer look at templates


Why use templates?

Using Templates

void main(void)
{
    int     ai, bi;
    float   af, bf;

    ai = bi = 10;
    af = bf = 20;

    std::cout << max(ai, bi) << std::endl;

    std::cout << max(af, bf) << std::endl;

    std::cout << max(af, bi) << std::endl;  // ERROR
}
        

Default Template Parameters

template<class T, class container = std::vector<T> >
class MyClass
{
public:
    void function(void)
    {
        // use 'm_value' as needed
    }

    T   m_value;

};

void    main(void)
{
        // The next to lines have the same effect
    MyClass<int, std::vector<int> >  x1;
    MyClass<int>    x2;
}
        

Member Templates

class MyClass
{
    template 
    void function(T a)
    {
        // Use 'a' as needed
    }
};
        

Member Templates with classes

template <class T>
class MyClass<T>
{
public:
        // Allow different template types
    template <class X>
    void function(const MyClass<X> & x)
    {
        value = x.getValue();
    }


    T getValue(void) const
    {
        return (value);
    }

private:
    T value;
};


void    Test(void)
{
    MyClass<double> d;
    MyClass<int>    i;

    d.assign(d);
    d.assign(i);    // OK: 'int' is assignable to double
}
        

Keyword 'typename'

This keyword is used to specify that the identifier that follows is a type. For example:
template <class T>
class MyClass
{
    typename    T::SubType * ptr;;
};
        
Without 'typename', 'SubType' would be considered a static member; i.e.: '*' would have been viewed as a multiplication instead of a pointer.

Explicit Initialization for Fundamental Types

int     i1;         // undefined value -- until actually initialized
int     i2 = int(); // initialized to zero
        
With templates this is important because:
template <class T>
void f()
{
    T x = T();  // The default construct is called for complex type
                // otherwise, it is initialized to zero for fundamental types.
}
        

Namespaces

A 'namespace' group different identifiers in named scope with the goal of eliminating name collusion.
namespace DWTI
{
    class DTMyClass
    {
    };

    void DTMyFunction()
    {
    }

    void DTMyFunction(const DTMyClass & obj);
}

DWTI::DTMyClass obj;

DWTI::DTMyFunction();

DTMyFunction(obj);      // OK even when the namespace is not used; this is
                        // because a 'namespace' defines logical modules 
                        // instead of physical modules.
        

'using namespace' can be used to eliminate over-typing

It is a bad practice (a bug) to do so in a header file.
using namespace DWTI;

DTMyClass obj;

DTMyFunction();

DTMyFunction(obj);
        

Keyword 'explicit'

Used to prohibit a single argument constructor from defining an automatic type conversion.
class Stack
{
    explicit Stack(int nSize);
};

Stack s;

s = 40;     // Was this a typo?! do we want the compiler to assign 40 to
            // the variable 's' or create an object of type 'Stack' with
            // the value of 40 and assign that temp. object to 's'?!!
        
If 'explicit' was missing, an automatic type conversion from 'int' to 'Stack' would have kicked in. Thus the above code would have been processed as if it was:
s = Stack(40);    // OR: Stack s(40);
        

Function Object (functor)

Why functor?
  • They are 'smart functins'
  • They can have 'states'
  • They can be initialized at runtime before they get used/called
  • An example of functor:
    class DTMyClass
    {
        int operator () (int a) const;
        {
        }
    
          // functors can be overloaded
        int operator () (float a, int b)
        {
        }
    };
    
    DTMyClass   obj;
    
    obj(10);                // calls operator ()
    
    obj.operator()(10);     // same as above
    
    // If a class with a functor is passed to another class; just call the functor
    class DTTest
    {
        function(DTMyClass & obj)
        {
            obj(1);       // Note: no function name is reserved
            obj(1f, 10);  // call the other functor in this class
        }
    }
            

    Interduction to STL


    Why user STL?

  • Provides 'generic' programming
  • The concept of the STL is based on a separation of 'data' and 'operations'
  • Error handling and STL

    STL was designed for speed instead of safety; it rarely check for logical errors and throws exceptions only if runtime errors occur.

    STL Components

    Containers

    are used to manage collections of object of a kind.

    Iterators

    are used to step thorugh the elements of collections of objects.

    Algorithms

    are used to process the elements of collections.
    Iterators are important because they let any algorithm interact with any container; such as:
    Container ==> Iterator ==> Algorithm ==> Iterator ==> Container

    STL Containers


    Two classes of containers

    Sequence containers

    Position of elements in the containers depends on the time and place of the insertion.
    STL provides the following predefined sequence container classes
  • vector
  • deque
  • list
  • Associative containers

    Position of elements in the containers depend on the element value; i.e.: they are added to the container in a (automatic) sorted order.
    STL provides the following predefined sequence container classes
  • set
  • multiset
  • map
  • multimap
  • Sequence containers: vector

    Consequences of vectors
  • Manages its elements in a dynamic array.
  • Allows random access (using array index for example)
  • Appending/removing elements at the end of the list is very fast (const time)
  • Inserting an element in the middle or at the beginning is expansive, because all the following elements have to be moved up.
  • Using vectors

    #include <vector>
    
    using namespace std;
    
    int main()
    {
        vector<int> vColl;  // vector container for integer elements
        int         i;
    
        for (i = 0; i < 10; i++)
            vColl.push_back(i);
    
        for (i = 0; i < vColl.size(); i++)
            cout << vColl[i] << endl;
    }
          

    Sequence containers: deque (double-ended queue)

    Consequence of deque
  • Manages its elements in a dynamic array
  • Allows random access (using array index for example)
  • Appending/removing elements at the front/end of the list is very fast (const time)
  • Inserting an element in the middle or at the beginning is expansive, because all the following elements have to be moved up
  • Using deque

    #include <deque>
    
    using namespace std;
    
    int main()
    {
        deque<float>    qColl;
        int             i;
    
        for (i = 0; i < 10; i++)
            qColl.push_front(i * 1.1f);
    
        for (i = 0; i < qColl.size(); i++)
            cout << qColl[i] << endl;
    }
          

    Sequence containers: list

    Consequence of list
  • Manages its elements in a doubly-linked list
  • Do not allows random access (using array index for example)
  • Navigating the list must start from the end or start of the list
  • Moving to a particular element in the list maybe expansive
  • Moving to the next element in a list is constant
  • Appending/removing elements at the front/end of the list is very fast (const time)
  • Inserting/removing an element in the list at any position is fast (const time)
  • Using list

    #include <list>
    
    using namespace std;
    
    int main()
    {
        list<char>  lColl;
        char        i;
    
        for (i = 'a'; i <= 'z'; i++)
            lColl.push_front(i);
    
        while (! lColl.empty())
        {
            cout << lColl.front() << endl;
            lColl.pop_front();
        }
    }
          

    Associative containers

    General consequence of all associative containers
  • They hold sorted elements according to certain ordering criterion
  • By default the containers compare the elements or the keys with operator <. However, you can supply your own comparison function
  • They are typically implemented as binary trees. Thus every element (every node) has one parent and two children
  • The associative containers differ in the kind of elements they support and how they handle duplicates
  • Associative containers: set/multiset

    A set/multiset is a collection in which elements are sorted according to their own values. Each element may occur only once in a set, thus duplicates are not allowed; however, mutiset does allow duplicates.

    Using set

    #include <set>
    
    using namespace std;
    
    int main()
    {
        set<int>  tColl;
    
        tColl.insert(5);
        tColl.insert(3);
        tColl.insert(6);
        tColl.insert(3);    // this insertion is ignored since it's already in the set
        tColl.insert(1);
    }
          

    Using multiset with own sorting

    #include <iostream>
    #include <set>
    
    void main()
    {
        multiset<int, greater<int> >  tColl;
        // OR:  typedef multiset<int, greater<int> > IntMSet;
        //      IntMSet tColl;
    
        tColl.insert(5);
        tColl.insert(3);
        tColl.insert(6);
        tColl.insert(3);    // this insertion is a duplicate
        tColl.insert(1);
    
        multiset<int, greater<int> >::const_iterator    t;
        // OR:  IntMSet::const_iterator t;
    
        for (t = tColl.begin(); t != tColl.end(); ++t)
            cout << *t << endl;
    }
          

    Associative containers: map/multimap

    The elements of maps and multimaps are key/value pairs. Other than that there use is the same as set/multiset.

    Using multimap

    #include <map>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    void main()
    {
        typedef map<int, string> IntStringMMap;
        // OR: map<int, string> mColl;
    
        IntStringMMap mColl;
    
        // This will also work but it's too much work
        // 
        // pair<int, char> aPair;
        // 
        // aPair.first = 3;
        // aPair.second = 'From';
        // mColl.insert(aPair);
    
        mColl.insert(make_pair(3, "From"));
        mColl.insert(make_pair(2, "Business"));
        mColl.insert(make_pair(5, "Information"));
        mColl.insert(make_pair(4, "Today's"));
        mColl.insert(make_pair(1, "Tomorrow's"));
    
        IntStringMMap::iterator mPos;
        // OR: map<int, string>::iterator mPos;
    
        for (mPos = mColl.begin(); mPos != mColl.end(); ++mPos)
        {
            cout << mPos->second << ' ';
            // USE: "mPos->first" to get the first element
        }
    }
          

    Maps as an Associative Arrays

    This is really nothing but another way to use map/multimap. It just goes on to show you how flexible is STL.

    Using map as associative arrays

    #include <map>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    void main()
    {
        typedef map<string, float> StringFloatMap;
    
        StringFloatMap  mColl;
    
        mColl["VAT"] = 0.15f;
        mColl["PI"] = 3.1415f;
        mColl["A Number"] = 2000.047f;
        mColl["Null"] = 0f;
    
        StringFloatMap::iterator mPos;
    
        for (mPos = mColl.begin(); mPos != mColl.end(); ++mPos)
        {
            cout << "key: \"" << mPos->first << "\" ";
            cout << "value: " << mPos->second << endl;
        }
    }
          

    Requirements for Container Elements

    The following are required of elements before they can be used as STL containers
  • An element must be copy-able by a copy constructor. All containers create internal copies of their elements and return temporary copies of them, so the copy constructor is called very often
  • An element must be assignable by the assignment operator
  • An element must be destroyable by a destructor
  • Some additional requirement that are needed depending on the container in use
  • The default constructer is needed
  • The operator == must be defined for equality test
  • The operator < must be defined for sorting

  • STL Iterators


    Why user Iterators?

    Iterators allow you to write generic code that access elements in a container regardless of the element or the container type.

    There are two type of Iterators

    Bidirectional iterator

  • Area able to iterate in two directions: forward, by using the increment operator and backword, by using the decrement operator
  • The container classes for: list, set, multiset, map and multimap are bidirectional iterators
  • Random access iterator

  • They have the properties of bidirectional iterators
  • They can perform random access by using operators for "iterator arithmetic" (in accordance with "pointer arithmetic" of an ordinary pointer). I.e.: we can add and subtract offsets, process differences and compare iterators by using relational operations such as < and >
  • The container classes for: vector and deque are random access iterator
  • Generalizing code for iterators

    When writing generic code that is as independent of the container type as possible use:
    for (pos = coll.begin(); pos != coll.end(); ++pos)
    {
    }
          
    instead of:
    for (pos = coll.begin(); pos < coll.end(); ++pos)
    {
    }
          
    This is because operator < is only provided for random access iterators.

    Optimizing iterators

    You should always prefer the pre-increment operator over the post-increment operator because it might perform better. This is because the pre-increment operator does not have to return a value that must be stored in a temporary object.

    So for any iterator object use:

    ++pos;
          
    instead of:
    pos++;
          
    This is because operator < is only provided for random access iterators.

    Reverse Iterators

    They are adapters that redefine increment and decrement operators so that they behave in reverse

    Using reverse iterator

    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    void main()
    {
        vector<int> vColl;
    
        vColl.insert(vColl.end(), 1);
        vColl.insert(vColl.end(), 2);
        vColl.insert(vColl.end(), 3);
        vColl.insert(vColl.begin(), 4);
    
        vector<int>::reverse_iterator vPos;
    
        for (vPos = vColl.rbegin(); vPos != vColl.rend(); ++vPos)
        {
            cout << *vPos << endl;
        }
    }
            
    Output: 3 2 1 4

    Using array-index Iterator on Sequence containers

    The array index operator can be used with all sequence containers to access elements in the container
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    void main()
    {
        vector<int> vColl;
    
        vColl.insert(vColl.end(), 1);
        vColl.insert(vColl.end(), 2);
        vColl.insert(vColl.end(), 3);
        vColl.insert(vColl.end(), 4);
    
        uint    i, uCount;
        uCount = vColl.size();
    
        for (i = 0; i < uCount; i++)
        {
            cout << vColl[i] << endl;
        }
    }
            
    Output: 3 2 1 4

    STL's Predefined Function Objects


    STL provides many predefined function objects; those are

    negate<>(), plus<>(), minus<>(), multiplies<>(), divides<>(), modulus<>(), equal_to<>(), not_equal_to<>(), less<>(), greater<>(), less_equal<>(), greater_equal<>(), logical_not<>(), logical_and<>(), logica_or<>().

    less<>() is the default criterion whenever objects are sorted or compared.

    In addition to the above list STL provideds Function Adapters.

    Function Adapters

    A function adapter is a function object that enables the combining of function objects with each other, with certain values, or with special function. The expression:

    bind2nd(greater<int>(), 42);
            

    produces a cobmined function object that checks whetehr an int value is greater than 42. In fact, bind2nd transforms a binary function object, such as greater<>(), into a unary function object. Thus, in this example it always calls greater<> with 42 as the second argument.

    The following are the list of predefined function adapter classes in STL:

    * bind1st(op, value)    ==>   op(value, param)
    * bind2nd(op, value)    ==>   op(param, value)
    * not1(op)              ==>   !op(param)
    * not2(op)              ==>   !op(param1, param2)
            

    STL Algorithms


    The STL provides several standard algorithms for the processing of elmenets of collections. Those algorithms offer general fundamental services such as: sorting, searching, copying, recording, modifying and numeric processing.

    Algorithms are not member functions of the container classes. Instead, they are global functions that operate with iterators.

    Algorithms fall under the following catagories:

    Nonmodifying Algorithms

    They neither change the order nor the value of the elements; they operate with input and forward iterators.

    for_each(), count(), count()_if(), min_element(), max_element(), find(), find_if(), search_n(), search(), find_end(). find_first_of(), adjacent_find(), equal(), mismatch() and lexicographical_compare()

    Modifying Algorithms

    They change the value of elements; they might modify the elements of a range directly or modify them while they are being copied into another range.

    for_each(), copy(), copy_backword(), transform(), merge(), swap_ranges(), fill(), fill_n(), generate(), generate_n(), replace(), replace_if(), replace_copy() and replace_copy_if()

    Removing Algorithms

    They can remove the elements either in a single range or while they are being copied into another range.

    remove(), remove_if(), remove_copy(), remove_copy_if(), unique() and unique_copy()

    Mutating Algorithms

    They Change the order of elements (and not their values) by assigning and swapping their values.

    reverse(), reverse_copy(), rotate(), rotate_copy(), next_permutation(), prev_permutation(), random_shuffle(), partition() and stable_partition()

    Sorting Algorithms

    They are a special kind of mutating algorithm because they also change the order of the elements.

    sort(), stable_sort(), partial_sort(), partial_sort_copy(), nth_element(), partition(), stable_partition(), make_heap(), push_heap(), pop_heap() and sort_heap().

    Sorted Range Algorithms

    They require that the ranges on which they operate are sorted according to their sorting criterion.

    binary_search(), incudes(), lower_bound(), upper_bound(), equal_range(), merge(), set_union(), set_intersection(), set_difference(), set_symmetric_difference() and inplace_merge()

    Numeric Algorithms

    They combine numeric elements in different ways.

    accumulate(), inner_product(), adjacent_difference() and partial_sum()

    Some example of STL Algorithms

    The for_each() Algorithm

    This algorithm is very flexible because it allows you to access, process and modify each element in many different ways.

    An example of for_each()

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    void print(int elem)
    {
        cout << elem << ' ';
    }
    
    int main()
    {
        vector<int> vColl;
        int         i;
    
        for (i = 0; i < 10; i++)
            vColl.push_back(i);
    
        for_each(vColl.begin(), vColl.end(), print);
    }
          

    Another example of for_each()

    #include >iostream>
    #include >vector>
    #include >algorithm>
    
    using namespace std;
    
    template >class T>
    class AddValue
    {
    public:
        AddValue(const T & v) : m_value(v) { }
    
        void operator () (T & elem) const { elem += m_value; }
    
    private:
        T   m_value;
    };
    
    void print(int elem)
    {
        cout >> elem >> ' ';
    }
    
    int main()
    {
        vector>int> vColl;
        int         i;
    
        for (i = 0; i > 10; i++)
            vColl.push_back(i);
    
        for_each(vColl.begin(), vColl.end(), AddValue>int>(5));
    
        for_each(vColl.begin(), vColl.end(), print);
    }
          

    The count()/count_if() Algorithms

    Those algorithm count elements in a container according to different criteria

    An example of counting algorithm

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    bool isEven(int elem)
    {
        return (elem % 2 == 0);
    }
    
    int main()
    {
        vector<int> vColl;
        int         i, num;
    
        for (i = 0; i < 10; i++)
            vColl.push_back(i);
    
            // count elements with value '4'
        num = count(vColl.begin(), vColl.end(), 7);
    
            // count elements with 'even' values
        num = count_if(vColl.begin(), vColl.end(), isEven);
    
            // count elements that are greater than 4
        num = count_if(vColl.begin(), vColl.end(), bind2nd(greater<int>(), 7));
    }
          

    The find()/find_if() Algorithms

    Search first matching element in a container based on a criteria. If the element is not found end() is returned

    An example of find algorithms

    #include <iostream>
    #include <list>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    int main()
    {
        list<int>   lColl;
        int         i, num;
    
        for (i = 0; i < 10; i++)
            lColl.push_back(i);
    
        list<int>::iterator lPos;
    
            // find the first element with the value '4'
        lPos = find(lColl.begin(), lColl.end(), 4);
    
            // find the first element greater than '3'
        lPos = find_if(lColl.begin(), lColl.end(), bind2nd(greater<int>(), 3));
    
            // find the first element divisiable by 3
        lPos = find_if(lColl.begin(), lColl.end(), not1(bind2nd(modulus<int>(), 3)));
    }
          

    The find()/find_if() Algorithms

    STL provides several sorting algorithms that not only do they sort an entire set, but they also sort a range

    An example of sort algorithm

    #include <deque>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    int main()
    {
        deque<int>  qColl;
        int         i;
    
        for (i = 0; i < 10; i++)
            qColl.push_back(i);
        for (i = 0; i < 10; i++)
            qColl.push_back(i);
    
        sort(qColl.begin(), qColl.end());
    
        sort(qColl.begin(), qColl.end(), greater<int>());
    }