作者:小爬虫 | 来源:互联网 | 2023-09-24 21:00
今天被同事问到一个问题,map中第三个参数的意思是什么,于是写了下面这个程序测试了一下。#include<map>#include<iostream>usingname
今天被同事问到一个问题,map中第三个参数的意思是什么,于是写了下面这个程序测试了一下。
#include
第三个参数MSDN的解释如下:
Traits
The type that provides a function object that can compare two element values as sort keys to determine their relative order in the map. This argument is optional and the binary predicate less is the default value.
MSDN上说的已经很清楚了,缺省的是 std::less
看stl_map.h中看map的定义:
template ,
typename _Alloc = std::allocator > >
class map
缺省的compare确实是std::less,std::less。在stl_function.h中std::less的实现如下:
template
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x <__y; }
};
return __x <__y;原来如此。但是这仅仅是比较函数,比较了之后map又是如何处理的呢?好像还是没有找到根源。
那就继续追踪,map的构造函数:
map()
: _M_t(_Compare(), allocator_type()) { }
用_Compare()初始化了_M_t,那就继续追踪_M_t,追踪到了map内部的红黑树。
typedef _Rb_tree,
key_compare, _Pair_alloc_type> _Rep_type;
/// @if maint The actual tree structure. @endif
_Rep_type _M_t;
最后到了insert_unique函数中:
template typename _Compare, typename _Alloc>
pair _Compare, _Alloc>::iterator, bool>
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(const _Val& __v)
{
_Link_type __x = _M_begin();
_Link_type __y = _M_end();
bool __comp = true;
while (__x != 0)
{
__y = __x;
__comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
if (__comp)
if (__j == begin())
return pair(_M_insert(__x, __y, __v), true);
else
--__j;
if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair(_M_insert(__x, __y, __v), true);
return pair(__j, false);
}
函数前面的返回值类型定义有点复杂,其实就是返回pair的pair,然后根据要插入的值__v来比较,如果是真,就往左边找,否则就往右边找。
template typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
_M_insert(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
{
bool __insert_left = (__x != 0 || __p == _M_end()
|| _M_impl._M_key_compare(_KeyOfValue()(__v),
_S_key(__p)));
_Link_type __z = _M_create_node(__v);
_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
this->_M_impl._M_header);
++_M_impl._M_node_count;
return iterator(__z);
}
找到位置之后,创建节点,然后插入到二叉平衡树(也就是红黑树)中。
哈哈哈,_Rb_tree_insert_and_rebalance找不到代码。居然在STLPort里面找到了下面的代码。
template class _Compare, class _Alloc> __iterator__
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_insert(_Rb_tree_node_base* __x_, _Rb_tree_node_base* __y_, const _Value& __v,
_Rb_tree_node_base* __w_)
{
_Link_type __w = (_Link_type) __w_;
_Link_type __x = (_Link_type) __x_;
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
if ( __y == this->_M_header._M_data ||
( __w == 0 && // If w != 0, the remainder fails to false
( __x != 0 || // If x != 0, the remainder succeeds to true
_M_key_compare( _KeyOfValue()(__v), _S_key(__y) ) )
)
) {
__z = _M_create_node(__v);
_S_left(__y) = __z; // also makes _M_leftmost() = __z
// when __y == _M_header
if (__y == this->_M_header._M_data) {
_M_root() = __z;
_M_rightmost() = __z;
}
else if (__y == _M_leftmost())
_M_leftmost() = __z; // maintain _M_leftmost() pointing to min node
}
else {
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z; // maintain _M_rightmost() pointing to max node
}
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0;
_Rb_global_inst::_Rebalance(__z, this->_M_header._M_data->_M_parent);
++_M_node_count;
return iterator(__z);
}