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>());
}