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