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