Lines Matching defs:__x
101 _S_minimum(_Base_ptr __x)
103 while (__x->_M_left != 0) __x = __x->_M_left;
104 return __x;
108 _S_minimum(_Const_Base_ptr __x)
110 while (__x->_M_left != 0) __x = __x->_M_left;
111 return __x;
115 _S_maximum(_Base_ptr __x)
117 while (__x->_M_right != 0) __x = __x->_M_right;
118 return __x;
122 _S_maximum(_Const_Base_ptr __x)
124 while (__x->_M_right != 0) __x = __x->_M_right;
125 return __x;
144 _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
147 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
150 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
153 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
173 _Rb_tree_iterator(_Link_type __x)
174 : _M_node(__x) { }
216 operator==(const _Self& __x) const
217 { return _M_node == __x._M_node; }
220 operator!=(const _Self& __x) const
221 { return _M_node != __x._M_node; }
246 _Rb_tree_const_iterator(_Link_type __x)
247 : _M_node(__x) { }
297 operator==(const _Self& __x) const
298 { return _M_node == __x._M_node; }
301 operator!=(const _Self& __x) const
302 { return _M_node != __x._M_node; }
309 operator==(const _Rb_tree_iterator<_Val>& __x,
311 { return __x._M_node == __y._M_node; }
315 operator!=(const _Rb_tree_iterator<_Val>& __x,
317 { return __x._M_node != __y._M_node; }
321 _Rb_tree_node_base* __x,
377 _M_create_node(const value_type& __x)
382 (std::__addressof(__tmp->_M_value_field), __x); }
425 _M_clone_node(_Const_Link_type __x)
427 _Link_type __tmp = _M_create_node(__x->_M_value_field);
428 __tmp->_M_color = __x->_M_color;
518 _S_value(_Const_Link_type __x)
519 { return __x->_M_value_field; }
522 _S_key(_Const_Link_type __x)
523 { return _KeyOfValue()(_S_value(__x)); }
526 _S_left(_Base_ptr __x)
527 { return static_cast<_Link_type>(__x->_M_left); }
530 _S_left(_Const_Base_ptr __x)
531 { return static_cast<_Const_Link_type>(__x->_M_left); }
534 _S_right(_Base_ptr __x)
535 { return static_cast<_Link_type>(__x->_M_right); }
538 _S_right(_Const_Base_ptr __x)
539 { return static_cast<_Const_Link_type>(__x->_M_right); }
542 _S_value(_Const_Base_ptr __x)
543 { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
546 _S_key(_Const_Base_ptr __x)
547 { return _KeyOfValue()(_S_value(__x)); }
550 _S_minimum(_Base_ptr __x)
551 { return _Rb_tree_node_base::_S_minimum(__x); }
554 _S_minimum(_Const_Base_ptr __x)
555 { return _Rb_tree_node_base::_S_minimum(__x); }
558 _S_maximum(_Base_ptr __x)
559 { return _Rb_tree_node_base::_S_maximum(__x); }
562 _S_maximum(_Const_Base_ptr __x)
563 { return _Rb_tree_node_base::_S_maximum(__x); }
576 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
580 _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
584 _M_insert_equal_lower(_Arg&& __x);
587 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
593 _M_insert_lower(_Base_ptr __x
596 _M_insert_equal_lower(const value_type& __x);
600 _M_copy(_Const_Link_type __x, _Link_type __p);
603 _M_erase(_Link_type __x);
606 _M_lower_bound(_Link_type __x, _Link_type __y,
610 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
614 _M_upper_bound(_Link_type __x, _Link_type __y,
618 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
629 _Rb_tree(const _Rb_tree& __x)
630 : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
632 if (__x._M_root() != 0)
634 _M_root() = _M_copy(__x._M_begin(), _M_end());
637 _M_impl._M_node_count = __x._M_impl._M_node_count;
642 _Rb_tree(_Rb_tree&& __x);
649 operator=(const _Rb_tree& __x);
716 _M_insert_unique(_Arg&& __x);
720 _M_insert_equal(_Arg&& __x);
724 _M_insert_unique_(const_iterator __position, _Arg&& __x);
728 _M_insert_equal_(const_iterator __position, _Arg&& __x);
731 _M_insert_unique(const value_type& __x);
734 _M_insert_equal(const value_type& __x);
737 _M_insert_unique_(const_iterator __position, const value_type& __x);
740 _M_insert_equal_(const_iterator __position, const value_type& __x);
790 erase(const key_type& __x);
863 operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
866 return __x.size() == __y.size()
867 && std::equal(__x.begin(), __x.end(), __y.begin());
873 operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
876 return std::lexicographical_compare(__x.begin(), __x.end(),
883 operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
885 { return !(__x == __y); }
890 operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
892 { return __y < __x; }
897 operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
899 { return !(__y < __x); }
904 operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
906 { return !(__x < __y); }
911 swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
913 { __x.swap(__y); }
919 _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
920 : _M_impl(__x._M_impl._M_key_compare,
921 std::move(__x._M_get_Node_allocator()))
923 if (__x._M_root() != 0)
925 _M_root() = __x._M_root();
926 _M_leftmost() = __x._M_leftmost();
927 _M_rightmost() = __x._M_rightmost();
930 __x._M_root() = 0;
931 __x._M_leftmost() = __x._M_end();
932 __x._M_rightmost() = __x._M_end();
934 this->_M_impl._M_node_count = __x._M_impl._M_node_count;
935 __x._M_impl._M_node_count = 0;
944 operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
946 if (this != &__x)
950 _M_impl._M_key_compare = __x._M_impl._M_key_compare;
951 if (__x._M_root() != 0)
953 _M_root() = _M_copy(__x._M_begin(), _M_end());
956 _M_impl._M_node_count = __x._M_impl._M_node_count;
970 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
972 _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
975 bool __insert_left = (__x != 0 || __p == _M_end()
996 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
998 _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1001 bool __insert_left = (__x != 0 || __p == _M_end()
1026 _Link_type __x = _M_begin();
1028 while (__x != 0)
1030 __y = __x;
1031 __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1032 _S_left(__x) : _S_right(__x);
1034 return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1041 _M_copy(_Const_Link_type __x, _Link_type __p)
1043 // Structural copy. __x and __p must be non-null.
1044 _Link_type __top = _M_clone_node(__x);
1049 if (__x->_M_right)
1050 __top->_M_right = _M_copy(_S_right(__x), __top);
1052 __x = _S_left(__x);
1054 while (__x != 0)
1056 _Link_type __y = _M_clone_node(__x);
1059 if (__x->_M_right)
1060 __y->_M_right = _M_copy(_S_right(__x), __y);
1062 __x = _S_left(__x);
1077 _M_erase(_Link_type __x)
1080 while (__x != 0)
1082 _M_erase(_S_right(__x));
1083 _Link_type __y = _S_left(__x);
1084 _M_destroy_node(__x);
1085 __x = __y;
1094 _M_lower_bound(_Link_type __x, _Link_type __y,
1097 while (__x != 0)
1098 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1099 __y = __x, __x = _S_left(__x);
1101 __x = _S_right(__x);
1110 _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1113 while (__x != 0)
1114 if (!_M_impl._M_key_compare(_S_key(__x), __k))
1115 __y = __x, __x = _S_left(__x);
1117 __x = _S_right(__x);
1126 _M_upper_bound(_Link_type __x, _Link_type __y,
1129 while (__x != 0)
1130 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1131 __y = __x, __x = _S_left(__x);
1133 __x = _S_right(__x);
1142 _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1145 while (__x != 0)
1146 if (_M_impl._M_key_compare(__k, _S_key(__x)))
1147 __y = __x, __x = _S_left(__x);
1149 __x = _S_right(__x);
1162 _Link_type __x = _M_begin();
1164 while (__x != 0)
1166 if (_M_impl._M_key_compare(_S_key(__x), __k))
1167 __x = _S_right(__x);
1168 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1169 __y = __x, __x = _S_left(__x);
1172 _Link_type __xu(__x), __yu(__y);
1173 __y = __x, __x = _S_left(__x);
1176 iterator>(_M_lower_bound(__x, __y, __k),
1193 _Const_Link_type __x = _M_begin();
1195 while (__x != 0)
1197 if (_M_impl._M_key_compare(_S_key(__x), __k))
1198 __x = _S_right(__x);
1199 else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1200 __y = __x, __x = _S_left(__x);
1203 _Const_Link_type __xu(__x), __yu(__y);
1204 __y = __x, __x = _S_left(__x);
1207 const_iterator>(_M_lower_bound(__x, __y, __k),
1279 _Link_type __x = _M_begin();
1282 while (__x != 0)
1284 __y = __x;
1285 __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1286 __x = __comp ? _S_left(__x) : _S_right(__x);
1293 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1299 (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
1316 _Link_type __x = _M_begin();
1318 while (__x != 0)
1320 __y = __x;
1321 __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1322 _S_left(__x) : _S_right(__x);
1324 return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
1519 erase(const _Key& __x)
1521 pair<iterator, iterator> __p = equal_range(__x);
1591 _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1592 _Const_Link_type __L = _S_left(__x);
1593 _Const_Link_type __R = _S_right(__x);
1595 if (__x->_M_color == _S_red)
1600 if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1602 if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1605 if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
