Line data Source code
1 : // RB tree implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2014 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 : #include <bits/stl_algobase.h>
62 : #include <bits/allocator.h>
63 : #include <bits/stl_function.h>
64 : #include <bits/cpp_type_traits.h>
65 : #include <ext/alloc_traits.h>
66 : #if __cplusplus >= 201103L
67 : #include <ext/aligned_buffer.h>
68 : #endif
69 :
70 : namespace std _GLIBCXX_VISIBILITY(default)
71 : {
72 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
73 :
74 : // Red-black tree class, designed for use in implementing STL
75 : // associative containers (set, multiset, map, and multimap). The
76 : // insertion and deletion algorithms are based on those in Cormen,
77 : // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
78 : // 1990), except that
79 : //
80 : // (1) the header cell is maintained with links not only to the root
81 : // but also to the leftmost node of the tree, to enable constant
82 : // time begin(), and to the rightmost node of the tree, to enable
83 : // linear time performance when used with the generic set algorithms
84 : // (set_union, etc.)
85 : //
86 : // (2) when a node being deleted has two children its successor node
87 : // is relinked into its place, rather than copied, so that the only
88 : // iterators invalidated are those referring to the deleted node.
89 :
90 : enum _Rb_tree_color { _S_red = false, _S_black = true };
91 :
92 : struct _Rb_tree_node_base
93 : {
94 : typedef _Rb_tree_node_base* _Base_ptr;
95 : typedef const _Rb_tree_node_base* _Const_Base_ptr;
96 :
97 : _Rb_tree_color _M_color;
98 : _Base_ptr _M_parent;
99 : _Base_ptr _M_left;
100 : _Base_ptr _M_right;
101 :
102 : static _Base_ptr
103 : _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
104 : {
105 : while (__x->_M_left != 0) __x = __x->_M_left;
106 : return __x;
107 : }
108 :
109 : static _Const_Base_ptr
110 : _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
111 : {
112 : while (__x->_M_left != 0) __x = __x->_M_left;
113 : return __x;
114 : }
115 :
116 : static _Base_ptr
117 : _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
118 : {
119 : while (__x->_M_right != 0) __x = __x->_M_right;
120 : return __x;
121 : }
122 :
123 : static _Const_Base_ptr
124 : _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
125 : {
126 : while (__x->_M_right != 0) __x = __x->_M_right;
127 : return __x;
128 : }
129 : };
130 :
131 : template<typename _Val>
132 : struct _Rb_tree_node : public _Rb_tree_node_base
133 : {
134 : typedef _Rb_tree_node<_Val>* _Link_type;
135 :
136 : #if __cplusplus < 201103L
137 : _Val _M_value_field;
138 :
139 : _Val*
140 : _M_valptr()
141 : { return std::__addressof(_M_value_field); }
142 :
143 : const _Val*
144 : _M_valptr() const
145 : { return std::__addressof(_M_value_field); }
146 : #else
147 : __gnu_cxx::__aligned_buffer<_Val> _M_storage;
148 :
149 : _Val*
150 0 : _M_valptr()
151 0 : { return _M_storage._M_ptr(); }
152 :
153 : const _Val*
154 0 : _M_valptr() const
155 0 : { return _M_storage._M_ptr(); }
156 : #endif
157 : };
158 :
159 : _GLIBCXX_PURE _Rb_tree_node_base*
160 : _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
161 :
162 : _GLIBCXX_PURE const _Rb_tree_node_base*
163 : _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
164 :
165 : _GLIBCXX_PURE _Rb_tree_node_base*
166 : _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
167 :
168 : _GLIBCXX_PURE const _Rb_tree_node_base*
169 : _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
170 :
171 : template<typename _Tp>
172 : struct _Rb_tree_iterator
173 : {
174 : typedef _Tp value_type;
175 : typedef _Tp& reference;
176 : typedef _Tp* pointer;
177 :
178 : typedef bidirectional_iterator_tag iterator_category;
179 : typedef ptrdiff_t difference_type;
180 :
181 : typedef _Rb_tree_iterator<_Tp> _Self;
182 : typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
183 : typedef _Rb_tree_node<_Tp>* _Link_type;
184 :
185 : _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
186 : : _M_node() { }
187 :
188 : explicit
189 0 : _Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT
190 0 : : _M_node(__x) { }
191 :
192 : reference
193 0 : operator*() const _GLIBCXX_NOEXCEPT
194 0 : { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
195 :
196 : pointer
197 : operator->() const _GLIBCXX_NOEXCEPT
198 : { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
199 :
200 : _Self&
201 0 : operator++() _GLIBCXX_NOEXCEPT
202 : {
203 0 : _M_node = _Rb_tree_increment(_M_node);
204 0 : return *this;
205 : }
206 :
207 : _Self
208 : operator++(int) _GLIBCXX_NOEXCEPT
209 : {
210 : _Self __tmp = *this;
211 : _M_node = _Rb_tree_increment(_M_node);
212 : return __tmp;
213 : }
214 :
215 : _Self&
216 0 : operator--() _GLIBCXX_NOEXCEPT
217 : {
218 0 : _M_node = _Rb_tree_decrement(_M_node);
219 0 : return *this;
220 : }
221 :
222 : _Self
223 : operator--(int) _GLIBCXX_NOEXCEPT
224 : {
225 : _Self __tmp = *this;
226 : _M_node = _Rb_tree_decrement(_M_node);
227 : return __tmp;
228 : }
229 :
230 : bool
231 0 : operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
232 0 : { return _M_node == __x._M_node; }
233 :
234 : bool
235 : operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
236 : { return _M_node != __x._M_node; }
237 :
238 : _Base_ptr _M_node;
239 : };
240 :
241 : template<typename _Tp>
242 : struct _Rb_tree_const_iterator
243 : {
244 : typedef _Tp value_type;
245 : typedef const _Tp& reference;
246 : typedef const _Tp* pointer;
247 :
248 : typedef _Rb_tree_iterator<_Tp> iterator;
249 :
250 : typedef bidirectional_iterator_tag iterator_category;
251 : typedef ptrdiff_t difference_type;
252 :
253 : typedef _Rb_tree_const_iterator<_Tp> _Self;
254 : typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
255 : typedef const _Rb_tree_node<_Tp>* _Link_type;
256 :
257 : _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
258 : : _M_node() { }
259 :
260 : explicit
261 0 : _Rb_tree_const_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT
262 0 : : _M_node(__x) { }
263 :
264 0 : _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
265 0 : : _M_node(__it._M_node) { }
266 :
267 : iterator
268 0 : _M_const_cast() const _GLIBCXX_NOEXCEPT
269 : { return iterator(static_cast<typename iterator::_Link_type>
270 0 : (const_cast<typename iterator::_Base_ptr>(_M_node))); }
271 :
272 : reference
273 : operator*() const _GLIBCXX_NOEXCEPT
274 : { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
275 :
276 : pointer
277 0 : operator->() const _GLIBCXX_NOEXCEPT
278 0 : { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
279 :
280 : _Self&
281 : operator++() _GLIBCXX_NOEXCEPT
282 : {
283 : _M_node = _Rb_tree_increment(_M_node);
284 : return *this;
285 : }
286 :
287 : _Self
288 : operator++(int) _GLIBCXX_NOEXCEPT
289 : {
290 : _Self __tmp = *this;
291 : _M_node = _Rb_tree_increment(_M_node);
292 : return __tmp;
293 : }
294 :
295 : _Self&
296 : operator--() _GLIBCXX_NOEXCEPT
297 : {
298 : _M_node = _Rb_tree_decrement(_M_node);
299 : return *this;
300 : }
301 :
302 : _Self
303 : operator--(int) _GLIBCXX_NOEXCEPT
304 : {
305 : _Self __tmp = *this;
306 : _M_node = _Rb_tree_decrement(_M_node);
307 : return __tmp;
308 : }
309 :
310 : bool
311 0 : operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
312 0 : { return _M_node == __x._M_node; }
313 :
314 : bool
315 0 : operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
316 0 : { return _M_node != __x._M_node; }
317 :
318 : _Base_ptr _M_node;
319 : };
320 :
321 : template<typename _Val>
322 : inline bool
323 : operator==(const _Rb_tree_iterator<_Val>& __x,
324 : const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
325 : { return __x._M_node == __y._M_node; }
326 :
327 : template<typename _Val>
328 : inline bool
329 : operator!=(const _Rb_tree_iterator<_Val>& __x,
330 : const _Rb_tree_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT
331 : { return __x._M_node != __y._M_node; }
332 :
333 : void
334 : _Rb_tree_insert_and_rebalance(const bool __insert_left,
335 : _Rb_tree_node_base* __x,
336 : _Rb_tree_node_base* __p,
337 : _Rb_tree_node_base& __header) throw ();
338 :
339 : _Rb_tree_node_base*
340 : _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
341 : _Rb_tree_node_base& __header) throw ();
342 :
343 :
344 : template<typename _Key, typename _Val, typename _KeyOfValue,
345 : typename _Compare, typename _Alloc = allocator<_Val> >
346 : class _Rb_tree
347 : {
348 : typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
349 : rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
350 :
351 : typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
352 :
353 : protected:
354 : typedef _Rb_tree_node_base* _Base_ptr;
355 : typedef const _Rb_tree_node_base* _Const_Base_ptr;
356 :
357 : public:
358 : typedef _Key key_type;
359 : typedef _Val value_type;
360 : typedef value_type* pointer;
361 : typedef const value_type* const_pointer;
362 : typedef value_type& reference;
363 : typedef const value_type& const_reference;
364 : typedef _Rb_tree_node<_Val>* _Link_type;
365 : typedef const _Rb_tree_node<_Val>* _Const_Link_type;
366 : typedef size_t size_type;
367 : typedef ptrdiff_t difference_type;
368 : typedef _Alloc allocator_type;
369 :
370 : _Node_allocator&
371 0 : _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
372 0 : { return *static_cast<_Node_allocator*>(&this->_M_impl); }
373 :
374 : const _Node_allocator&
375 : _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
376 : { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
377 :
378 : allocator_type
379 : get_allocator() const _GLIBCXX_NOEXCEPT
380 : { return allocator_type(_M_get_Node_allocator()); }
381 :
382 : protected:
383 : _Link_type
384 0 : _M_get_node()
385 0 : { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
386 :
387 : void
388 0 : _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
389 0 : { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
390 :
391 : #if __cplusplus < 201103L
392 : _Link_type
393 : _M_create_node(const value_type& __x)
394 : {
395 : _Link_type __tmp = _M_get_node();
396 : __try
397 : { get_allocator().construct(__tmp->_M_valptr(), __x); }
398 : __catch(...)
399 : {
400 : _M_put_node(__tmp);
401 : __throw_exception_again;
402 : }
403 : return __tmp;
404 : }
405 :
406 : void
407 : _M_destroy_node(_Link_type __p)
408 : {
409 : get_allocator().destroy(__p->_M_valptr());
410 : _M_put_node(__p);
411 : }
412 : #else
413 : template<typename... _Args>
414 : _Link_type
415 0 : _M_create_node(_Args&&... __args)
416 : {
417 0 : _Link_type __tmp = _M_get_node();
418 : __try
419 : {
420 0 : ::new(__tmp) _Rb_tree_node<_Val>;
421 0 : _Alloc_traits::construct(_M_get_Node_allocator(),
422 : __tmp->_M_valptr(),
423 0 : std::forward<_Args>(__args)...);
424 : }
425 0 : __catch(...)
426 : {
427 0 : _M_put_node(__tmp);
428 0 : __throw_exception_again;
429 : }
430 0 : return __tmp;
431 : }
432 :
433 : void
434 0 : _M_destroy_node(_Link_type __p) noexcept
435 : {
436 0 : _Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
437 : __p->~_Rb_tree_node<_Val>();
438 0 : _M_put_node(__p);
439 0 : }
440 : #endif
441 :
442 : _Link_type
443 : _M_clone_node(_Const_Link_type __x)
444 : {
445 : _Link_type __tmp = _M_create_node(*__x->_M_valptr());
446 : __tmp->_M_color = __x->_M_color;
447 : __tmp->_M_left = 0;
448 : __tmp->_M_right = 0;
449 : return __tmp;
450 : }
451 :
452 : protected:
453 : template<typename _Key_compare,
454 : bool _Is_pod_comparator = __is_pod(_Key_compare)>
455 0 : struct _Rb_tree_impl : public _Node_allocator
456 : {
457 : _Key_compare _M_key_compare;
458 : _Rb_tree_node_base _M_header;
459 : size_type _M_node_count; // Keeps track of size of tree.
460 :
461 0 : _Rb_tree_impl()
462 : : _Node_allocator(), _M_key_compare(), _M_header(),
463 0 : _M_node_count(0)
464 0 : { _M_initialize(); }
465 :
466 : _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
467 : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
468 : _M_node_count(0)
469 : { _M_initialize(); }
470 :
471 : #if __cplusplus >= 201103L
472 : _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
473 : : _Node_allocator(std::move(__a)), _M_key_compare(__comp),
474 : _M_header(), _M_node_count(0)
475 : { _M_initialize(); }
476 : #endif
477 :
478 : private:
479 : void
480 0 : _M_initialize()
481 : {
482 0 : this->_M_header._M_color = _S_red;
483 0 : this->_M_header._M_parent = 0;
484 0 : this->_M_header._M_left = &this->_M_header;
485 0 : this->_M_header._M_right = &this->_M_header;
486 0 : }
487 : };
488 :
489 : _Rb_tree_impl<_Compare> _M_impl;
490 :
491 : protected:
492 : _Base_ptr&
493 : _M_root() _GLIBCXX_NOEXCEPT
494 : { return this->_M_impl._M_header._M_parent; }
495 :
496 : _Const_Base_ptr
497 : _M_root() const _GLIBCXX_NOEXCEPT
498 : { return this->_M_impl._M_header._M_parent; }
499 :
500 : _Base_ptr&
501 0 : _M_leftmost() _GLIBCXX_NOEXCEPT
502 0 : { return this->_M_impl._M_header._M_left; }
503 :
504 : _Const_Base_ptr
505 : _M_leftmost() const _GLIBCXX_NOEXCEPT
506 : { return this->_M_impl._M_header._M_left; }
507 :
508 : _Base_ptr&
509 0 : _M_rightmost() _GLIBCXX_NOEXCEPT
510 0 : { return this->_M_impl._M_header._M_right; }
511 :
512 : _Const_Base_ptr
513 : _M_rightmost() const _GLIBCXX_NOEXCEPT
514 : { return this->_M_impl._M_header._M_right; }
515 :
516 : _Link_type
517 0 : _M_begin() _GLIBCXX_NOEXCEPT
518 0 : { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
519 :
520 : _Const_Link_type
521 0 : _M_begin() const _GLIBCXX_NOEXCEPT
522 : {
523 : return static_cast<_Const_Link_type>
524 0 : (this->_M_impl._M_header._M_parent);
525 : }
526 :
527 : _Link_type
528 0 : _M_end() _GLIBCXX_NOEXCEPT
529 0 : { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
530 :
531 : _Const_Link_type
532 0 : _M_end() const _GLIBCXX_NOEXCEPT
533 0 : { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
534 :
535 : static const_reference
536 0 : _S_value(_Const_Link_type __x)
537 0 : { return *__x->_M_valptr(); }
538 :
539 : static const _Key&
540 0 : _S_key(_Const_Link_type __x)
541 0 : { return _KeyOfValue()(_S_value(__x)); }
542 :
543 : static _Link_type
544 0 : _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
545 0 : { return static_cast<_Link_type>(__x->_M_left); }
546 :
547 : static _Const_Link_type
548 0 : _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
549 0 : { return static_cast<_Const_Link_type>(__x->_M_left); }
550 :
551 : static _Link_type
552 0 : _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
553 0 : { return static_cast<_Link_type>(__x->_M_right); }
554 :
555 : static _Const_Link_type
556 0 : _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
557 0 : { return static_cast<_Const_Link_type>(__x->_M_right); }
558 :
559 : static const_reference
560 0 : _S_value(_Const_Base_ptr __x)
561 0 : { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
562 :
563 : static const _Key&
564 0 : _S_key(_Const_Base_ptr __x)
565 0 : { return _KeyOfValue()(_S_value(__x)); }
566 :
567 : static _Base_ptr
568 : _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
569 : { return _Rb_tree_node_base::_S_minimum(__x); }
570 :
571 : static _Const_Base_ptr
572 : _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
573 : { return _Rb_tree_node_base::_S_minimum(__x); }
574 :
575 : static _Base_ptr
576 : _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
577 : { return _Rb_tree_node_base::_S_maximum(__x); }
578 :
579 : static _Const_Base_ptr
580 : _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
581 : { return _Rb_tree_node_base::_S_maximum(__x); }
582 :
583 : public:
584 : typedef _Rb_tree_iterator<value_type> iterator;
585 : typedef _Rb_tree_const_iterator<value_type> const_iterator;
586 :
587 : typedef std::reverse_iterator<iterator> reverse_iterator;
588 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
589 :
590 : private:
591 : pair<_Base_ptr, _Base_ptr>
592 : _M_get_insert_unique_pos(const key_type& __k);
593 :
594 : pair<_Base_ptr, _Base_ptr>
595 : _M_get_insert_equal_pos(const key_type& __k);
596 :
597 : pair<_Base_ptr, _Base_ptr>
598 : _M_get_insert_hint_unique_pos(const_iterator __pos,
599 : const key_type& __k);
600 :
601 : pair<_Base_ptr, _Base_ptr>
602 : _M_get_insert_hint_equal_pos(const_iterator __pos,
603 : const key_type& __k);
604 :
605 : #if __cplusplus >= 201103L
606 : template<typename _Arg>
607 : iterator
608 : _M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
609 :
610 : iterator
611 : _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
612 :
613 : template<typename _Arg>
614 : iterator
615 : _M_insert_lower(_Base_ptr __y, _Arg&& __v);
616 :
617 : template<typename _Arg>
618 : iterator
619 : _M_insert_equal_lower(_Arg&& __x);
620 :
621 : iterator
622 : _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
623 :
624 : iterator
625 : _M_insert_equal_lower_node(_Link_type __z);
626 : #else
627 : iterator
628 : _M_insert_(_Base_ptr __x, _Base_ptr __y,
629 : const value_type& __v);
630 :
631 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
632 : // 233. Insertion hints in associative containers.
633 : iterator
634 : _M_insert_lower(_Base_ptr __y, const value_type& __v);
635 :
636 : iterator
637 : _M_insert_equal_lower(const value_type& __x);
638 : #endif
639 :
640 : _Link_type
641 : _M_copy(_Const_Link_type __x, _Link_type __p);
642 :
643 : void
644 : _M_erase(_Link_type __x);
645 :
646 : iterator
647 : _M_lower_bound(_Link_type __x, _Link_type __y,
648 : const _Key& __k);
649 :
650 : const_iterator
651 : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
652 : const _Key& __k) const;
653 :
654 : iterator
655 : _M_upper_bound(_Link_type __x, _Link_type __y,
656 : const _Key& __k);
657 :
658 : const_iterator
659 : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
660 : const _Key& __k) const;
661 :
662 : public:
663 : // allocation/deallocation
664 0 : _Rb_tree() { }
665 :
666 : _Rb_tree(const _Compare& __comp,
667 : const allocator_type& __a = allocator_type())
668 : : _M_impl(__comp, _Node_allocator(__a)) { }
669 :
670 : _Rb_tree(const _Rb_tree& __x)
671 : : _M_impl(__x._M_impl._M_key_compare,
672 : _Alloc_traits::_S_select_on_copy(__x._M_get_Node_allocator()))
673 : {
674 : if (__x._M_root() != 0)
675 : {
676 : _M_root() = _M_copy(__x._M_begin(), _M_end());
677 : _M_leftmost() = _S_minimum(_M_root());
678 : _M_rightmost() = _S_maximum(_M_root());
679 : _M_impl._M_node_count = __x._M_impl._M_node_count;
680 : }
681 : }
682 :
683 : #if __cplusplus >= 201103L
684 : _Rb_tree(const allocator_type& __a)
685 : : _M_impl(_Compare(), _Node_allocator(__a))
686 : { }
687 :
688 : _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
689 : : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
690 : {
691 : if (__x._M_root() != 0)
692 : {
693 : _M_root() = _M_copy(__x._M_begin(), _M_end());
694 : _M_leftmost() = _S_minimum(_M_root());
695 : _M_rightmost() = _S_maximum(_M_root());
696 : _M_impl._M_node_count = __x._M_impl._M_node_count;
697 : }
698 : }
699 :
700 : _Rb_tree(_Rb_tree&& __x)
701 : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
702 : {
703 : if (__x._M_root() != 0)
704 : _M_move_data(__x, std::true_type());
705 : }
706 :
707 : _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
708 : : _Rb_tree(std::move(__x), _Node_allocator(__a))
709 : { }
710 :
711 : _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
712 : #endif
713 :
714 0 : ~_Rb_tree() _GLIBCXX_NOEXCEPT
715 0 : { _M_erase(_M_begin()); }
716 :
717 : _Rb_tree&
718 : operator=(const _Rb_tree& __x);
719 :
720 : // Accessors.
721 : _Compare
722 0 : key_comp() const
723 0 : { return _M_impl._M_key_compare; }
724 :
725 : iterator
726 0 : begin() _GLIBCXX_NOEXCEPT
727 : {
728 : return iterator(static_cast<_Link_type>
729 0 : (this->_M_impl._M_header._M_left));
730 : }
731 :
732 : const_iterator
733 : begin() const _GLIBCXX_NOEXCEPT
734 : {
735 : return const_iterator(static_cast<_Const_Link_type>
736 : (this->_M_impl._M_header._M_left));
737 : }
738 :
739 : iterator
740 0 : end() _GLIBCXX_NOEXCEPT
741 0 : { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
742 :
743 : const_iterator
744 0 : end() const _GLIBCXX_NOEXCEPT
745 : {
746 : return const_iterator(static_cast<_Const_Link_type>
747 0 : (&this->_M_impl._M_header));
748 : }
749 :
750 : reverse_iterator
751 : rbegin() _GLIBCXX_NOEXCEPT
752 : { return reverse_iterator(end()); }
753 :
754 : const_reverse_iterator
755 : rbegin() const _GLIBCXX_NOEXCEPT
756 : { return const_reverse_iterator(end()); }
757 :
758 : reverse_iterator
759 : rend() _GLIBCXX_NOEXCEPT
760 : { return reverse_iterator(begin()); }
761 :
762 : const_reverse_iterator
763 : rend() const _GLIBCXX_NOEXCEPT
764 : { return const_reverse_iterator(begin()); }
765 :
766 : bool
767 : empty() const _GLIBCXX_NOEXCEPT
768 : { return _M_impl._M_node_count == 0; }
769 :
770 : size_type
771 0 : size() const _GLIBCXX_NOEXCEPT
772 0 : { return _M_impl._M_node_count; }
773 :
774 : size_type
775 : max_size() const _GLIBCXX_NOEXCEPT
776 : { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
777 :
778 : void
779 : #if __cplusplus >= 201103L
780 : swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
781 : #else
782 : swap(_Rb_tree& __t);
783 : #endif
784 :
785 : // Insert/erase.
786 : #if __cplusplus >= 201103L
787 : template<typename _Arg>
788 : pair<iterator, bool>
789 : _M_insert_unique(_Arg&& __x);
790 :
791 : template<typename _Arg>
792 : iterator
793 : _M_insert_equal(_Arg&& __x);
794 :
795 : template<typename _Arg>
796 : iterator
797 : _M_insert_unique_(const_iterator __position, _Arg&& __x);
798 :
799 : template<typename _Arg>
800 : iterator
801 : _M_insert_equal_(const_iterator __position, _Arg&& __x);
802 :
803 : template<typename... _Args>
804 : pair<iterator, bool>
805 : _M_emplace_unique(_Args&&... __args);
806 :
807 : template<typename... _Args>
808 : iterator
809 : _M_emplace_equal(_Args&&... __args);
810 :
811 : template<typename... _Args>
812 : iterator
813 : _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
814 :
815 : template<typename... _Args>
816 : iterator
817 : _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
818 : #else
819 : pair<iterator, bool>
820 : _M_insert_unique(const value_type& __x);
821 :
822 : iterator
823 : _M_insert_equal(const value_type& __x);
824 :
825 : iterator
826 : _M_insert_unique_(const_iterator __position, const value_type& __x);
827 :
828 : iterator
829 : _M_insert_equal_(const_iterator __position, const value_type& __x);
830 : #endif
831 :
832 : template<typename _InputIterator>
833 : void
834 : _M_insert_unique(_InputIterator __first, _InputIterator __last);
835 :
836 : template<typename _InputIterator>
837 : void
838 : _M_insert_equal(_InputIterator __first, _InputIterator __last);
839 :
840 : private:
841 : void
842 : _M_erase_aux(const_iterator __position);
843 :
844 : void
845 : _M_erase_aux(const_iterator __first, const_iterator __last);
846 :
847 : public:
848 : #if __cplusplus >= 201103L
849 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
850 : // DR 130. Associative erase should return an iterator.
851 : _GLIBCXX_ABI_TAG_CXX11
852 : iterator
853 : erase(const_iterator __position)
854 : {
855 : const_iterator __result = __position;
856 : ++__result;
857 : _M_erase_aux(__position);
858 : return __result._M_const_cast();
859 : }
860 :
861 : // LWG 2059.
862 : _GLIBCXX_ABI_TAG_CXX11
863 : iterator
864 : erase(iterator __position)
865 : {
866 : iterator __result = __position;
867 : ++__result;
868 : _M_erase_aux(__position);
869 : return __result;
870 : }
871 : #else
872 : void
873 : erase(iterator __position)
874 : { _M_erase_aux(__position); }
875 :
876 : void
877 : erase(const_iterator __position)
878 : { _M_erase_aux(__position); }
879 : #endif
880 : size_type
881 : erase(const key_type& __x);
882 :
883 : #if __cplusplus >= 201103L
884 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
885 : // DR 130. Associative erase should return an iterator.
886 : _GLIBCXX_ABI_TAG_CXX11
887 : iterator
888 : erase(const_iterator __first, const_iterator __last)
889 : {
890 : _M_erase_aux(__first, __last);
891 : return __last._M_const_cast();
892 : }
893 : #else
894 : void
895 : erase(iterator __first, iterator __last)
896 : { _M_erase_aux(__first, __last); }
897 :
898 : void
899 : erase(const_iterator __first, const_iterator __last)
900 : { _M_erase_aux(__first, __last); }
901 : #endif
902 : void
903 : erase(const key_type* __first, const key_type* __last);
904 :
905 : void
906 : clear() _GLIBCXX_NOEXCEPT
907 : {
908 : _M_erase(_M_begin());
909 : _M_leftmost() = _M_end();
910 : _M_root() = 0;
911 : _M_rightmost() = _M_end();
912 : _M_impl._M_node_count = 0;
913 : }
914 :
915 : // Set operations.
916 : iterator
917 : find(const key_type& __k);
918 :
919 : const_iterator
920 : find(const key_type& __k) const;
921 :
922 : size_type
923 : count(const key_type& __k) const;
924 :
925 : iterator
926 0 : lower_bound(const key_type& __k)
927 0 : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
928 :
929 : const_iterator
930 : lower_bound(const key_type& __k) const
931 : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
932 :
933 : iterator
934 : upper_bound(const key_type& __k)
935 : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
936 :
937 : const_iterator
938 : upper_bound(const key_type& __k) const
939 : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
940 :
941 : pair<iterator, iterator>
942 : equal_range(const key_type& __k);
943 :
944 : pair<const_iterator, const_iterator>
945 : equal_range(const key_type& __k) const;
946 :
947 : // Debugging.
948 : bool
949 : __rb_verify() const;
950 :
951 : #if __cplusplus >= 201103L
952 : bool
953 : _M_move_assign(_Rb_tree&);
954 :
955 : private:
956 : // Move elements from container with equal allocator.
957 : void
958 : _M_move_data(_Rb_tree&, std::true_type);
959 :
960 : // Move elements from container with possibly non-equal allocator,
961 : // which might result in a copy not a move.
962 : void
963 : _M_move_data(_Rb_tree&, std::false_type);
964 : #endif
965 : };
966 :
967 : template<typename _Key, typename _Val, typename _KeyOfValue,
968 : typename _Compare, typename _Alloc>
969 : inline bool
970 : operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
971 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
972 : {
973 : return __x.size() == __y.size()
974 : && std::equal(__x.begin(), __x.end(), __y.begin());
975 : }
976 :
977 : template<typename _Key, typename _Val, typename _KeyOfValue,
978 : typename _Compare, typename _Alloc>
979 : inline bool
980 : operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
981 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
982 : {
983 : return std::lexicographical_compare(__x.begin(), __x.end(),
984 : __y.begin(), __y.end());
985 : }
986 :
987 : template<typename _Key, typename _Val, typename _KeyOfValue,
988 : typename _Compare, typename _Alloc>
989 : inline bool
990 : operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
991 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
992 : { return !(__x == __y); }
993 :
994 : template<typename _Key, typename _Val, typename _KeyOfValue,
995 : typename _Compare, typename _Alloc>
996 : inline bool
997 : operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
998 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
999 : { return __y < __x; }
1000 :
1001 : template<typename _Key, typename _Val, typename _KeyOfValue,
1002 : typename _Compare, typename _Alloc>
1003 : inline bool
1004 : operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1005 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1006 : { return !(__y < __x); }
1007 :
1008 : template<typename _Key, typename _Val, typename _KeyOfValue,
1009 : typename _Compare, typename _Alloc>
1010 : inline bool
1011 : operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1012 : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1013 : { return !(__x < __y); }
1014 :
1015 : template<typename _Key, typename _Val, typename _KeyOfValue,
1016 : typename _Compare, typename _Alloc>
1017 : inline void
1018 : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1019 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1020 : { __x.swap(__y); }
1021 :
1022 : #if __cplusplus >= 201103L
1023 : template<typename _Key, typename _Val, typename _KeyOfValue,
1024 : typename _Compare, typename _Alloc>
1025 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1026 : _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1027 : : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1028 : {
1029 : using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
1030 : if (__x._M_root() != 0)
1031 : _M_move_data(__x, __eq());
1032 : }
1033 :
1034 : template<typename _Key, typename _Val, typename _KeyOfValue,
1035 : typename _Compare, typename _Alloc>
1036 : void
1037 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1038 : _M_move_data(_Rb_tree& __x, std::true_type)
1039 : {
1040 : _M_root() = __x._M_root();
1041 : _M_leftmost() = __x._M_leftmost();
1042 : _M_rightmost() = __x._M_rightmost();
1043 : _M_root()->_M_parent = _M_end();
1044 :
1045 : __x._M_root() = 0;
1046 : __x._M_leftmost() = __x._M_end();
1047 : __x._M_rightmost() = __x._M_end();
1048 :
1049 : this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1050 : __x._M_impl._M_node_count = 0;
1051 : }
1052 :
1053 : template<typename _Key, typename _Val, typename _KeyOfValue,
1054 : typename _Compare, typename _Alloc>
1055 : void
1056 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1057 : _M_move_data(_Rb_tree& __x, std::false_type)
1058 : {
1059 : if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1060 : _M_move_data(__x, std::true_type());
1061 : else
1062 : {
1063 : _M_root() = _M_copy(__x._M_begin(), _M_end());
1064 : _M_leftmost() = _S_minimum(_M_root());
1065 : _M_rightmost() = _S_maximum(_M_root());
1066 : _M_impl._M_node_count = __x._M_impl._M_node_count;
1067 : }
1068 : }
1069 :
1070 : template<typename _Key, typename _Val, typename _KeyOfValue,
1071 : typename _Compare, typename _Alloc>
1072 : bool
1073 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1074 : _M_move_assign(_Rb_tree& __x)
1075 : {
1076 : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1077 : if (_Alloc_traits::_S_propagate_on_move_assign()
1078 : || _Alloc_traits::_S_always_equal()
1079 : || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1080 : {
1081 : clear();
1082 : if (__x._M_root() != 0)
1083 : _M_move_data(__x, std::true_type());
1084 : std::__alloc_on_move(_M_get_Node_allocator(),
1085 : __x._M_get_Node_allocator());
1086 : return true;
1087 : }
1088 : return false;
1089 : }
1090 : #endif
1091 :
1092 : template<typename _Key, typename _Val, typename _KeyOfValue,
1093 : typename _Compare, typename _Alloc>
1094 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1095 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1096 : operator=(const _Rb_tree& __x)
1097 : {
1098 : if (this != &__x)
1099 : {
1100 : // Note that _Key may be a constant type.
1101 : clear();
1102 : #if __cplusplus >= 201103L
1103 : if (_Alloc_traits::_S_propagate_on_copy_assign())
1104 : {
1105 : auto& __this_alloc = this->_M_get_Node_allocator();
1106 : auto& __that_alloc = __x._M_get_Node_allocator();
1107 : if (!_Alloc_traits::_S_always_equal()
1108 : && __this_alloc != __that_alloc)
1109 : {
1110 : std::__alloc_on_copy(__this_alloc, __that_alloc);
1111 : }
1112 : }
1113 : #endif
1114 : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1115 : if (__x._M_root() != 0)
1116 : {
1117 : _M_root() = _M_copy(__x._M_begin(), _M_end());
1118 : _M_leftmost() = _S_minimum(_M_root());
1119 : _M_rightmost() = _S_maximum(_M_root());
1120 : _M_impl._M_node_count = __x._M_impl._M_node_count;
1121 : }
1122 : }
1123 : return *this;
1124 : }
1125 :
1126 : template<typename _Key, typename _Val, typename _KeyOfValue,
1127 : typename _Compare, typename _Alloc>
1128 : #if __cplusplus >= 201103L
1129 : template<typename _Arg>
1130 : #endif
1131 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1132 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1133 : #if __cplusplus >= 201103L
1134 : _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
1135 : #else
1136 : _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1137 : #endif
1138 : {
1139 : bool __insert_left = (__x != 0 || __p == _M_end()
1140 : || _M_impl._M_key_compare(_KeyOfValue()(__v),
1141 : _S_key(__p)));
1142 :
1143 : _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1144 :
1145 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1146 : this->_M_impl._M_header);
1147 : ++_M_impl._M_node_count;
1148 : return iterator(__z);
1149 : }
1150 :
1151 : template<typename _Key, typename _Val, typename _KeyOfValue,
1152 : typename _Compare, typename _Alloc>
1153 : #if __cplusplus >= 201103L
1154 : template<typename _Arg>
1155 : #endif
1156 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1157 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1158 : #if __cplusplus >= 201103L
1159 : _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1160 : #else
1161 : _M_insert_lower(_Base_ptr __p, const _Val& __v)
1162 : #endif
1163 : {
1164 : bool __insert_left = (__p == _M_end()
1165 : || !_M_impl._M_key_compare(_S_key(__p),
1166 : _KeyOfValue()(__v)));
1167 :
1168 : _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1169 :
1170 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1171 : this->_M_impl._M_header);
1172 : ++_M_impl._M_node_count;
1173 : return iterator(__z);
1174 : }
1175 :
1176 : template<typename _Key, typename _Val, typename _KeyOfValue,
1177 : typename _Compare, typename _Alloc>
1178 : #if __cplusplus >= 201103L
1179 : template<typename _Arg>
1180 : #endif
1181 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1182 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1183 : #if __cplusplus >= 201103L
1184 : _M_insert_equal_lower(_Arg&& __v)
1185 : #else
1186 : _M_insert_equal_lower(const _Val& __v)
1187 : #endif
1188 : {
1189 : _Link_type __x = _M_begin();
1190 : _Link_type __y = _M_end();
1191 : while (__x != 0)
1192 : {
1193 : __y = __x;
1194 : __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1195 : _S_left(__x) : _S_right(__x);
1196 : }
1197 : return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1198 : }
1199 :
1200 : template<typename _Key, typename _Val, typename _KoV,
1201 : typename _Compare, typename _Alloc>
1202 : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1203 : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1204 : _M_copy(_Const_Link_type __x, _Link_type __p)
1205 : {
1206 : // Structural copy. __x and __p must be non-null.
1207 : _Link_type __top = _M_clone_node(__x);
1208 : __top->_M_parent = __p;
1209 :
1210 : __try
1211 : {
1212 : if (__x->_M_right)
1213 : __top->_M_right = _M_copy(_S_right(__x), __top);
1214 : __p = __top;
1215 : __x = _S_left(__x);
1216 :
1217 : while (__x != 0)
1218 : {
1219 : _Link_type __y = _M_clone_node(__x);
1220 : __p->_M_left = __y;
1221 : __y->_M_parent = __p;
1222 : if (__x->_M_right)
1223 : __y->_M_right = _M_copy(_S_right(__x), __y);
1224 : __p = __y;
1225 : __x = _S_left(__x);
1226 : }
1227 : }
1228 : __catch(...)
1229 : {
1230 : _M_erase(__top);
1231 : __throw_exception_again;
1232 : }
1233 : return __top;
1234 : }
1235 :
1236 : template<typename _Key, typename _Val, typename _KeyOfValue,
1237 : typename _Compare, typename _Alloc>
1238 : void
1239 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1240 : _M_erase(_Link_type __x)
1241 : {
1242 : // Erase without rebalancing.
1243 0 : while (__x != 0)
1244 : {
1245 0 : _M_erase(_S_right(__x));
1246 0 : _Link_type __y = _S_left(__x);
1247 0 : _M_destroy_node(__x);
1248 0 : __x = __y;
1249 : }
1250 0 : }
1251 :
1252 : template<typename _Key, typename _Val, typename _KeyOfValue,
1253 : typename _Compare, typename _Alloc>
1254 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1255 : _Compare, _Alloc>::iterator
1256 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1257 : _M_lower_bound(_Link_type __x, _Link_type __y,
1258 : const _Key& __k)
1259 : {
1260 0 : while (__x != 0)
1261 0 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1262 0 : __y = __x, __x = _S_left(__x);
1263 : else
1264 0 : __x = _S_right(__x);
1265 0 : return iterator(__y);
1266 : }
1267 :
1268 : template<typename _Key, typename _Val, typename _KeyOfValue,
1269 : typename _Compare, typename _Alloc>
1270 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1271 : _Compare, _Alloc>::const_iterator
1272 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1273 : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1274 : const _Key& __k) const
1275 : {
1276 0 : while (__x != 0)
1277 0 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
1278 0 : __y = __x, __x = _S_left(__x);
1279 : else
1280 0 : __x = _S_right(__x);
1281 0 : return const_iterator(__y);
1282 : }
1283 :
1284 : template<typename _Key, typename _Val, typename _KeyOfValue,
1285 : typename _Compare, typename _Alloc>
1286 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1287 : _Compare, _Alloc>::iterator
1288 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1289 : _M_upper_bound(_Link_type __x, _Link_type __y,
1290 : const _Key& __k)
1291 : {
1292 : while (__x != 0)
1293 : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1294 : __y = __x, __x = _S_left(__x);
1295 : else
1296 : __x = _S_right(__x);
1297 : return iterator(__y);
1298 : }
1299 :
1300 : template<typename _Key, typename _Val, typename _KeyOfValue,
1301 : typename _Compare, typename _Alloc>
1302 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1303 : _Compare, _Alloc>::const_iterator
1304 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1305 : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1306 : const _Key& __k) const
1307 : {
1308 : while (__x != 0)
1309 : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1310 : __y = __x, __x = _S_left(__x);
1311 : else
1312 : __x = _S_right(__x);
1313 : return const_iterator(__y);
1314 : }
1315 :
1316 : template<typename _Key, typename _Val, typename _KeyOfValue,
1317 : typename _Compare, typename _Alloc>
1318 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1319 : _Compare, _Alloc>::iterator,
1320 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1321 : _Compare, _Alloc>::iterator>
1322 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1323 : equal_range(const _Key& __k)
1324 : {
1325 : _Link_type __x = _M_begin();
1326 : _Link_type __y = _M_end();
1327 : while (__x != 0)
1328 : {
1329 : if (_M_impl._M_key_compare(_S_key(__x), __k))
1330 : __x = _S_right(__x);
1331 : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1332 : __y = __x, __x = _S_left(__x);
1333 : else
1334 : {
1335 : _Link_type __xu(__x), __yu(__y);
1336 : __y = __x, __x = _S_left(__x);
1337 : __xu = _S_right(__xu);
1338 : return pair<iterator,
1339 : iterator>(_M_lower_bound(__x, __y, __k),
1340 : _M_upper_bound(__xu, __yu, __k));
1341 : }
1342 : }
1343 : return pair<iterator, iterator>(iterator(__y),
1344 : iterator(__y));
1345 : }
1346 :
1347 : template<typename _Key, typename _Val, typename _KeyOfValue,
1348 : typename _Compare, typename _Alloc>
1349 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1350 : _Compare, _Alloc>::const_iterator,
1351 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1352 : _Compare, _Alloc>::const_iterator>
1353 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1354 : equal_range(const _Key& __k) const
1355 : {
1356 : _Const_Link_type __x = _M_begin();
1357 : _Const_Link_type __y = _M_end();
1358 : while (__x != 0)
1359 : {
1360 : if (_M_impl._M_key_compare(_S_key(__x), __k))
1361 : __x = _S_right(__x);
1362 : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1363 : __y = __x, __x = _S_left(__x);
1364 : else
1365 : {
1366 : _Const_Link_type __xu(__x), __yu(__y);
1367 : __y = __x, __x = _S_left(__x);
1368 : __xu = _S_right(__xu);
1369 : return pair<const_iterator,
1370 : const_iterator>(_M_lower_bound(__x, __y, __k),
1371 : _M_upper_bound(__xu, __yu, __k));
1372 : }
1373 : }
1374 : return pair<const_iterator, const_iterator>(const_iterator(__y),
1375 : const_iterator(__y));
1376 : }
1377 :
1378 : template<typename _Key, typename _Val, typename _KeyOfValue,
1379 : typename _Compare, typename _Alloc>
1380 : void
1381 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1382 : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1383 : #if __cplusplus >= 201103L
1384 : noexcept(_Alloc_traits::_S_nothrow_swap())
1385 : #endif
1386 : {
1387 : if (_M_root() == 0)
1388 : {
1389 : if (__t._M_root() != 0)
1390 : {
1391 : _M_root() = __t._M_root();
1392 : _M_leftmost() = __t._M_leftmost();
1393 : _M_rightmost() = __t._M_rightmost();
1394 : _M_root()->_M_parent = _M_end();
1395 :
1396 : __t._M_root() = 0;
1397 : __t._M_leftmost() = __t._M_end();
1398 : __t._M_rightmost() = __t._M_end();
1399 : }
1400 : }
1401 : else if (__t._M_root() == 0)
1402 : {
1403 : __t._M_root() = _M_root();
1404 : __t._M_leftmost() = _M_leftmost();
1405 : __t._M_rightmost() = _M_rightmost();
1406 : __t._M_root()->_M_parent = __t._M_end();
1407 :
1408 : _M_root() = 0;
1409 : _M_leftmost() = _M_end();
1410 : _M_rightmost() = _M_end();
1411 : }
1412 : else
1413 : {
1414 : std::swap(_M_root(),__t._M_root());
1415 : std::swap(_M_leftmost(),__t._M_leftmost());
1416 : std::swap(_M_rightmost(),__t._M_rightmost());
1417 :
1418 : _M_root()->_M_parent = _M_end();
1419 : __t._M_root()->_M_parent = __t._M_end();
1420 : }
1421 : // No need to swap header's color as it does not change.
1422 : std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1423 : std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1424 :
1425 : _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1426 : __t._M_get_Node_allocator());
1427 : }
1428 :
1429 : template<typename _Key, typename _Val, typename _KeyOfValue,
1430 : typename _Compare, typename _Alloc>
1431 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1432 : _Compare, _Alloc>::_Base_ptr,
1433 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1434 : _Compare, _Alloc>::_Base_ptr>
1435 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1436 : _M_get_insert_unique_pos(const key_type& __k)
1437 : {
1438 : typedef pair<_Base_ptr, _Base_ptr> _Res;
1439 0 : _Link_type __x = _M_begin();
1440 0 : _Link_type __y = _M_end();
1441 0 : bool __comp = true;
1442 0 : while (__x != 0)
1443 : {
1444 0 : __y = __x;
1445 0 : __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1446 0 : __x = __comp ? _S_left(__x) : _S_right(__x);
1447 : }
1448 0 : iterator __j = iterator(__y);
1449 0 : if (__comp)
1450 : {
1451 0 : if (__j == begin())
1452 0 : return _Res(__x, __y);
1453 : else
1454 0 : --__j;
1455 : }
1456 0 : if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1457 0 : return _Res(__x, __y);
1458 0 : return _Res(__j._M_node, 0);
1459 : }
1460 :
1461 : template<typename _Key, typename _Val, typename _KeyOfValue,
1462 : typename _Compare, typename _Alloc>
1463 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1464 : _Compare, _Alloc>::_Base_ptr,
1465 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1466 : _Compare, _Alloc>::_Base_ptr>
1467 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1468 : _M_get_insert_equal_pos(const key_type& __k)
1469 : {
1470 : typedef pair<_Base_ptr, _Base_ptr> _Res;
1471 : _Link_type __x = _M_begin();
1472 : _Link_type __y = _M_end();
1473 : while (__x != 0)
1474 : {
1475 : __y = __x;
1476 : __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1477 : _S_left(__x) : _S_right(__x);
1478 : }
1479 : return _Res(__x, __y);
1480 : }
1481 :
1482 : template<typename _Key, typename _Val, typename _KeyOfValue,
1483 : typename _Compare, typename _Alloc>
1484 : #if __cplusplus >= 201103L
1485 : template<typename _Arg>
1486 : #endif
1487 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1488 : _Compare, _Alloc>::iterator, bool>
1489 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1490 : #if __cplusplus >= 201103L
1491 : _M_insert_unique(_Arg&& __v)
1492 : #else
1493 : _M_insert_unique(const _Val& __v)
1494 : #endif
1495 : {
1496 : typedef pair<iterator, bool> _Res;
1497 : pair<_Base_ptr, _Base_ptr> __res
1498 : = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1499 :
1500 : if (__res.second)
1501 : return _Res(_M_insert_(__res.first, __res.second,
1502 : _GLIBCXX_FORWARD(_Arg, __v)),
1503 : true);
1504 :
1505 : return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1506 : }
1507 :
1508 : template<typename _Key, typename _Val, typename _KeyOfValue,
1509 : typename _Compare, typename _Alloc>
1510 : #if __cplusplus >= 201103L
1511 : template<typename _Arg>
1512 : #endif
1513 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1514 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1515 : #if __cplusplus >= 201103L
1516 : _M_insert_equal(_Arg&& __v)
1517 : #else
1518 : _M_insert_equal(const _Val& __v)
1519 : #endif
1520 : {
1521 : pair<_Base_ptr, _Base_ptr> __res
1522 : = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1523 : return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
1524 : }
1525 :
1526 : template<typename _Key, typename _Val, typename _KeyOfValue,
1527 : typename _Compare, typename _Alloc>
1528 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1529 : _Compare, _Alloc>::_Base_ptr,
1530 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1531 : _Compare, _Alloc>::_Base_ptr>
1532 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1533 : _M_get_insert_hint_unique_pos(const_iterator __position,
1534 : const key_type& __k)
1535 : {
1536 0 : iterator __pos = __position._M_const_cast();
1537 : typedef pair<_Base_ptr, _Base_ptr> _Res;
1538 :
1539 : // end()
1540 0 : if (__pos._M_node == _M_end())
1541 : {
1542 0 : if (size() > 0
1543 0 : && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1544 0 : return _Res(0, _M_rightmost());
1545 : else
1546 0 : return _M_get_insert_unique_pos(__k);
1547 : }
1548 0 : else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1549 : {
1550 : // First, try before...
1551 0 : iterator __before = __pos;
1552 0 : if (__pos._M_node == _M_leftmost()) // begin()
1553 0 : return _Res(_M_leftmost(), _M_leftmost());
1554 0 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1555 : {
1556 0 : if (_S_right(__before._M_node) == 0)
1557 0 : return _Res(0, __before._M_node);
1558 : else
1559 0 : return _Res(__pos._M_node, __pos._M_node);
1560 : }
1561 : else
1562 0 : return _M_get_insert_unique_pos(__k);
1563 : }
1564 0 : else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1565 : {
1566 : // ... then try after.
1567 0 : iterator __after = __pos;
1568 0 : if (__pos._M_node == _M_rightmost())
1569 0 : return _Res(0, _M_rightmost());
1570 0 : else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1571 : {
1572 0 : if (_S_right(__pos._M_node) == 0)
1573 0 : return _Res(0, __pos._M_node);
1574 : else
1575 0 : return _Res(__after._M_node, __after._M_node);
1576 : }
1577 : else
1578 0 : return _M_get_insert_unique_pos(__k);
1579 : }
1580 : else
1581 : // Equivalent keys.
1582 0 : return _Res(__pos._M_node, 0);
1583 : }
1584 :
1585 : template<typename _Key, typename _Val, typename _KeyOfValue,
1586 : typename _Compare, typename _Alloc>
1587 : #if __cplusplus >= 201103L
1588 : template<typename _Arg>
1589 : #endif
1590 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1591 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1592 : #if __cplusplus >= 201103L
1593 : _M_insert_unique_(const_iterator __position, _Arg&& __v)
1594 : #else
1595 : _M_insert_unique_(const_iterator __position, const _Val& __v)
1596 : #endif
1597 : {
1598 : pair<_Base_ptr, _Base_ptr> __res
1599 : = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1600 :
1601 : if (__res.second)
1602 : return _M_insert_(__res.first, __res.second,
1603 : _GLIBCXX_FORWARD(_Arg, __v));
1604 : return iterator(static_cast<_Link_type>(__res.first));
1605 : }
1606 :
1607 : template<typename _Key, typename _Val, typename _KeyOfValue,
1608 : typename _Compare, typename _Alloc>
1609 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1610 : _Compare, _Alloc>::_Base_ptr,
1611 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1612 : _Compare, _Alloc>::_Base_ptr>
1613 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1614 : _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1615 : {
1616 : iterator __pos = __position._M_const_cast();
1617 : typedef pair<_Base_ptr, _Base_ptr> _Res;
1618 :
1619 : // end()
1620 : if (__pos._M_node == _M_end())
1621 : {
1622 : if (size() > 0
1623 : && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1624 : return _Res(0, _M_rightmost());
1625 : else
1626 : return _M_get_insert_equal_pos(__k);
1627 : }
1628 : else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1629 : {
1630 : // First, try before...
1631 : iterator __before = __pos;
1632 : if (__pos._M_node == _M_leftmost()) // begin()
1633 : return _Res(_M_leftmost(), _M_leftmost());
1634 : else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
1635 : {
1636 : if (_S_right(__before._M_node) == 0)
1637 : return _Res(0, __before._M_node);
1638 : else
1639 : return _Res(__pos._M_node, __pos._M_node);
1640 : }
1641 : else
1642 : return _M_get_insert_equal_pos(__k);
1643 : }
1644 : else
1645 : {
1646 : // ... then try after.
1647 : iterator __after = __pos;
1648 : if (__pos._M_node == _M_rightmost())
1649 : return _Res(0, _M_rightmost());
1650 : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
1651 : {
1652 : if (_S_right(__pos._M_node) == 0)
1653 : return _Res(0, __pos._M_node);
1654 : else
1655 : return _Res(__after._M_node, __after._M_node);
1656 : }
1657 : else
1658 : return _Res(0, 0);
1659 : }
1660 : }
1661 :
1662 : template<typename _Key, typename _Val, typename _KeyOfValue,
1663 : typename _Compare, typename _Alloc>
1664 : #if __cplusplus >= 201103L
1665 : template<typename _Arg>
1666 : #endif
1667 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1668 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1669 : #if __cplusplus >= 201103L
1670 : _M_insert_equal_(const_iterator __position, _Arg&& __v)
1671 : #else
1672 : _M_insert_equal_(const_iterator __position, const _Val& __v)
1673 : #endif
1674 : {
1675 : pair<_Base_ptr, _Base_ptr> __res
1676 : = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
1677 :
1678 : if (__res.second)
1679 : return _M_insert_(__res.first, __res.second,
1680 : _GLIBCXX_FORWARD(_Arg, __v));
1681 :
1682 : return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1683 : }
1684 :
1685 : #if __cplusplus >= 201103L
1686 : template<typename _Key, typename _Val, typename _KeyOfValue,
1687 : typename _Compare, typename _Alloc>
1688 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1689 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1690 : _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
1691 : {
1692 0 : bool __insert_left = (__x != 0 || __p == _M_end()
1693 0 : || _M_impl._M_key_compare(_S_key(__z),
1694 0 : _S_key(__p)));
1695 :
1696 0 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1697 0 : this->_M_impl._M_header);
1698 0 : ++_M_impl._M_node_count;
1699 0 : return iterator(__z);
1700 : }
1701 :
1702 : template<typename _Key, typename _Val, typename _KeyOfValue,
1703 : typename _Compare, typename _Alloc>
1704 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1705 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1706 : _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
1707 : {
1708 : bool __insert_left = (__p == _M_end()
1709 : || !_M_impl._M_key_compare(_S_key(__p),
1710 : _S_key(__z)));
1711 :
1712 : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1713 : this->_M_impl._M_header);
1714 : ++_M_impl._M_node_count;
1715 : return iterator(__z);
1716 : }
1717 :
1718 : template<typename _Key, typename _Val, typename _KeyOfValue,
1719 : typename _Compare, typename _Alloc>
1720 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1721 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1722 : _M_insert_equal_lower_node(_Link_type __z)
1723 : {
1724 : _Link_type __x = _M_begin();
1725 : _Link_type __y = _M_end();
1726 : while (__x != 0)
1727 : {
1728 : __y = __x;
1729 : __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
1730 : _S_left(__x) : _S_right(__x);
1731 : }
1732 : return _M_insert_lower_node(__y, __z);
1733 : }
1734 :
1735 : template<typename _Key, typename _Val, typename _KeyOfValue,
1736 : typename _Compare, typename _Alloc>
1737 : template<typename... _Args>
1738 : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1739 : _Compare, _Alloc>::iterator, bool>
1740 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1741 : _M_emplace_unique(_Args&&... __args)
1742 : {
1743 : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1744 :
1745 : __try
1746 : {
1747 : typedef pair<iterator, bool> _Res;
1748 : auto __res = _M_get_insert_unique_pos(_S_key(__z));
1749 : if (__res.second)
1750 : return _Res(_M_insert_node(__res.first, __res.second, __z), true);
1751 :
1752 : _M_destroy_node(__z);
1753 : return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1754 : }
1755 : __catch(...)
1756 : {
1757 : _M_destroy_node(__z);
1758 : __throw_exception_again;
1759 : }
1760 : }
1761 :
1762 : template<typename _Key, typename _Val, typename _KeyOfValue,
1763 : typename _Compare, typename _Alloc>
1764 : template<typename... _Args>
1765 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1766 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1767 : _M_emplace_equal(_Args&&... __args)
1768 : {
1769 : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1770 :
1771 : __try
1772 : {
1773 : auto __res = _M_get_insert_equal_pos(_S_key(__z));
1774 : return _M_insert_node(__res.first, __res.second, __z);
1775 : }
1776 : __catch(...)
1777 : {
1778 : _M_destroy_node(__z);
1779 : __throw_exception_again;
1780 : }
1781 : }
1782 :
1783 : template<typename _Key, typename _Val, typename _KeyOfValue,
1784 : typename _Compare, typename _Alloc>
1785 : template<typename... _Args>
1786 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1787 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1788 : _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
1789 : {
1790 0 : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1791 :
1792 : __try
1793 : {
1794 0 : auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
1795 :
1796 0 : if (__res.second)
1797 0 : return _M_insert_node(__res.first, __res.second, __z);
1798 :
1799 0 : _M_destroy_node(__z);
1800 0 : return iterator(static_cast<_Link_type>(__res.first));
1801 : }
1802 0 : __catch(...)
1803 : {
1804 0 : _M_destroy_node(__z);
1805 0 : __throw_exception_again;
1806 : }
1807 : }
1808 :
1809 : template<typename _Key, typename _Val, typename _KeyOfValue,
1810 : typename _Compare, typename _Alloc>
1811 : template<typename... _Args>
1812 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1813 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1814 : _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
1815 : {
1816 : _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1817 :
1818 : __try
1819 : {
1820 : auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
1821 :
1822 : if (__res.second)
1823 : return _M_insert_node(__res.first, __res.second, __z);
1824 :
1825 : return _M_insert_equal_lower_node(__z);
1826 : }
1827 : __catch(...)
1828 : {
1829 : _M_destroy_node(__z);
1830 : __throw_exception_again;
1831 : }
1832 : }
1833 : #endif
1834 :
1835 : template<typename _Key, typename _Val, typename _KoV,
1836 : typename _Cmp, typename _Alloc>
1837 : template<class _II>
1838 : void
1839 : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1840 : _M_insert_unique(_II __first, _II __last)
1841 : {
1842 : for (; __first != __last; ++__first)
1843 : _M_insert_unique_(end(), *__first);
1844 : }
1845 :
1846 : template<typename _Key, typename _Val, typename _KoV,
1847 : typename _Cmp, typename _Alloc>
1848 : template<class _II>
1849 : void
1850 : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1851 : _M_insert_equal(_II __first, _II __last)
1852 : {
1853 : for (; __first != __last; ++__first)
1854 : _M_insert_equal_(end(), *__first);
1855 : }
1856 :
1857 : template<typename _Key, typename _Val, typename _KeyOfValue,
1858 : typename _Compare, typename _Alloc>
1859 : void
1860 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1861 : _M_erase_aux(const_iterator __position)
1862 : {
1863 : _Link_type __y =
1864 : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1865 : (const_cast<_Base_ptr>(__position._M_node),
1866 : this->_M_impl._M_header));
1867 : _M_destroy_node(__y);
1868 : --_M_impl._M_node_count;
1869 : }
1870 :
1871 : template<typename _Key, typename _Val, typename _KeyOfValue,
1872 : typename _Compare, typename _Alloc>
1873 : void
1874 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1875 : _M_erase_aux(const_iterator __first, const_iterator __last)
1876 : {
1877 : if (__first == begin() && __last == end())
1878 : clear();
1879 : else
1880 : while (__first != __last)
1881 : erase(__first++);
1882 : }
1883 :
1884 : template<typename _Key, typename _Val, typename _KeyOfValue,
1885 : typename _Compare, typename _Alloc>
1886 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1887 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1888 : erase(const _Key& __x)
1889 : {
1890 : pair<iterator, iterator> __p = equal_range(__x);
1891 : const size_type __old_size = size();
1892 : erase(__p.first, __p.second);
1893 : return __old_size - size();
1894 : }
1895 :
1896 : template<typename _Key, typename _Val, typename _KeyOfValue,
1897 : typename _Compare, typename _Alloc>
1898 : void
1899 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1900 : erase(const _Key* __first, const _Key* __last)
1901 : {
1902 : while (__first != __last)
1903 : erase(*__first++);
1904 : }
1905 :
1906 : template<typename _Key, typename _Val, typename _KeyOfValue,
1907 : typename _Compare, typename _Alloc>
1908 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1909 : _Compare, _Alloc>::iterator
1910 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1911 : find(const _Key& __k)
1912 : {
1913 : iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1914 : return (__j == end()
1915 : || _M_impl._M_key_compare(__k,
1916 : _S_key(__j._M_node))) ? end() : __j;
1917 : }
1918 :
1919 : template<typename _Key, typename _Val, typename _KeyOfValue,
1920 : typename _Compare, typename _Alloc>
1921 : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1922 : _Compare, _Alloc>::const_iterator
1923 0 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1924 : find(const _Key& __k) const
1925 : {
1926 0 : const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1927 0 : return (__j == end()
1928 0 : || _M_impl._M_key_compare(__k,
1929 0 : _S_key(__j._M_node))) ? end() : __j;
1930 : }
1931 :
1932 : template<typename _Key, typename _Val, typename _KeyOfValue,
1933 : typename _Compare, typename _Alloc>
1934 : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1935 : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1936 : count(const _Key& __k) const
1937 : {
1938 : pair<const_iterator, const_iterator> __p = equal_range(__k);
1939 : const size_type __n = std::distance(__p.first, __p.second);
1940 : return __n;
1941 : }
1942 :
1943 : _GLIBCXX_PURE unsigned int
1944 : _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1945 : const _Rb_tree_node_base* __root) throw ();
1946 :
1947 : template<typename _Key, typename _Val, typename _KeyOfValue,
1948 : typename _Compare, typename _Alloc>
1949 : bool
1950 : _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1951 : {
1952 : if (_M_impl._M_node_count == 0 || begin() == end())
1953 : return _M_impl._M_node_count == 0 && begin() == end()
1954 : && this->_M_impl._M_header._M_left == _M_end()
1955 : && this->_M_impl._M_header._M_right == _M_end();
1956 :
1957 : unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1958 : for (const_iterator __it = begin(); __it != end(); ++__it)
1959 : {
1960 : _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1961 : _Const_Link_type __L = _S_left(__x);
1962 : _Const_Link_type __R = _S_right(__x);
1963 :
1964 : if (__x->_M_color == _S_red)
1965 : if ((__L && __L->_M_color == _S_red)
1966 : || (__R && __R->_M_color == _S_red))
1967 : return false;
1968 :
1969 : if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1970 : return false;
1971 : if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1972 : return false;
1973 :
1974 : if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1975 : return false;
1976 : }
1977 :
1978 : if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1979 : return false;
1980 : if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1981 : return false;
1982 : return true;
1983 : }
1984 :
1985 : _GLIBCXX_END_NAMESPACE_VERSION
1986 : } // namespace
1987 :
1988 : #endif
|
