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  {
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  : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
702  {
703  if (__x._M_root() != 0)
704  _M_move_data(__x, std::true_type());
705  }
706 
707  _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
708  : _Rb_tree(std::move(__x), _Node_allocator(__a))
709  { }
710 
711  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a);
712 #endif
713 
714  ~_Rb_tree() _GLIBCXX_NOEXCEPT
715  { _M_erase(_M_begin()); }
716 
717  _Rb_tree&
718  operator=(const _Rb_tree& __x);
719 
720  // Accessors.
721  _Compare
722  key_comp() const
723  { return _M_impl._M_key_compare; }
724 
725  iterator
726  begin() _GLIBCXX_NOEXCEPT
727  {
728  return iterator(static_cast<_Link_type>
729  (this->_M_impl._M_header._M_left));
730  }
731 
732  const_iterator
733  begin() const _GLIBCXX_NOEXCEPT
734  {
735  return const_iterator(static_cast<_Const_Link_type>
736  (this->_M_impl._M_header._M_left));
737  }
738 
739  iterator
740  end() _GLIBCXX_NOEXCEPT
741  { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
742 
743  const_iterator
744  end() const _GLIBCXX_NOEXCEPT
745  {
746  return const_iterator(static_cast<_Const_Link_type>
747  (&this->_M_impl._M_header));
748  }
749 
750  reverse_iterator
751  rbegin() _GLIBCXX_NOEXCEPT
752  { return reverse_iterator(end()); }
753 
754  const_reverse_iterator
755  rbegin() const _GLIBCXX_NOEXCEPT
756  { return const_reverse_iterator(end()); }
757 
758  reverse_iterator
759  rend() _GLIBCXX_NOEXCEPT
760  { return reverse_iterator(begin()); }
761 
762  const_reverse_iterator
763  rend() const _GLIBCXX_NOEXCEPT
764  { return const_reverse_iterator(begin()); }
765 
766  bool
767  empty() const _GLIBCXX_NOEXCEPT
768  { return _M_impl._M_node_count == 0; }
769 
770  size_type
771  size() const _GLIBCXX_NOEXCEPT
772  { return _M_impl._M_node_count; }
773 
774  size_type
775  max_size() const _GLIBCXX_NOEXCEPT
776  { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
777 
778  void
779 #if __cplusplus >= 201103L
780  swap(_Rb_tree& __t) noexcept(_Alloc_traits::_S_nothrow_swap());
781 #else
782  swap(_Rb_tree& __t);
783 #endif
784 
785  // Insert/erase.
786 #if __cplusplus >= 201103L
787  template<typename _Arg>
788  pair<iterator, bool>
789  _M_insert_unique(_Arg&& __x);
790 
791  template<typename _Arg>
792  iterator
793  _M_insert_equal(_Arg&& __x);
794 
795  template<typename _Arg>
796  iterator
797  _M_insert_unique_(const_iterator __position, _Arg&& __x);
798 
799  template<typename _Arg>
800  iterator
801  _M_insert_equal_(const_iterator __position, _Arg&& __x);
802 
803  template<typename... _Args>
804  pair<iterator, bool>
805  _M_emplace_unique(_Args&&... __args);
806 
807  template<typename... _Args>
808  iterator
809  _M_emplace_equal(_Args&&... __args);
810 
811  template<typename... _Args>
812  iterator
813  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
814 
815  template<typename... _Args>
816  iterator
817  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
818 #else
819  pair<iterator, bool>
820  _M_insert_unique(const value_type& __x);
821 
822  iterator
823  _M_insert_equal(const value_type& __x);
824 
825  iterator
826  _M_insert_unique_(const_iterator __position, const value_type& __x);
827 
828  iterator
829  _M_insert_equal_(const_iterator __position, const value_type& __x);
830 #endif
831 
832  template<typename _InputIterator>
833  void
834  _M_insert_unique(_InputIterator __first, _InputIterator __last);
835 
836  template<typename _InputIterator>
837  void
838  _M_insert_equal(_InputIterator __first, _InputIterator __last);
839 
840  private:
841  void
842  _M_erase_aux(const_iterator __position);
843 
844  void
845  _M_erase_aux(const_iterator __first, const_iterator __last);
846 
847  public:
848 #if __cplusplus >= 201103L
849  // _GLIBCXX_RESOLVE_LIB_DEFECTS
850  // DR 130. Associative erase should return an iterator.
851  _GLIBCXX_ABI_TAG_CXX11
852  iterator
853  erase(const_iterator __position)
854  {
855  const_iterator __result = __position;
856  ++__result;
857  _M_erase_aux(__position);
858  return __result._M_const_cast();
859  }
860 
861  // LWG 2059.
862  _GLIBCXX_ABI_TAG_CXX11
863  iterator
864  erase(iterator __position)
865  {
866  iterator __result = __position;
867  ++__result;
868  _M_erase_aux(__position);
869  return __result;
870  }
871 #else
872  void
873  erase(iterator __position)
874  { _M_erase_aux(__position); }
875 
876  void
877  erase(const_iterator __position)
878  { _M_erase_aux(__position); }
879 #endif
880  size_type
881  erase(const key_type& __x);
882 
883 #if __cplusplus >= 201103L
884  // _GLIBCXX_RESOLVE_LIB_DEFECTS
885  // DR 130. Associative erase should return an iterator.
886  _GLIBCXX_ABI_TAG_CXX11
887  iterator
888  erase(const_iterator __first, const_iterator __last)
889  {
890  _M_erase_aux(__first, __last);
891  return __last._M_const_cast();
892  }
893 #else
894  void
895  erase(iterator __first, iterator __last)
896  { _M_erase_aux(__first, __last); }
897 
898  void
899  erase(const_iterator __first, const_iterator __last)
900  { _M_erase_aux(__first, __last); }
901 #endif
902  void
903  erase(const key_type* __first, const key_type* __last);
904 
905  void
906  clear() _GLIBCXX_NOEXCEPT
907  {
908  _M_erase(_M_begin());
909  _M_leftmost() = _M_end();
910  _M_root() = 0;
911  _M_rightmost() = _M_end();
912  _M_impl._M_node_count = 0;
913  }
914 
915  // Set operations.
916  iterator
917  find(const key_type& __k);
918 
919  const_iterator
920  find(const key_type& __k) const;
921 
922  size_type
923  count(const key_type& __k) const;
924 
925  iterator
926  lower_bound(const key_type& __k)
927  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
928 
929  const_iterator
930  lower_bound(const key_type& __k) const
931  { return _M_lower_bound(_M_begin(), _M_end(), __k); }
932 
933  iterator
934  upper_bound(const key_type& __k)
935  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
936 
937  const_iterator
938  upper_bound(const key_type& __k) const
939  { return _M_upper_bound(_M_begin(), _M_end(), __k); }
940 
941  pair<iterator, iterator>
942  equal_range(const key_type& __k);
943 
944  pair<const_iterator, const_iterator>
945  equal_range(const key_type& __k) const;
946 
947  // Debugging.
948  bool
949  __rb_verify() const;
950 
951 #if __cplusplus >= 201103L
952  bool
953  _M_move_assign(_Rb_tree&);
954 
955  private:
956  // Move elements from container with equal allocator.
957  void
958  _M_move_data(_Rb_tree&, std::true_type);
959 
960  // Move elements from container with possibly non-equal allocator,
961  // which might result in a copy not a move.
962  void
963  _M_move_data(_Rb_tree&, std::false_type);
964 #endif
965  };
966 
967  template<typename _Key, typename _Val, typename _KeyOfValue,
968  typename _Compare, typename _Alloc>
969  inline bool
970  operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
971  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
972  {
973  return __x.size() == __y.size()
974  && std::equal(__x.begin(), __x.end(), __y.begin());
975  }
976 
977  template<typename _Key, typename _Val, typename _KeyOfValue,
978  typename _Compare, typename _Alloc>
979  inline bool
980  operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
981  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
982  {
983  return std::lexicographical_compare(__x.begin(), __x.end(),
984  __y.begin(), __y.end());
985  }
986 
987  template<typename _Key, typename _Val, typename _KeyOfValue,
988  typename _Compare, typename _Alloc>
989  inline bool
990  operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
991  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
992  { return !(__x == __y); }
993 
994  template<typename _Key, typename _Val, typename _KeyOfValue,
995  typename _Compare, typename _Alloc>
996  inline bool
997  operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
998  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
999  { return __y < __x; }
1000 
1001  template<typename _Key, typename _Val, typename _KeyOfValue,
1002  typename _Compare, typename _Alloc>
1003  inline bool
1004  operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1005  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1006  { return !(__y < __x); }
1007 
1008  template<typename _Key, typename _Val, typename _KeyOfValue,
1009  typename _Compare, typename _Alloc>
1010  inline bool
1011  operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1012  const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1013  { return !(__x < __y); }
1014 
1015  template<typename _Key, typename _Val, typename _KeyOfValue,
1016  typename _Compare, typename _Alloc>
1017  inline void
1018  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
1019  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
1020  { __x.swap(__y); }
1021 
1022 #if __cplusplus >= 201103L
1023  template<typename _Key, typename _Val, typename _KeyOfValue,
1024  typename _Compare, typename _Alloc>
1025  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1026  _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
1027  : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
1028  {
1029  using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
1030  if (__x._M_root() != 0)
1031  _M_move_data(__x, __eq());
1032  }
1033 
1034  template<typename _Key, typename _Val, typename _KeyOfValue,
1035  typename _Compare, typename _Alloc>
1036  void
1037  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1038  _M_move_data(_Rb_tree& __x, std::true_type)
1039  {
1040  _M_root() = __x._M_root();
1041  _M_leftmost() = __x._M_leftmost();
1042  _M_rightmost() = __x._M_rightmost();
1043  _M_root()->_M_parent = _M_end();
1044 
1045  __x._M_root() = 0;
1046  __x._M_leftmost() = __x._M_end();
1047  __x._M_rightmost() = __x._M_end();
1048 
1049  this->_M_impl._M_node_count = __x._M_impl._M_node_count;
1050  __x._M_impl._M_node_count = 0;
1051  }
1052 
1053  template<typename _Key, typename _Val, typename _KeyOfValue,
1054  typename _Compare, typename _Alloc>
1055  void
1056  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1057  _M_move_data(_Rb_tree& __x, std::false_type)
1058  {
1059  if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
1060  _M_move_data(__x, std::true_type());
1061  else
1062  {
1063  _M_root() = _M_copy(__x._M_begin(), _M_end());
1064  _M_leftmost() = _S_minimum(_M_root());
1065  _M_rightmost() = _S_maximum(_M_root());
1066  _M_impl._M_node_count = __x._M_impl._M_node_count;
1067  }
1068  }
1069 
1070  template<typename _Key, typename _Val, typename _KeyOfValue,
1071  typename _Compare, typename _Alloc>
1072  bool
1073  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1074  _M_move_assign(_Rb_tree& __x)
1075  {
1076  if (_Alloc_traits::_S_propagate_on_move_assign()
1077  || _Alloc_traits::_S_always_equal()
1078  || _M_get_Node_allocator() == __x._M_get_Node_allocator())
1079  {
1080  clear();
1081  if (__x._M_root() != 0)
1082  _M_move_data(__x, std::true_type());
1083  std::__alloc_on_move(_M_get_Node_allocator(),
1084  __x._M_get_Node_allocator());
1085  return true;
1086  }
1087  return false;
1088  }
1089 #endif
1090 
1091  template<typename _Key, typename _Val, typename _KeyOfValue,
1092  typename _Compare, typename _Alloc>
1093  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
1094  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1095  operator=(const _Rb_tree& __x)
1096  {
1097  if (this != &__x)
1098  {
1099  // Note that _Key may be a constant type.
1100  clear();
1101 #if __cplusplus >= 201103L
1102  if (_Alloc_traits::_S_propagate_on_copy_assign())
1103  {
1104  auto& __this_alloc = this->_M_get_Node_allocator();
1105  auto& __that_alloc = __x._M_get_Node_allocator();
1106  if (!_Alloc_traits::_S_always_equal()
1107  && __this_alloc != __that_alloc)
1108  {
1109  std::__alloc_on_copy(__this_alloc, __that_alloc);
1110  }
1111  }
1112 #endif
1113  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
1114  if (__x._M_root() != 0)
1115  {
1116  _M_root() = _M_copy(__x._M_begin(), _M_end());
1117  _M_leftmost() = _S_minimum(_M_root());
1118  _M_rightmost() = _S_maximum(_M_root());
1119  _M_impl._M_node_count = __x._M_impl._M_node_count;
1120  }
1121  }
1122  return *this;
1123  }
1124 
1125  template<typename _Key, typename _Val, typename _KeyOfValue,
1126  typename _Compare, typename _Alloc>
1127 #if __cplusplus >= 201103L
1128  template<typename _Arg>
1129 #endif
1130  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1131  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1132 #if __cplusplus >= 201103L
1133  _M_insert_(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
1134 #else
1135  _M_insert_(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
1136 #endif
1137  {
1138  bool __insert_left = (__x != 0 || __p == _M_end()
1139  || _M_impl._M_key_compare(_KeyOfValue()(__v),
1140  _S_key(__p)));
1141 
1142  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1143 
1144  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1145  this->_M_impl._M_header);
1146  ++_M_impl._M_node_count;
1147  return iterator(__z);
1148  }
1149 
1150  template<typename _Key, typename _Val, typename _KeyOfValue,
1151  typename _Compare, typename _Alloc>
1152 #if __cplusplus >= 201103L
1153  template<typename _Arg>
1154 #endif
1155  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1156  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1157 #if __cplusplus >= 201103L
1158  _M_insert_lower(_Base_ptr __p, _Arg&& __v)
1159 #else
1160  _M_insert_lower(_Base_ptr __p, const _Val& __v)
1161 #endif
1162  {
1163  bool __insert_left = (__p == _M_end()
1164  || !_M_impl._M_key_compare(_S_key(__p),
1165  _KeyOfValue()(__v)));
1166 
1167  _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
1168 
1169  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1170  this->_M_impl._M_header);
1171  ++_M_impl._M_node_count;
1172  return iterator(__z);
1173  }
1174 
1175  template<typename _Key, typename _Val, typename _KeyOfValue,
1176  typename _Compare, typename _Alloc>
1177 #if __cplusplus >= 201103L
1178  template<typename _Arg>
1179 #endif
1180  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1181  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1182 #if __cplusplus >= 201103L
1183  _M_insert_equal_lower(_Arg&& __v)
1184 #else
1185  _M_insert_equal_lower(const _Val& __v)
1186 #endif
1187  {
1188  _Link_type __x = _M_begin();
1189  _Link_type __y = _M_end();
1190  while (__x != 0)
1191  {
1192  __y = __x;
1193  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
1194  _S_left(__x) : _S_right(__x);
1195  }
1196  return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
1197  }
1198 
1199  template<typename _Key, typename _Val, typename _KoV,
1200  typename _Compare, typename _Alloc>
1201  typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
1202  _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
1203  _M_copy(_Const_Link_type __x, _Link_type __p)
1204  {
1205  // Structural copy. __x and __p must be non-null.
1206  _Link_type __top = _M_clone_node(__x);
1207  __top->_M_parent = __p;
1208 
1209  __try
1210  {
1211  if (__x->_M_right)
1212  __top->_M_right = _M_copy(_S_right(__x), __top);
1213  __p = __top;
1214  __x = _S_left(__x);
1215 
1216  while (__x != 0)
1217  {
1218  _Link_type __y = _M_clone_node(__x);
1219  __p->_M_left = __y;
1220  __y->_M_parent = __p;
1221  if (__x->_M_right)
1222  __y->_M_right = _M_copy(_S_right(__x), __y);
1223  __p = __y;
1224  __x = _S_left(__x);
1225  }
1226  }
1227  __catch(...)
1228  {
1229  _M_erase(__top);
1230  __throw_exception_again;
1231  }
1232  return __top;
1233  }
1234 
1235  template<typename _Key, typename _Val, typename _KeyOfValue,
1236  typename _Compare, typename _Alloc>
1237  void
1238  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1239  _M_erase(_Link_type __x)
1240  {
1241  // Erase without rebalancing.
1242  while (__x != 0)
1243  {
1244  _M_erase(_S_right(__x));
1245  _Link_type __y = _S_left(__x);
1246  _M_destroy_node(__x);
1247  __x = __y;
1248  }
1249  }
1250 
1251  template<typename _Key, typename _Val, typename _KeyOfValue,
1252  typename _Compare, typename _Alloc>
1253  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1254  _Compare, _Alloc>::iterator
1255  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1256  _M_lower_bound(_Link_type __x, _Link_type __y,
1257  const _Key& __k)
1258  {
1259  while (__x != 0)
1260  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1261  __y = __x, __x = _S_left(__x);
1262  else
1263  __x = _S_right(__x);
1264  return iterator(__y);
1265  }
1266 
1267  template<typename _Key, typename _Val, typename _KeyOfValue,
1268  typename _Compare, typename _Alloc>
1269  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1270  _Compare, _Alloc>::const_iterator
1271  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1272  _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
1273  const _Key& __k) const
1274  {
1275  while (__x != 0)
1276  if (!_M_impl._M_key_compare(_S_key(__x), __k))
1277  __y = __x, __x = _S_left(__x);
1278  else
1279  __x = _S_right(__x);
1280  return const_iterator(__y);
1281  }
1282 
1283  template<typename _Key, typename _Val, typename _KeyOfValue,
1284  typename _Compare, typename _Alloc>
1285  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1286  _Compare, _Alloc>::iterator
1287  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1288  _M_upper_bound(_Link_type __x, _Link_type __y,
1289  const _Key& __k)
1290  {
1291  while (__x != 0)
1292  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1293  __y = __x, __x = _S_left(__x);
1294  else
1295  __x = _S_right(__x);
1296  return iterator(__y);
1297  }
1298 
1299  template<typename _Key, typename _Val, typename _KeyOfValue,
1300  typename _Compare, typename _Alloc>
1301  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1302  _Compare, _Alloc>::const_iterator
1303  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1304  _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1305  const _Key& __k) const
1306  {
1307  while (__x != 0)
1308  if (_M_impl._M_key_compare(__k, _S_key(__x)))
1309  __y = __x, __x = _S_left(__x);
1310  else
1311  __x = _S_right(__x);
1312  return const_iterator(__y);
1313  }
1314 
1315  template<typename _Key, typename _Val, typename _KeyOfValue,
1316  typename _Compare, typename _Alloc>
1317  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1318  _Compare, _Alloc>::iterator,
1319  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1320  _Compare, _Alloc>::iterator>
1321  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1322  equal_range(const _Key& __k)
1323  {
1324  _Link_type __x = _M_begin();
1325  _Link_type __y = _M_end();
1326  while (__x != 0)
1327  {
1328  if (_M_impl._M_key_compare(_S_key(__x), __k))
1329  __x = _S_right(__x);
1330  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1331  __y = __x, __x = _S_left(__x);
1332  else
1333  {
1334  _Link_type __xu(__x), __yu(__y);
1335  __y = __x, __x = _S_left(__x);
1336  __xu = _S_right(__xu);
1337  return pair<iterator,
1338  iterator>(_M_lower_bound(__x, __y, __k),
1339  _M_upper_bound(__xu, __yu, __k));
1340  }
1341  }
1342  return pair<iterator, iterator>(iterator(__y),
1343  iterator(__y));
1344  }
1345 
1346  template<typename _Key, typename _Val, typename _KeyOfValue,
1347  typename _Compare, typename _Alloc>
1348  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1349  _Compare, _Alloc>::const_iterator,
1350  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1351  _Compare, _Alloc>::const_iterator>
1352  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1353  equal_range(const _Key& __k) const
1354  {
1355  _Const_Link_type __x = _M_begin();
1356  _Const_Link_type __y = _M_end();
1357  while (__x != 0)
1358  {
1359  if (_M_impl._M_key_compare(_S_key(__x), __k))
1360  __x = _S_right(__x);
1361  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1362  __y = __x, __x = _S_left(__x);
1363  else
1364  {
1365  _Const_Link_type __xu(__x), __yu(__y);
1366  __y = __x, __x = _S_left(__x);
1367  __xu = _S_right(__xu);
1368  return pair<const_iterator,
1369  const_iterator>(_M_lower_bound(__x, __y, __k),
1370  _M_upper_bound(__xu, __yu, __k));
1371  }
1372  }
1373  return pair<const_iterator, const_iterator>(const_iterator(__y),
1374  const_iterator(__y));
1375  }
1376 
1377  template<typename _Key, typename _Val, typename _KeyOfValue,
1378  typename _Compare, typename _Alloc>
1379  void
1380  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1381  swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1382 #if __cplusplus >= 201103L
1383  noexcept(_Alloc_traits::_S_nothrow_swap())
1384 #endif
1385  {
1386  if (_M_root() == 0)
1387  {
1388  if (__t._M_root() != 0)
1389  {
1390  _M_root() = __t._M_root();
1391  _M_leftmost() = __t._M_leftmost();
1392  _M_rightmost() = __t._M_rightmost();
1393  _M_root()->_M_parent = _M_end();
1394 
1395  __t._M_root() = 0;
1396  __t._M_leftmost() = __t._M_end();
1397  __t._M_rightmost() = __t._M_end();
1398  }
1399  }
1400  else if (__t._M_root() == 0)
1401  {
1402  __t._M_root() = _M_root();
1403  __t._M_leftmost() = _M_leftmost();
1404  __t._M_rightmost() = _M_rightmost();
1405  __t._M_root()->_M_parent = __t._M_end();
1406 
1407  _M_root() = 0;
1408  _M_leftmost() = _M_end();
1409  _M_rightmost() = _M_end();
1410  }
1411  else
1412  {
1413  std::swap(_M_root(),__t._M_root());
1414  std::swap(_M_leftmost(),__t._M_leftmost());
1415  std::swap(_M_rightmost(),__t._M_rightmost());
1416 
1417  _M_root()->_M_parent = _M_end();
1418  __t._M_root()->_M_parent = __t._M_end();
1419  }
1420  // No need to swap header's color as it does not change.
1421  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1422  std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1423 
1424  _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
1425  __t._M_get_Node_allocator());
1426  }
1427 
1428  template<typename _Key, typename _Val, typename _KeyOfValue,
1429  typename _Compare, typename _Alloc>
1430  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1431  _Compare, _Alloc>::_Base_ptr,
1432  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1433  _Compare, _Alloc>::_Base_ptr>
1434  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1435  _M_get_insert_unique_pos(const key_type& __k)
1436  {
1437  typedef pair<_Base_ptr, _Base_ptr> _Res;
1438  _Link_type __x = _M_begin();
1439  _Link_type __y = _M_end();
1440  bool __comp = true;
1441  while (__x != 0)
1442  {
1443  __y = __x;
1444  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
1445  __x = __comp ? _S_left(__x) : _S_right(__x);
1446  }
1447  iterator __j = iterator(__y);
1448  if (__comp)
1449  {
1450  if (__j == begin())
1451  return _Res(__x, __y);
1452  else
1453  --__j;
1454  }
1455  if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
1456  return _Res(__x, __y);
1457  return _Res(__j._M_node, 0);
1458  }
1459 
1460  template<typename _Key, typename _Val, typename _KeyOfValue,
1461  typename _Compare, typename _Alloc>
1462  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1463  _Compare, _Alloc>::_Base_ptr,
1464  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1465  _Compare, _Alloc>::_Base_ptr>
1466  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1467  _M_get_insert_equal_pos(const key_type& __k)
1468  {
1469  typedef pair<_Base_ptr, _Base_ptr> _Res;
1470  _Link_type __x = _M_begin();
1471  _Link_type __y = _M_end();
1472  while (__x != 0)
1473  {
1474  __y = __x;
1475  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
1476  _S_left(__x) : _S_right(__x);
1477  }
1478  return _Res(__x, __y);
1479  }
1480 
1481  template<typename _Key, typename _Val, typename _KeyOfValue,
1482  typename _Compare, typename _Alloc>
1483 #if __cplusplus >= 201103L
1484  template<typename _Arg>
1485 #endif
1486  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1487  _Compare, _Alloc>::iterator, bool>
1488  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1489 #if __cplusplus >= 201103L
1490  _M_insert_unique(_Arg&& __v)
1491 #else
1492  _M_insert_unique(const _Val& __v)
1493 #endif
1494  {
1495  typedef pair<iterator, bool> _Res;
1496  pair<_Base_ptr, _Base_ptr> __res
1497  = _M_get_insert_unique_pos(_KeyOfValue()(__v));
1498 
1499  if (__res.second)
1500  return _Res(_M_insert_(__res.first, __res.second,
1501  _GLIBCXX_FORWARD(_Arg, __v)),
1502  true);
1503 
1504  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1505  }
1506 
1507  template<typename _Key, typename _Val, typename _KeyOfValue,
1508  typename _Compare, typename _Alloc>
1509 #if __cplusplus >= 201103L
1510  template<typename _Arg>
1511 #endif
1512  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1513  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1514 #if __cplusplus >= 201103L
1515  _M_insert_equal(_Arg&& __v)
1516 #else
1517  _M_insert_equal(const _Val& __v)
1518 #endif
1519  {
1520  pair<_Base_ptr, _Base_ptr> __res
1521  = _M_get_insert_equal_pos(_KeyOfValue()(__v));
1522  return _M_insert_(__res.first, __res.second, _GLIBCXX_FORWARD(_Arg, __v));
1523  }
1524 
1525  template<typename _Key, typename _Val, typename _KeyOfValue,
1526  typename _Compare, typename _Alloc>
1527  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1528  _Compare, _Alloc>::_Base_ptr,
1529  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1530  _Compare, _Alloc>::_Base_ptr>
1531  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1532  _M_get_insert_hint_unique_pos(const_iterator __position,
1533  const key_type& __k)
1534  {
1535  iterator __pos = __position._M_const_cast();
1536  typedef pair<_Base_ptr, _Base_ptr> _Res;
1537 
1538  // end()
1539  if (__pos._M_node == _M_end())
1540  {
1541  if (size() > 0
1542  && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
1543  return _Res(0, _M_rightmost());
1544  else
1545  return _M_get_insert_unique_pos(__k);
1546  }
1547  else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
1548  {
1549  // First, try before...
1550  iterator __before = __pos;
1551  if (__pos._M_node == _M_leftmost()) // begin()
1552  return _Res(_M_leftmost(), _M_leftmost());
1553  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
1554  {
1555  if (_S_right(__before._M_node) == 0)
1556  return _Res(0, __before._M_node);
1557  else
1558  return _Res(__pos._M_node, __pos._M_node);
1559  }
1560  else
1561  return _M_get_insert_unique_pos(__k);
1562  }
1563  else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1564  {
1565  // ... then try after.
1566  iterator __after = __pos;
1567  if (__pos._M_node == _M_rightmost())
1568  return _Res(0, _M_rightmost());
1569  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
1570  {
1571  if (_S_right(__pos._M_node) == 0)
1572  return _Res(0, __pos._M_node);
1573  else
1574  return _Res(__after._M_node, __after._M_node);
1575  }
1576  else
1577  return _M_get_insert_unique_pos(__k);
1578  }
1579  else
1580  // Equivalent keys.
1581  return _Res(__pos._M_node, 0);
1582  }
1583 
1584  template<typename _Key, typename _Val, typename _KeyOfValue,
1585  typename _Compare, typename _Alloc>
1586 #if __cplusplus >= 201103L
1587  template<typename _Arg>
1588 #endif
1589  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1590  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1591 #if __cplusplus >= 201103L
1592  _M_insert_unique_(const_iterator __position, _Arg&& __v)
1593 #else
1594  _M_insert_unique_(const_iterator __position, const _Val& __v)
1595 #endif
1596  {
1597  pair<_Base_ptr, _Base_ptr> __res
1598  = _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
1599 
1600  if (__res.second)
1601  return _M_insert_(__res.first, __res.second,
1602  _GLIBCXX_FORWARD(_Arg, __v));
1603  return iterator(static_cast<_Link_type>(__res.first));
1604  }
1605 
1606  template<typename _Key, typename _Val, typename _KeyOfValue,
1607  typename _Compare, typename _Alloc>
1608  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1609  _Compare, _Alloc>::_Base_ptr,
1610  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1611  _Compare, _Alloc>::_Base_ptr>
1612  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1613  _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
1614  {
1615  iterator __pos = __position._M_const_cast();
1616  typedef pair<_Base_ptr, _Base_ptr> _Res;
1617 
1618  // end()
1619  if (__pos._M_node == _M_end())
1620  {
1621  if (size() > 0
1622  && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
1623  return _Res(0, _M_rightmost());
1624  else
1625  return _M_get_insert_equal_pos(__k);
1626  }
1627  else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
1628  {
1629  // First, try before...
1630  iterator __before = __pos;
1631  if (__pos._M_node == _M_leftmost()) // begin()
1632  return _Res(_M_leftmost(), _M_leftmost());
1633  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
1634  {
1635  if (_S_right(__before._M_node) == 0)
1636  return _Res(0, __before._M_node);
1637  else
1638  return _Res(__pos._M_node, __pos._M_node);
1639  }
1640  else
1641  return _M_get_insert_equal_pos(__k);
1642  }
1643  else
1644  {
1645  // ... then try after.
1646  iterator __after = __pos;
1647  if (__pos._M_node == _M_rightmost())
1648  return _Res(0, _M_rightmost());
1649  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
1650  {
1651  if (_S_right(__pos._M_node) == 0)
1652  return _Res(0, __pos._M_node);
1653  else
1654  return _Res(__after._M_node, __after._M_node);
1655  }
1656  else
1657  return _Res(0, 0);
1658  }
1659  }
1660 
1661  template<typename _Key, typename _Val, typename _KeyOfValue,
1662  typename _Compare, typename _Alloc>
1663 #if __cplusplus >= 201103L
1664  template<typename _Arg>
1665 #endif
1666  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1667  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1668 #if __cplusplus >= 201103L
1669  _M_insert_equal_(const_iterator __position, _Arg&& __v)
1670 #else
1671  _M_insert_equal_(const_iterator __position, const _Val& __v)
1672 #endif
1673  {
1674  pair<_Base_ptr, _Base_ptr> __res
1675  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
1676 
1677  if (__res.second)
1678  return _M_insert_(__res.first, __res.second,
1679  _GLIBCXX_FORWARD(_Arg, __v));
1680 
1681  return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
1682  }
1683 
1684 #if __cplusplus >= 201103L
1685  template<typename _Key, typename _Val, typename _KeyOfValue,
1686  typename _Compare, typename _Alloc>
1687  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1688  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1689  _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
1690  {
1691  bool __insert_left = (__x != 0 || __p == _M_end()
1692  || _M_impl._M_key_compare(_S_key(__z),
1693  _S_key(__p)));
1694 
1695  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1696  this->_M_impl._M_header);
1697  ++_M_impl._M_node_count;
1698  return iterator(__z);
1699  }
1700 
1701  template<typename _Key, typename _Val, typename _KeyOfValue,
1702  typename _Compare, typename _Alloc>
1703  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1704  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1705  _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
1706  {
1707  bool __insert_left = (__p == _M_end()
1708  || !_M_impl._M_key_compare(_S_key(__p),
1709  _S_key(__z)));
1710 
1711  _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
1712  this->_M_impl._M_header);
1713  ++_M_impl._M_node_count;
1714  return iterator(__z);
1715  }
1716 
1717  template<typename _Key, typename _Val, typename _KeyOfValue,
1718  typename _Compare, typename _Alloc>
1719  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1720  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1721  _M_insert_equal_lower_node(_Link_type __z)
1722  {
1723  _Link_type __x = _M_begin();
1724  _Link_type __y = _M_end();
1725  while (__x != 0)
1726  {
1727  __y = __x;
1728  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
1729  _S_left(__x) : _S_right(__x);
1730  }
1731  return _M_insert_lower_node(__y, __z);
1732  }
1733 
1734  template<typename _Key, typename _Val, typename _KeyOfValue,
1735  typename _Compare, typename _Alloc>
1736  template<typename... _Args>
1737  pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1738  _Compare, _Alloc>::iterator, bool>
1739  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1740  _M_emplace_unique(_Args&&... __args)
1741  {
1742  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1743 
1744  __try
1745  {
1746  typedef pair<iterator, bool> _Res;
1747  auto __res = _M_get_insert_unique_pos(_S_key(__z));
1748  if (__res.second)
1749  return _Res(_M_insert_node(__res.first, __res.second, __z), true);
1750 
1751  _M_destroy_node(__z);
1752  return _Res(iterator(static_cast<_Link_type>(__res.first)), false);
1753  }
1754  __catch(...)
1755  {
1756  _M_destroy_node(__z);
1757  __throw_exception_again;
1758  }
1759  }
1760 
1761  template<typename _Key, typename _Val, typename _KeyOfValue,
1762  typename _Compare, typename _Alloc>
1763  template<typename... _Args>
1764  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1765  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1766  _M_emplace_equal(_Args&&... __args)
1767  {
1768  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1769 
1770  __try
1771  {
1772  auto __res = _M_get_insert_equal_pos(_S_key(__z));
1773  return _M_insert_node(__res.first, __res.second, __z);
1774  }
1775  __catch(...)
1776  {
1777  _M_destroy_node(__z);
1778  __throw_exception_again;
1779  }
1780  }
1781 
1782  template<typename _Key, typename _Val, typename _KeyOfValue,
1783  typename _Compare, typename _Alloc>
1784  template<typename... _Args>
1785  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1786  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1787  _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
1788  {
1789  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1790 
1791  __try
1792  {
1793  auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
1794 
1795  if (__res.second)
1796  return _M_insert_node(__res.first, __res.second, __z);
1797 
1798  _M_destroy_node(__z);
1799  return iterator(static_cast<_Link_type>(__res.first));
1800  }
1801  __catch(...)
1802  {
1803  _M_destroy_node(__z);
1804  __throw_exception_again;
1805  }
1806  }
1807 
1808  template<typename _Key, typename _Val, typename _KeyOfValue,
1809  typename _Compare, typename _Alloc>
1810  template<typename... _Args>
1811  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1812  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1813  _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
1814  {
1815  _Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
1816 
1817  __try
1818  {
1819  auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
1820 
1821  if (__res.second)
1822  return _M_insert_node(__res.first, __res.second, __z);
1823 
1824  return _M_insert_equal_lower_node(__z);
1825  }
1826  __catch(...)
1827  {
1828  _M_destroy_node(__z);
1829  __throw_exception_again;
1830  }
1831  }
1832 #endif
1833 
1834  template<typename _Key, typename _Val, typename _KoV,
1835  typename _Cmp, typename _Alloc>
1836  template<class _II>
1837  void
1838  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1839  _M_insert_unique(_II __first, _II __last)
1840  {
1841  for (; __first != __last; ++__first)
1842  _M_insert_unique_(end(), *__first);
1843  }
1844 
1845  template<typename _Key, typename _Val, typename _KoV,
1846  typename _Cmp, typename _Alloc>
1847  template<class _II>
1848  void
1849  _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1850  _M_insert_equal(_II __first, _II __last)
1851  {
1852  for (; __first != __last; ++__first)
1853  _M_insert_equal_(end(), *__first);
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 __position)
1861  {
1862  _Link_type __y =
1863  static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1864  (const_cast<_Base_ptr>(__position._M_node),
1865  this->_M_impl._M_header));
1866  _M_destroy_node(__y);
1867  --_M_impl._M_node_count;
1868  }
1869 
1870  template<typename _Key, typename _Val, typename _KeyOfValue,
1871  typename _Compare, typename _Alloc>
1872  void
1873  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1874  _M_erase_aux(const_iterator __first, const_iterator __last)
1875  {
1876  if (__first == begin() && __last == end())
1877  clear();
1878  else
1879  while (__first != __last)
1880  erase(__first++);
1881  }
1882 
1883  template<typename _Key, typename _Val, typename _KeyOfValue,
1884  typename _Compare, typename _Alloc>
1885  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1886  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1887  erase(const _Key& __x)
1888  {
1889  pair<iterator, iterator> __p = equal_range(__x);
1890  const size_type __old_size = size();
1891  erase(__p.first, __p.second);
1892  return __old_size - size();
1893  }
1894 
1895  template<typename _Key, typename _Val, typename _KeyOfValue,
1896  typename _Compare, typename _Alloc>
1897  void
1898  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1899  erase(const _Key* __first, const _Key* __last)
1900  {
1901  while (__first != __last)
1902  erase(*__first++);
1903  }
1904 
1905  template<typename _Key, typename _Val, typename _KeyOfValue,
1906  typename _Compare, typename _Alloc>
1907  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1908  _Compare, _Alloc>::iterator
1909  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1910  find(const _Key& __k)
1911  {
1912  iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1913  return (__j == end()
1914  || _M_impl._M_key_compare(__k,
1915  _S_key(__j._M_node))) ? end() : __j;
1916  }
1917 
1918  template<typename _Key, typename _Val, typename _KeyOfValue,
1919  typename _Compare, typename _Alloc>
1920  typename _Rb_tree<_Key, _Val, _KeyOfValue,
1921  _Compare, _Alloc>::const_iterator
1922  _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1923  find(const _Key& __k) const
1924  {
1925  const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1926  return (__j == end()
1927  || _M_impl._M_key_compare(__k,
1928  _S_key(__j._M_node))) ? end() : __j;
1929  }
1930 
1931  template<typename _Key, typename _Val, typename _KeyOfValue,
1932  typename _Compare, typename _Alloc>
1933  typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1935  count(const _Key& __k) const
1936  {
1937  pair<const_iterator, const_iterator> __p = equal_range(__k);
1938  const size_type __n = std::distance(__p.first, __p.second);
1939  return __n;
1940  }
1941 
1942  _GLIBCXX_PURE unsigned int
1943  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1944  const _Rb_tree_node_base* __root) throw ();
1945 
1946  template<typename _Key, typename _Val, typename _KeyOfValue,
1947  typename _Compare, typename _Alloc>
1948  bool
1949  _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1950  {
1951  if (_M_impl._M_node_count == 0 || begin() == end())
1952  return _M_impl._M_node_count == 0 && begin() == end()
1953  && this->_M_impl._M_header._M_left == _M_end()
1954  && this->_M_impl._M_header._M_right == _M_end();
1955 
1956  unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1957  for (const_iterator __it = begin(); __it != end(); ++__it)
1958  {
1959  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1960  _Const_Link_type __L = _S_left(__x);
1961  _Const_Link_type __R = _S_right(__x);
1962 
1963  if (__x->_M_color == _S_red)
1964  if ((__L && __L->_M_color == _S_red)
1965  || (__R && __R->_M_color == _S_red))
1966  return false;
1967 
1968  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1969  return false;
1970  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1971  return false;
1972 
1973  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1974  return false;
1975  }
1976 
1977  if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1978  return false;
1979  if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1980  return false;
1981  return true;
1982  }
1983 
1984 _GLIBCXX_END_NAMESPACE_VERSION
1985 } // namespace
1986 
1987 #endif
Uniform interface to C++98 and C++0x allocators.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
static void deallocate(_Alloc &__a, pointer __p, size_type __n)
Deallocate memory.
constexpr size_t size() const noexcept
Returns the total number of bits.
Definition: bitset:1293
static size_type max_size(const _Alloc &__a) noexcept
The maximum supported allocation size.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
Tests a range for element-wise equality.
size_t count() const noexcept
Returns the number of bits which are set.
Definition: bitset:1288
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition: move.h:76
static pointer allocate(_Alloc &__a, size_type __n)
Allocate memory.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition: complex:381
integral_constant
Definition: type_traits:57
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs dictionary comparison on ranges.