// RB tree implementation -*- C++ -*-
-// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.
// As a special exception, you may use this file as part of a free software
#include <bits/stl_function.h>
#include <bits/cpp_type_traits.h>
-namespace std
-{
+_GLIBCXX_BEGIN_NAMESPACE(std)
+
// Red-black tree class, designed for use in implementing STL
// associative containers (set, multiset, map, and multimap). The
// insertion and deletion algorithms are based on those in Cormen,
typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef _Rb_tree_node<_Tp>* _Link_type;
- _Rb_tree_iterator() { }
+ _Rb_tree_iterator()
+ : _M_node() { }
+ explicit
_Rb_tree_iterator(_Link_type __x)
: _M_node(__x) { }
typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
typedef const _Rb_tree_node<_Tp>* _Link_type;
- _Rb_tree_const_iterator() { }
+ _Rb_tree_const_iterator()
+ : _M_node() { }
+ explicit
_Rb_tree_const_iterator(_Link_type __x)
: _M_node(__x) { }
typedef ptrdiff_t difference_type;
typedef _Alloc allocator_type;
- allocator_type
- get_allocator() const
+ _Node_allocator&
+ _M_get_Node_allocator()
+ { return *static_cast<_Node_allocator*>(&this->_M_impl); }
+
+ const _Node_allocator&
+ _M_get_Node_allocator() const
{ return *static_cast<const _Node_allocator*>(&this->_M_impl); }
+ allocator_type
+ get_allocator() const
+ { return allocator_type(_M_get_Node_allocator()); }
+
protected:
_Rb_tree_node*
_M_get_node()
protected:
template<typename _Key_compare,
- bool _Is_pod_comparator = std::__is_pod<_Key_compare>::_M_type>
+ bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
struct _Rb_tree_impl : public _Node_allocator
{
_Key_compare _M_key_compare;
_Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
- : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
+ : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
+ _M_node_count(0)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
_Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(),
const _Key_compare& __comp = _Key_compare())
- : _Node_allocator(__a), _M_key_compare(__comp), _M_node_count(0)
+ : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
+ _M_node_count(0)
{
this->_M_header._M_color = _S_red;
this->_M_header._M_parent = 0;
_Const_Link_type
_M_begin() const
- { return static_cast<
- _Const_Link_type>(this->_M_impl._M_header._M_parent); }
+ {
+ return static_cast<_Const_Link_type>
+ (this->_M_impl._M_header._M_parent);
+ }
_Link_type
_M_end()
iterator
_M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 233. Insertion hints in associative containers.
+ iterator
+ _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
+
+ const_iterator
+ _M_insert(_Const_Base_ptr __x, _Const_Base_ptr __y,
+ const value_type& __v);
+
_Link_type
_M_copy(_Const_Link_type __x, _Link_type __p);
: _M_impl(__a, __comp)
{ }
- _Rb_tree(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
- : _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
+ _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
+ : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare)
{
if (__x._M_root() != 0)
{
~_Rb_tree()
{ _M_erase(_M_begin()); }
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
- operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x);
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
+ operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x);
// Accessors.
_Compare
iterator
begin()
- { return static_cast<_Link_type>(this->_M_impl._M_header._M_left); }
+ {
+ return iterator(static_cast<_Link_type>
+ (this->_M_impl._M_header._M_left));
+ }
const_iterator
begin() const
- { return static_cast<_Const_Link_type>(this->_M_impl._M_header._M_left); }
+ {
+ return const_iterator(static_cast<_Const_Link_type>
+ (this->_M_impl._M_header._M_left));
+ }
iterator
end()
- { return static_cast<_Link_type>(&this->_M_impl._M_header); }
+ { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
const_iterator
end() const
- { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
+ {
+ return const_iterator(static_cast<_Const_Link_type>
+ (&this->_M_impl._M_header));
+ }
reverse_iterator
rbegin()
size_type
max_size() const
- { return size_type(-1); }
+ { return get_allocator().max_size(); }
void
- swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t);
+ swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t);
// Insert/erase.
- pair<iterator,bool>
- insert_unique(const value_type& __x);
+ pair<iterator, bool>
+ _M_insert_unique(const value_type& __x);
+
+ iterator
+ _M_insert_equal(const value_type& __x);
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 233. Insertion hints in associative containers.
iterator
- insert_equal(const value_type& __x);
+ _M_insert_equal_lower(const value_type& __x);
iterator
- insert_unique(iterator __position, const value_type& __x);
+ _M_insert_unique(iterator __position, const value_type& __x);
+
+ const_iterator
+ _M_insert_unique(const_iterator __position, const value_type& __x);
iterator
- insert_equal(iterator __position, const value_type& __x);
+ _M_insert_equal(iterator __position, const value_type& __x);
+
+ const_iterator
+ _M_insert_equal(const_iterator __position, const value_type& __x);
template<typename _InputIterator>
- void
- insert_unique(_InputIterator __first, _InputIterator __last);
+ void
+ _M_insert_unique(_InputIterator __first, _InputIterator __last);
template<typename _InputIterator>
- void
- insert_equal(_InputIterator __first, _InputIterator __last);
+ void
+ _M_insert_equal(_InputIterator __first, _InputIterator __last);
void
erase(iterator __position);
+ void
+ erase(const_iterator __position);
+
size_type
erase(const key_type& __x);
erase(iterator __first, iterator __last);
void
+ erase(const_iterator __first, const_iterator __last);
+
+ void
erase(const key_type* __first, const key_type* __last);
void
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator==(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{
return __x.size() == __y.size()
- && equal(__x.begin(), __x.end(), __y.begin());
+ && std::equal(__x.begin(), __x.end(), __y.begin());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator<(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{
- return lexicographical_compare(__x.begin(), __x.end(),
- __y.begin(), __y.end());
+ return std::lexicographical_compare(__x.begin(), __x.end(),
+ __y.begin(), __y.end());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator!=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{ return !(__x == __y); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator>(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{ return __y < __x; }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator<=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{ return !(__y < __x); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline bool
- operator>=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{ return !(__x < __y); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline void
- swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x,
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __y)
+ swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
{ __x.swap(__y); }
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>&
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
- operator=(const _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __x)
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
{
if (this != &__x)
{
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_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);
- bool __insert_left;
- __insert_left = __x != 0 || __p == _M_end()
- || _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__p));
+ _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
+ this->_M_impl._M_header);
+ ++_M_impl._M_node_count;
+ return iterator(__z);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
+ {
+ bool __insert_left = (__x != 0 || __p == _M_end()
+ || !_M_impl._M_key_compare(_S_key(__p),
+ _KeyOfValue()(__v)));
+
+ _Link_type __z = _M_create_node(__v);
_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
this->_M_impl._M_header);
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
- insert_equal(const _Val& __v)
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert(_Const_Base_ptr __x, _Const_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,
+ const_cast<_Base_ptr>(__p),
+ this->_M_impl._M_header);
+ ++_M_impl._M_node_count;
+ return const_iterator(__z);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_equal(const _Val& __v)
{
_Link_type __x = _M_begin();
_Link_type __y = _M_end();
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_equal_lower(const _Val& __v)
+ {
+ _Link_type __x = _M_begin();
+ _Link_type __y = _M_end();
+ while (__x != 0)
+ {
+ __y = __x;
+ __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
+ _S_left(__x) : _S_right(__x);
+ }
+ return _M_insert_lower(__x, __y, __v);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
void
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
- swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
{
if (_M_root() == 0)
- {
- if (__t._M_root() != 0)
{
- _M_root() = __t._M_root();
- _M_leftmost() = __t._M_leftmost();
- _M_rightmost() = __t._M_rightmost();
- _M_root()->_M_parent = _M_end();
-
- __t._M_root() = 0;
- __t._M_leftmost() = __t._M_end();
- __t._M_rightmost() = __t._M_end();
+ if (__t._M_root() != 0)
+ {
+ _M_root() = __t._M_root();
+ _M_leftmost() = __t._M_leftmost();
+ _M_rightmost() = __t._M_rightmost();
+ _M_root()->_M_parent = _M_end();
+
+ __t._M_root() = 0;
+ __t._M_leftmost() = __t._M_end();
+ __t._M_rightmost() = __t._M_end();
+ }
}
- }
else if (__t._M_root() == 0)
- {
- __t._M_root() = _M_root();
- __t._M_leftmost() = _M_leftmost();
- __t._M_rightmost() = _M_rightmost();
- __t._M_root()->_M_parent = __t._M_end();
-
- _M_root() = 0;
- _M_leftmost() = _M_end();
- _M_rightmost() = _M_end();
- }
+ {
+ __t._M_root() = _M_root();
+ __t._M_leftmost() = _M_leftmost();
+ __t._M_rightmost() = _M_rightmost();
+ __t._M_root()->_M_parent = __t._M_end();
+
+ _M_root() = 0;
+ _M_leftmost() = _M_end();
+ _M_rightmost() = _M_end();
+ }
else
- {
- std::swap(_M_root(),__t._M_root());
- std::swap(_M_leftmost(),__t._M_leftmost());
- std::swap(_M_rightmost(),__t._M_rightmost());
-
- _M_root()->_M_parent = _M_end();
- __t._M_root()->_M_parent = __t._M_end();
- }
+ {
+ std::swap(_M_root(),__t._M_root());
+ std::swap(_M_leftmost(),__t._M_leftmost());
+ std::swap(_M_rightmost(),__t._M_rightmost());
+
+ _M_root()->_M_parent = _M_end();
+ __t._M_root()->_M_parent = __t._M_end();
+ }
// No need to swap header's color as it does not change.
std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
+
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 431. Swapping containers with unequal allocators.
+ std::__alloc_swap<_Node_allocator>::
+ _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
- bool>
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
- insert_unique(const _Val& __v)
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator, bool>
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_unique(const _Val& __v)
{
_Link_type __x = _M_begin();
_Link_type __y = _M_end();
else
--__j;
if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
- return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
- return pair<iterator,bool>(__j, false);
+ return pair<iterator, bool>(_M_insert(__x, __y, __v), true);
+ return pair<iterator, bool>(__j, false);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- insert_unique(iterator __position, const _Val& __v)
+ _M_insert_unique(iterator __position, const _Val& __v)
{
- if (__position._M_node == _M_leftmost())
+ // end()
+ if (__position._M_node == _M_end())
{
- // begin()
if (size() > 0
- && _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__position._M_node)))
- return _M_insert(__position._M_node, __position._M_node, __v);
- // First argument just needs to be non-null.
+ && _M_impl._M_key_compare(_S_key(_M_rightmost()),
+ _KeyOfValue()(__v)))
+ return _M_insert(0, _M_rightmost(), __v);
+ else
+ return _M_insert_unique(__v).first;
+ }
+ else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key(__position._M_node)))
+ {
+ // First, try before...
+ 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(_S_key((--__before)._M_node),
+ _KeyOfValue()(__v)))
+ {
+ 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 insert_unique(__v).first;
+ return _M_insert_unique(__v).first;
}
- else if (__position._M_node == _M_end())
+ else if (_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
{
- // end()
- if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
- _KeyOfValue()(__v)))
+ // ... then try after.
+ iterator __after = __position;
+ if (__position._M_node == _M_rightmost())
return _M_insert(0, _M_rightmost(), __v);
+ else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key((++__after)._M_node)))
+ {
+ 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 insert_unique(__v).first;
+ return _M_insert_unique(__v).first;
}
else
+ return __position; // Equivalent keys.
+ }
+
+ 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_unique(const_iterator __position, const _Val& __v)
+ {
+ // end()
+ if (__position._M_node == _M_end())
{
- iterator __before = __position;
- --__before;
- if (_M_impl._M_key_compare(_S_key(__before._M_node),
- _KeyOfValue()(__v))
- && _M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__position._M_node)))
+ if (size() > 0
+ && _M_impl._M_key_compare(_S_key(_M_rightmost()),
+ _KeyOfValue()(__v)))
+ return _M_insert(0, _M_rightmost(), __v);
+ else
+ return const_iterator(_M_insert_unique(__v).first);
+ }
+ else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key(__position._M_node)))
+ {
+ // 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(_S_key((--__before)._M_node),
+ _KeyOfValue()(__v)))
{
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);
- // First argument just needs to be non-null.
+ return _M_insert(__position._M_node,
+ __position._M_node, __v);
}
else
- return insert_unique(__v).first;
+ return const_iterator(_M_insert_unique(__v).first);
}
+ else if (_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
+ {
+ // ... 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(_KeyOfValue()(__v),
+ _S_key((++__after)._M_node)))
+ {
+ 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 const_iterator(_M_insert_unique(__v).first);
+ }
+ else
+ return __position; // Equivalent keys.
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
- insert_equal(iterator __position, const _Val& __v)
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_insert_equal(iterator __position, const _Val& __v)
{
- if (__position._M_node == _M_leftmost())
+ // end()
+ if (__position._M_node == _M_end())
{
- // begin()
if (size() > 0
- && !_M_impl._M_key_compare(_S_key(__position._M_node),
- _KeyOfValue()(__v)))
- return _M_insert(__position._M_node, __position._M_node, __v);
- // first argument just needs to be non-null
+ && !_M_impl._M_key_compare(_KeyOfValue()(__v),
+ _S_key(_M_rightmost())))
+ return _M_insert(0, _M_rightmost(), __v);
else
- return insert_equal(__v);
+ return _M_insert_equal(__v);
}
- else if (__position._M_node == _M_end())
+ else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
+ _KeyOfValue()(__v)))
{
- // end()
- if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(_M_rightmost())))
- return _M_insert(0, _M_rightmost(), __v);
+ // First, try before...
+ 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 insert_equal(__v);
+ return _M_insert_equal(__v);
}
else
{
- iterator __before = __position;
- --__before;
- if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
- _S_key(__before._M_node))
- && !_M_impl._M_key_compare(_S_key(__position._M_node),
- _KeyOfValue()(__v)))
+ // ... then try after.
+ 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)))
+ {
+ 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);
- // First argument just needs to be non-null.
+ 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)))
+ {
+ 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 insert_equal(__v);
+ return const_iterator(_M_insert_equal_lower(__v));
}
}
typename _Cmp, typename _Alloc>
template<class _II>
void
- _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
- insert_equal(_II __first, _II __last)
+ _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
+ _M_insert_equal(_II __first, _II __last)
{
- for ( ; __first != __last; ++__first)
- insert_equal(*__first);
+ for (; __first != __last; ++__first)
+ _M_insert_equal(end(), *__first);
}
template<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>
- void
- _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
- insert_unique(_II __first, _II __last)
+ void
+ _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
+ _M_insert_unique(_II __first, _II __last)
+ {
+ for (; __first != __last; ++__first)
+ _M_insert_unique(end(), *__first);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ inline void
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ erase(iterator __position)
{
- for ( ; __first != __last; ++__first)
- insert_unique(*__first);
+ _Link_type __y =
+ static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
+ (__position._M_node,
+ this->_M_impl._M_header));
+ destroy_node(__y);
+ --_M_impl._M_node_count;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline void
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ erase(const_iterator __position)
{
- _Link_type __y = static_cast<
- _Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
- this->_M_impl._M_header));
+ _Link_type __y =
+ static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
+ (const_cast<_Base_ptr>(__position._M_node),
+ this->_M_impl._M_header));
destroy_node(__y);
--_M_impl._M_node_count;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ erase(const _Key& __x)
{
pair<iterator,iterator> __p = equal_range(__x);
size_type __n = std::distance(__p.first, __p.second);
template<typename _Key, typename _Val, typename _KoV,
typename _Compare, typename _Alloc>
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
- _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
+ _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
_M_copy(_Const_Link_type __x, _Link_type __p)
{
// Structural copy. __x and __p must be non-null.
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
void
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_erase(_Link_type __x)
{
// Erase without rebalancing.
while (__x != 0)
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
void
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
erase(iterator __first, iterator __last)
{
if (__first == begin() && __last == end())
clear();
else
- while (__first != __last) erase(__first++);
+ while (__first != __last)
+ erase(__first++);
+ }
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ void
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ erase(const_iterator __first, const_iterator __last)
+ {
+ if (__first == begin() && __last == end())
+ clear();
+ else
+ while (__first != __last)
+ erase(__first++);
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
void
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
erase(const _Key* __first, const _Key* __last)
{
while (__first != __last)
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ find(const _Key& __k)
{
_Link_type __x = _M_begin(); // Current node.
_Link_type __y = _M_end(); // Last node which is not less than __k.
__x = _S_right(__x);
iterator __j = iterator(__y);
- return (__j == end()
- || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
+ return (__j == end()
+ || _M_impl._M_key_compare(__k,
+ _S_key(__j._M_node))) ? end() : __j;
}
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>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
find(const _Key& __k) const
{
_Const_Link_type __x = _M_begin(); // Current node.
__x = _S_right(__x);
}
const_iterator __j = const_iterator(__y);
- return (__j == end()
- || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
+ return (__j == end()
+ || _M_impl._M_key_compare(__k,
+ _S_key(__j._M_node))) ? end() : __j;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
count(const _Key& __k) const
{
pair<const_iterator, const_iterator> __p = equal_range(__k);
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
lower_bound(const _Key& __k)
{
_Link_type __x = _M_begin(); // Current node.
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>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
lower_bound(const _Key& __k) const
{
_Const_Link_type __x = _M_begin(); // Current node.
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
upper_bound(const _Key& __k)
{
_Link_type __x = _M_begin(); // Current node.
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>::
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
upper_bound(const _Key& __k) const
{
_Const_Link_type __x = _M_begin(); // Current node.
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
inline
- pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
- _Compare,_Alloc>::iterator,
- typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
- _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
+ pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
+ _Compare, _Alloc>::iterator,
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator>
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
equal_range(const _Key& __k)
{ return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }
return false;
return true;
}
-} // namespace std
+
+_GLIBCXX_END_NAMESPACE
#endif
OSDN Git Service
