STL- Map&&Set

RB_Tree

​ 非公开，这是map,set的底层支撑。它在STL中的实现：

 struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;//指向树节点的指针
    typedef const _Rb_tree_node_base* _Const_Base_ptr;//同上但是是const型

    _Rb_tree_color  _M_color;//枚举类型，如下
    _Base_ptr       _M_parent;
    _Base_ptr       _M_left;
    _Base_ptr       _M_right;
  }
  enum _Rb_tree_color { _S_red = false, _S_black = true };//以上均可在mingw7.2.0中找到。
  //由于新版的_RB_tree有许多继承关系,这里直接贴出《STL源码解析》的RB_tree
template<class Key,
         class Value,
         class KeyOfValue,
         class Compare,
         class Alloc = alloc>
class rb_tree{//mingw7.2.0中为_Rb_tree
protected:
    typedef _rb_tree_node<Value> rb_tree_node;
public:
    typedef rb_tree_node* link_type;
protected:
    //红黑树以三个数据表现它
    size_type node_count;//节点数量
    link_type header;
    Compare key_compare;//key比较关系，是一个仿函数
}

有下图表示这个结构：

​ head并非是根节点，而是拥有指向最左端和最右端的指针的一个额外节点。而无论是map以及set他们的begin()以及end()都是以上图进行返回的。而迭代器的访问顺序正是在指定比较关系下的逻辑关系。

map&&set

​ 标准模板库中，除了sequence containers(序列式容器)，也有associative containers(关联式容器)。其中关联式容器包含setmapmultisetmultimap。这些容器的底层实现是红黑树，map以及set均有红黑树作为数据成员来实现各种功能。

​ map的模板参数;

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

​ map的值类型实际上是

typedef pair<const Key, T> value_type;

​ pair的定义如下:

template<typename _T1, typename _T2>
struct pair
{
    typedef _T1 first_type;    /// @c first_type is the first bound type
    typedef _T2 second_type;   /// @c second_type is the second bound type
    _T1 first;                 /// @c first is a copy of the first object
    _T2 second;                /// @c second is a copy of the second object
    //除此之外定义了各种重载，此处略
}

​ set的模板参数：

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

​ set并无映射值，只有key值。并且需要指定Compare类型（仿函数，key之间的比较关系），其中less是标准模板库中的仿函数：

 template<typename _Tp>
 struct less : public binary_function<_Tp, _Tp, bool>
 {
     bool
     operator()(const _Tp& __x, const _Tp& __y) const
     { return __x < __y; }
 };

map/set的具体使用如下：

构造、析构、赋值

构造

没有fill类型的构造函数(对于map,set，key是唯一的)

map：

set:

析构

map：~map();

set：~set();

赋值

map:

operator =

没有assign

set:

同样也没有assign

迭代器

​ map与set迭代函数一致：

​ 迭代器类型为Bidirectional Iterator：双向迭代器。其中map迭代器指向的是*typedef pair<const Key, T> value_type;*这种类型。而set指向的就是key_type。既然迭代器类型为双向迭代器。那么迭代器++，迭代器–，会分别去走向哪呢？是根据比较关系来确定++、–后的元素嘛？迭代器的顺序是key_type在compare仿函数定义的比较关系下的逻辑顺序。默认的less仿函数，就是递增的访问元素。因此递增访问迭代器，能得到按照key从小到大的排序。

​ 同样值得说明的是，begin()以及 end()它们到底指向哪一个元素，由之前的红黑树的实现图可清楚知道。

​ 另外，当尝试通过迭代器修改key值时（无论是map或set),编译器报错表达式必须是可修改的左值。实际上为了维护红黑树的正常结构。map与set的迭代器都做了处理使得不能通过迭代器去修改key值。但是对于map的Value值是可以通过迭代器修改的。

大小与修改

大小有关函数

修改内容

map:

set:除了没有那两个函数(try_emplace ，insert_or_assign)，其余功能一致，用法类似。

查找

map与set这些函数相同;

仿函数

参考文档上写的是observers(设计模式中的观察者模式？)。函数功能都是返回一个函数对象(仿函数，返回的是key的比较关系)。

multimap&&multiset

和map、set操作类似。最大的区别在于multimap和multiset可以存放相同key的元素。

Reference

[1]候捷，《STL源码解析》

[2]http://www.cplusplus.com/reference/map/

[3]http://www.cplusplus.com/reference/set/