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