STL map, multimap, set, multiset 函數介紹

說明：本博文中提到但為給出的例子參見 http://www.cplusplus.com/reference/

1. 類模闆和構造函數

和前面介紹的容器類似，可以通過類模闆參數指定 key 的比較類型和存儲器類型，通過構造函數參數指定比較類型對象和存儲器對象。

預設地使用 std:: less, std::allocator, 如 map:

less<Key>

allocator<pair<const Key,T> >

2. 疊代器與 begin(), end(), rbebin(), rend()

1. 關聯容器也可以通過疊代器通路，map 存儲的元素為 pair<key, value>, set 存儲的元素為 key.

2. 從 begin(), 到 end() 是按 key 值升序排列。

3. erase(), insert(), operator[]

3.1. erase()

可以指定 key 值删除，也可以指定疊代器删除。

3.2. insert()

(1) 傳回值：multimap, multiset 傳回新插入元素的疊代器，map, set 傳回新插入元素的疊代器或者已經存在的同 key 的元素的疊代器，對于第一種形式傳回值為 pair<iterator,bool> 類型， second 表示是否插入成功（key 重複則失敗）

(2) 指定“線索”（hint）優化插入操作

iterator insert (iterator position, const value_type& val);
           

并不是指定插入到哪裡，因為關聯容器是按照規則（如紅黑樹）插入的，插入位置是根據規則來的，那這個 position 參數是啥意思呢？

這個參數隻是給出了“線索”（hint），也就是說如果已知按照紅黑樹的算法規則，知道接下來的元素插入到哪裡，那麼指定這個參數就能加快操作，而不是從根節點一級級往下找插入點，換句話說，這個參數是起優化作用的。

3.3. operator[]

這個隻有 map 特有（想想為什麼？原因很簡單），即通過 map[key] = value 的方式插入

4. count(), find(), equal_range(), lower_bound(), upper_bound()

這幾個函數都有查找的功能，是以歸類在一起：

1. count() 為計算指定 key 值得元素有多少個，對于 map 和 set 而言是不是感覺這個函數有點奇怪，因為其值隻可能為 0 或 1.

2. find() 是通過指定 key 查找，傳回找到的第一個元素的疊代器，由于是有序的，是以對于 multimap 和 multiset 來說，結合 count() 就能通路所有找到的元素，當然對于 multimap 和 multiset 來說還有更好的方法，那就是 equal_range()

3. equal_range() 傳回一個找到的區間——pair<iterator,iterator> [first, second), 如：

key 值序列為 a b b b c d, equal_range(b) 的傳回結果為 first( lower_bound() ) = b1, second( upper_bound() ) = c

4. lower_bound(), upper_bound()

key 值序列為 a c c d e, lower_bound(b) = c1, upper_bound(d) = e

5. size(), max_size()

同 list ( http://blog.csdn.net/duyiwuer2009/article/details/23749363)

6. key_comp(), value_comp()

key_comp() 為傳回 key 的比較規則的對象，value_comp() 為傳回 value 的比較規則的對象。

1. 對于 set 和 multiset 來說，key 和 value 一樣，是以二者等同。 2.對于 map 和 multimap 來說，value 為 pair<key, value>, 見實作：

// bits/stl_map.h
template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{
public:
    typedef _Key                         key_type;
    typedef _Tp                          mapped_type;
    typedef std::pair<const _Key, _Tp>   value_type;
    typedef _Compare                     key_compare;
......

public:
    class value_compare
    : public std::binary_function<value_type, value_type, bool>
    {
        friend class map<_Key, _Tp, _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); }
    };
......
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
                key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;
......
};
           

value_compare 為 map 的 内部類，可以看出，最終還是使用的 key 的比較規則。

7. 重載關系操作符

對于 set 和 multiset 來說，兩個容器之間的比較規則跟前面介紹 deque, list 是一樣的； 對于 map 和multimap 來說，容器的元素為 pair, 是以，比較是基于 pair 的（pair 的比較見前一篇博文 http://blog.csdn.net/duyiwuer2009/article/details/23780041），把 pair<key, value> 看成一個元素（實質上就是），規則跟 deque, list 也是一樣的。 注意： 1. 這裡的比較值得是兩個容器之間的比較，不是容器内兩個元素之間的比較。這裡的“重載關系操作符”也指的是容器的關系操作符而非容器中的元素，而且重載操作是 STL 已經實作的，不需要使用者去管。

2. 比較兩個容器采用的是 lexicographical_compare, 是以，對于複合類型， 比較容器必須重載 "<".