+ if (__position._M_node == _M_rightmost())
+ return _M_insert(0, _M_rightmost(), __v);
+ else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
+ _KeyOfValue()(__v)))
+ {
+ if (_S_right(__position._M_node) == 0)
+ return _M_insert(0, __position._M_node, __v);
+ else
+ return _M_insert(__after._M_node, __after._M_node, __v);
+ }
+ else
+ return _M_insert_equal_lower(__v);
+ }
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_equal(const_iterator __position, const _Val& __v)
+ {
+ // end()
+ if (__position._M_node == _M_end())
+ {
+ if (size() > 0
+ && !_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key(_M_rightmost())))
+ return _M_insert(0, _M_rightmost(), __v);
+ else
+ return const_iterator(_M_insert_equal(__v));
+ }
+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
+ {
+ // First, try before...
+ const_iterator __before = __position;
+ if (__position._M_node == _M_leftmost()) // begin()
+ return _M_insert(_M_leftmost(), _M_leftmost(), __v);
+ else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key((--__before)._M_node)))
+ {
+ if (_S_right(__before._M_node) == 0)
+ return _M_insert(0, __before._M_node, __v);
+ else
+ return _M_insert(__position._M_node,
+ __position._M_node, __v);
+ }
+ else
+ return const_iterator(_M_insert_equal(__v));
+ }
+ else
+ {
+ // ... then try after.
+ const_iterator __after = __position;
+ if (__position._M_node == _M_rightmost())
+ return _M_insert(0, _M_rightmost(), __v);
+ else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
+ _KeyOfValue()(__v)))