[C++知识库]【c++从菜鸡到王者】第三篇：STL关联容器-Map

map

• map特性：所有的元素会根据元素的键值被排序，pair的所有元素都为键值，同时拥有键值和实值，pair的第一元素为键值，第二元素为实值，map不允许两个相同键值的元素存在。

  //pair的定义
  template<class T1,class T2>
  struct pair{
      typedef T1 first_type;
      typedef T2 secend_type;
      T1 first;
      T2 secend;
      pair():first(T1()),secend(T2()){}
      pair(const T1&a,const T2&b):first(a),senend(b){}
  }
  

• map不能修改其键值，这会破坏掉它的排序规则，但是可以修改实值

• 客户端对元素进行插入或者是删除操作时，其他元素的迭代器都是有效的，除了被删除的元素的迭代器除外

• 标准map底层是rb_tree，也存在以hash_map为底层的map，下面是map的参数推导

• //map的源码与set在操作行为方面都差不多，因为都是调用底层的红黑树，我这里只提供部分代码
  template<class Key,
           class T,
           class Compare = less<Key>,
           class Alloc = alloc>
  class map {
  public:
      typedef Key key_type;
      typedef T data_type;
      typedef T mapped_type;
      typedef pair<const Key, T> value_type;//主要区别
      typedef Compare key_compare;
  private:
      typedef rb_tree <key_type, 
      				 value_type, 
      				 select1st<value_type>, 
      				 key_compare, 
      				 Alloc> rep_type;
      rep_type t;		// 内部rb_tree容器
  public:
      typedef typename rep_type::iterator)
      iterator;
  }; 
  //map容器重载的[]运算符返回对应data的引用
  T& operator[](const key_value& k){
      return(*((insert(value_type(k,T()))).first)).secend;
  }
  //首先检查key是否存在，如果存在就直接返回对应的引用，若不存在就插入key,再返回对应的引用；
  //下标操作符的使用：可用作右值（内容不能被修改），也可用作左值，返回值采用引用
  //我们继续分析一下这个复杂的式子。首先我们根据键值和实值创建一个元素，但我们传入的是一个键值，所以我们产生了一个与实值类型相同的暂时对象T(),再通过insert将这个元素插入到map中。这时，insert操作返回的是一个pair，一个是迭代器，指向我们插入妥当的新元素，或者指向插入失败点的旧元素（因键值重复）。这时注意，如果我们的下标操作符是左值引用，表示我们要插入新值，这时我们恰好可以用“实值待填”的元素占位，如果是右值引用（通常是要根据键值取其实值），此时插入操作返回的pair的第一元素恰指向键值符合的元素。
  

• 注意

pair<iterator,bool>insert(const value_type& x){
    return t.insert_unique(x);
}
//这个函数返回的是一个pair由一个迭代器和一个bool组成，后者表示插入是否成功，如果成功，就返回一个指向该元素的迭代器。