1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2007-2013
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9// See http://www.boost.org/libs/intrusive for documentation.
10//
11/////////////////////////////////////////////////////////////////////////////
12#ifndef BOOST_INTRUSIVE_AVLTREE_HPP
13#define BOOST_INTRUSIVE_AVLTREE_HPP
14
15#include <boost/intrusive/detail/config_begin.hpp>
16#include <boost/intrusive/intrusive_fwd.hpp>
17#include <cstddef>
18#include <boost/intrusive/detail/minimal_less_equal_header.hpp>
19#include <boost/intrusive/detail/minimal_pair_header.hpp>
20
21#include <boost/static_assert.hpp>
22#include <boost/intrusive/avl_set_hook.hpp>
23#include <boost/intrusive/detail/avltree_node.hpp>
24#include <boost/intrusive/bstree.hpp>
25#include <boost/intrusive/detail/tree_node.hpp>
26#include <boost/intrusive/detail/ebo_functor_holder.hpp>
27#include <boost/intrusive/detail/mpl.hpp>
28#include <boost/intrusive/pointer_traits.hpp>
29#include <boost/intrusive/detail/get_value_traits.hpp>
30#include <boost/intrusive/avltree_algorithms.hpp>
31#include <boost/intrusive/link_mode.hpp>
32#include <boost/move/utility_core.hpp>
33
34#if defined(BOOST_HAS_PRAGMA_ONCE)
35# pragma once
36#endif
37
38namespace boost {
39namespace intrusive {
40
41/// @cond
42
43struct default_avltree_hook_applier
44{ template <class T> struct apply{ typedef typename T::default_avltree_hook type; }; };
45
46template<>
47struct is_default_hook_tag<default_avltree_hook_applier>
48{ static const bool value = true; };
49
50struct avltree_defaults
51 : bstree_defaults
52{
53 typedef default_avltree_hook_applier proto_value_traits;
54};
55
56/// @endcond
57
58//! The class template avltree is an intrusive AVL tree container, that
59//! is used to construct intrusive avl_set and avl_multiset containers.
60//! The no-throw guarantee holds only, if the key_compare object
61//! doesn't throw.
62//!
63//! The template parameter \c T is the type to be managed by the container.
64//! The user can specify additional options and if no options are provided
65//! default options are used.
66//!
67//! The container supports the following options:
68//! \c base_hook<>/member_hook<>/value_traits<>,
69//! \c constant_time_size<>, \c size_type<> and
70//! \c compare<>.
71#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
72template<class T, class ...Options>
73#else
74template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
75#endif
76class avltree_impl
77 /// @cond
78 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, AvlTreeAlgorithms, HeaderHolder>
79 /// @endcond
80{
81 public:
82 typedef ValueTraits value_traits;
83 /// @cond
84 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
85 , ConstantTimeSize, AvlTreeAlgorithms
86 , HeaderHolder> tree_type;
87 typedef tree_type implementation_defined;
88 /// @endcond
89
90 typedef typename implementation_defined::pointer pointer;
91 typedef typename implementation_defined::const_pointer const_pointer;
92 typedef typename implementation_defined::value_type value_type;
93 typedef typename implementation_defined::key_type key_type;
94 typedef typename implementation_defined::key_of_value key_of_value;
95 typedef typename implementation_defined::reference reference;
96 typedef typename implementation_defined::const_reference const_reference;
97 typedef typename implementation_defined::difference_type difference_type;
98 typedef typename implementation_defined::size_type size_type;
99 typedef typename implementation_defined::value_compare value_compare;
100 typedef typename implementation_defined::key_compare key_compare;
101 typedef typename implementation_defined::iterator iterator;
102 typedef typename implementation_defined::const_iterator const_iterator;
103 typedef typename implementation_defined::reverse_iterator reverse_iterator;
104 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
105 typedef typename implementation_defined::node_traits node_traits;
106 typedef typename implementation_defined::node node;
107 typedef typename implementation_defined::node_ptr node_ptr;
108 typedef typename implementation_defined::const_node_ptr const_node_ptr;
109 typedef typename implementation_defined::node_algorithms node_algorithms;
110
111 static const bool constant_time_size = implementation_defined::constant_time_size;
112 /// @cond
113 private:
114
115 //noncopyable
116 BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree_impl)
117
118 /// @endcond
119
120 public:
121
122 typedef typename implementation_defined::insert_commit_data insert_commit_data;
123
124
125 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
126 explicit avltree_impl( const key_compare &cmp = key_compare()
127 , const value_traits &v_traits = value_traits())
128 : tree_type(cmp, v_traits)
129 {}
130
131 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
132 template<class Iterator>
133 avltree_impl( bool unique, Iterator b, Iterator e
134 , const key_compare &cmp = key_compare()
135 , const value_traits &v_traits = value_traits())
136 : tree_type(unique, b, e, cmp, v_traits)
137 {}
138
139 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
140 avltree_impl(BOOST_RV_REF(avltree_impl) x)
141 : tree_type(BOOST_MOVE_BASE(tree_type, x))
142 {}
143
144 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
145 avltree_impl& operator=(BOOST_RV_REF(avltree_impl) x)
146 { return static_cast<avltree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
147
148 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
149
150 //! @copydoc ::boost::intrusive::bstree::~bstree()
151 ~avltree_impl();
152
153 //! @copydoc ::boost::intrusive::bstree::begin()
154 iterator begin();
155
156 //! @copydoc ::boost::intrusive::bstree::begin()const
157 const_iterator begin() const;
158
159 //! @copydoc ::boost::intrusive::bstree::cbegin()const
160 const_iterator cbegin() const;
161
162 //! @copydoc ::boost::intrusive::bstree::end()
163 iterator end();
164
165 //! @copydoc ::boost::intrusive::bstree::end()const
166 const_iterator end() const;
167
168 //! @copydoc ::boost::intrusive::bstree::cend()const
169 const_iterator cend() const;
170
171 //! @copydoc ::boost::intrusive::bstree::rbegin()
172 reverse_iterator rbegin();
173
174 //! @copydoc ::boost::intrusive::bstree::rbegin()const
175 const_reverse_iterator rbegin() const;
176
177 //! @copydoc ::boost::intrusive::bstree::crbegin()const
178 const_reverse_iterator crbegin() const;
179
180 //! @copydoc ::boost::intrusive::bstree::rend()
181 reverse_iterator rend();
182
183 //! @copydoc ::boost::intrusive::bstree::rend()const
184 const_reverse_iterator rend() const;
185
186 //! @copydoc ::boost::intrusive::bstree::crend()const
187 const_reverse_iterator crend() const;
188
189 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
190 static avltree_impl &container_from_end_iterator(iterator end_iterator);
191
192 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
193 static const avltree_impl &container_from_end_iterator(const_iterator end_iterator);
194
195 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
196 static avltree_impl &container_from_iterator(iterator it);
197
198 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
199 static const avltree_impl &container_from_iterator(const_iterator it);
200
201 //! @copydoc ::boost::intrusive::bstree::key_comp()const
202 key_compare key_comp() const;
203
204 //! @copydoc ::boost::intrusive::bstree::value_comp()const
205 value_compare value_comp() const;
206
207 //! @copydoc ::boost::intrusive::bstree::empty()const
208 bool empty() const;
209
210 //! @copydoc ::boost::intrusive::bstree::size()const
211 size_type size() const;
212
213 //! @copydoc ::boost::intrusive::bstree::swap
214 void swap(avltree_impl& other);
215
216 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
217 template <class Cloner, class Disposer>
218 void clone_from(const avltree_impl &src, Cloner cloner, Disposer disposer);
219
220 #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED
221
222 using tree_type::clone_from;
223
224 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
225
226 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
227 template <class Cloner, class Disposer>
228 void clone_from(BOOST_RV_REF(avltree_impl) src, Cloner cloner, Disposer disposer)
229 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); }
230
231 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
232
233 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
234 iterator insert_equal(reference value);
235
236 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
237 iterator insert_equal(const_iterator hint, reference value);
238
239 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
240 template<class Iterator>
241 void insert_equal(Iterator b, Iterator e);
242
243 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
244 std::pair<iterator, bool> insert_unique(reference value);
245
246 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
247 iterator insert_unique(const_iterator hint, reference value);
248
249 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
250 template<class KeyType, class KeyTypeKeyCompare>
251 std::pair<iterator, bool> insert_unique_check
252 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
253
254 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
255 template<class KeyType, class KeyTypeKeyCompare>
256 std::pair<iterator, bool> insert_unique_check
257 (const_iterator hint, const KeyType &key
258 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
259
260 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
261 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data);
262
263 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
264 template<class Iterator>
265 void insert_unique(Iterator b, Iterator e);
266
267 //! @copydoc ::boost::intrusive::bstree::insert_before
268 iterator insert_before(const_iterator pos, reference value);
269
270 //! @copydoc ::boost::intrusive::bstree::push_back
271 void push_back(reference value);
272
273 //! @copydoc ::boost::intrusive::bstree::push_front
274 void push_front(reference value);
275
276 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
277 iterator erase(const_iterator i);
278
279 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
280 iterator erase(const_iterator b, const_iterator e);
281
282 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
283 size_type erase(const key_type &key);
284
285 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
286 template<class KeyType, class KeyTypeKeyCompare>
287 size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
288
289 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
290 template<class Disposer>
291 iterator erase_and_dispose(const_iterator i, Disposer disposer);
292
293 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
294 template<class Disposer>
295 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
296
297 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
298 template<class Disposer>
299 size_type erase_and_dispose(const key_type &key, Disposer disposer);
300
301 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
302 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
303 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
304
305 //! @copydoc ::boost::intrusive::bstree::clear
306 void clear();
307
308 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
309 template<class Disposer>
310 void clear_and_dispose(Disposer disposer);
311
312 //! @copydoc ::boost::intrusive::bstree::count(const key_type &ke)const
313 size_type count(const key_type &key) const;
314
315 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
316 template<class KeyType, class KeyTypeKeyCompare>
317 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
318
319 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
320 iterator lower_bound(const key_type &key);
321
322 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
323 template<class KeyType, class KeyTypeKeyCompare>
324 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
325
326 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
327 const_iterator lower_bound(const key_type &key) const;
328
329 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
330 template<class KeyType, class KeyTypeKeyCompare>
331 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
332
333 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &key)
334 iterator upper_bound(const key_type &key);
335
336 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
337 template<class KeyType, class KeyTypeKeyCompare>
338 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
339
340 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
341 const_iterator upper_bound(const key_type &key) const;
342
343 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
344 template<class KeyType, class KeyTypeKeyCompare>
345 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
346
347 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
348 iterator find(const key_type &key);
349
350 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
351 template<class KeyType, class KeyTypeKeyCompare>
352 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
353
354 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
355 const_iterator find(const key_type &key) const;
356
357 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
358 template<class KeyType, class KeyTypeKeyCompare>
359 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
360
361 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
362 std::pair<iterator,iterator> equal_range(const key_type &key);
363
364 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
365 template<class KeyType, class KeyTypeKeyCompare>
366 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
367
368 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
369 std::pair<const_iterator, const_iterator>
370 equal_range(const key_type &key) const;
371
372 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
373 template<class KeyType, class KeyTypeKeyCompare>
374 std::pair<const_iterator, const_iterator>
375 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
376
377 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
378 std::pair<iterator,iterator> bounded_range
379 (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed);
380
381 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
382 template<class KeyType, class KeyTypeKeyCompare>
383 std::pair<iterator,iterator> bounded_range
384 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
385
386 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
387 std::pair<const_iterator, const_iterator>
388 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
389
390 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
391 template<class KeyType, class KeyTypeKeyCompare>
392 std::pair<const_iterator, const_iterator> bounded_range
393 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
394
395 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
396 static iterator s_iterator_to(reference value);
397
398 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
399 static const_iterator s_iterator_to(const_reference value);
400
401 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
402 iterator iterator_to(reference value);
403
404 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
405 const_iterator iterator_to(const_reference value) const;
406
407 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
408 static void init_node(reference value);
409
410 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
411 pointer unlink_leftmost_without_rebalance();
412
413 //! @copydoc ::boost::intrusive::bstree::replace_node
414 void replace_node(iterator replace_this, reference with_this);
415
416 //! @copydoc ::boost::intrusive::bstree::remove_node
417 void remove_node(reference value);
418
419 friend bool operator< (const avltree_impl &x, const avltree_impl &y);
420
421 friend bool operator==(const avltree_impl &x, const avltree_impl &y);
422
423 friend bool operator!= (const avltree_impl &x, const avltree_impl &y);
424
425 friend bool operator>(const avltree_impl &x, const avltree_impl &y);
426
427 friend bool operator<=(const avltree_impl &x, const avltree_impl &y);
428
429 friend bool operator>=(const avltree_impl &x, const avltree_impl &y);
430
431 friend void swap(avltree_impl &x, avltree_impl &y);
432 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
433};
434
435
436//! Helper metafunction to define a \c avltree that yields to the same type when the
437//! same options (either explicitly or implicitly) are used.
438#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
439template<class T, class ...Options>
440#else
441template<class T, class O1 = void, class O2 = void
442 , class O3 = void, class O4 = void
443 , class O5 = void, class O6 = void>
444#endif
445struct make_avltree
446{
447 /// @cond
448 typedef typename pack_options
449 < avltree_defaults,
450 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
451 O1, O2, O3, O4, O5, O6
452 #else
453 Options...
454 #endif
455 >::type packed_options;
456
457 typedef typename detail::get_value_traits
458 <T, typename packed_options::proto_value_traits>::type value_traits;
459
460 typedef avltree_impl
461 < value_traits
462 , typename packed_options::key_of_value
463 , typename packed_options::compare
464 , typename packed_options::size_type
465 , packed_options::constant_time_size
466 , typename packed_options::header_holder_type
467 > implementation_defined;
468 /// @endcond
469 typedef implementation_defined type;
470};
471
472
473#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
474
475#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
476template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
477#else
478template<class T, class ...Options>
479#endif
480class avltree
481 : public make_avltree<T,
482 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
483 O1, O2, O3, O4, O5, O6
484 #else
485 Options...
486 #endif
487 >::type
488{
489 typedef typename make_avltree
490 <T,
491 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
492 O1, O2, O3, O4, O5, O6
493 #else
494 Options...
495 #endif
496 >::type Base;
497 BOOST_MOVABLE_BUT_NOT_COPYABLE(avltree)
498
499 public:
500 typedef typename Base::key_compare key_compare;
501 typedef typename Base::value_traits value_traits;
502 typedef typename Base::iterator iterator;
503 typedef typename Base::const_iterator const_iterator;
504 typedef typename Base::reverse_iterator reverse_iterator;
505 typedef typename Base::const_reverse_iterator const_reverse_iterator;
506
507 //Assert if passed value traits are compatible with the type
508 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
509
510 explicit avltree( const key_compare &cmp = key_compare()
511 , const value_traits &v_traits = value_traits())
512 : Base(cmp, v_traits)
513 {}
514
515 template<class Iterator>
516 avltree( bool unique, Iterator b, Iterator e
517 , const key_compare &cmp = key_compare()
518 , const value_traits &v_traits = value_traits())
519 : Base(unique, b, e, cmp, v_traits)
520 {}
521
522 avltree(BOOST_RV_REF(avltree) x)
523 : Base(BOOST_MOVE_BASE(Base, x))
524 {}
525
526 avltree& operator=(BOOST_RV_REF(avltree) x)
527 { return static_cast<avltree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
528
529 template <class Cloner, class Disposer>
530 void clone_from(const avltree &src, Cloner cloner, Disposer disposer)
531 { Base::clone_from(src, cloner, disposer); }
532
533 template <class Cloner, class Disposer>
534 void clone_from(BOOST_RV_REF(avltree) src, Cloner cloner, Disposer disposer)
535 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
536
537 static avltree &container_from_end_iterator(iterator end_iterator)
538 { return static_cast<avltree &>(Base::container_from_end_iterator(end_iterator)); }
539
540 static const avltree &container_from_end_iterator(const_iterator end_iterator)
541 { return static_cast<const avltree &>(Base::container_from_end_iterator(end_iterator)); }
542
543 static avltree &container_from_iterator(iterator it)
544 { return static_cast<avltree &>(Base::container_from_iterator(it)); }
545
546 static const avltree &container_from_iterator(const_iterator it)
547 { return static_cast<const avltree &>(Base::container_from_iterator(it)); }
548};
549
550#endif
551
552} //namespace intrusive
553} //namespace boost
554
555#include <boost/intrusive/detail/config_end.hpp>
556
557#endif //BOOST_INTRUSIVE_AVLTREE_HPP
558

source code of boost/boost/intrusive/avltree.hpp