Branch data Line data Source code
1 : : // RB tree implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001-2015 Free Software Foundation, Inc.
4 : : //
5 : : // This file is part of the GNU ISO C++ Library. This library is free
6 : : // software; you can redistribute it and/or modify it under the
7 : : // terms of the GNU General Public License as published by the
8 : : // Free Software Foundation; either version 3, or (at your option)
9 : : // any later version.
10 : :
11 : : // This library is distributed in the hope that it will be useful,
12 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : // GNU General Public License for more details.
15 : :
16 : : // Under Section 7 of GPL version 3, you are granted additional
17 : : // permissions described in the GCC Runtime Library Exception, version
18 : : // 3.1, as published by the Free Software Foundation.
19 : :
20 : : // You should have received a copy of the GNU General Public License and
21 : : // a copy of the GCC Runtime Library Exception along with this program;
22 : : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : : // <http://www.gnu.org/licenses/>.
24 : :
25 : : /*
26 : : *
27 : : * Copyright (c) 1996,1997
28 : : * Silicon Graphics Computer Systems, Inc.
29 : : *
30 : : * Permission to use, copy, modify, distribute and sell this software
31 : : * and its documentation for any purpose is hereby granted without fee,
32 : : * provided that the above copyright notice appear in all copies and
33 : : * that both that copyright notice and this permission notice appear
34 : : * in supporting documentation. Silicon Graphics makes no
35 : : * representations about the suitability of this software for any
36 : : * purpose. It is provided "as is" without express or implied warranty.
37 : : *
38 : : *
39 : : * Copyright (c) 1994
40 : : * Hewlett-Packard Company
41 : : *
42 : : * Permission to use, copy, modify, distribute and sell this software
43 : : * and its documentation for any purpose is hereby granted without fee,
44 : : * provided that the above copyright notice appear in all copies and
45 : : * that both that copyright notice and this permission notice appear
46 : : * in supporting documentation. Hewlett-Packard Company makes no
47 : : * representations about the suitability of this software for any
48 : : * purpose. It is provided "as is" without express or implied warranty.
49 : : *
50 : : *
51 : : */
52 : :
53 : : /** @file bits/stl_tree.h
54 : : * This is an internal header file, included by other library headers.
55 : : * Do not attempt to use it directly. @headername{map,set}
56 : : */
57 : :
58 : : #ifndef _STL_TREE_H
59 : : #define _STL_TREE_H 1
60 : :
61 : : #pragma GCC system_header
62 : :
63 : : #include <bits/stl_algobase.h>
64 : : #include <bits/allocator.h>
65 : : #include <bits/stl_function.h>
66 : : #include <bits/cpp_type_traits.h>
67 : : #include <ext/alloc_traits.h>
68 : : #if __cplusplus >= 201103L
69 : : #include <ext/aligned_buffer.h>
70 : : #endif
71 : :
72 : : namespace std _GLIBCXX_VISIBILITY(default)
73 : : {
74 : : _GLIBCXX_BEGIN_NAMESPACE_VERSION
75 : :
76 : : // Red-black tree class, designed for use in implementing STL
77 : : // associative containers (set, multiset, map, and multimap). The
78 : : // insertion and deletion algorithms are based on those in Cormen,
79 : : // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
80 : : // 1990), except that
81 : : //
82 : : // (1) the header cell is maintained with links not only to the root
83 : : // but also to the leftmost node of the tree, to enable constant
84 : : // time begin(), and to the rightmost node of the tree, to enable
85 : : // linear time performance when used with the generic set algorithms
86 : : // (set_union, etc.)
87 : : //
88 : : // (2) when a node being deleted has two children its successor node
89 : : // is relinked into its place, rather than copied, so that the only
90 : : // iterators invalidated are those referring to the deleted node.
91 : :
92 : : enum _Rb_tree_color { _S_red = false, _S_black = true };
93 : :
94 : : struct _Rb_tree_node_base
95 : : {
96 : : typedef _Rb_tree_node_base* _Base_ptr;
97 : : typedef const _Rb_tree_node_base* _Const_Base_ptr;
98 : :
99 : : _Rb_tree_color _M_color;
100 : : _Base_ptr _M_parent;
101 : : _Base_ptr _M_left;
102 : : _Base_ptr _M_right;
103 : :
104 : : static _Base_ptr
105 : : _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
106 : : {
107 : : while (__x->_M_left != 0) __x = __x->_M_left;
108 : : return __x;
109 : : }
110 : :
111 : : static _Const_Base_ptr
112 : : _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
113 : : {
114 : : while (__x->_M_left != 0) __x = __x->_M_left;
115 : : return __x;
116 : : }
117 : :
118 : : static _Base_ptr
119 : : _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
120 : : {
121 : : while (__x->_M_right != 0) __x = __x->_M_right;
122 : : return __x;
123 : : }
124 : :
125 : : static _Const_Base_ptr
126 : : _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
127 : : {
128 : : while (__x->_M_right != 0) __x = __x->_M_right;
129 : : return __x;
130 : : }
131 : : };
132 : :
133 : : template<typename _Val>
134 : : struct _Rb_tree_node : public _Rb_tree_node_base
135 : : {
136 : : typedef _Rb_tree_node<_Val>* _Link_type;
137 : :
138 : : #if __cplusplus < 201103L
139 : : _Val _M_value_field;
140 : :
141 : : _Val*
142 : : _M_valptr()
143 : : { return std::__addressof(_M_value_field); }
144 : :
145 : : const _Val*
146 : : _M_valptr() const
147 : : { return std::__addressof(_M_value_field); }
148 : : #else
149 : : __gnu_cxx::__aligned_membuf<_Val> _M_storage;
150 : :
151 : : _Val*
152 : : _M_valptr()
153 : : { return _M_storage._M_ptr(); }
154 : :
155 : : const _Val*
156 : : _M_valptr() const
157 : : { return _M_storage._M_ptr(); }
158 : : #endif
159 : : };
160 : :
161 : : _GLIBCXX_PURE _Rb_tree_node_base*
162 : : _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
163 : :
164 : : _GLIBCXX_PURE const _Rb_tree_node_base*
165 : : _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
166 : :
167 : : _GLIBCXX_PURE _Rb_tree_node_base*
168 : : _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
169 : :
170 : : _GLIBCXX_PURE const _Rb_tree_node_base*
171 : : _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
172 : :
173 : : template<typename _Tp>
174 : : struct _Rb_tree_iterator
175 : : {
176 : : typedef _Tp value_type;
177 : : typedef _Tp& reference;
178 : : typedef _Tp* pointer;
179 : :
180 : : typedef bidirectional_iterator_tag iterator_category;
181 : : typedef ptrdiff_t difference_type;
182 : :
183 : : typedef _Rb_tree_iterator<_Tp> _Self;
184 : : typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
185 : : typedef _Rb_tree_node<_Tp>* _Link_type;
186 : :
187 : : _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
188 : : : _M_node() { }
189 : :
190 : : explicit
191 : : _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
192 : : : _M_node(__x) { }
193 : :
194 : : reference
195 : : operator*() const _GLIBCXX_NOEXCEPT
196 : : { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
197 : :
198 : : pointer
199 : : operator->() const _GLIBCXX_NOEXCEPT
200 : : { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
201 : :
202 : : _Self&
203 : : operator++() _GLIBCXX_NOEXCEPT
204 : : {
205 : 0 : _M_node = _Rb_tree_increment(_M_node);
206 : : return *this;
207 : : }
208 : :
209 : : _Self
210 : : operator++(int) _GLIBCXX_NOEXCEPT
211 : : {
212 : : _Self __tmp = *this;
213 : 0 : _M_node = _Rb_tree_increment(_M_node);
214 : : return __tmp;
215 : : }
216 : :
217 : : _Self&
218 : : operator--() _GLIBCXX_NOEXCEPT
219 : : {
220 : 0 : _M_node = _Rb_tree_decrement(_M_node);
221 : : return *this;
222 : : }
223 : :
224 : : _Self
225 : : operator--(int) _GLIBCXX_NOEXCEPT
226 : : {
227 : : _Self __tmp = *this;
228 : : _M_node = _Rb_tree_decrement(_M_node);
229 : : return __tmp;
230 : : }
231 : :
232 : : bool
233 : : operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
234 : : { return _M_node == __x._M_node; }
235 : :
236 : : bool
237 : : operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
238 : 0 : { return _M_node != __x._M_node; }
239 : :
240 : : _Base_ptr _M_node;
241 : : };
242 : :
243 : : template<typename _Tp>
244 : : struct _Rb_tree_const_iterator
245 : : {
246 : : typedef _Tp value_type;
247 : : typedef const _Tp& reference;
248 : : typedef const _Tp* pointer;
249 : :
250 : : typedef _Rb_tree_iterator<_Tp> iterator;
251 : :
252 : : typedef bidirectional_iterator_tag iterator_category;
253 : : typedef ptrdiff_t difference_type;
254 : :
255 : : typedef _Rb_tree_const_iterator<_Tp> _Self;
256 : : typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
257 : : typedef const _Rb_tree_node<_Tp>* _Link_type;
258 : :
259 : : _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
260 : : : _M_node() { }
261 : :
262 : : explicit
263 : : _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
264 : : : _M_node(__x) { }
265 : :
266 : : _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
267 : 0 : : _M_node(__it._M_node) { }
268 : :
269 : : iterator
270 : : _M_const_cast() const _GLIBCXX_NOEXCEPT
271 : 0 : { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
272 : :
273 : : reference
274 : : operator*() const _GLIBCXX_NOEXCEPT
275 : : { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
276 : :
277 : : pointer
278 : : operator->() const _GLIBCXX_NOEXCEPT
279 : : { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
280 : :
281 : : _Self&
282 : : operator++() _GLIBCXX_NOEXCEPT
283 : : {
284 : : _M_node = _Rb_tree_increment(_M_node);
285 : : return *this;
286 : : }
287 : :
288 : : _Self
289 : : operator++(int) _GLIBCXX_NOEXCEPT
290 : : {
291 : : _Self __tmp = *this;
292 : : _M_node = _Rb_tree_increment(_M_node);
293 : : return __tmp;
294 : : }
295 : :
296 : : _Self&
297 : : operator--() _GLIBCXX_NOEXCEPT
298 : : {
299 : : _M_node = _Rb_tree_decrement(_M_node);
300 : : return *this;
301 : : }
302 : :
303 : : _Self
304 : : operator--(int) _GLIBCXX_NOEXCEPT
305 : : {
306 : : _Self __tmp = *this;
307 : : _M_node = _Rb_tree_decrement(_M_node);
308 : : return __tmp;
309 : : }
310 : :
311 : : bool
312 : : operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
313 : : { return _M_node == __x._M_node; }
314 : :
315 : : bool
316 : : operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
317 : : { return _M_node != __x._M_node; }
318 : :
319 : : _Base_ptr _M_node;
320 : : };
321 : :
322 : : template<typename _Val>
323 : : inline bool
324 : : operator==(const _Rb_tree_iterator<_Val>& __x,
325 : : const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
326 : : { return __x._M_node == __y._M_node; }
327 : :
328 : : template<typename _Val>
329 : : inline bool
330 : : operator!=(const _Rb_tree_iterator<_Val>& __x,
331 : : const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
332 : : { return __x._M_node != __y._M_node; }
333 : :
334 : : void
335 : : _Rb_tree_insert_and_rebalance(const bool __insert_left,
336 : : _Rb_tree_node_base* __x,
337 : : _Rb_tree_node_base* __p,
338 : : _Rb_tree_node_base& __header) throw ();
339 : :
340 : : _Rb_tree_node_base*
341 : : _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
342 : : _Rb_tree_node_base& __header) throw ();
343 : :
344 : :
345 : : template<typename _Key, typename _Val, typename _KeyOfValue,
346 : : typename _Compare, typename _Alloc = allocator<_Val> >
347 : : class _Rb_tree
348 : : {
349 : : typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
350 : : rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
351 : :
352 : : typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
353 : :
354 : : protected:
355 : : typedef _Rb_tree_node_base* _Base_ptr;
356 : : typedef const _Rb_tree_node_base* _Const_Base_ptr;
357 : : typedef _Rb_tree_node<_Val>* _Link_type;
358 : : typedef const _Rb_tree_node<_Val>* _Const_Link_type;
359 : :
360 : : private:
361 : : // Functor recycling a pool of nodes and using allocation once the pool
362 : : // is empty.
363 : : struct _Reuse_or_alloc_node
364 : : {
365 : : _Reuse_or_alloc_node(_Rb_tree& __t)
366 : : : _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
367 : : {
368 : : if (_M_root)
369 : : {
370 : : _M_root->_M_parent = 0;
371 : :
372 : : if (_M_nodes->_M_left)
373 : : _M_nodes = _M_nodes->_M_left;
374 : : }
375 : : else
376 : : _M_nodes = 0;
377 : : }
378 : :
379 : : #if __cplusplus >= 201103L
380 : : _Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
381 : : #endif
382 : :
383 : : ~_Reuse_or_alloc_node()
384 : : { _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
385 : :
386 : : template<typename _Arg>
387 : : _Link_type
388 : : #if __cplusplus < 201103L
389 : : operator()(const _Arg& __arg)
390 : : #else
391 : : operator()(_Arg&& __arg)
392 : : #endif
393 : : {
394 : : _Link_type __node = static_cast<_Link_type>(_M_extract());
395 : : if (__node)
396 : : {
397 : : _M_t._M_destroy_node(__node);
398 : : _M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
399 : : return __node;
400 : : }
401 : :
402 : : return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
403 : : }
404 : :
405 : : private:
406 : : _Base_ptr
407 : : _M_extract()
408 : : {
409 : : if (!_M_nodes)
410 : : return _M_nodes;
411 : :
412 : : _Base_ptr __node = _M_nodes;
413 : : _M_nodes = _M_nodes->_M_parent;
414 : : if (_M_nodes)
415 : : {
416 : : if (_M_nodes->_M_right == __node)
417 : : {
418 : : _M_nodes->_M_right = 0;
419 : :
420 : : if (_M_nodes->_M_left)
421 : : {
422 : : _M_nodes = _M_nodes->_M_left;
423 : :
424 : : while (_M_nodes->_M_right)
425 : : _M_nodes = _M_nodes->_M_right;
426 : :
427 : : if (_M_nodes->_M_left)
428 : : _M_nodes = _M_nodes->_M_left;
429 : : }
430 : : }
431 : : else // __node is on the left.
432 : : _M_nodes->_M_left = 0;
433 : : }
434 : : else
435 : : _M_root = 0;
436 : :
437 : : return __node;
438 : : }
439 : :
440 : : _Base_ptr _M_root;
441 : : _Base_ptr _M_nodes;
442 : : _Rb_tree& _M_t;
443 : : };
444 : :
445 : : // Functor similar to the previous one but without any pool of nodes to
446 : : // recycle.
447 : : struct _Alloc_node
448 : : {
449 : : _Alloc_node(_Rb_tree& __t)
450 : 0 : : _M_t(__t) { }
451 : :
452 : : template<typename _Arg>
453 : : _Link_type
454 : : #if __cplusplus < 201103L
455 : : operator()(const _Arg& __arg) const
456 : : #else
457 : : operator()(_Arg&& __arg) const
458 : : #endif
459 : : { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
460 : :
461 : : private:
462 : : _Rb_tree& _M_t;
463 : : };
464 : :
465 : : public:
466 : : typedef _Key key_type;
467 : : typedef _Val value_type;
468 : : typedef value_type* pointer;
469 : : typedef const value_type* const_pointer;
470 : : typedef value_type& reference;
471 : : typedef const value_type& const_reference;
472 : : typedef size_t size_type;
473 : : typedef ptrdiff_t difference_type;
474 : : typedef _Alloc allocator_type;
475 : :
476 : : _Node_allocator&
477 : : _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
478 : : { return *static_cast<_Node_allocator*>(&this->_M_impl); }
479 : :
480 : : const _Node_allocator&
481 : : _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
482 : : { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
483 : :
484 : : allocator_type
485 : : get_allocator() const _GLIBCXX_NOEXCEPT
486 : : { return allocator_type(_M_get_Node_allocator()); }
487 : :
488 : : protected:
489 : : _Link_type
490 : : _M_get_node()
491 : : { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
492 : :
493 : : void
494 : : _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
495 : : { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
496 : :
497 : : #if __cplusplus < 201103L
498 : : void
499 : : _M_construct_node(_Link_type __node, const value_type& __x)
500 : : {
501 : : __try
502 : : { get_allocator().construct(__node->_M_valptr(), __x); }
503 : : __catch(...)
504 : : {
505 : : _M_put_node(__node);
506 : : __throw_exception_again;
507 : : }
508 : : }
509 : :
510 : : _Link_type
511 : : _M_create_node(const value_type& __x)
512 : : {
513 : : _Link_type __tmp = _M_get_node();
514 : : _M_construct_node(__tmp, __x);
515 : : return __tmp;
516 : : }
517 : :
518 : : void
519 : : _M_destroy_node(_Link_type __p)
520 : : { get_allocator().destroy(__p->_M_valptr()); }
521 : : #else
522 : : template<typename... _Args>
523 : : void
524 : : _M_construct_node(_Link_type __node, _Args&&... __args)
525 : : {
526 : : __try
527 : : {
528 : : ::new(__node) _Rb_tree_node<_Val>;
529 : : _Alloc_traits::construct(_M_get_Node_allocator(),
530 : : __node->_M_valptr(),
531 : : std::forward<_Args>(__args)...);
532 : : }
533 : : __catch(...)
534 : : {
535 : : __node->~_Rb_tree_node<_Val>();
536 : : _M_put_node(__node);
537 : : __throw_exception_again;
538 : : }
539 : : }
540 : :
541 : : template<typename... _Args>
542 : : _Link_type
543 : : _M_create_node(_Args&&... __args)
544 : : {
545 : : _Link_type __tmp = _M_get_node();
546 : : _M_construct_node(__tmp, std::forward<_Args>(__args)...);
547 : : return __tmp;
548 : : }
549 : :
550 : : void
551 : : _M_destroy_node(_Link_type __p) noexcept
552 : : {
553 : : _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
554 : : __p->~_Rb_tree_node<_Val>();
555 : : }
556 : : #endif
557 : :
558 : : void
559 : : _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
560 : : {
561 : : _M_destroy_node(__p);
562 : : _M_put_node(__p);
563 : : }
564 : :
565 : : template<typename _NodeGen>
566 : : _Link_type
567 : : _M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
568 : : {
569 : : _Link_type __tmp = __node_gen(*__x->_M_valptr());
570 : : __tmp->_M_color = __x->_M_color;
571 : : __tmp->_M_left = 0;
572 : : __tmp->_M_right = 0;
573 : : return __tmp;
574 : : }
575 : :
576 : : protected:
577 : : // Unused _Is_pod_comparator is kept as it is part of mangled name.
578 : : template<typename _Key_compare,
579 : : bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
580 : 0 : struct _Rb_tree_impl : public _Node_allocator
581 : : {
582 : : _Key_compare _M_key_compare;
583 : : _Rb_tree_node_base _M_header;
584 : : size_type _M_node_count; // Keeps track of size of tree.
585 : :
586 : : _Rb_tree_impl()
587 : : : _Node_allocator(), _M_key_compare(), _M_header(),
588 : 0 : _M_node_count(0)
589 : : { _M_initialize(); }
590 : :
591 : : _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
592 : : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
593 : : _M_node_count(0)
594 : : { _M_initialize(); }
595 : :
596 : : #if __cplusplus >= 201103L
597 : : _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
598 : : : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
599 : : _M_header(), _M_node_count(0)
600 : : { _M_initialize(); }
601 : : #endif
602 : :
603 : : void
604 : : _M_reset()
605 : : {
606 : : this->_M_header._M_parent = 0;
607 : : this->_M_header._M_left = &this->_M_header;
608 : : this->_M_header._M_right = &this->_M_header;
609 : : this->_M_node_count = 0;
610 : : }
611 : :
612 : : private:
613 : : void
614 : : _M_initialize()
615 : : {
616 : : this->_M_header._M_color = _S_red;
617 : : this->_M_header._M_parent = 0;
618 : 0 : this->_M_header._M_left = &this->_M_header;
619 : 0 : this->_M_header._M_right = &this->_M_header;
620 : : }
621 : : };
622 : :
623 : : _Rb_tree_impl<_Compare> _M_impl;
624 : :
625 : : protected:
626 : : _Base_ptr&
627 : : _M_root() _GLIBCXX_NOEXCEPT
628 : : { return this->_M_impl._M_header._M_parent; }
629 : :
630 : : _Const_Base_ptr
631 : : _M_root() const _GLIBCXX_NOEXCEPT
632 : : { return this->_M_impl._M_header._M_parent; }
633 : :
634 : : _Base_ptr&
635 : : _M_leftmost() _GLIBCXX_NOEXCEPT
636 : : { return this->_M_impl._M_header._M_left; }
637 : :
638 : : _Const_Base_ptr
639 : : _M_leftmost() const _GLIBCXX_NOEXCEPT
640 : : { return this->_M_impl._M_header._M_left; }
641 : :
642 : : _Base_ptr&
643 : : _M_rightmost() _GLIBCXX_NOEXCEPT
644 : : { return this->_M_impl._M_header._M_right; }
645 : :
646 : : _Const_Base_ptr
647 : : _M_rightmost() const _GLIBCXX_NOEXCEPT
648 : : { return this->_M_impl._M_header._M_right; }
649 : :
650 : : _Link_type
651 : : _M_begin() _GLIBCXX_NOEXCEPT
652 : : { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
653 : :
654 : : _Const_Link_type
655 : : _M_begin() const _GLIBCXX_NOEXCEPT
656 : : {
657 : : return static_cast<_Const_Link_type>
658 : : (this->_M_impl._M_header._M_parent);
659 : : }
660 : :
661 : : _Link_type
662 : : _M_end() _GLIBCXX_NOEXCEPT
663 : 0 : { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
664 : :
665 : : _Const_Link_type
666 : : _M_end() const _GLIBCXX_NOEXCEPT
667 : : { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
668 : :
669 : : static const_reference
670 : : _S_value(_Const_Link_type __x)
671 : : { return *__x->_M_valptr(); }
672 : :
673 : : static const _Key&
674 : : _S_key(_Const_Link_type __x)
675 : : { return _KeyOfValue()(_S_value(__x)); }
676 : :
677 : : static _Link_type
678 : : _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
679 : : { return static_cast<_Link_type>(__x->_M_left); }
680 : :
681 : : static _Const_Link_type
682 : : _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
683 : : { return static_cast<_Const_Link_type>(__x->_M_left); }
684 : :
685 : : static _Link_type
686 : : _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
687 : : { return static_cast<_Link_type>(__x->_M_right); }
688 : :
689 : : static _Const_Link_type
690 : : _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
691 : : { return static_cast<_Const_Link_type>(__x->_M_right); }
692 : :
693 : : static const_reference
694 : : _S_value(_Const_Base_ptr __x)
695 : : { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
696 : :
697 : : static const _Key&
698 : : _S_key(_Const_Base_ptr __x)
699 : : { return _KeyOfValue()(_S_value(__x)); }
700 : :
701 : : static _Base_ptr
702 : : _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
703 : : { return _Rb_tree_node_base::_S_minimum(__x); }
704 : :
705 : : static _Const_Base_ptr
706 : : _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
707 : : { return _Rb_tree_node_base::_S_minimum(__x); }
708 : :
709 : : static _Base_ptr
710 : : _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
711 : : { return _Rb_tree_node_base::_S_maximum(__x); }
712 : :
713 : : static _Const_Base_ptr
714 : : _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
715 : : { return _Rb_tree_node_base::_S_maximum(__x); }
716 : :
717 : : public:
718 : : typedef _Rb_tree_iterator<value_type> iterator;
719 : : typedef _Rb_tree_const_iterator<value_type> const_iterator;
720 : :
721 : : typedef std::reverse_iterator<iterator> reverse_iterator;
722 : : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
723 : :
724 : : private:
725 : : pair<_Base_ptr, _Base_ptr>
726 : : _M_get_insert_unique_pos(const key_type& __k);
727 : :
728 : : pair<_Base_ptr, _Base_ptr>
729 : : _M_get_insert_equal_pos(const key_type& __k);
730 : :
731 : : pair<_Base_ptr, _Base_ptr>
732 : : _M_get_insert_hint_unique_pos(const_iterator __pos,
733 : : const key_type& __k);
734 : :
735 : : pair<_Base_ptr, _Base_ptr>
736 : : _M_get_insert_hint_equal_pos(const_iterator __pos,
737 : : const key_type& __k);
738 : :
739 : : #if __cplusplus >= 201103L
740 : : template<typename _Arg, typename _NodeGen>
741 : : iterator
742 : : _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
743 : :
744 : : iterator
745 : : _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
746 : :
747 : : template<typename _Arg>
748 : : iterator
749 : : _M_insert_lower(_Base_ptr __y, _Arg&& __v);
750 : :
751 : : template<typename _Arg>
752 : : iterator
753 : : _M_insert_equal_lower(_Arg&& __x);
754 : :
755 : : iterator
756 : : _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
757 : :
758 : : iterator
759 : : _M_insert_equal_lower_node(_Link_type __z);
760 : : #else
761 : : template<typename _NodeGen>
762 : : iterator
763 : : _M_insert_(_Base_ptr __x, _Base_ptr __y,
764 : : const value_type& __v, _NodeGen&);
765 : :
766 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
767 : : // 233. Insertion hints in associative containers.
768 : : iterator
769 : : _M_insert_lower(_Base_ptr __y, const value_type& __v);
770 : :
771 : : iterator
772 : : _M_insert_equal_lower(const value_type& __x);
773 : : #endif
774 : :
775 : : template<typename _NodeGen>
776 : : _Link_type
777 : : _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&);
778 : :
779 : : _Link_type
780 : : _M_copy(_Const_Link_type __x, _Link_type __p)
781 : : {
782 : : _Alloc_node __an(*this);
783 : : return _M_copy(__x, __p, __an);
784 : : }
785 : :
786 : : void
787 : : _M_erase(_Link_type __x);
788 : :
789 : : iterator
790 : : _M_lower_bound(_Link_type __x, _Link_type __y,
791 : : const _Key& __k);
792 : :
793 : : const_iterator
794 : : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
795 : : const _Key& __k) const;
796 : :
797 : : iterator
798 : : _M_upper_bound(_Link_type __x, _Link_type __y,
799 : : const _Key& __k);
800 : :
801 : : const_iterator
802 : : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
803 : : const _Key& __k) const;
804 : :
805 : : public:
806 : : // allocation/deallocation
807 : : _Rb_tree() { }
808 : :
809 : : _Rb_tree(const _Compare& __comp,
810 : : const allocator_type& __a = allocator_type())
811 : : : _M_impl(__comp, _Node_allocator(__a)) { }
812 : :
813 : : _Rb_tree(const _Rb_tree& __x)
814 : : : _M_impl(__x._M_impl._M_key_compare,
815 : : _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
816 : : {
817 : : if (__x._M_root() != 0)
818 : : {
819 : : _M_root() = _M_copy(__x._M_begin(), _M_end());
820 : : _M_leftmost() = _S_minimum(_M_root());
821 : : _M_rightmost() = _S_maximum(_M_root());
822 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
823 : : }
824 : : }
825 : :
826 : : #if __cplusplus >= 201103L
827 : : _Rb_tree(const allocator_type& __a)
828 : : : _M_impl(_Compare(), _Node_allocator(__a))
829 : : { }
830 : :
831 : : _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
832 : : : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
833 : : {
834 : : if (__x._M_root() != nullptr)
835 : : {
836 : : _M_root() = _M_copy(__x._M_begin(), _M_end());
837 : : _M_leftmost() = _S_minimum(_M_root());
838 : : _M_rightmost() = _S_maximum(_M_root());
839 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
840 : : }
841 : : }
842 : :
843 : : _Rb_tree(_Rb_tree&& __x)
844 : : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
845 : : {
846 : : if (__x._M_root() != 0)
847 : : _M_move_data(__x, std::true_type());
848 : : }
849 : :
850 : : _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
851 : : : _Rb_tree(std::move(__x), _Node_allocator(__a))
852 : : { }
853 : :
854 : : _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
855 : : #endif
856 : :
857 : : ~_Rb_tree() _GLIBCXX_NOEXCEPT
858 : 0 : { _M_erase(_M_begin()); }
859 : :
860 : : _Rb_tree&
861 : : operator=(const _Rb_tree& __x);
862 : :
863 : : // Accessors.
864 : : _Compare
865 : : key_comp() const
866 : : { return _M_impl._M_key_compare; }
867 : :
868 : : iterator
869 : : begin() _GLIBCXX_NOEXCEPT
870 : : { return iterator(this->_M_impl._M_header._M_left); }
871 : :
872 : : const_iterator
873 : : begin() const _GLIBCXX_NOEXCEPT
874 : : { return const_iterator(this->_M_impl._M_header._M_left); }
875 : :
876 : : iterator
877 : : end() _GLIBCXX_NOEXCEPT
878 : 0 : { return iterator(&this->_M_impl._M_header); }
879 : :
880 : : const_iterator
881 : : end() const _GLIBCXX_NOEXCEPT
882 : : { return const_iterator(&this->_M_impl._M_header); }
883 : :
884 : : reverse_iterator
885 : : rbegin() _GLIBCXX_NOEXCEPT
886 : : { return reverse_iterator(end()); }
887 : :
888 : : const_reverse_iterator
889 : : rbegin() const _GLIBCXX_NOEXCEPT
890 : : { return const_reverse_iterator(end()); }
891 : :
892 : : reverse_iterator
893 : : rend() _GLIBCXX_NOEXCEPT
894 : : { return reverse_iterator(begin()); }
895 : :
896 : : const_reverse_iterator
897 : : rend() const _GLIBCXX_NOEXCEPT
898 : : { return const_reverse_iterator(begin()); }
899 : :
900 : : bool
901 : : empty() const _GLIBCXX_NOEXCEPT
902 : : { return _M_impl._M_node_count == 0; }
903 : :
904 : : size_type
905 : : size() const _GLIBCXX_NOEXCEPT
906 : : { return _M_impl._M_node_count; }
907 : :
908 : : size_type
909 : : max_size() const _GLIBCXX_NOEXCEPT
910 : : { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
911 : :
912 : : void
913 : : #if __cplusplus >= 201103L
914 : : swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
915 : : #else
916 : : swap(_Rb_tree& __t);
917 : : #endif
918 : :
919 : : // Insert/erase.
920 : : #if __cplusplus >= 201103L
921 : : template<typename _Arg>
922 : : pair<iterator, bool>
923 : : _M_insert_unique(_Arg&& __x);
924 : :
925 : : template<typename _Arg>
926 : : iterator
927 : : _M_insert_equal(_Arg&& __x);
928 : :
929 : : template<typename _Arg, typename _NodeGen>
930 : : iterator
931 : : _M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
932 : :
933 : : template<typename _Arg>
934 : : iterator
935 : : _M_insert_unique_(const_iterator __pos, _Arg&& __x)
936 : : {
937 : : _Alloc_node __an(*this);
938 : : return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
939 : : }
940 : :
941 : : template<typename _Arg, typename _NodeGen>
942 : : iterator
943 : : _M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
944 : :
945 : : template<typename _Arg>
946 : : iterator
947 : : _M_insert_equal_(const_iterator __pos, _Arg&& __x)
948 : : {
949 : : _Alloc_node __an(*this);
950 : : return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
951 : : }
952 : :
953 : : template<typename... _Args>
954 : : pair<iterator, bool>
955 : : _M_emplace_unique(_Args&&... __args);
956 : :
957 : : template<typename... _Args>
958 : : iterator
959 : : _M_emplace_equal(_Args&&... __args);
960 : :
961 : : template<typename... _Args>
962 : : iterator
963 : : _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
964 : :
965 : : template<typename... _Args>
966 : : iterator
967 : : _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
968 : : #else
969 : : pair<iterator, bool>
970 : : _M_insert_unique(const value_type& __x);
971 : :
972 : : iterator
973 : : _M_insert_equal(const value_type& __x);
974 : :
975 : : template<typename _NodeGen>
976 : : iterator
977 : : _M_insert_unique_(const_iterator __pos, const value_type& __x,
978 : : _NodeGen&);
979 : :
980 : : iterator
981 : : _M_insert_unique_(const_iterator __pos, const value_type& __x)
982 : : {
983 : : _Alloc_node __an(*this);
984 : : return _M_insert_unique_(__pos, __x, __an);
985 : : }
986 : :
987 : : template<typename _NodeGen>
988 : : iterator
989 : : _M_insert_equal_(const_iterator __pos, const value_type& __x,
990 : : _NodeGen&);
991 : : iterator
992 : : _M_insert_equal_(const_iterator __pos, const value_type& __x)
993 : : {
994 : : _Alloc_node __an(*this);
995 : : return _M_insert_equal_(__pos, __x, __an);
996 : : }
997 : : #endif
998 : :
999 : : template<typename _InputIterator>
1000 : : void
1001 : : _M_insert_unique(_InputIterator __first, _InputIterator __last);
1002 : :
1003 : : template<typename _InputIterator>
1004 : : void
1005 : : _M_insert_equal(_InputIterator __first, _InputIterator __last);
1006 : :
1007 : : private:
1008 : : void
1009 : : _M_erase_aux(const_iterator __position);
1010 : :
1011 : : void
1012 : : _M_erase_aux(const_iterator __first, const_iterator __last);
1013 : :
1014 : : public:
1015 : : #if __cplusplus >= 201103L
1016 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1017 : : // DR 130. Associative erase should return an iterator.
1018 : : _GLIBCXX_ABI_TAG_CXX11
1019 : : iterator
1020 : : erase(const_iterator __position)
1021 : : {
1022 : : const_iterator __result = __position;
1023 : : ++__result;
1024 : : _M_erase_aux(__position);
1025 : : return __result._M_const_cast();
1026 : : }
1027 : :
1028 : : // LWG 2059.
1029 : : _GLIBCXX_ABI_TAG_CXX11
1030 : : iterator
1031 : : erase(iterator __position)
1032 : : {
1033 : : iterator __result = __position;
1034 : : ++__result;
1035 : 0 : _M_erase_aux(__position);
1036 : : return __result;
1037 : : }
1038 : : #else
1039 : : void
1040 : : erase(iterator __position)
1041 : : { _M_erase_aux(__position); }
1042 : :
1043 : : void
1044 : : erase(const_iterator __position)
1045 : : { _M_erase_aux(__position); }
1046 : : #endif
1047 : : size_type
1048 : : erase(const key_type& __x);
1049 : :
1050 : : #if __cplusplus >= 201103L
1051 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1052 : : // DR 130. Associative erase should return an iterator.
1053 : : _GLIBCXX_ABI_TAG_CXX11
1054 : : iterator
1055 : : erase(const_iterator __first, const_iterator __last)
1056 : : {
1057 : : _M_erase_aux(__first, __last);
1058 : : return __last._M_const_cast();
1059 : : }
1060 : : #else
1061 : : void
1062 : : erase(iterator __first, iterator __last)
1063 : : { _M_erase_aux(__first, __last); }
1064 : :
1065 : : void
1066 : : erase(const_iterator __first, const_iterator __last)
1067 : : { _M_erase_aux(__first, __last); }
1068 : : #endif
1069 : : void
1070 : : erase(const key_type* __first, const key_type* __last);
1071 : :
1072 : : void
1073 : : clear() _GLIBCXX_NOEXCEPT
1074 : : {
1075 : : _M_erase(_M_begin());
1076 : : _M_impl._M_reset();
1077 : : }
1078 : :
1079 : : // Set operations.
1080 : : iterator
1081 : : find(const key_type& __k);
1082 : :
1083 : : const_iterator
1084 : : find(const key_type& __k) const;
1085 : :
1086 : : size_type
1087 : : count(const key_type& __k) const;
1088 : :
1089 : : iterator
1090 : : lower_bound(const key_type& __k)
1091 : : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1092 : :
1093 : : const_iterator
1094 : : lower_bound(const key_type& __k) const
1095 : : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
1096 : :
1097 : : iterator
1098 : : upper_bound(const key_type& __k)
1099 : : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1100 : :
1101 : : const_iterator
1102 : : upper_bound(const key_type& __k) const
1103 : : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
1104 : :
1105 : : pair<iterator, iterator>
1106 : : equal_range(const key_type& __k);
1107 : :
1108 : : pair<const_iterator, const_iterator>
1109 : : equal_range(const key_type& __k) const;
1110 : :
1111 : : #if __cplusplus > 201103L
1112 : : template<typename _Cmp, typename _Kt, typename = __void_t<>>
1113 : : struct __is_transparent { };
1114 : :
1115 : : template<typename _Cmp, typename _Kt>
1116 : : struct
1117 : : __is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
1118 : : { typedef void type; };
1119 : :
1120 : : static auto _S_iter(_Link_type __x) { return iterator(__x); }
1121 : :
1122 : : static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
1123 : :
1124 : : template<typename _Cmp, typename _Link, typename _Kt>
1125 : : static auto
1126 : : _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1127 : : {
1128 : : while (__x != 0)
1129 : : if (!__cmp(_S_key(__x), __k))
1130 : : __y = __x, __x = _S_left(__x);
1131 : : else
1132 : : __x = _S_right(__x);
1133 : : return _S_iter(__y);
1134 : : }
1135 : :
1136 : : template<typename _Cmp, typename _Link, typename _Kt>
1137 : : static auto
1138 : : _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
1139 : : {
1140 : : while (__x != 0)
1141 : : if (__cmp(__k, _S_key(__x)))
1142 : : __y = __x, __x = _S_left(__x);
1143 : : else
1144 : : __x = _S_right(__x);
1145 : : return _S_iter(__y);
1146 : : }
1147 : :
1148 : : template<typename _Kt,
1149 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1150 : : iterator
1151 : : _M_find_tr(const _Kt& __k)
1152 : : {
1153 : : auto& __cmp = _M_impl._M_key_compare;
1154 : : auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1155 : : return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1156 : : ? end() : __j;
1157 : : }
1158 : :
1159 : : template<typename _Kt,
1160 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1161 : : const_iterator
1162 : : _M_find_tr(const _Kt& __k) const
1163 : : {
1164 : : auto& __cmp = _M_impl._M_key_compare;
1165 : : auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1166 : : return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
1167 : : ? end() : __j;
1168 : : }
1169 : :
1170 : : template<typename _Kt,
1171 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1172 : : size_type
1173 : : _M_count_tr(const _Kt& __k) const
1174 : : {
1175 : : auto __p = _M_equal_range_tr(__k);
1176 : : return std::distance(__p.first, __p.second);
1177 : : }
1178 : :
1179 : : template<typename _Kt,
1180 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1181 : : iterator
1182 : : _M_lower_bound_tr(const _Kt& __k)
1183 : : {
1184 : : auto& __cmp = _M_impl._M_key_compare;
1185 : : return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1186 : : }
1187 : :
1188 : : template<typename _Kt,
1189 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1190 : : const_iterator
1191 : : _M_lower_bound_tr(const _Kt& __k) const
1192 : : {
1193 : : auto& __cmp = _M_impl._M_key_compare;
1194 : : return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1195 : : }
1196 : :
1197 : : template<typename _Kt,
1198 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1199 : : iterator
1200 : : _M_upper_bound_tr(const _Kt& __k)
1201 : : {
1202 : : auto& __cmp = _M_impl._M_key_compare;
1203 : : return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1204 : : }
1205 : :
1206 : : template<typename _Kt,
1207 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1208 : : const_iterator
1209 : : _M_upper_bound_tr(const _Kt& __k) const
1210 : : {
1211 : : auto& __cmp = _M_impl._M_key_compare;
1212 : : return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
1213 : : }
1214 : :
1215 : : template<typename _Kt,
1216 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1217 : : pair<iterator, iterator>
1218 : : _M_equal_range_tr(const _Kt& __k)
1219 : : {
1220 : : auto __low = _M_lower_bound_tr(__k);
1221 : : auto __high = __low;
1222 : : auto& __cmp = _M_impl._M_key_compare;
1223 : : while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1224 : : ++__high;
1225 : : return { __low, __high };
1226 : : }
1227 : :
1228 : : template<typename _Kt,
1229 : : typename _Req = typename __is_transparent<_Compare, _Kt>::type>
1230 : : pair<const_iterator, const_iterator>
1231 : : _M_equal_range_tr(const _Kt& __k) const
1232 : : {
1233 : : auto __low = _M_lower_bound_tr(__k);
1234 : : auto __high = __low;
1235 : : auto& __cmp = _M_impl._M_key_compare;
1236 : : while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
1237 : : ++__high;
1238 : : return { __low, __high };
1239 : : }
1240 : : #endif
1241 : :
1242 : : // Debugging.
1243 : : bool
1244 : : __rb_verify() const;
1245 : :
1246 : : #if __cplusplus >= 201103L
1247 : : _Rb_tree&
1248 : : operator=(_Rb_tree&&) noexcept(_Alloc_traits::_S_nothrow_move());
1249 : :
1250 : : template<typename _Iterator>
1251 : : void
1252 : : _M_assign_unique(_Iterator, _Iterator);
1253 : :
1254 : : template<typename _Iterator>
1255 : : void
1256 : : _M_assign_equal(_Iterator, _Iterator);
1257 : :
1258 : : private:
1259 : : // Move elements from container with equal allocator.
1260 : : void
1261 : : _M_move_data(_Rb_tree&, std::true_type);
1262 : :
1263 : : // Move elements from container with possibly non-equal allocator,
1264 : : // which might result in a copy not a move.
1265 : : void
1266 : : _M_move_data(_Rb_tree&, std::false_type);
1267 : : #endif
1268 : : };
1269 : :
1270 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1271 : : typename _Compare, typename _Alloc>
1272 : : inline bool
1273 : : operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1274 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1275 : : {
1276 : : return __x.size() == __y.size()
1277 : : && std::equal(__x.begin(), __x.end(), __y.begin());
1278 : : }
1279 : :
1280 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1281 : : typename _Compare, typename _Alloc>
1282 : : inline bool
1283 : : operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1284 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1285 : : {
1286 : : return std::lexicographical_compare(__x.begin(), __x.end(),
1287 : : __y.begin(), __y.end());
1288 : : }
1289 : :
1290 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1291 : : typename _Compare, typename _Alloc>
1292 : : inline bool
1293 : : operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1294 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1295 : : { return !(__x == __y); }
1296 : :
1297 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1298 : : typename _Compare, typename _Alloc>
1299 : : inline bool
1300 : : operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1301 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1302 : : { return __y < __x; }
1303 : :
1304 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1305 : : typename _Compare, typename _Alloc>
1306 : : inline bool
1307 : : operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1308 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1309 : : { return !(__y < __x); }
1310 : :
1311 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1312 : : typename _Compare, typename _Alloc>
1313 : : inline bool
1314 : : operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1315 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1316 : : { return !(__x < __y); }
1317 : :
1318 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1319 : : typename _Compare, typename _Alloc>
1320 : : inline void
1321 : : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1322 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1323 : : { __x.swap(__y); }
1324 : :
1325 : : #if __cplusplus >= 201103L
1326 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1327 : : typename _Compare, typename _Alloc>
1328 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1329 : : _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1330 : : : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1331 : : {
1332 : : using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
1333 : : if (__x._M_root() != nullptr)
1334 : : _M_move_data(__x, __eq());
1335 : : }
1336 : :
1337 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1338 : : typename _Compare, typename _Alloc>
1339 : : void
1340 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1341 : : _M_move_data(_Rb_tree& __x, std::true_type)
1342 : : {
1343 : : _M_root() = __x._M_root();
1344 : : _M_leftmost() = __x._M_leftmost();
1345 : : _M_rightmost() = __x._M_rightmost();
1346 : : _M_root()->_M_parent = _M_end();
1347 : :
1348 : : __x._M_root() = 0;
1349 : : __x._M_leftmost() = __x._M_end();
1350 : : __x._M_rightmost() = __x._M_end();
1351 : :
1352 : : this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1353 : : __x._M_impl._M_node_count = 0;
1354 : : }
1355 : :
1356 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1357 : : typename _Compare, typename _Alloc>
1358 : : void
1359 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1360 : : _M_move_data(_Rb_tree& __x, std::false_type)
1361 : : {
1362 : : if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1363 : : _M_move_data(__x, std::true_type());
1364 : : else
1365 : : {
1366 : : _Alloc_node __an(*this);
1367 : : auto __lbd =
1368 : : [&__an](const value_type& __cval)
1369 : : {
1370 : : auto& __val = const_cast<value_type&>(__cval);
1371 : : return __an(std::move_if_noexcept(__val));
1372 : : };
1373 : : _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1374 : : _M_leftmost() = _S_minimum(_M_root());
1375 : : _M_rightmost() = _S_maximum(_M_root());
1376 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
1377 : : }
1378 : : }
1379 : :
1380 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1381 : : typename _Compare, typename _Alloc>
1382 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1383 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1384 : : operator=(_Rb_tree&& __x)
1385 : : noexcept(_Alloc_traits::_S_nothrow_move())
1386 : : {
1387 : : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1388 : : if (_Alloc_traits::_S_propagate_on_move_assign()
1389 : : || _Alloc_traits::_S_always_equal()
1390 : : || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1391 : : {
1392 : : clear();
1393 : : if (__x._M_root() != nullptr)
1394 : : _M_move_data(__x, std::true_type());
1395 : : std::__alloc_on_move(_M_get_Node_allocator(),
1396 : : __x._M_get_Node_allocator());
1397 : : return *this;
1398 : : }
1399 : :
1400 : : // Try to move each node reusing existing nodes and copying __x nodes
1401 : : // structure.
1402 : : _Reuse_or_alloc_node __roan(*this);
1403 : : _M_impl._M_reset();
1404 : : if (__x._M_root() != nullptr)
1405 : : {
1406 : : auto __lbd =
1407 : : [&__roan](const value_type& __cval)
1408 : : {
1409 : : auto& __val = const_cast<value_type&>(__cval);
1410 : : return __roan(std::move_if_noexcept(__val));
1411 : : };
1412 : : _M_root() = _M_copy(__x._M_begin(), _M_end(), __lbd);
1413 : : _M_leftmost() = _S_minimum(_M_root());
1414 : : _M_rightmost() = _S_maximum(_M_root());
1415 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
1416 : : __x.clear();
1417 : : }
1418 : : return *this;
1419 : : }
1420 : :
1421 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1422 : : typename _Compare, typename _Alloc>
1423 : : template<typename _Iterator>
1424 : : void
1425 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1426 : : _M_assign_unique(_Iterator __first, _Iterator __last)
1427 : : {
1428 : : _Reuse_or_alloc_node __roan(*this);
1429 : : _M_impl._M_reset();
1430 : : for (; __first != __last; ++__first)
1431 : : _M_insert_unique_(end(), *__first, __roan);
1432 : : }
1433 : :
1434 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1435 : : typename _Compare, typename _Alloc>
1436 : : template<typename _Iterator>
1437 : : void
1438 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1439 : : _M_assign_equal(_Iterator __first, _Iterator __last)
1440 : : {
1441 : : _Reuse_or_alloc_node __roan(*this);
1442 : : _M_impl._M_reset();
1443 : : for (; __first != __last; ++__first)
1444 : : _M_insert_equal_(end(), *__first, __roan);
1445 : : }
1446 : : #endif
1447 : :
1448 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1449 : : typename _Compare, typename _Alloc>
1450 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1451 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1452 : : operator=(const _Rb_tree& __x)
1453 : : {
1454 : : if (this != &__x)
1455 : : {
1456 : : // Note that _Key may be a constant type.
1457 : : #if __cplusplus >= 201103L
1458 : : if (_Alloc_traits::_S_propagate_on_copy_assign())
1459 : : {
1460 : : auto& __this_alloc = this->_M_get_Node_allocator();
1461 : : auto& __that_alloc = __x._M_get_Node_allocator();
1462 : : if (!_Alloc_traits::_S_always_equal()
1463 : : && __this_alloc != __that_alloc)
1464 : : {
1465 : : // Replacement allocator cannot free existing storage, we need
1466 : : // to erase nodes first.
1467 : : clear();
1468 : : std::__alloc_on_copy(__this_alloc, __that_alloc);
1469 : : }
1470 : : }
1471 : : #endif
1472 : :
1473 : : _Reuse_or_alloc_node __roan(*this);
1474 : : _M_impl._M_reset();
1475 : : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1476 : : if (__x._M_root() != 0)
1477 : : {
1478 : : _M_root() = _M_copy(__x._M_begin(), _M_end(), __roan);
1479 : : _M_leftmost() = _S_minimum(_M_root());
1480 : : _M_rightmost() = _S_maximum(_M_root());
1481 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
1482 : : }
1483 : : }
1484 : :
1485 : : return *this;
1486 : : }
1487 : :
1488 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1489 : : typename _Compare, typename _Alloc>
1490 : : #if __cplusplus >= 201103L
1491 : : template<typename _Arg, typename _NodeGen>
1492 : : #else
1493 : : template<typename _NodeGen>
1494 : : #endif
1495 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1496 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1497 : : _M_insert_(_Base_ptr __x, _Base_ptr __p,
1498 : : #if __cplusplus >= 201103L
1499 : : _Arg&& __v,
1500 : : #else
1501 : : const _Val& __v,
1502 : : #endif
1503 : : _NodeGen& __node_gen)
1504 : : {
1505 : : bool __insert_left = (__x != 0 || __p == _M_end()
1506 : 0 : || _M_impl._M_key_compare(_KeyOfValue()(__v),
1507 [ # # ]: 0 : _S_key(__p)));
[ # # # # ]
1508 : :
1509 : : _Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
1510 : :
1511 : 0 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1512 : : this->_M_impl._M_header);
1513 : 0 : ++_M_impl._M_node_count;
1514 : 0 : return iterator(__z);
1515 : : }
1516 : :
1517 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1518 : : typename _Compare, typename _Alloc>
1519 : : #if __cplusplus >= 201103L
1520 : : template<typename _Arg>
1521 : : #endif
1522 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1523 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1524 : : #if __cplusplus >= 201103L
1525 : : _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1526 : : #else
1527 : : _M_insert_lower(_Base_ptr __p, const _Val& __v)
1528 : : #endif
1529 : : {
1530 : : bool __insert_left = (__p == _M_end()
1531 : : || !_M_impl._M_key_compare(_S_key(__p),
1532 : : _KeyOfValue()(__v)));
1533 : :
1534 : : _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1535 : :
1536 : : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1537 : : this->_M_impl._M_header);
1538 : : ++_M_impl._M_node_count;
1539 : : return iterator(__z);
1540 : : }
1541 : :
1542 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1543 : : typename _Compare, typename _Alloc>
1544 : : #if __cplusplus >= 201103L
1545 : : template<typename _Arg>
1546 : : #endif
1547 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1548 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1549 : : #if __cplusplus >= 201103L
1550 : : _M_insert_equal_lower(_Arg&& __v)
1551 : : #else
1552 : : _M_insert_equal_lower(const _Val& __v)
1553 : : #endif
1554 : : {
1555 : : _Link_type __x = _M_begin();
1556 : : _Link_type __y = _M_end();
1557 : : while (__x != 0)
1558 : : {
1559 : : __y = __x;
1560 : : __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1561 : : _S_left(__x) : _S_right(__x);
1562 : : }
1563 : : return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1564 : : }
1565 : :
1566 : : template<typename _Key, typename _Val, typename _KoV,
1567 : : typename _Compare, typename _Alloc>
1568 : : template<typename _NodeGen>
1569 : : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1570 : : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1571 : : _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
1572 : : {
1573 : : // Structural copy. __x and __p must be non-null.
1574 : : _Link_type __top = _M_clone_node(__x, __node_gen);
1575 : : __top->_M_parent = __p;
1576 : :
1577 : : __try
1578 : : {
1579 : : if (__x->_M_right)
1580 : : __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
1581 : : __p = __top;
1582 : : __x = _S_left(__x);
1583 : :
1584 : : while (__x != 0)
1585 : : {
1586 : : _Link_type __y = _M_clone_node(__x, __node_gen);
1587 : : __p->_M_left = __y;
1588 : : __y->_M_parent = __p;
1589 : : if (__x->_M_right)
1590 : : __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
1591 : : __p = __y;
1592 : : __x = _S_left(__x);
1593 : : }
1594 : : }
1595 : : __catch(...)
1596 : : {
1597 : : _M_erase(__top);
1598 : : __throw_exception_again;
1599 : : }
1600 : : return __top;
1601 : : }
1602 : :
1603 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1604 : : typename _Compare, typename _Alloc>
1605 : : void
1606 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1607 : : _M_erase(_Link_type __x)
1608 : : {
1609 : : // Erase without rebalancing.
1610 [ # # ]: 0 : while (__x != 0)
1611 : : {
1612 : 0 : _M_erase(_S_right(__x));
1613 : : _Link_type __y = _S_left(__x);
1614 : : _M_drop_node(__x);
1615 : : __x = __y;
1616 : : }
1617 : 0 : }
1618 : :
1619 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1620 : : typename _Compare, typename _Alloc>
1621 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1622 : : _Compare, _Alloc>::iterator
1623 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1624 : : _M_lower_bound(_Link_type __x, _Link_type __y,
1625 : : const _Key& __k)
1626 : : {
1627 : : while (__x != 0)
1628 : : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1629 : : __y = __x, __x = _S_left(__x);
1630 : : else
1631 : : __x = _S_right(__x);
1632 : : return iterator(__y);
1633 : : }
1634 : :
1635 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1636 : : typename _Compare, typename _Alloc>
1637 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1638 : : _Compare, _Alloc>::const_iterator
1639 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1640 : : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1641 : : const _Key& __k) const
1642 : : {
1643 : : while (__x != 0)
1644 : : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1645 : : __y = __x, __x = _S_left(__x);
1646 : : else
1647 : : __x = _S_right(__x);
1648 : : return const_iterator(__y);
1649 : : }
1650 : :
1651 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1652 : : typename _Compare, typename _Alloc>
1653 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1654 : : _Compare, _Alloc>::iterator
1655 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1656 : : _M_upper_bound(_Link_type __x, _Link_type __y,
1657 : : const _Key& __k)
1658 : : {
1659 : : while (__x != 0)
1660 : : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1661 : : __y = __x, __x = _S_left(__x);
1662 : : else
1663 : : __x = _S_right(__x);
1664 : : return iterator(__y);
1665 : : }
1666 : :
1667 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1668 : : typename _Compare, typename _Alloc>
1669 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1670 : : _Compare, _Alloc>::const_iterator
1671 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1672 : : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1673 : : const _Key& __k) const
1674 : : {
1675 : : while (__x != 0)
1676 : : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1677 : : __y = __x, __x = _S_left(__x);
1678 : : else
1679 : : __x = _S_right(__x);
1680 : : return const_iterator(__y);
1681 : : }
1682 : :
1683 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1684 : : typename _Compare, typename _Alloc>
1685 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1686 : : _Compare, _Alloc>::iterator,
1687 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1688 : : _Compare, _Alloc>::iterator>
1689 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1690 : : equal_range(const _Key& __k)
1691 : : {
1692 : : _Link_type __x = _M_begin();
1693 : : _Link_type __y = _M_end();
1694 : : while (__x != 0)
1695 : : {
1696 : : if (_M_impl._M_key_compare(_S_key(__x), __k))
1697 : : __x = _S_right(__x);
1698 : : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1699 : : __y = __x, __x = _S_left(__x);
1700 : : else
1701 : : {
1702 : : _Link_type __xu(__x), __yu(__y);
1703 : : __y = __x, __x = _S_left(__x);
1704 : : __xu = _S_right(__xu);
1705 : : return pair<iterator,
1706 : : iterator>(_M_lower_bound(__x, __y, __k),
1707 : : _M_upper_bound(__xu, __yu, __k));
1708 : : }
1709 : : }
1710 : : return pair<iterator, iterator>(iterator(__y),
1711 : : iterator(__y));
1712 : : }
1713 : :
1714 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1715 : : typename _Compare, typename _Alloc>
1716 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1717 : : _Compare, _Alloc>::const_iterator,
1718 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1719 : : _Compare, _Alloc>::const_iterator>
1720 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1721 : : equal_range(const _Key& __k) const
1722 : : {
1723 : : _Const_Link_type __x = _M_begin();
1724 : : _Const_Link_type __y = _M_end();
1725 : : while (__x != 0)
1726 : : {
1727 : : if (_M_impl._M_key_compare(_S_key(__x), __k))
1728 : : __x = _S_right(__x);
1729 : : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1730 : : __y = __x, __x = _S_left(__x);
1731 : : else
1732 : : {
1733 : : _Const_Link_type __xu(__x), __yu(__y);
1734 : : __y = __x, __x = _S_left(__x);
1735 : : __xu = _S_right(__xu);
1736 : : return pair<const_iterator,
1737 : : const_iterator>(_M_lower_bound(__x, __y, __k),
1738 : : _M_upper_bound(__xu, __yu, __k));
1739 : : }
1740 : : }
1741 : : return pair<const_iterator, const_iterator>(const_iterator(__y),
1742 : : const_iterator(__y));
1743 : : }
1744 : :
1745 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1746 : : typename _Compare, typename _Alloc>
1747 : : void
1748 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1749 : : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1750 : : #if __cplusplus >= 201103L
1751 : : noexcept(_Alloc_traits::_S_nothrow_swap())
1752 : : #endif
1753 : : {
1754 : : if (_M_root() == 0)
1755 : : {
1756 : : if (__t._M_root() != 0)
1757 : : {
1758 : : _M_root() = __t._M_root();
1759 : : _M_leftmost() = __t._M_leftmost();
1760 : : _M_rightmost() = __t._M_rightmost();
1761 : : _M_root()->_M_parent = _M_end();
1762 : : _M_impl._M_node_count = __t._M_impl._M_node_count;
1763 : :
1764 : : __t._M_impl._M_reset();
1765 : : }
1766 : : }
1767 : : else if (__t._M_root() == 0)
1768 : : {
1769 : : __t._M_root() = _M_root();
1770 : : __t._M_leftmost() = _M_leftmost();
1771 : : __t._M_rightmost() = _M_rightmost();
1772 : : __t._M_root()->_M_parent = __t._M_end();
1773 : : __t._M_impl._M_node_count = _M_impl._M_node_count;
1774 : :
1775 : : _M_impl._M_reset();
1776 : : }
1777 : : else
1778 : : {
1779 : : std::swap(_M_root(),__t._M_root());
1780 : : std::swap(_M_leftmost(),__t._M_leftmost());
1781 : : std::swap(_M_rightmost(),__t._M_rightmost());
1782 : :
1783 : : _M_root()->_M_parent = _M_end();
1784 : : __t._M_root()->_M_parent = __t._M_end();
1785 : : std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1786 : : }
1787 : : // No need to swap header's color as it does not change.
1788 : : std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1789 : :
1790 : : _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1791 : : __t._M_get_Node_allocator());
1792 : : }
1793 : :
1794 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1795 : : typename _Compare, typename _Alloc>
1796 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1797 : : _Compare, _Alloc>::_Base_ptr,
1798 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1799 : : _Compare, _Alloc>::_Base_ptr>
1800 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1801 : : _M_get_insert_unique_pos(const key_type& __k)
1802 : : {
1803 : : typedef pair<_Base_ptr, _Base_ptr> _Res;
1804 : : _Link_type __x = _M_begin();
1805 : : _Link_type __y = _M_end();
1806 : : bool __comp = true;
1807 [ # # ]: 0 : while (__x != 0)
1808 : : {
1809 : : __y = __x;
1810 : 0 : __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1811 [ # # ]: 0 : __x = __comp ? _S_left(__x) : _S_right(__x);
1812 : : }
1813 : : iterator __j = iterator(__y);
1814 [ # # ]: 0 : if (__comp)
1815 : : {
1816 [ # # ]: 0 : if (__j == begin())
1817 : 0 : return _Res(__x, __y);
1818 : : else
1819 : : --__j;
1820 : : }
1821 [ # # ]: 0 : if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1822 : 0 : return _Res(__x, __y);
1823 : 0 : return _Res(__j._M_node, 0);
1824 : : }
1825 : :
1826 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1827 : : typename _Compare, typename _Alloc>
1828 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1829 : : _Compare, _Alloc>::_Base_ptr,
1830 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1831 : : _Compare, _Alloc>::_Base_ptr>
1832 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1833 : : _M_get_insert_equal_pos(const key_type& __k)
1834 : : {
1835 : : typedef pair<_Base_ptr, _Base_ptr> _Res;
1836 : : _Link_type __x = _M_begin();
1837 : : _Link_type __y = _M_end();
1838 : : while (__x != 0)
1839 : : {
1840 : : __y = __x;
1841 : : __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1842 : : _S_left(__x) : _S_right(__x);
1843 : : }
1844 : : return _Res(__x, __y);
1845 : : }
1846 : :
1847 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1848 : : typename _Compare, typename _Alloc>
1849 : : #if __cplusplus >= 201103L
1850 : : template<typename _Arg>
1851 : : #endif
1852 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1853 : : _Compare, _Alloc>::iterator, bool>
1854 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1855 : : #if __cplusplus >= 201103L
1856 : : _M_insert_unique(_Arg&& __v)
1857 : : #else
1858 : : _M_insert_unique(const _Val& __v)
1859 : : #endif
1860 : : {
1861 : : typedef pair<iterator, bool> _Res;
1862 : : pair<_Base_ptr, _Base_ptr> __res
1863 : 0 : = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1864 : :
1865 [ # # ]: 0 : if (__res.second)
1866 : : {
1867 : : _Alloc_node __an(*this);
1868 : : return _Res(_M_insert_(__res.first, __res.second,
1869 : : _GLIBCXX_FORWARD(_Arg, __v), __an),
1870 : 0 : true);
1871 : : }
1872 : :
1873 : 0 : return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1874 : : }
1875 : :
1876 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1877 : : typename _Compare, typename _Alloc>
1878 : : #if __cplusplus >= 201103L
1879 : : template<typename _Arg>
1880 : : #endif
1881 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1882 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1883 : : #if __cplusplus >= 201103L
1884 : : _M_insert_equal(_Arg&& __v)
1885 : : #else
1886 : : _M_insert_equal(const _Val& __v)
1887 : : #endif
1888 : : {
1889 : : pair<_Base_ptr, _Base_ptr> __res
1890 : : = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1891 : : _Alloc_node __an(*this);
1892 : : return _M_insert_(__res.first, __res.second,
1893 : : _GLIBCXX_FORWARD(_Arg, __v), __an);
1894 : : }
1895 : :
1896 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1897 : : typename _Compare, typename _Alloc>
1898 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1899 : : _Compare, _Alloc>::_Base_ptr,
1900 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1901 : : _Compare, _Alloc>::_Base_ptr>
1902 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1903 : : _M_get_insert_hint_unique_pos(const_iterator __position,
1904 : : const key_type& __k)
1905 : : {
1906 : : iterator __pos = __position._M_const_cast();
1907 : : typedef pair<_Base_ptr, _Base_ptr> _Res;
1908 : :
1909 : : // end()
1910 [ # # ]: 0 : if (__pos._M_node == _M_end())
1911 : : {
1912 [ # # # # ]: 0 : if (size() > 0
[ # # ]
1913 : 0 : && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1914 : 0 : return _Res(0, _M_rightmost());
1915 : : else
1916 : 0 : return _M_get_insert_unique_pos(__k);
1917 : : }
1918 [ # # ]: 0 : else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1919 : : {
1920 : : // First, try before...
1921 : : iterator __before = __pos;
1922 [ # # ]: 0 : if (__pos._M_node == _M_leftmost()) // begin()
1923 : 0 : return _Res(_M_leftmost(), _M_leftmost());
1924 [ # # ]: 0 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1925 : : {
1926 [ # # ]: 0 : if (_S_right(__before._M_node) == 0)
1927 : 0 : return _Res(0, __before._M_node);
1928 : : else
1929 : 0 : return _Res(__pos._M_node, __pos._M_node);
1930 : : }
1931 : : else
1932 : 0 : return _M_get_insert_unique_pos(__k);
1933 : : }
1934 [ # # ]: 0 : else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1935 : : {
1936 : : // ... then try after.
1937 : : iterator __after = __pos;
1938 [ # # ]: 0 : if (__pos._M_node == _M_rightmost())
1939 : 0 : return _Res(0, _M_rightmost());
1940 [ # # ]: 0 : else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1941 : : {
1942 [ # # ]: 0 : if (_S_right(__pos._M_node) == 0)
1943 : 0 : return _Res(0, __pos._M_node);
1944 : : else
1945 : 0 : return _Res(__after._M_node, __after._M_node);
1946 : : }
1947 : : else
1948 : 0 : return _M_get_insert_unique_pos(__k);
1949 : : }
1950 : : else
1951 : : // Equivalent keys.
1952 : 0 : return _Res(__pos._M_node, 0);
1953 : : }
1954 : :
1955 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1956 : : typename _Compare, typename _Alloc>
1957 : : #if __cplusplus >= 201103L
1958 : : template<typename _Arg, typename _NodeGen>
1959 : : #else
1960 : : template<typename _NodeGen>
1961 : : #endif
1962 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1963 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1964 : : _M_insert_unique_(const_iterator __position,
1965 : : #if __cplusplus >= 201103L
1966 : : _Arg&& __v,
1967 : : #else
1968 : : const _Val& __v,
1969 : : #endif
1970 : : _NodeGen& __node_gen)
1971 : : {
1972 : : pair<_Base_ptr, _Base_ptr> __res
1973 : 0 : = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1974 : :
1975 [ # # ]: 0 : if (__res.second)
1976 : : return _M_insert_(__res.first, __res.second,
1977 : : _GLIBCXX_FORWARD(_Arg, __v),
1978 : 0 : __node_gen);
1979 : 0 : return iterator(static_cast<_Link_type>(__res.first));
1980 : : }
1981 : :
1982 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1983 : : typename _Compare, typename _Alloc>
1984 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1985 : : _Compare, _Alloc>::_Base_ptr,
1986 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1987 : : _Compare, _Alloc>::_Base_ptr>
1988 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1989 : : _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1990 : : {
1991 : : iterator __pos = __position._M_const_cast();
1992 : : typedef pair<_Base_ptr, _Base_ptr> _Res;
1993 : :
1994 : : // end()
1995 : : if (__pos._M_node == _M_end())
1996 : : {
1997 : : if (size() > 0
1998 : : && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1999 : : return _Res(0, _M_rightmost());
2000 : : else
2001 : : return _M_get_insert_equal_pos(__k);
2002 : : }
2003 : : else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
2004 : : {
2005 : : // First, try before...
2006 : : iterator __before = __pos;
2007 : : if (__pos._M_node == _M_leftmost()) // begin()
2008 : : return _Res(_M_leftmost(), _M_leftmost());
2009 : : else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
2010 : : {
2011 : : if (_S_right(__before._M_node) == 0)
2012 : : return _Res(0, __before._M_node);
2013 : : else
2014 : : return _Res(__pos._M_node, __pos._M_node);
2015 : : }
2016 : : else
2017 : : return _M_get_insert_equal_pos(__k);
2018 : : }
2019 : : else
2020 : : {
2021 : : // ... then try after.
2022 : : iterator __after = __pos;
2023 : : if (__pos._M_node == _M_rightmost())
2024 : : return _Res(0, _M_rightmost());
2025 : : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
2026 : : {
2027 : : if (_S_right(__pos._M_node) == 0)
2028 : : return _Res(0, __pos._M_node);
2029 : : else
2030 : : return _Res(__after._M_node, __after._M_node);
2031 : : }
2032 : : else
2033 : : return _Res(0, 0);
2034 : : }
2035 : : }
2036 : :
2037 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2038 : : typename _Compare, typename _Alloc>
2039 : : #if __cplusplus >= 201103L
2040 : : template<typename _Arg, typename _NodeGen>
2041 : : #else
2042 : : template<typename _NodeGen>
2043 : : #endif
2044 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2045 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2046 : : _M_insert_equal_(const_iterator __position,
2047 : : #if __cplusplus >= 201103L
2048 : : _Arg&& __v,
2049 : : #else
2050 : : const _Val& __v,
2051 : : #endif
2052 : : _NodeGen& __node_gen)
2053 : : {
2054 : : pair<_Base_ptr, _Base_ptr> __res
2055 : : = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
2056 : :
2057 : : if (__res.second)
2058 : : return _M_insert_(__res.first, __res.second,
2059 : : _GLIBCXX_FORWARD(_Arg, __v),
2060 : : __node_gen);
2061 : :
2062 : : return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
2063 : : }
2064 : :
2065 : : #if __cplusplus >= 201103L
2066 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2067 : : typename _Compare, typename _Alloc>
2068 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2069 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2070 : : _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
2071 : : {
2072 : : bool __insert_left = (__x != 0 || __p == _M_end()
2073 : : || _M_impl._M_key_compare(_S_key(__z),
2074 : : _S_key(__p)));
2075 : :
2076 : : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2077 : : this->_M_impl._M_header);
2078 : : ++_M_impl._M_node_count;
2079 : : return iterator(__z);
2080 : : }
2081 : :
2082 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2083 : : typename _Compare, typename _Alloc>
2084 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2085 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2086 : : _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
2087 : : {
2088 : : bool __insert_left = (__p == _M_end()
2089 : : || !_M_impl._M_key_compare(_S_key(__p),
2090 : : _S_key(__z)));
2091 : :
2092 : : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
2093 : : this->_M_impl._M_header);
2094 : : ++_M_impl._M_node_count;
2095 : : return iterator(__z);
2096 : : }
2097 : :
2098 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2099 : : typename _Compare, typename _Alloc>
2100 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2101 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2102 : : _M_insert_equal_lower_node(_Link_type __z)
2103 : : {
2104 : : _Link_type __x = _M_begin();
2105 : : _Link_type __y = _M_end();
2106 : : while (__x != 0)
2107 : : {
2108 : : __y = __x;
2109 : : __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
2110 : : _S_left(__x) : _S_right(__x);
2111 : : }
2112 : : return _M_insert_lower_node(__y, __z);
2113 : : }
2114 : :
2115 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2116 : : typename _Compare, typename _Alloc>
2117 : : template<typename... _Args>
2118 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
2119 : : _Compare, _Alloc>::iterator, bool>
2120 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2121 : : _M_emplace_unique(_Args&&... __args)
2122 : : {
2123 : : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2124 : :
2125 : : __try
2126 : : {
2127 : : typedef pair<iterator, bool> _Res;
2128 : : auto __res = _M_get_insert_unique_pos(_S_key(__z));
2129 : : if (__res.second)
2130 : : return _Res(_M_insert_node(__res.first, __res.second, __z), true);
2131 : :
2132 : : _M_drop_node(__z);
2133 : : return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
2134 : : }
2135 : : __catch(...)
2136 : : {
2137 : : _M_drop_node(__z);
2138 : : __throw_exception_again;
2139 : : }
2140 : : }
2141 : :
2142 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2143 : : typename _Compare, typename _Alloc>
2144 : : template<typename... _Args>
2145 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2146 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2147 : : _M_emplace_equal(_Args&&... __args)
2148 : : {
2149 : : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2150 : :
2151 : : __try
2152 : : {
2153 : : auto __res = _M_get_insert_equal_pos(_S_key(__z));
2154 : : return _M_insert_node(__res.first, __res.second, __z);
2155 : : }
2156 : : __catch(...)
2157 : : {
2158 : : _M_drop_node(__z);
2159 : : __throw_exception_again;
2160 : : }
2161 : : }
2162 : :
2163 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2164 : : typename _Compare, typename _Alloc>
2165 : : template<typename... _Args>
2166 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2167 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2168 : : _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
2169 : : {
2170 : : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2171 : :
2172 : : __try
2173 : : {
2174 : : auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
2175 : :
2176 : : if (__res.second)
2177 : : return _M_insert_node(__res.first, __res.second, __z);
2178 : :
2179 : : _M_drop_node(__z);
2180 : : return iterator(static_cast<_Link_type>(__res.first));
2181 : : }
2182 : : __catch(...)
2183 : : {
2184 : : _M_drop_node(__z);
2185 : : __throw_exception_again;
2186 : : }
2187 : : }
2188 : :
2189 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2190 : : typename _Compare, typename _Alloc>
2191 : : template<typename... _Args>
2192 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
2193 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2194 : : _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
2195 : : {
2196 : : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
2197 : :
2198 : : __try
2199 : : {
2200 : : auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
2201 : :
2202 : : if (__res.second)
2203 : : return _M_insert_node(__res.first, __res.second, __z);
2204 : :
2205 : : return _M_insert_equal_lower_node(__z);
2206 : : }
2207 : : __catch(...)
2208 : : {
2209 : : _M_drop_node(__z);
2210 : : __throw_exception_again;
2211 : : }
2212 : : }
2213 : : #endif
2214 : :
2215 : : template<typename _Key, typename _Val, typename _KoV,
2216 : : typename _Cmp, typename _Alloc>
2217 : : template<class _II>
2218 : : void
2219 : 0 : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2220 : : _M_insert_unique(_II __first, _II __last)
2221 : : {
2222 : : _Alloc_node __an(*this);
2223 [ # # ]: 0 : for (; __first != __last; ++__first)
2224 : 0 : _M_insert_unique_(end(), *__first, __an);
2225 : 0 : }
2226 : :
2227 : : template<typename _Key, typename _Val, typename _KoV,
2228 : : typename _Cmp, typename _Alloc>
2229 : : template<class _II>
2230 : : void
2231 : : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
2232 : : _M_insert_equal(_II __first, _II __last)
2233 : : {
2234 : : _Alloc_node __an(*this);
2235 : : for (; __first != __last; ++__first)
2236 : : _M_insert_equal_(end(), *__first, __an);
2237 : : }
2238 : :
2239 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2240 : : typename _Compare, typename _Alloc>
2241 : : void
2242 : 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2243 : : _M_erase_aux(const_iterator __position)
2244 : : {
2245 : : _Link_type __y =
2246 : : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
2247 : 0 : (const_cast<_Base_ptr>(__position._M_node),
2248 : 0 : this->_M_impl._M_header));
2249 : : _M_drop_node(__y);
2250 : 0 : --_M_impl._M_node_count;
2251 : 0 : }
2252 : :
2253 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2254 : : typename _Compare, typename _Alloc>
2255 : : void
2256 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2257 : : _M_erase_aux(const_iterator __first, const_iterator __last)
2258 : : {
2259 : : if (__first == begin() && __last == end())
2260 : : clear();
2261 : : else
2262 : : while (__first != __last)
2263 : : erase(__first++);
2264 : : }
2265 : :
2266 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2267 : : typename _Compare, typename _Alloc>
2268 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2269 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2270 : : erase(const _Key& __x)
2271 : : {
2272 : : pair<iterator, iterator> __p = equal_range(__x);
2273 : : const size_type __old_size = size();
2274 : : erase(__p.first, __p.second);
2275 : : return __old_size - size();
2276 : : }
2277 : :
2278 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2279 : : typename _Compare, typename _Alloc>
2280 : : void
2281 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2282 : : erase(const _Key* __first, const _Key* __last)
2283 : : {
2284 : : while (__first != __last)
2285 : : erase(*__first++);
2286 : : }
2287 : :
2288 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2289 : : typename _Compare, typename _Alloc>
2290 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
2291 : : _Compare, _Alloc>::iterator
2292 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2293 : : find(const _Key& __k)
2294 : : {
2295 : : iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2296 : : return (__j == end()
2297 : : || _M_impl._M_key_compare(__k,
2298 : : _S_key(__j._M_node))) ? end() : __j;
2299 : : }
2300 : :
2301 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2302 : : typename _Compare, typename _Alloc>
2303 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
2304 : : _Compare, _Alloc>::const_iterator
2305 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2306 : : find(const _Key& __k) const
2307 : : {
2308 : : const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
2309 : : return (__j == end()
2310 : : || _M_impl._M_key_compare(__k,
2311 : : _S_key(__j._M_node))) ? end() : __j;
2312 : : }
2313 : :
2314 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2315 : : typename _Compare, typename _Alloc>
2316 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
2317 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
2318 : : count(const _Key& __k) const
2319 : : {
2320 : : pair<const_iterator, const_iterator> __p = equal_range(__k);
2321 : : const size_type __n = std::distance(__p.first, __p.second);
2322 : : return __n;
2323 : : }
2324 : :
2325 : : _GLIBCXX_PURE unsigned int
2326 : : _Rb_tree_black_count(const _Rb_tree_node_base* __node,
2327 : : const _Rb_tree_node_base* __root) throw ();
2328 : :
2329 : : template<typename _Key, typename _Val, typename _KeyOfValue,
2330 : : typename _Compare, typename _Alloc>
2331 : : bool
2332 : : _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
2333 : : {
2334 : : if (_M_impl._M_node_count == 0 || begin() == end())
2335 : : return _M_impl._M_node_count == 0 && begin() == end()
2336 : : && this->_M_impl._M_header._M_left == _M_end()
2337 : : && this->_M_impl._M_header._M_right == _M_end();
2338 : :
2339 : : unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
2340 : : for (const_iterator __it = begin(); __it != end(); ++__it)
2341 : : {
2342 : : _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
2343 : : _Const_Link_type __L = _S_left(__x);
2344 : : _Const_Link_type __R = _S_right(__x);
2345 : :
2346 : : if (__x->_M_color == _S_red)
2347 : : if ((__L && __L->_M_color == _S_red)
2348 : : || (__R && __R->_M_color == _S_red))
2349 : : return false;
2350 : :
2351 : : if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
2352 : : return false;
2353 : : if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
2354 : : return false;
2355 : :
2356 : : if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
2357 : : return false;
2358 : : }
2359 : :
2360 : : if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
2361 : : return false;
2362 : : if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
2363 : : return false;
2364 : : return true;
2365 : : }
2366 : :
2367 : : _GLIBCXX_END_NAMESPACE_VERSION
2368 : : } // namespace
2369 : :
2370 : : #endif
|
