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, 因此，对于复合类型， 比较容器必须重载 "<".