map源码分析
map可谓是最经常使用的关联容器，其实现同样基于红黑树。我们知道红黑树中一个节点保存一个value，其并没有明显的key，value概念，其在插入时比较的是value值的大小。因此我们需要对value和value的compare做一点小小的修改，这样便可以通过红黑树实现这种key，value的关联。
其实现过程类似如下代码：
我们将map的key, value作为一个整体setvalue，此setvalue便是set的value，之后重定义setvalue的compare行为，使其只比较key，经过这样的修改便通过set实现了map。
struct node {
int m_id;
string m_name;
node(int id, string name) : m_id(id), m_name(name) {};
};
struct nodeCompare {
bool operator()(const node& lhs, const node& rhs) const{
return lhs.m_id < rhs.m_id;
}
};
int main() {
set<node, nodeCompare> simpleMap;
simpleMap.insert({1, "LA"});
simpleMap.insert({2, "KA"});
simpleMap.insert({3, "DS"});
simpleMap.insert({4, "QW"});
simpleMap.insert({5, "PO"});
cout << simpleMap.find({1, ""})->m_name << endl;
cout << simpleMap.find({3, ""})->m_name << endl;
cout << simpleMap.find({5, ""})->m_name << endl;
cout << simpleMap.count({1, ""}) << endl;
simpleMap.erase({1, ""});
cout << simpleMap.count({1, ""}) << endl;
}
stl中的map实现了这种封装并提供了更为友好的接口，其定义如下
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; // 节点存储的值为{key， value}pair
typedef _Compare key_compare;
typedef _Alloc allocator_type;
private:
/// This turns a red-black tree into a [multi]map.
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
rebind<value_type>::other _Pair_alloc_type;
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; // 其内部依然存在_M_t
typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
public:
// many of these are specified differently in ISO, but the following are
// "functionally equivalent"
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
typedef typename _Rep_type::reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
此定义与set几乎一致，唯一的不同点在于红黑树的定义上，其value type为{_key, _Tp}的集合，而_Select1st<value_type>则是一个函数对象，用于获取value_type.first，也就是key。
/*
typedef _Key key_type;
typedef _Tp mapped_type;
typedef std::pair<const _Key, _Tp> value_type;
*/
typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
key_compare, _Pair_alloc_type> _Rep_type;
// _Select1st<value_type>定义
template<typename _Pair>
struct _Select1st
: public unary_function<_Pair, typename _Pair::first_type>
{
typename _Pair::first_type&
operator()(_Pair& __x) const
{ return __x.first; }
const typename _Pair::first_type&
operator()(const _Pair& __x) const
{ return __x.first; }
};
这里对比set的红黑树定义，可以更加理解传入参数的意义
/*
typedef _Key key_type;
typedef _Key value_type;
typedef _Compare key_compare;
*/
typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
key_compare, _Key_alloc_type> _Rep_type;
// _Identity<value_type>
template<typename _Tp>
struct _Identity
: public unary_function<_Tp,_Tp>
{
_Tp&
operator()(_Tp& __x) const
{ return __x; }
const _Tp&
operator()(const _Tp& __x) const
{ return __x; }
};
结合前面的两个例子和下面红黑树的定义，我们可以得出各个模板参数的意义：
_Key ： _val之间用于比较的key数据类型，其为_Val的内部数据变量
_Val ： 实际存储的数据类型
_KeyOfValue ： 函数对象，用于从_Val中提取_Key
_Compare ： 函数对象，_Key的比较函数
_Alloc :内存分配器
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >
class _Rb_tree
由此便得出红黑树节点在比较时并不是直接比较节点的值，而是通过_KeyOfValue获取节点的_Key，比较的是两个节点的key而不是节点的整个值。
container
set和map实质上并没有太大差别，所以其相关操作并不存在太大差别。
constructor
default constructor
map() = default;
range constructor
template<typename _InputIterator>
map(_InputIterator __first, _InputIterator __last,
const allocator_type& __a)
: _M_t(_Compare(), _Pair_alloc_type(__a))
{ _M_t._M_insert_unique(__first, __last); }
insert
std::pair<iterator,bool> insert( const value_type& value )
std::pair<iterator, bool>
insert(const value_type& __x)
{ return _M_t._M_insert_unique(__x); }
erase
iterator erase( const_iterator pos )
iterator
erase(const_iterator __position)
{ return _M_t.erase(__position); }
iterator erase( const_iterator first, const_iterator last )
iterator
erase(const_iterator __first, const_iterator __last)
{ return _M_t.erase(__first, __last); }
size_type erase( const key_type& key )
size_type
erase(const key_type& __x)
{ return _M_t.erase(__x); }
lookup
iterator find( const Key& key );
iterator
find(const key_type& __x)
{ return _M_t.find(__x); }
size_type count( const Key& key ) const;
size_type
count(const key_type& __x) const
{ return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
element access
T& operator[]( const Key& key )，其会判断内部是否有此元素，如果没有才会进行创建，函数实现如下
mapped_type&
operator[](const key_type& __k)
{
// concept requirements
__glibcxx_function_requires(_DefaultConstructibleConcept<mapped_type>)
iterator __i = lower_bound(__k); // lower_bound返回第一个不小于__k的元素迭代器
// __i->first is greater than or equivalent to __k.
if (__i == end() || key_comp()(__k, (*__i).first)) // 判断其是否存在重复元素
__i = insert(__i, value_type(__k, mapped_type())); // 构造的value，调用默认构造函数
return (*__i).second; // 返回插入元素的second索引
}
因此直接调用[]操作符将创建一个default value的{key，value}组合。
int main() {
map<int, string> mp;
mp[3];
cout << mp.count(3); // print 1
}
T& at( const Key& key )返回key对应value的reference，与map如果不存在则创建不同，当不存在时throw异常。
mapped_type&
at(const key_type& __k)
{
iterator __i = lower_bound(__k);
if (__i == end() || key_comp()(__k, (*__i).first))
__throw_out_of_range(__N("map::at")); //operator[] 为直接创建
return (*__i).second;
}
总结
红黑树对于其内部节点的定义不同于我们平常所认知的简单元素。其内部节点的元素可以划分为两个部分，一部分为Key，另一部分为Value。模板中为了从节点中提取Key，定义了函数对象_KeyOfValue，在每次比较时会从节点元素中调用此函数来获取Key进行比较。