std::map

map所开放的各种接口操作，RB-Tree也都提供了，因此几乎所有的map的操作只是转用RB-Tree的操作行为。

template <class Key, class T, 
          class Compare = less<Key>,
          class Alloc = alloc>
class map {
    public:
    //typedef
    typedef Key key_type; //键值型别
    typedef T data_type;
    typedef T mapped_type;
    typedef pair<const Key, T> value_type;
    typedef Compare key_compare;
    //以下定义一个functor，其作用就是调用“元素比较函数”
    class value_compare
        : public binary_function<value_type, value_type, bool> {
            friend class map<Key, T, Compare, Alloc>;
            protected:
                Compare comp;
                value_compare(Compare c) : comp(c) {}
            public:
                bool operator()(const value_type& x, const value_type& y) const {
                    return comp(x.first, y.first);
                }
     };
     private:
         typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc>rep_type;
        rep_type t;
     public:
         typedef typename rep_type::pointer pointer;
        typedef typename rep_type::const_pointer const_pointer;
        typedef typename rep_type::reference reference;
        typedef typename rep_type::const_reference const_reference;
        typedef typename rep_type::iterator iterator; //允许用户通过迭代器修改元素的值
        typedef typename rep_type::const_iterator const_iterator;
        typedef typename rep_type::reverse_iterator reverse_iterator;
        typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
        typedef typename rep_type::size_type size_type;
        typedef typename rep_type::difference_type difference_type;
        //map一直使用的是底层RB-tree的insert_unique(),而非insert_equal()
        map() : t(Compare()) {}
        explicit map(const Compare& comp) : t(comp) {}
        template <class InputIterator>
        map(InputIterator first, InputIterator last)
          : t(Compare()) {t.insert_unique(first, last);}
        template <class InputIterator>
        map(InputIterator first, InputIterator last, const Compare& comp)
           : t(comp) {t.insert_unique(first, last);}
        map(const map<Key, T, Compare, Alloc>& x) : t(x.t){}
        map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& operator=
        (const map<Key, T, Compare, Alloc>& x))
        {
            t = x.t;
            return *this;
        }
}