/*
 *  Map
 *
 *  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) { }
};