]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // RB tree implementation -*- C++ -*- |
2 | ||
31905f34 PC |
3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 |
4 | // Free Software Foundation, Inc. | |
42526146 PE |
5 | // |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
9 | // Free Software Foundation; either version 2, or (at your option) | |
10 | // any later version. | |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
17 | // You should have received a copy of the GNU General Public License along | |
18 | // with this library; see the file COPYING. If not, write to the Free | |
83f51799 | 19 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, |
42526146 PE |
20 | // USA. |
21 | ||
22 | // As a special exception, you may use this file as part of a free software | |
23 | // library without restriction. Specifically, if other files instantiate | |
24 | // templates or use macros or inline functions from this file, or you compile | |
25 | // this file and link it with other files to produce an executable, this | |
26 | // file does not by itself cause the resulting executable to be covered by | |
27 | // the GNU General Public License. This exception does not however | |
28 | // invalidate any other reasons why the executable file might be covered by | |
29 | // the GNU General Public License. | |
30 | ||
725dc051 BK |
31 | /* |
32 | * | |
33 | * Copyright (c) 1996,1997 | |
34 | * Silicon Graphics Computer Systems, Inc. | |
35 | * | |
36 | * Permission to use, copy, modify, distribute and sell this software | |
37 | * and its documentation for any purpose is hereby granted without fee, | |
38 | * provided that the above copyright notice appear in all copies and | |
39 | * that both that copyright notice and this permission notice appear | |
40 | * in supporting documentation. Silicon Graphics makes no | |
41 | * representations about the suitability of this software for any | |
42 | * purpose. It is provided "as is" without express or implied warranty. | |
43 | * | |
44 | * | |
45 | * Copyright (c) 1994 | |
46 | * Hewlett-Packard Company | |
47 | * | |
48 | * Permission to use, copy, modify, distribute and sell this software | |
49 | * and its documentation for any purpose is hereby granted without fee, | |
50 | * provided that the above copyright notice appear in all copies and | |
51 | * that both that copyright notice and this permission notice appear | |
52 | * in supporting documentation. Hewlett-Packard Company makes no | |
53 | * representations about the suitability of this software for any | |
54 | * purpose. It is provided "as is" without express or implied warranty. | |
55 | * | |
56 | * | |
57 | */ | |
58 | ||
729e3d3f PE |
59 | /** @file stl_tree.h |
60 | * This is an internal header file, included by other library headers. | |
61 | * You should not attempt to use it directly. | |
725dc051 BK |
62 | */ |
63 | ||
3d7c150e BK |
64 | #ifndef _TREE_H |
65 | #define _TREE_H 1 | |
725dc051 | 66 | |
725dc051 | 67 | #include <bits/stl_algobase.h> |
1ff9402d | 68 | #include <bits/allocator.h> |
725dc051 BK |
69 | #include <bits/stl_construct.h> |
70 | #include <bits/stl_function.h> | |
8bd22a3c | 71 | #include <bits/cpp_type_traits.h> |
725dc051 | 72 | |
3cbc7af0 BK |
73 | _GLIBCXX_BEGIN_NAMESPACE(std) |
74 | ||
8bd22a3c BK |
75 | // Red-black tree class, designed for use in implementing STL |
76 | // associative containers (set, multiset, map, and multimap). The | |
77 | // insertion and deletion algorithms are based on those in Cormen, | |
78 | // Leiserson, and Rivest, Introduction to Algorithms (MIT Press, | |
79 | // 1990), except that | |
80 | // | |
81 | // (1) the header cell is maintained with links not only to the root | |
82 | // but also to the leftmost node of the tree, to enable constant | |
83 | // time begin(), and to the rightmost node of the tree, to enable | |
84 | // linear time performance when used with the generic set algorithms | |
85 | // (set_union, etc.) | |
86 | // | |
87 | // (2) when a node being deleted has two children its successor node | |
88 | // is relinked into its place, rather than copied, so that the only | |
89 | // iterators invalidated are those referring to the deleted node. | |
90 | ||
655d7821 | 91 | enum _Rb_tree_color { _S_red = false, _S_black = true }; |
725dc051 | 92 | |
d3d526ac BK |
93 | struct _Rb_tree_node_base |
94 | { | |
95 | typedef _Rb_tree_node_base* _Base_ptr; | |
b4c70e89 | 96 | typedef const _Rb_tree_node_base* _Const_Base_ptr; |
ed6814f7 BI |
97 | |
98 | _Rb_tree_color _M_color; | |
99 | _Base_ptr _M_parent; | |
100 | _Base_ptr _M_left; | |
101 | _Base_ptr _M_right; | |
102 | ||
103 | static _Base_ptr | |
d3d526ac BK |
104 | _S_minimum(_Base_ptr __x) |
105 | { | |
106 | while (__x->_M_left != 0) __x = __x->_M_left; | |
107 | return __x; | |
108 | } | |
725dc051 | 109 | |
b4c70e89 GB |
110 | static _Const_Base_ptr |
111 | _S_minimum(_Const_Base_ptr __x) | |
112 | { | |
113 | while (__x->_M_left != 0) __x = __x->_M_left; | |
114 | return __x; | |
115 | } | |
116 | ||
ed6814f7 | 117 | static _Base_ptr |
d3d526ac BK |
118 | _S_maximum(_Base_ptr __x) |
119 | { | |
120 | while (__x->_M_right != 0) __x = __x->_M_right; | |
121 | return __x; | |
122 | } | |
b4c70e89 GB |
123 | |
124 | static _Const_Base_ptr | |
125 | _S_maximum(_Const_Base_ptr __x) | |
126 | { | |
127 | while (__x->_M_right != 0) __x = __x->_M_right; | |
128 | return __x; | |
129 | } | |
d3d526ac | 130 | }; |
725dc051 | 131 | |
d3d526ac BK |
132 | template<typename _Val> |
133 | struct _Rb_tree_node : public _Rb_tree_node_base | |
134 | { | |
135 | typedef _Rb_tree_node<_Val>* _Link_type; | |
136 | _Val _M_value_field; | |
137 | }; | |
ed6814f7 | 138 | |
b4c70e89 GB |
139 | _Rb_tree_node_base* |
140 | _Rb_tree_increment(_Rb_tree_node_base* __x); | |
d3d526ac | 141 | |
e135a038 BK |
142 | const _Rb_tree_node_base* |
143 | _Rb_tree_increment(const _Rb_tree_node_base* __x); | |
144 | ||
b4c70e89 GB |
145 | _Rb_tree_node_base* |
146 | _Rb_tree_decrement(_Rb_tree_node_base* __x); | |
d3d526ac | 147 | |
e135a038 BK |
148 | const _Rb_tree_node_base* |
149 | _Rb_tree_decrement(const _Rb_tree_node_base* __x); | |
150 | ||
151 | template<typename _Tp> | |
b4c70e89 | 152 | struct _Rb_tree_iterator |
d3d526ac | 153 | { |
e135a038 BK |
154 | typedef _Tp value_type; |
155 | typedef _Tp& reference; | |
156 | typedef _Tp* pointer; | |
157 | ||
b4c70e89 | 158 | typedef bidirectional_iterator_tag iterator_category; |
e135a038 BK |
159 | typedef ptrdiff_t difference_type; |
160 | ||
161 | typedef _Rb_tree_iterator<_Tp> _Self; | |
162 | typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; | |
163 | typedef _Rb_tree_node<_Tp>* _Link_type; | |
ed6814f7 | 164 | |
a7a44441 VR |
165 | _Rb_tree_iterator() |
166 | : _M_node() { } | |
b4c70e89 | 167 | |
e182017e | 168 | explicit |
b4c70e89 | 169 | _Rb_tree_iterator(_Link_type __x) |
8bd22a3c | 170 | : _M_node(__x) { } |
b4c70e89 | 171 | |
ed6814f7 | 172 | reference |
b4c70e89 GB |
173 | operator*() const |
174 | { return static_cast<_Link_type>(_M_node)->_M_value_field; } | |
d3d526ac | 175 | |
ed6814f7 | 176 | pointer |
b4c70e89 GB |
177 | operator->() const |
178 | { return &static_cast<_Link_type>(_M_node)->_M_value_field; } | |
d3d526ac | 179 | |
ed6814f7 BI |
180 | _Self& |
181 | operator++() | |
182 | { | |
b4c70e89 | 183 | _M_node = _Rb_tree_increment(_M_node); |
ed6814f7 | 184 | return *this; |
d3d526ac | 185 | } |
725dc051 | 186 | |
ed6814f7 BI |
187 | _Self |
188 | operator++(int) | |
d3d526ac BK |
189 | { |
190 | _Self __tmp = *this; | |
b4c70e89 | 191 | _M_node = _Rb_tree_increment(_M_node); |
d3d526ac BK |
192 | return __tmp; |
193 | } | |
ed6814f7 BI |
194 | |
195 | _Self& | |
b4c70e89 GB |
196 | operator--() |
197 | { | |
198 | _M_node = _Rb_tree_decrement(_M_node); | |
199 | return *this; | |
200 | } | |
d3d526ac | 201 | |
ed6814f7 BI |
202 | _Self |
203 | operator--(int) | |
d3d526ac BK |
204 | { |
205 | _Self __tmp = *this; | |
b4c70e89 | 206 | _M_node = _Rb_tree_decrement(_M_node); |
d3d526ac BK |
207 | return __tmp; |
208 | } | |
b4c70e89 | 209 | |
e135a038 BK |
210 | bool |
211 | operator==(const _Self& __x) const | |
212 | { return _M_node == __x._M_node; } | |
213 | ||
214 | bool | |
215 | operator!=(const _Self& __x) const | |
216 | { return _M_node != __x._M_node; } | |
217 | ||
b4c70e89 | 218 | _Base_ptr _M_node; |
d3d526ac BK |
219 | }; |
220 | ||
e135a038 BK |
221 | template<typename _Tp> |
222 | struct _Rb_tree_const_iterator | |
223 | { | |
224 | typedef _Tp value_type; | |
225 | typedef const _Tp& reference; | |
226 | typedef const _Tp* pointer; | |
d3d526ac | 227 | |
e135a038 | 228 | typedef _Rb_tree_iterator<_Tp> iterator; |
d3d526ac | 229 | |
e135a038 BK |
230 | typedef bidirectional_iterator_tag iterator_category; |
231 | typedef ptrdiff_t difference_type; | |
d3d526ac | 232 | |
e135a038 BK |
233 | typedef _Rb_tree_const_iterator<_Tp> _Self; |
234 | typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr; | |
235 | typedef const _Rb_tree_node<_Tp>* _Link_type; | |
ed6814f7 | 236 | |
a7a44441 VR |
237 | _Rb_tree_const_iterator() |
238 | : _M_node() { } | |
e135a038 | 239 | |
e182017e | 240 | explicit |
e135a038 | 241 | _Rb_tree_const_iterator(_Link_type __x) |
8bd22a3c | 242 | : _M_node(__x) { } |
e135a038 BK |
243 | |
244 | _Rb_tree_const_iterator(const iterator& __it) | |
8bd22a3c | 245 | : _M_node(__it._M_node) { } |
e135a038 BK |
246 | |
247 | reference | |
248 | operator*() const | |
249 | { return static_cast<_Link_type>(_M_node)->_M_value_field; } | |
250 | ||
251 | pointer | |
252 | operator->() const | |
253 | { return &static_cast<_Link_type>(_M_node)->_M_value_field; } | |
254 | ||
ed6814f7 BI |
255 | _Self& |
256 | operator++() | |
257 | { | |
e135a038 | 258 | _M_node = _Rb_tree_increment(_M_node); |
ed6814f7 | 259 | return *this; |
e135a038 BK |
260 | } |
261 | ||
ed6814f7 BI |
262 | _Self |
263 | operator++(int) | |
e135a038 BK |
264 | { |
265 | _Self __tmp = *this; | |
266 | _M_node = _Rb_tree_increment(_M_node); | |
267 | return __tmp; | |
268 | } | |
ed6814f7 BI |
269 | |
270 | _Self& | |
e135a038 BK |
271 | operator--() |
272 | { | |
273 | _M_node = _Rb_tree_decrement(_M_node); | |
274 | return *this; | |
275 | } | |
276 | ||
ed6814f7 BI |
277 | _Self |
278 | operator--(int) | |
e135a038 BK |
279 | { |
280 | _Self __tmp = *this; | |
281 | _M_node = _Rb_tree_decrement(_M_node); | |
282 | return __tmp; | |
283 | } | |
284 | ||
285 | bool | |
286 | operator==(const _Self& __x) const | |
287 | { return _M_node == __x._M_node; } | |
288 | ||
289 | bool | |
290 | operator!=(const _Self& __x) const | |
291 | { return _M_node != __x._M_node; } | |
292 | ||
293 | _Base_ptr _M_node; | |
737ab798 | 294 | }; |
d3d526ac BK |
295 | |
296 | template<typename _Val> | |
ed6814f7 | 297 | inline bool |
e135a038 | 298 | operator==(const _Rb_tree_iterator<_Val>& __x, |
ed6814f7 | 299 | const _Rb_tree_const_iterator<_Val>& __y) |
e135a038 | 300 | { return __x._M_node == __y._M_node; } |
d3d526ac BK |
301 | |
302 | template<typename _Val> | |
ed6814f7 | 303 | inline bool |
e135a038 | 304 | operator!=(const _Rb_tree_iterator<_Val>& __x, |
ed6814f7 | 305 | const _Rb_tree_const_iterator<_Val>& __y) |
d3d526ac BK |
306 | { return __x._M_node != __y._M_node; } |
307 | ||
ed6814f7 | 308 | void |
8bd22a3c | 309 | _Rb_tree_insert_and_rebalance(const bool __insert_left, |
e135a038 BK |
310 | _Rb_tree_node_base* __x, |
311 | _Rb_tree_node_base* __p, | |
312 | _Rb_tree_node_base& __header); | |
ca1c7011 GB |
313 | |
314 | _Rb_tree_node_base* | |
ed6814f7 | 315 | _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z, |
8bd22a3c | 316 | _Rb_tree_node_base& __header); |
d3d526ac | 317 | |
d3d526ac | 318 | |
ed6814f7 | 319 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 320 | typename _Compare, typename _Alloc = allocator<_Val> > |
34c87829 | 321 | class _Rb_tree |
d3d526ac | 322 | { |
34c87829 MA |
323 | typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other |
324 | _Node_allocator; | |
ed6814f7 | 325 | |
d3d526ac BK |
326 | protected: |
327 | typedef _Rb_tree_node_base* _Base_ptr; | |
b4c70e89 | 328 | typedef const _Rb_tree_node_base* _Const_Base_ptr; |
d3d526ac | 329 | typedef _Rb_tree_node<_Val> _Rb_tree_node; |
ed6814f7 | 330 | |
d3d526ac BK |
331 | public: |
332 | typedef _Key key_type; | |
333 | typedef _Val value_type; | |
334 | typedef value_type* pointer; | |
335 | typedef const value_type* const_pointer; | |
336 | typedef value_type& reference; | |
337 | typedef const value_type& const_reference; | |
338 | typedef _Rb_tree_node* _Link_type; | |
b4c70e89 | 339 | typedef const _Rb_tree_node* _Const_Link_type; |
d3d526ac BK |
340 | typedef size_t size_type; |
341 | typedef ptrdiff_t difference_type; | |
34c87829 | 342 | typedef _Alloc allocator_type; |
8bd22a3c | 343 | |
31905f34 PC |
344 | _Node_allocator& |
345 | _M_get_Node_allocator() | |
346 | { return *static_cast<_Node_allocator*>(&this->_M_impl); } | |
347 | ||
348 | const _Node_allocator& | |
349 | _M_get_Node_allocator() const | |
8bd22a3c | 350 | { return *static_cast<const _Node_allocator*>(&this->_M_impl); } |
ed6814f7 | 351 | |
31905f34 PC |
352 | allocator_type |
353 | get_allocator() const | |
354 | { return allocator_type(_M_get_Node_allocator()); } | |
355 | ||
d3d526ac | 356 | protected: |
34c87829 | 357 | _Rb_tree_node* |
62e67651 | 358 | _M_get_node() |
8bd22a3c | 359 | { return _M_impl._Node_allocator::allocate(1); } |
34c87829 | 360 | |
ed6814f7 | 361 | void |
62e67651 | 362 | _M_put_node(_Rb_tree_node* __p) |
8bd22a3c | 363 | { _M_impl._Node_allocator::deallocate(__p, 1); } |
ed6814f7 | 364 | |
d3d526ac BK |
365 | _Link_type |
366 | _M_create_node(const value_type& __x) | |
367 | { | |
34c87829 | 368 | _Link_type __tmp = _M_get_node(); |
ed6814f7 | 369 | try |
1985f1cd | 370 | { get_allocator().construct(&__tmp->_M_value_field, __x); } |
d3d526ac BK |
371 | catch(...) |
372 | { | |
62e67651 | 373 | _M_put_node(__tmp); |
ed6814f7 | 374 | __throw_exception_again; |
d3d526ac BK |
375 | } |
376 | return __tmp; | |
725dc051 | 377 | } |
ed6814f7 BI |
378 | |
379 | _Link_type | |
b4c70e89 | 380 | _M_clone_node(_Const_Link_type __x) |
d3d526ac BK |
381 | { |
382 | _Link_type __tmp = _M_create_node(__x->_M_value_field); | |
383 | __tmp->_M_color = __x->_M_color; | |
384 | __tmp->_M_left = 0; | |
385 | __tmp->_M_right = 0; | |
386 | return __tmp; | |
725dc051 | 387 | } |
d3d526ac BK |
388 | |
389 | void | |
dc4871cb | 390 | _M_destroy_node(_Link_type __p) |
d3d526ac | 391 | { |
1985f1cd | 392 | get_allocator().destroy(&__p->_M_value_field); |
d3d526ac BK |
393 | _M_put_node(__p); |
394 | } | |
395 | ||
34c87829 | 396 | protected: |
8bd22a3c | 397 | template<typename _Key_compare, |
4d73fac9 | 398 | bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value> |
8bd22a3c BK |
399 | struct _Rb_tree_impl : public _Node_allocator |
400 | { | |
401 | _Key_compare _M_key_compare; | |
402 | _Rb_tree_node_base _M_header; | |
403 | size_type _M_node_count; // Keeps track of size of tree. | |
404 | ||
405 | _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), | |
406 | const _Key_compare& __comp = _Key_compare()) | |
dda6e8cd BK |
407 | : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), |
408 | _M_node_count(0) | |
8bd22a3c BK |
409 | { |
410 | this->_M_header._M_color = _S_red; | |
411 | this->_M_header._M_parent = 0; | |
412 | this->_M_header._M_left = &this->_M_header; | |
413 | this->_M_header._M_right = &this->_M_header; | |
414 | } | |
415 | }; | |
416 | ||
417 | // Specialization for _Comparison types that are not capable of | |
418 | // being base classes / super classes. | |
419 | template<typename _Key_compare> | |
420 | struct _Rb_tree_impl<_Key_compare, true> : public _Node_allocator | |
421 | { | |
422 | _Key_compare _M_key_compare; | |
423 | _Rb_tree_node_base _M_header; | |
424 | size_type _M_node_count; // Keeps track of size of tree. | |
425 | ||
426 | _Rb_tree_impl(const _Node_allocator& __a = _Node_allocator(), | |
427 | const _Key_compare& __comp = _Key_compare()) | |
3d480e2f PC |
428 | : _Node_allocator(__a), _M_key_compare(__comp), _M_header(), |
429 | _M_node_count(0) | |
8bd22a3c BK |
430 | { |
431 | this->_M_header._M_color = _S_red; | |
432 | this->_M_header._M_parent = 0; | |
433 | this->_M_header._M_left = &this->_M_header; | |
434 | this->_M_header._M_right = &this->_M_header; | |
435 | } | |
436 | }; | |
437 | ||
438 | _Rb_tree_impl<_Compare> _M_impl; | |
ed6814f7 | 439 | |
34c87829 | 440 | protected: |
b4c70e89 | 441 | _Base_ptr& |
62e67651 | 442 | _M_root() |
8bd22a3c | 443 | { return this->_M_impl._M_header._M_parent; } |
d3d526ac | 444 | |
b4c70e89 | 445 | _Const_Base_ptr |
62e67651 | 446 | _M_root() const |
8bd22a3c | 447 | { return this->_M_impl._M_header._M_parent; } |
d3d526ac | 448 | |
b4c70e89 | 449 | _Base_ptr& |
62e67651 | 450 | _M_leftmost() |
8bd22a3c | 451 | { return this->_M_impl._M_header._M_left; } |
b4c70e89 GB |
452 | |
453 | _Const_Base_ptr | |
62e67651 | 454 | _M_leftmost() const |
8bd22a3c | 455 | { return this->_M_impl._M_header._M_left; } |
b4c70e89 GB |
456 | |
457 | _Base_ptr& | |
62e67651 | 458 | _M_rightmost() |
8bd22a3c | 459 | { return this->_M_impl._M_header._M_right; } |
b4c70e89 GB |
460 | |
461 | _Const_Base_ptr | |
62e67651 | 462 | _M_rightmost() const |
8bd22a3c | 463 | { return this->_M_impl._M_header._M_right; } |
d3d526ac | 464 | |
7f6dd1ca | 465 | _Link_type |
62e67651 | 466 | _M_begin() |
8bd22a3c | 467 | { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); } |
b4c70e89 GB |
468 | |
469 | _Const_Link_type | |
62e67651 | 470 | _M_begin() const |
11aaf40c PC |
471 | { |
472 | return static_cast<_Const_Link_type> | |
473 | (this->_M_impl._M_header._M_parent); | |
474 | } | |
d3d526ac | 475 | |
b4c70e89 | 476 | _Link_type |
62e67651 | 477 | _M_end() |
8bd22a3c | 478 | { return static_cast<_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 479 | |
b4c70e89 | 480 | _Const_Link_type |
62e67651 | 481 | _M_end() const |
8bd22a3c | 482 | { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); } |
d3d526ac | 483 | |
ed6814f7 | 484 | static const_reference |
62e67651 PC |
485 | _S_value(_Const_Link_type __x) |
486 | { return __x->_M_value_field; } | |
d3d526ac | 487 | |
ed6814f7 | 488 | static const _Key& |
62e67651 PC |
489 | _S_key(_Const_Link_type __x) |
490 | { return _KeyOfValue()(_S_value(__x)); } | |
b4c70e89 GB |
491 | |
492 | static _Link_type | |
62e67651 PC |
493 | _S_left(_Base_ptr __x) |
494 | { return static_cast<_Link_type>(__x->_M_left); } | |
d3d526ac | 495 | |
b4c70e89 | 496 | static _Const_Link_type |
62e67651 PC |
497 | _S_left(_Const_Base_ptr __x) |
498 | { return static_cast<_Const_Link_type>(__x->_M_left); } | |
d3d526ac | 499 | |
b4c70e89 | 500 | static _Link_type |
62e67651 PC |
501 | _S_right(_Base_ptr __x) |
502 | { return static_cast<_Link_type>(__x->_M_right); } | |
d3d526ac | 503 | |
b4c70e89 | 504 | static _Const_Link_type |
62e67651 PC |
505 | _S_right(_Const_Base_ptr __x) |
506 | { return static_cast<_Const_Link_type>(__x->_M_right); } | |
d3d526ac | 507 | |
b4c70e89 | 508 | static const_reference |
62e67651 PC |
509 | _S_value(_Const_Base_ptr __x) |
510 | { return static_cast<_Const_Link_type>(__x)->_M_value_field; } | |
d3d526ac | 511 | |
ed6814f7 | 512 | static const _Key& |
62e67651 PC |
513 | _S_key(_Const_Base_ptr __x) |
514 | { return _KeyOfValue()(_S_value(__x)); } | |
b4c70e89 | 515 | |
ed6814f7 BI |
516 | static _Base_ptr |
517 | _S_minimum(_Base_ptr __x) | |
b4c70e89 | 518 | { return _Rb_tree_node_base::_S_minimum(__x); } |
d3d526ac | 519 | |
b4c70e89 GB |
520 | static _Const_Base_ptr |
521 | _S_minimum(_Const_Base_ptr __x) | |
522 | { return _Rb_tree_node_base::_S_minimum(__x); } | |
d3d526ac | 523 | |
b4c70e89 GB |
524 | static _Base_ptr |
525 | _S_maximum(_Base_ptr __x) | |
526 | { return _Rb_tree_node_base::_S_maximum(__x); } | |
d3d526ac | 527 | |
b4c70e89 GB |
528 | static _Const_Base_ptr |
529 | _S_maximum(_Const_Base_ptr __x) | |
530 | { return _Rb_tree_node_base::_S_maximum(__x); } | |
d3d526ac BK |
531 | |
532 | public: | |
e135a038 BK |
533 | typedef _Rb_tree_iterator<value_type> iterator; |
534 | typedef _Rb_tree_const_iterator<value_type> const_iterator; | |
d3d526ac | 535 | |
e135a038 | 536 | typedef std::reverse_iterator<iterator> reverse_iterator; |
be26865d | 537 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
d3d526ac BK |
538 | |
539 | private: | |
ed6814f7 | 540 | iterator |
dc4871cb PC |
541 | _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, |
542 | const value_type& __v); | |
d3d526ac | 543 | |
cf1e0371 PC |
544 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
545 | // 233. Insertion hints in associative containers. | |
546 | iterator | |
547 | _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v); | |
548 | ||
dc4871cb PC |
549 | iterator |
550 | _M_insert_equal_lower(const value_type& __x); | |
d5e07b79 | 551 | |
ed6814f7 | 552 | _Link_type |
b4c70e89 | 553 | _M_copy(_Const_Link_type __x, _Link_type __p); |
d3d526ac | 554 | |
ed6814f7 | 555 | void |
d3d526ac BK |
556 | _M_erase(_Link_type __x); |
557 | ||
dc4871cb PC |
558 | iterator |
559 | _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, | |
560 | const _Key& __k) const; | |
561 | ||
562 | iterator | |
563 | _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, | |
564 | const _Key& __k) const; | |
565 | ||
639b490b PC |
566 | pair<iterator, iterator> |
567 | _M_equal_range(const _Key& __k) const; | |
568 | ||
d3d526ac BK |
569 | public: |
570 | // allocation/deallocation | |
571 | _Rb_tree() | |
8bd22a3c | 572 | { } |
d3d526ac BK |
573 | |
574 | _Rb_tree(const _Compare& __comp) | |
8bd22a3c BK |
575 | : _M_impl(allocator_type(), __comp) |
576 | { } | |
d3d526ac BK |
577 | |
578 | _Rb_tree(const _Compare& __comp, const allocator_type& __a) | |
8bd22a3c BK |
579 | : _M_impl(__a, __comp) |
580 | { } | |
d3d526ac | 581 | |
11aaf40c | 582 | _Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) |
31905f34 | 583 | : _M_impl(__x._M_get_Node_allocator(), __x._M_impl._M_key_compare) |
ed6814f7 | 584 | { |
8bd22a3c | 585 | if (__x._M_root() != 0) |
d3d526ac | 586 | { |
b4c70e89 | 587 | _M_root() = _M_copy(__x._M_begin(), _M_end()); |
d3d526ac BK |
588 | _M_leftmost() = _S_minimum(_M_root()); |
589 | _M_rightmost() = _S_maximum(_M_root()); | |
8bd22a3c | 590 | _M_impl._M_node_count = __x._M_impl._M_node_count; |
d3d526ac | 591 | } |
725dc051 | 592 | } |
d3d526ac | 593 | |
737ab798 PC |
594 | ~_Rb_tree() |
595 | { _M_erase(_M_begin()); } | |
d3d526ac | 596 | |
11aaf40c PC |
597 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& |
598 | operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x); | |
d3d526ac | 599 | |
d3d526ac | 600 | // Accessors. |
ed6814f7 | 601 | _Compare |
62e67651 | 602 | key_comp() const |
8bd22a3c | 603 | { return _M_impl._M_key_compare; } |
d3d526ac | 604 | |
ed6814f7 | 605 | iterator |
62e67651 | 606 | begin() |
e182017e PC |
607 | { |
608 | return iterator(static_cast<_Link_type> | |
609 | (this->_M_impl._M_header._M_left)); | |
610 | } | |
d3d526ac | 611 | |
ed6814f7 | 612 | const_iterator |
62e67651 | 613 | begin() const |
e182017e PC |
614 | { |
615 | return const_iterator(static_cast<_Const_Link_type> | |
616 | (this->_M_impl._M_header._M_left)); | |
11aaf40c | 617 | } |
d3d526ac | 618 | |
ed6814f7 | 619 | iterator |
62e67651 | 620 | end() |
e182017e | 621 | { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); } |
d3d526ac | 622 | |
7f6dd1ca | 623 | const_iterator |
62e67651 | 624 | end() const |
e182017e PC |
625 | { |
626 | return const_iterator(static_cast<_Const_Link_type> | |
627 | (&this->_M_impl._M_header)); | |
628 | } | |
d3d526ac | 629 | |
ed6814f7 | 630 | reverse_iterator |
62e67651 PC |
631 | rbegin() |
632 | { return reverse_iterator(end()); } | |
d3d526ac | 633 | |
ed6814f7 | 634 | const_reverse_iterator |
62e67651 PC |
635 | rbegin() const |
636 | { return const_reverse_iterator(end()); } | |
d3d526ac | 637 | |
ed6814f7 | 638 | reverse_iterator |
62e67651 PC |
639 | rend() |
640 | { return reverse_iterator(begin()); } | |
d3d526ac | 641 | |
ed6814f7 | 642 | const_reverse_iterator |
62e67651 PC |
643 | rend() const |
644 | { return const_reverse_iterator(begin()); } | |
ed6814f7 BI |
645 | |
646 | bool | |
62e67651 | 647 | empty() const |
8bd22a3c | 648 | { return _M_impl._M_node_count == 0; } |
d3d526ac | 649 | |
ed6814f7 | 650 | size_type |
62e67651 | 651 | size() const |
8bd22a3c | 652 | { return _M_impl._M_node_count; } |
d3d526ac | 653 | |
ed6814f7 | 654 | size_type |
62e67651 | 655 | max_size() const |
1f9c69a9 | 656 | { return get_allocator().max_size(); } |
d3d526ac | 657 | |
ed6814f7 | 658 | void |
11aaf40c | 659 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t); |
ed6814f7 | 660 | |
d3d526ac | 661 | // Insert/erase. |
42a27024 PC |
662 | pair<iterator, bool> |
663 | _M_insert_unique(const value_type& __x); | |
d3d526ac | 664 | |
ed6814f7 | 665 | iterator |
42a27024 | 666 | _M_insert_equal(const value_type& __x); |
d3d526ac | 667 | |
ed6814f7 | 668 | iterator |
dc4871cb | 669 | _M_insert_unique_(const_iterator __position, const value_type& __x); |
d5e07b79 | 670 | |
ed6814f7 | 671 | iterator |
dc4871cb | 672 | _M_insert_equal_(const_iterator __position, const value_type& __x); |
d5e07b79 | 673 | |
d3d526ac | 674 | template<typename _InputIterator> |
e182017e | 675 | void |
42a27024 | 676 | _M_insert_unique(_InputIterator __first, _InputIterator __last); |
d3d526ac BK |
677 | |
678 | template<typename _InputIterator> | |
e182017e | 679 | void |
42a27024 | 680 | _M_insert_equal(_InputIterator __first, _InputIterator __last); |
d3d526ac | 681 | |
ed6814f7 | 682 | void |
d3d526ac BK |
683 | erase(iterator __position); |
684 | ||
d5e07b79 PC |
685 | void |
686 | erase(const_iterator __position); | |
687 | ||
ed6814f7 | 688 | size_type |
d3d526ac BK |
689 | erase(const key_type& __x); |
690 | ||
ed6814f7 | 691 | void |
d3d526ac BK |
692 | erase(iterator __first, iterator __last); |
693 | ||
d5e07b79 PC |
694 | void |
695 | erase(const_iterator __first, const_iterator __last); | |
696 | ||
ed6814f7 | 697 | void |
d3d526ac BK |
698 | erase(const key_type* __first, const key_type* __last); |
699 | ||
e135a038 BK |
700 | void |
701 | clear() | |
d3d526ac | 702 | { |
e135a038 BK |
703 | _M_erase(_M_begin()); |
704 | _M_leftmost() = _M_end(); | |
705 | _M_root() = 0; | |
706 | _M_rightmost() = _M_end(); | |
8bd22a3c | 707 | _M_impl._M_node_count = 0; |
e135a038 | 708 | } |
d3d526ac BK |
709 | |
710 | // Set operations. | |
ed6814f7 | 711 | iterator |
dc4871cb | 712 | find(const key_type& __k); |
d3d526ac | 713 | |
ed6814f7 | 714 | const_iterator |
dc4871cb | 715 | find(const key_type& __k) const; |
d3d526ac | 716 | |
ed6814f7 | 717 | size_type |
dc4871cb | 718 | count(const key_type& __k) const; |
d3d526ac | 719 | |
ed6814f7 | 720 | iterator |
dc4871cb PC |
721 | lower_bound(const key_type& __k) |
722 | { return iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } | |
d3d526ac | 723 | |
ed6814f7 | 724 | const_iterator |
dc4871cb PC |
725 | lower_bound(const key_type& __k) const |
726 | { return const_iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); } | |
d3d526ac | 727 | |
ed6814f7 | 728 | iterator |
dc4871cb PC |
729 | upper_bound(const key_type& __k) |
730 | { return iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } | |
d3d526ac | 731 | |
ed6814f7 | 732 | const_iterator |
dc4871cb PC |
733 | upper_bound(const key_type& __k) const |
734 | { return const_iterator(_M_upper_bound(_M_begin(), _M_end(), __k)); } | |
d3d526ac | 735 | |
dc4871cb | 736 | pair<iterator, iterator> |
639b490b PC |
737 | equal_range(const key_type& __k) |
738 | { return pair<iterator, iterator>(_M_equal_range(__k)); } | |
d3d526ac | 739 | |
ed6814f7 | 740 | pair<const_iterator, const_iterator> |
639b490b PC |
741 | equal_range(const key_type& __k) const |
742 | { return pair<const_iterator, const_iterator>(_M_equal_range(__k)); } | |
d3d526ac BK |
743 | |
744 | // Debugging. | |
ed6814f7 | 745 | bool |
d3d526ac BK |
746 | __rb_verify() const; |
747 | }; | |
748 | ||
ed6814f7 | 749 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 750 | typename _Compare, typename _Alloc> |
ed6814f7 | 751 | inline bool |
11aaf40c PC |
752 | operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
753 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac | 754 | { |
62e67651 | 755 | return __x.size() == __y.size() |
ac317859 | 756 | && std::equal(__x.begin(), __x.end(), __y.begin()); |
725dc051 | 757 | } |
d3d526ac | 758 | |
ed6814f7 | 759 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 760 | typename _Compare, typename _Alloc> |
ed6814f7 | 761 | inline bool |
11aaf40c PC |
762 | operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
763 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac | 764 | { |
ac317859 PC |
765 | return std::lexicographical_compare(__x.begin(), __x.end(), |
766 | __y.begin(), __y.end()); | |
725dc051 | 767 | } |
d3d526ac | 768 | |
ed6814f7 | 769 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 770 | typename _Compare, typename _Alloc> |
ed6814f7 | 771 | inline bool |
11aaf40c PC |
772 | operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
773 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
774 | { return !(__x == __y); } |
775 | ||
ed6814f7 | 776 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 777 | typename _Compare, typename _Alloc> |
ed6814f7 | 778 | inline bool |
11aaf40c PC |
779 | operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
780 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
781 | { return __y < __x; } |
782 | ||
ed6814f7 | 783 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 784 | typename _Compare, typename _Alloc> |
ed6814f7 | 785 | inline bool |
11aaf40c PC |
786 | operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
787 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
737ab798 | 788 | { return !(__y < __x); } |
d3d526ac | 789 | |
ed6814f7 | 790 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 791 | typename _Compare, typename _Alloc> |
ed6814f7 | 792 | inline bool |
11aaf40c PC |
793 | operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
794 | const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
737ab798 | 795 | { return !(__x < __y); } |
d3d526ac | 796 | |
ed6814f7 | 797 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 798 | typename _Compare, typename _Alloc> |
ed6814f7 | 799 | inline void |
11aaf40c PC |
800 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x, |
801 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y) | |
d3d526ac BK |
802 | { __x.swap(__y); } |
803 | ||
ed6814f7 | 804 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 805 | typename _Compare, typename _Alloc> |
11aaf40c PC |
806 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& |
807 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
808 | operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x) | |
d3d526ac | 809 | { |
ed6814f7 | 810 | if (this != &__x) |
d3d526ac BK |
811 | { |
812 | // Note that _Key may be a constant type. | |
813 | clear(); | |
8bd22a3c | 814 | _M_impl._M_key_compare = __x._M_impl._M_key_compare; |
ed6814f7 | 815 | if (__x._M_root() != 0) |
d3d526ac | 816 | { |
b4c70e89 | 817 | _M_root() = _M_copy(__x._M_begin(), _M_end()); |
d3d526ac BK |
818 | _M_leftmost() = _S_minimum(_M_root()); |
819 | _M_rightmost() = _S_maximum(_M_root()); | |
8bd22a3c | 820 | _M_impl._M_node_count = __x._M_impl._M_node_count; |
d3d526ac BK |
821 | } |
822 | } | |
823 | return *this; | |
725dc051 | 824 | } |
d3d526ac | 825 | |
ed6814f7 | 826 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 827 | typename _Compare, typename _Alloc> |
11aaf40c PC |
828 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
829 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
dc4871cb | 830 | _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v) |
d3d526ac | 831 | { |
7320b491 EC |
832 | bool __insert_left = (__x != 0 || __p == _M_end() |
833 | || _M_impl._M_key_compare(_KeyOfValue()(__v), | |
834 | _S_key(__p))); | |
e135a038 | 835 | |
7320b491 | 836 | _Link_type __z = _M_create_node(__v); |
e135a038 | 837 | |
dc4871cb PC |
838 | _Rb_tree_insert_and_rebalance(__insert_left, __z, |
839 | const_cast<_Base_ptr>(__p), | |
8bd22a3c BK |
840 | this->_M_impl._M_header); |
841 | ++_M_impl._M_node_count; | |
d3d526ac BK |
842 | return iterator(__z); |
843 | } | |
844 | ||
cf1e0371 PC |
845 | template<typename _Key, typename _Val, typename _KeyOfValue, |
846 | typename _Compare, typename _Alloc> | |
847 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator | |
848 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
849 | _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v) | |
850 | { | |
851 | bool __insert_left = (__x != 0 || __p == _M_end() | |
852 | || !_M_impl._M_key_compare(_S_key(__p), | |
853 | _KeyOfValue()(__v))); | |
854 | ||
855 | _Link_type __z = _M_create_node(__v); | |
856 | ||
857 | _Rb_tree_insert_and_rebalance(__insert_left, __z, __p, | |
858 | this->_M_impl._M_header); | |
859 | ++_M_impl._M_node_count; | |
860 | return iterator(__z); | |
861 | } | |
862 | ||
d5e07b79 PC |
863 | template<typename _Key, typename _Val, typename _KeyOfValue, |
864 | typename _Compare, typename _Alloc> | |
dc4871cb | 865 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
d5e07b79 | 866 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
dc4871cb | 867 | _M_insert_equal_lower(const _Val& __v) |
d5e07b79 | 868 | { |
dc4871cb PC |
869 | _Link_type __x = _M_begin(); |
870 | _Link_type __y = _M_end(); | |
871 | while (__x != 0) | |
872 | { | |
873 | __y = __x; | |
874 | __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ? | |
875 | _S_left(__x) : _S_right(__x); | |
876 | } | |
877 | return _M_insert_lower(__x, __y, __v); | |
878 | } | |
d5e07b79 | 879 | |
dc4871cb PC |
880 | template<typename _Key, typename _Val, typename _KoV, |
881 | typename _Compare, typename _Alloc> | |
882 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type | |
883 | _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>:: | |
884 | _M_copy(_Const_Link_type __x, _Link_type __p) | |
885 | { | |
886 | // Structural copy. __x and __p must be non-null. | |
887 | _Link_type __top = _M_clone_node(__x); | |
888 | __top->_M_parent = __p; | |
d5e07b79 | 889 | |
dc4871cb PC |
890 | try |
891 | { | |
892 | if (__x->_M_right) | |
893 | __top->_M_right = _M_copy(_S_right(__x), __top); | |
894 | __p = __top; | |
895 | __x = _S_left(__x); | |
896 | ||
897 | while (__x != 0) | |
898 | { | |
899 | _Link_type __y = _M_clone_node(__x); | |
900 | __p->_M_left = __y; | |
901 | __y->_M_parent = __p; | |
902 | if (__x->_M_right) | |
903 | __y->_M_right = _M_copy(_S_right(__x), __y); | |
904 | __p = __y; | |
905 | __x = _S_left(__x); | |
906 | } | |
907 | } | |
908 | catch(...) | |
909 | { | |
910 | _M_erase(__top); | |
911 | __throw_exception_again; | |
912 | } | |
913 | return __top; | |
d5e07b79 PC |
914 | } |
915 | ||
ed6814f7 | 916 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 917 | typename _Compare, typename _Alloc> |
dc4871cb | 918 | void |
11aaf40c | 919 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
dc4871cb | 920 | _M_erase(_Link_type __x) |
d3d526ac | 921 | { |
dc4871cb | 922 | // Erase without rebalancing. |
ed6814f7 | 923 | while (__x != 0) |
d3d526ac | 924 | { |
dc4871cb PC |
925 | _M_erase(_S_right(__x)); |
926 | _Link_type __y = _S_left(__x); | |
927 | _M_destroy_node(__x); | |
928 | __x = __y; | |
d3d526ac | 929 | } |
d3d526ac BK |
930 | } |
931 | ||
cf1e0371 PC |
932 | template<typename _Key, typename _Val, typename _KeyOfValue, |
933 | typename _Compare, typename _Alloc> | |
934 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator | |
935 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
dc4871cb PC |
936 | _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y, |
937 | const _Key& __k) const | |
cf1e0371 | 938 | { |
cf1e0371 | 939 | while (__x != 0) |
dc4871cb PC |
940 | if (!_M_impl._M_key_compare(_S_key(__x), __k)) |
941 | __y = __x, __x = _S_left(__x); | |
942 | else | |
943 | __x = _S_right(__x); | |
944 | return iterator(const_cast<_Link_type>(__y)); | |
945 | } | |
946 | ||
947 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
948 | typename _Compare, typename _Alloc> | |
949 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator | |
950 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
951 | _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y, | |
952 | const _Key& __k) const | |
953 | { | |
954 | while (__x != 0) | |
955 | if (_M_impl._M_key_compare(__k, _S_key(__x))) | |
956 | __y = __x, __x = _S_left(__x); | |
957 | else | |
958 | __x = _S_right(__x); | |
959 | return iterator(const_cast<_Link_type>(__y)); | |
cf1e0371 PC |
960 | } |
961 | ||
639b490b PC |
962 | template<typename _Key, typename _Val, typename _KeyOfValue, |
963 | typename _Compare, typename _Alloc> | |
964 | pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, | |
965 | _Compare, _Alloc>::iterator, | |
966 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator> | |
967 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
968 | _M_equal_range(const _Key& __k) const | |
969 | { | |
970 | _Const_Link_type __x = _M_begin(); | |
971 | _Const_Link_type __y = _M_end(); | |
972 | while (__x != 0) | |
973 | { | |
974 | if (_M_impl._M_key_compare(_S_key(__x), __k)) | |
975 | __x = _S_right(__x); | |
976 | else if (_M_impl._M_key_compare(__k, _S_key(__x))) | |
977 | __y = __x, __x = _S_left(__x); | |
978 | else | |
979 | { | |
980 | _Const_Link_type __xu(__x), __yu(__y); | |
981 | __y = __x, __x = _S_left(__x); | |
982 | __xu = _S_right(__xu); | |
983 | return pair<iterator, iterator>(_M_lower_bound(__x, __y, __k), | |
984 | _M_upper_bound(__xu, __yu, __k)); | |
985 | } | |
986 | } | |
987 | return pair<iterator, iterator>(iterator(const_cast<_Link_type>(__y)), | |
988 | iterator(const_cast<_Link_type>(__y))); | |
989 | } | |
990 | ||
ed6814f7 | 991 | template<typename _Key, typename _Val, typename _KeyOfValue, |
7f6dd1ca GB |
992 | typename _Compare, typename _Alloc> |
993 | void | |
11aaf40c PC |
994 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
995 | swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t) | |
7f6dd1ca GB |
996 | { |
997 | if (_M_root() == 0) | |
7f6dd1ca | 998 | { |
42a27024 PC |
999 | if (__t._M_root() != 0) |
1000 | { | |
1001 | _M_root() = __t._M_root(); | |
1002 | _M_leftmost() = __t._M_leftmost(); | |
1003 | _M_rightmost() = __t._M_rightmost(); | |
1004 | _M_root()->_M_parent = _M_end(); | |
1005 | ||
1006 | __t._M_root() = 0; | |
1007 | __t._M_leftmost() = __t._M_end(); | |
1008 | __t._M_rightmost() = __t._M_end(); | |
1009 | } | |
7f6dd1ca | 1010 | } |
7f6dd1ca | 1011 | else if (__t._M_root() == 0) |
42a27024 PC |
1012 | { |
1013 | __t._M_root() = _M_root(); | |
1014 | __t._M_leftmost() = _M_leftmost(); | |
1015 | __t._M_rightmost() = _M_rightmost(); | |
1016 | __t._M_root()->_M_parent = __t._M_end(); | |
1017 | ||
1018 | _M_root() = 0; | |
1019 | _M_leftmost() = _M_end(); | |
1020 | _M_rightmost() = _M_end(); | |
1021 | } | |
7f6dd1ca | 1022 | else |
42a27024 PC |
1023 | { |
1024 | std::swap(_M_root(),__t._M_root()); | |
1025 | std::swap(_M_leftmost(),__t._M_leftmost()); | |
1026 | std::swap(_M_rightmost(),__t._M_rightmost()); | |
1027 | ||
1028 | _M_root()->_M_parent = _M_end(); | |
1029 | __t._M_root()->_M_parent = __t._M_end(); | |
1030 | } | |
7f6dd1ca | 1031 | // No need to swap header's color as it does not change. |
8bd22a3c BK |
1032 | std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count); |
1033 | std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare); | |
42a27024 | 1034 | |
f7ace77f PC |
1035 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1036 | // 431. Swapping containers with unequal allocators. | |
1037 | std::__alloc_swap<_Node_allocator>:: | |
1038 | _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator()); | |
7f6dd1ca GB |
1039 | } |
1040 | ||
ed6814f7 | 1041 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1042 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1043 | pair<typename _Rb_tree<_Key, _Val, _KeyOfValue, |
1044 | _Compare, _Alloc>::iterator, bool> | |
1045 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
42a27024 | 1046 | _M_insert_unique(const _Val& __v) |
d3d526ac | 1047 | { |
b4c70e89 | 1048 | _Link_type __x = _M_begin(); |
7f6dd1ca | 1049 | _Link_type __y = _M_end(); |
d3d526ac | 1050 | bool __comp = true; |
62e67651 | 1051 | while (__x != 0) |
d3d526ac BK |
1052 | { |
1053 | __y = __x; | |
8bd22a3c | 1054 | __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)); |
d3d526ac BK |
1055 | __x = __comp ? _S_left(__x) : _S_right(__x); |
1056 | } | |
62e67651 | 1057 | iterator __j = iterator(__y); |
d3d526ac | 1058 | if (__comp) |
62e67651 | 1059 | if (__j == begin()) |
dc4871cb | 1060 | return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); |
d3d526ac BK |
1061 | else |
1062 | --__j; | |
8bd22a3c | 1063 | if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) |
dc4871cb | 1064 | return pair<iterator, bool>(_M_insert_(__x, __y, __v), true); |
11aaf40c | 1065 | return pair<iterator, bool>(__j, false); |
d3d526ac | 1066 | } |
ed6814f7 BI |
1067 | |
1068 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
d3d526ac | 1069 | typename _Compare, typename _Alloc> |
ed6814f7 | 1070 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
d3d526ac | 1071 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
dc4871cb | 1072 | _M_insert_equal(const _Val& __v) |
d3d526ac | 1073 | { |
dc4871cb PC |
1074 | _Link_type __x = _M_begin(); |
1075 | _Link_type __y = _M_end(); | |
1076 | while (__x != 0) | |
ec5537cc | 1077 | { |
dc4871cb PC |
1078 | __y = __x; |
1079 | __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? | |
1080 | _S_left(__x) : _S_right(__x); | |
d3d526ac | 1081 | } |
dc4871cb | 1082 | return _M_insert_(__x, __y, __v); |
725dc051 | 1083 | } |
d3d526ac | 1084 | |
d5e07b79 PC |
1085 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1086 | typename _Compare, typename _Alloc> | |
dc4871cb | 1087 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
d5e07b79 | 1088 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
dc4871cb | 1089 | _M_insert_unique_(const_iterator __position, const _Val& __v) |
d5e07b79 PC |
1090 | { |
1091 | // end() | |
1092 | if (__position._M_node == _M_end()) | |
1093 | { | |
1094 | if (size() > 0 | |
1095 | && _M_impl._M_key_compare(_S_key(_M_rightmost()), | |
1096 | _KeyOfValue()(__v))) | |
dc4871cb | 1097 | return _M_insert_(0, _M_rightmost(), __v); |
d5e07b79 | 1098 | else |
dc4871cb | 1099 | return _M_insert_unique(__v).first; |
d5e07b79 PC |
1100 | } |
1101 | else if (_M_impl._M_key_compare(_KeyOfValue()(__v), | |
1102 | _S_key(__position._M_node))) | |
1103 | { | |
1104 | // First, try before... | |
1105 | const_iterator __before = __position; | |
1106 | if (__position._M_node == _M_leftmost()) // begin() | |
dc4871cb | 1107 | return _M_insert_(_M_leftmost(), _M_leftmost(), __v); |
d5e07b79 PC |
1108 | else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), |
1109 | _KeyOfValue()(__v))) | |
1110 | { | |
1111 | if (_S_right(__before._M_node) == 0) | |
dc4871cb | 1112 | return _M_insert_(0, __before._M_node, __v); |
d5e07b79 | 1113 | else |
dc4871cb PC |
1114 | return _M_insert_(__position._M_node, |
1115 | __position._M_node, __v); | |
d5e07b79 PC |
1116 | } |
1117 | else | |
dc4871cb | 1118 | return _M_insert_unique(__v).first; |
d5e07b79 PC |
1119 | } |
1120 | else if (_M_impl._M_key_compare(_S_key(__position._M_node), | |
1121 | _KeyOfValue()(__v))) | |
1122 | { | |
1123 | // ... then try after. | |
1124 | const_iterator __after = __position; | |
1125 | if (__position._M_node == _M_rightmost()) | |
dc4871cb | 1126 | return _M_insert_(0, _M_rightmost(), __v); |
d5e07b79 PC |
1127 | else if (_M_impl._M_key_compare(_KeyOfValue()(__v), |
1128 | _S_key((++__after)._M_node))) | |
1129 | { | |
1130 | if (_S_right(__position._M_node) == 0) | |
dc4871cb | 1131 | return _M_insert_(0, __position._M_node, __v); |
d5e07b79 | 1132 | else |
dc4871cb | 1133 | return _M_insert_(__after._M_node, __after._M_node, __v); |
d5e07b79 PC |
1134 | } |
1135 | else | |
dc4871cb | 1136 | return _M_insert_unique(__v).first; |
d5e07b79 PC |
1137 | } |
1138 | else | |
dc4871cb PC |
1139 | // Equivalent keys. |
1140 | return iterator(static_cast<_Link_type> | |
1141 | (const_cast<_Base_ptr>(__position._M_node))); | |
d5e07b79 PC |
1142 | } |
1143 | ||
ed6814f7 | 1144 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1145 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1146 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
1147 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
dc4871cb | 1148 | _M_insert_equal_(const_iterator __position, const _Val& __v) |
d3d526ac | 1149 | { |
ec5537cc PC |
1150 | // end() |
1151 | if (__position._M_node == _M_end()) | |
ed6814f7 | 1152 | { |
62e67651 | 1153 | if (size() > 0 |
ec5537cc | 1154 | && !_M_impl._M_key_compare(_KeyOfValue()(__v), |
ac317859 | 1155 | _S_key(_M_rightmost()))) |
dc4871cb | 1156 | return _M_insert_(0, _M_rightmost(), __v); |
d3d526ac | 1157 | else |
42a27024 | 1158 | return _M_insert_equal(__v); |
ed6814f7 | 1159 | } |
d5e07b79 PC |
1160 | else if (!_M_impl._M_key_compare(_S_key(__position._M_node), |
1161 | _KeyOfValue()(__v))) | |
1162 | { | |
1163 | // First, try before... | |
1164 | const_iterator __before = __position; | |
1165 | if (__position._M_node == _M_leftmost()) // begin() | |
dc4871cb | 1166 | return _M_insert_(_M_leftmost(), _M_leftmost(), __v); |
d5e07b79 PC |
1167 | else if (!_M_impl._M_key_compare(_KeyOfValue()(__v), |
1168 | _S_key((--__before)._M_node))) | |
1169 | { | |
1170 | if (_S_right(__before._M_node) == 0) | |
dc4871cb | 1171 | return _M_insert_(0, __before._M_node, __v); |
d5e07b79 | 1172 | else |
dc4871cb PC |
1173 | return _M_insert_(__position._M_node, |
1174 | __position._M_node, __v); | |
d5e07b79 PC |
1175 | } |
1176 | else | |
dc4871cb | 1177 | return _M_insert_equal(__v); |
d5e07b79 PC |
1178 | } |
1179 | else | |
1180 | { | |
1181 | // ... then try after. | |
1182 | const_iterator __after = __position; | |
1183 | if (__position._M_node == _M_rightmost()) | |
dc4871cb | 1184 | return _M_insert_(0, _M_rightmost(), __v); |
d5e07b79 PC |
1185 | else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), |
1186 | _KeyOfValue()(__v))) | |
1187 | { | |
1188 | if (_S_right(__position._M_node) == 0) | |
dc4871cb | 1189 | return _M_insert_(0, __position._M_node, __v); |
d5e07b79 | 1190 | else |
dc4871cb | 1191 | return _M_insert_(__after._M_node, __after._M_node, __v); |
d5e07b79 PC |
1192 | } |
1193 | else | |
dc4871cb | 1194 | return _M_insert_equal_lower(__v); |
d5e07b79 PC |
1195 | } |
1196 | } | |
1197 | ||
ed6814f7 | 1198 | template<typename _Key, typename _Val, typename _KoV, |
d3d526ac BK |
1199 | typename _Cmp, typename _Alloc> |
1200 | template<class _II> | |
ed6814f7 | 1201 | void |
11aaf40c | 1202 | _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: |
dc4871cb | 1203 | _M_insert_unique(_II __first, _II __last) |
322821b9 | 1204 | { |
11aaf40c | 1205 | for (; __first != __last; ++__first) |
dc4871cb | 1206 | _M_insert_unique_(end(), *__first); |
322821b9 | 1207 | } |
725dc051 | 1208 | |
ed6814f7 BI |
1209 | template<typename _Key, typename _Val, typename _KoV, |
1210 | typename _Cmp, typename _Alloc> | |
d3d526ac | 1211 | template<class _II> |
d5e07b79 PC |
1212 | void |
1213 | _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>:: | |
dc4871cb | 1214 | _M_insert_equal(_II __first, _II __last) |
d5e07b79 PC |
1215 | { |
1216 | for (; __first != __last; ++__first) | |
dc4871cb | 1217 | _M_insert_equal_(end(), *__first); |
d5e07b79 | 1218 | } |
725dc051 | 1219 | |
ed6814f7 | 1220 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1221 | typename _Compare, typename _Alloc> |
ed6814f7 | 1222 | inline void |
11aaf40c PC |
1223 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
1224 | erase(iterator __position) | |
d3d526ac | 1225 | { |
11aaf40c PC |
1226 | _Link_type __y = |
1227 | static_cast<_Link_type>(_Rb_tree_rebalance_for_erase | |
1228 | (__position._M_node, | |
1229 | this->_M_impl._M_header)); | |
dc4871cb | 1230 | _M_destroy_node(__y); |
8bd22a3c | 1231 | --_M_impl._M_node_count; |
d3d526ac | 1232 | } |
725dc051 | 1233 | |
d5e07b79 PC |
1234 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1235 | typename _Compare, typename _Alloc> | |
1236 | inline void | |
1237 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1238 | erase(const_iterator __position) | |
1239 | { | |
1240 | _Link_type __y = | |
1241 | static_cast<_Link_type>(_Rb_tree_rebalance_for_erase | |
1242 | (const_cast<_Base_ptr>(__position._M_node), | |
1243 | this->_M_impl._M_header)); | |
dc4871cb | 1244 | _M_destroy_node(__y); |
d5e07b79 PC |
1245 | --_M_impl._M_node_count; |
1246 | } | |
1247 | ||
ed6814f7 | 1248 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1249 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1250 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
1251 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1252 | erase(const _Key& __x) | |
d3d526ac | 1253 | { |
55ce980d IG |
1254 | pair<iterator, iterator> __p = equal_range(__x); |
1255 | const size_type __old_size = size(); | |
d3d526ac | 1256 | erase(__p.first, __p.second); |
55ce980d | 1257 | return __old_size - size(); |
725dc051 | 1258 | } |
725dc051 | 1259 | |
ed6814f7 | 1260 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1261 | typename _Compare, typename _Alloc> |
ed6814f7 | 1262 | void |
11aaf40c | 1263 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
d3d526ac BK |
1264 | erase(iterator __first, iterator __last) |
1265 | { | |
1266 | if (__first == begin() && __last == end()) | |
1267 | clear(); | |
1268 | else | |
a3186d4e PC |
1269 | while (__first != __last) |
1270 | erase(__first++); | |
725dc051 | 1271 | } |
d3d526ac | 1272 | |
d5e07b79 PC |
1273 | template<typename _Key, typename _Val, typename _KeyOfValue, |
1274 | typename _Compare, typename _Alloc> | |
1275 | void | |
1276 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1277 | erase(const_iterator __first, const_iterator __last) | |
1278 | { | |
1279 | if (__first == begin() && __last == end()) | |
1280 | clear(); | |
1281 | else | |
1282 | while (__first != __last) | |
1283 | erase(__first++); | |
1284 | } | |
1285 | ||
ed6814f7 | 1286 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1287 | typename _Compare, typename _Alloc> |
ed6814f7 | 1288 | void |
11aaf40c | 1289 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: |
ed6814f7 BI |
1290 | erase(const _Key* __first, const _Key* __last) |
1291 | { | |
1292 | while (__first != __last) | |
1293 | erase(*__first++); | |
725dc051 | 1294 | } |
d3d526ac | 1295 | |
ed6814f7 | 1296 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1297 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1298 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
1299 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
1300 | find(const _Key& __k) | |
d3d526ac | 1301 | { |
dc4871cb | 1302 | iterator __j = iterator(_M_lower_bound(_M_begin(), _M_end(), __k)); |
11aaf40c PC |
1303 | return (__j == end() |
1304 | || _M_impl._M_key_compare(__k, | |
1305 | _S_key(__j._M_node))) ? end() : __j; | |
d3d526ac | 1306 | } |
ed6814f7 BI |
1307 | |
1308 | template<typename _Key, typename _Val, typename _KeyOfValue, | |
d3d526ac | 1309 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1310 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator |
1311 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac BK |
1312 | find(const _Key& __k) const |
1313 | { | |
dc4871cb PC |
1314 | const_iterator __j = const_iterator(_M_lower_bound(_M_begin(), |
1315 | _M_end(), __k)); | |
1316 | return (__j == end() | |
1317 | || _M_impl._M_key_compare(__k, | |
1318 | _S_key(__j._M_node))) ? end() : __j; | |
725dc051 | 1319 | } |
d3d526ac | 1320 | |
ed6814f7 | 1321 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1322 | typename _Compare, typename _Alloc> |
11aaf40c PC |
1323 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type |
1324 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>:: | |
d3d526ac | 1325 | count(const _Key& __k) const |
322821b9 | 1326 | { |
d3d526ac | 1327 | pair<const_iterator, const_iterator> __p = equal_range(__k); |
62e67651 | 1328 | const size_type __n = std::distance(__p.first, __p.second); |
d3d526ac | 1329 | return __n; |
322821b9 | 1330 | } |
d3d526ac | 1331 | |
b4c70e89 GB |
1332 | unsigned int |
1333 | _Rb_tree_black_count(const _Rb_tree_node_base* __node, | |
1334 | const _Rb_tree_node_base* __root); | |
d3d526ac | 1335 | |
ed6814f7 | 1336 | template<typename _Key, typename _Val, typename _KeyOfValue, |
d3d526ac | 1337 | typename _Compare, typename _Alloc> |
ed6814f7 | 1338 | bool |
d3d526ac BK |
1339 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const |
1340 | { | |
8bd22a3c BK |
1341 | if (_M_impl._M_node_count == 0 || begin() == end()) |
1342 | return _M_impl._M_node_count == 0 && begin() == end() | |
1343 | && this->_M_impl._M_header._M_left == _M_end() | |
1344 | && this->_M_impl._M_header._M_right == _M_end(); | |
ed6814f7 | 1345 | |
737ab798 | 1346 | unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root()); |
ed6814f7 | 1347 | for (const_iterator __it = begin(); __it != end(); ++__it) |
737ab798 PC |
1348 | { |
1349 | _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node); | |
1350 | _Const_Link_type __L = _S_left(__x); | |
1351 | _Const_Link_type __R = _S_right(__x); | |
ed6814f7 | 1352 | |
737ab798 | 1353 | if (__x->_M_color == _S_red) |
ed6814f7 | 1354 | if ((__L && __L->_M_color == _S_red) |
737ab798 PC |
1355 | || (__R && __R->_M_color == _S_red)) |
1356 | return false; | |
ed6814f7 | 1357 | |
8bd22a3c | 1358 | if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L))) |
737ab798 | 1359 | return false; |
8bd22a3c | 1360 | if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x))) |
737ab798 | 1361 | return false; |
ed6814f7 | 1362 | |
737ab798 PC |
1363 | if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len) |
1364 | return false; | |
1365 | } | |
ed6814f7 | 1366 | |
737ab798 PC |
1367 | if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) |
1368 | return false; | |
1369 | if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) | |
1370 | return false; | |
1371 | return true; | |
d3d526ac | 1372 | } |
3cbc7af0 BK |
1373 | |
1374 | _GLIBCXX_END_NAMESPACE | |
725dc051 | 1375 | |
ed6814f7 | 1376 | #endif |