C++ STL Container Map and MultiMap

Map and MultiMap

• based on gnu 2.9
• 底层用红黑树实现(RB Tree)
• 不同点在于使用rb tree::insert_unique/rb tree::insert_equal
• 并且multimap不支持[]访问元素, 其他相同

Map

Container

/*
    typedef Key key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef Compare key_compare;

    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;
*/
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
    // 包装Compare
    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);
        }
    };
    // value是一个pair
    typedef pair<const Key, T> value_type;
    // 与set的不同, 从value中提取key的方式不同
    // select1st<value_type>
    typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;  // red-black tree representing map

    // accessors
    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const { return value_compare(t.key_comp()); }
    // iterator
    iterator begin() { return t.begin(); }
    const_iterator begin() const { return t.begin(); }
    iterator end() { return t.end(); }
    const_iterator end() const { return t.end(); }
    reverse_iterator rbegin() { return t.rbegin(); }
    const_reverse_iterator rbegin() const { return t.rbegin(); }
    reverse_iterator rend() { return t.rend(); }
    const_reverse_iterator rend() const { return t.rend(); }
    // size
    bool empty() const { return t.empty(); }
    size_type size() const { return t.size(); }
    size_type max_size() const { return t.max_size(); }
    // 访问
    T& operator[](const key_type& k) {
        // 通过[]访问, 如何key不存在就insert
        return (*((insert(value_type(k, T()))).first)).second;
    }
    // 插入
    // rb tree::insert_unique
    pair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }
    iterator insert(iterator position, const value_type& x) { return t.insert_unique(position, x); }
    // 删除
    // rb tree::erase
    void erase(iterator position) { t.erase(position); }
    size_type erase(const key_type& x) { return t.erase(x); }
    // 查找
    // rb tree::find
    iterator find(const key_type& x) { return t.find(x); }
    // rb tree::count
    size_type count(const key_type& x) const { return t.count(x); }
    // rb tree::lower_bound
    iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
    // rb tree::upper_bound
    iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
}

MultiMap

Container

/*
    typedef Key key_type;
    typedef T data_type;
    typedef T mapped_type;
    typedef Compare key_compare;

    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;
*/
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class multimap {
    typedef pair<const Key, T> value_type;
    // select1st<value_type>
    typedef rb_tree<key_type, value_type, 
                  select1st<value_type>, key_compare, Alloc> rep_type;
    rep_type t;  // red-black tree representing multimap

    // iterator
    iterator begin() { return t.begin(); }
    const_iterator begin() const { return t.begin(); }
    iterator end() { return t.end(); }
    const_iterator end() const { return t.end(); }
    reverse_iterator rbegin() { return t.rbegin(); }
    const_reverse_iterator rbegin() const { return t.rbegin(); }
    reverse_iterator rend() { return t.rend(); }
    const_reverse_iterator rend() const { return t.rend(); }
    // size
    bool empty() const { return t.empty(); }
    size_type size() const { return t.size(); }
    size_type max_size() const { return t.max_size(); }
    // 访问
    // multimap不支持[]访问元素

    // 插入
    // rb tree::insert equal
    iterator insert(const value_type& x) { return t.insert_equal(x); }
    iterator insert(iterator position, const value_type& x) { return t.insert_equal(position, x); }
    // 删除
    // rb tree::erase
    void erase(iterator position) { t.erase(position); }
    size_type erase(const key_type& x) { return t.erase(x); }
    // 查找
    // rb tree::find
    iterator find(const key_type& x) { return t.find(x); }
    // rb tree::count
    size_type count(const key_type& x) const { return t.count(x); }
    // rb tree::lower_bound
    iterator lower_bound(const key_type& x) {return t.lower_bound(x); }
    // rb tree::upper_bound
    iterator upper_bound(const key_type& x) {return t.upper_bound(x); }
}