//
//
//

// Auxiliary iterator functions

#include <iterator>

void advance( InputIterator& pos, Dist n)
{
//  For bidirectional and random iterators n may negative
//  Dist is a template param, typically integral type
//  Does not check, whether crosses end() of container 
//  Use the best implementation via iterator trait
}

Dist distance(InputIterator pos1, InputIterator pos2)
{
//  Both iterator must refer to the same container
//  If not random access iterator, pos2 must be beyond pos1
//  Dist is iterator_traits<InputIterator>::difference_type
}

void iter_swap(ForwardIterator1 pos1, ForwardIterator2 pos2)
{
//  Swaps *pos1 and *pos2
//  Don't need to be the same type, but must be assignable
}

//
//  Reverse iterator:
//

template <class Iterator>
class reverse_iterator
{
    Iterator rbegin() { return reverse_iterator(begin()); }
    Iterator rend()   { return reverse_iterator(end()); }

    Iterator base() const { /* returns the phisical pos */ }
}




//
//  Inserters
//

                Class                   Constructor             Called function

Back inserter   back_insert_iterator    back_inserter(cont)     push_back(v)
Front inserter  front_insert_iterator   front_inserter(cont)    push_front(v)
Gen. inserter   insert_iterator         inserter(cont,pos)      insert(pos,v)


    // usage of inserter

    merge( v1.begin(), v1.end(),
           v2.begin(), v2.end(),
           back_inserter(v3));



//
//  Iterator traits
//

struct output_iterator_tag { };
struct input_iterator_tag  { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };


template <class T>
struct iterator_traits<T*>
{
    typedef T           value_type;
    typedef ptrdiff_t   difference_type;
    typedef random_access_iterator_tag  iterator_category;
    typedef T*          pointer;
    typedef T&          reference;
};


template <class Iterator>
inline void foo(Iterator beg, Iterator end)
{
    foo( beg, end, std::iterator_traits<Iterator>::iterator_category());
}


template <class Iterator>
void foo(BiIterator beg, BiIterator end, std::bidirectional_iterator_tag)
{
    // implementation for bidirectional iterator
}
template <class Iterator>
void foo(RaIterator beg, RaIterator end, std::random_access_iterator_tag)
{
    // implementation for random access iterator
}