//  (C) Porkolab 2003
//
//  A.6.12.
//  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) { }
};