STL关联式容器之multiset及multimap

multiset

        multiset的特性及用法和set 完成相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree的insert-equal()而非insert_unique().下面是multiset的源代码提要，只列出了与set的不同之处：

template<class Key, class Compare = less<Key>, class Alloc = alloc>
class multiset {
public:
    //typedefs:
    ... 与set相同

    template <class InputIterator>
    multiset(InputIterator first, InputIterator last)
     :t(Compare()) { t.insert_equal(first, last); }

    template<class InputIterator>
    multiset(InputIterator first, InputInterator last, const Compare& comp)
    :t(comp) {
        t.insert_equal(first, last);
    }

    iterator insert(const value_type&x ) {
        return t.insert_equal(x);
    }

    iterator insert(iterator position, const value_type&x) {
        typedef typename rep_type::iterator rep_iterator;
        return t.insert_equal((rep_iterator&)position, x);
    }

    template<class InputIterator>
    iterator insert(InputIterator first, InputIterator last ) {
        return t.insert_equal(first, last);
    }
    ...
};

multimap

        multimap的特性以及用法与map 完全相同，唯一差别在于它允许键值重复，因此它的插入操作采用的底层机制RB-tree的insert_equal而非insert_unique.下面是multimap的源代码摘要，只列出与map不同之处：

template<class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class multi map {
public :
    // typedefs 
    ... (与map相同)
    
    template <class InputIterator>
    multimap(InputIterator first, InputIterator last) 
    : t(Compare()) { t.insert_equal(first, last); }

    template <class InputIterator>
    multimap(InputIterator first, InputIterator last, Compare const& comp) 
    : t(comp) { t.insert_equal(first, last); }


    iterator insert(const value_type&x) { return t.insert_equal(x); }
    iterator insert(iterator position, cosnt value_type&x) {
        return t.insert_equal(position, x);
    }
    
    template<class InputIterator>
    void insert(InputIterator first, InputIterator last) {
        t.insert_equal(first, last);
    }
};

参考文档《STL源码剖析》--侯捷