1 /////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2007-2014
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)
9 // See http://www.boost.org/libs/intrusive for documentation.
11 /////////////////////////////////////////////////////////////////////////////
12 #ifndef BOOST_INTRUSIVE_SPLAYTREE_HPP
13 #define BOOST_INTRUSIVE_SPLAYTREE_HPP
15 #include <boost/intrusive/detail/config_begin.hpp>
16 #include <boost/intrusive/intrusive_fwd.hpp>
18 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
19 #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
21 #include <boost/static_assert.hpp>
22 #include <boost/intrusive/bstree.hpp>
23 #include <boost/intrusive/detail/tree_node.hpp>
24 #include <boost/intrusive/detail/mpl.hpp>
25 #include <boost/intrusive/pointer_traits.hpp>
26 #include <boost/intrusive/detail/function_detector.hpp>
27 #include <boost/intrusive/detail/get_value_traits.hpp>
28 #include <boost/intrusive/splaytree_algorithms.hpp>
29 #include <boost/intrusive/link_mode.hpp>
30 #include <boost/intrusive/detail/key_nodeptr_comp.hpp>
31 #include <boost/move/utility_core.hpp>
33 #if defined(BOOST_HAS_PRAGMA_ONCE)
42 struct splaytree_defaults
48 //! The class template splaytree is an intrusive splay tree container that
49 //! is used to construct intrusive splay_set and splay_multiset containers. The no-throw
50 //! guarantee holds only, if the key_compare object
53 //! The template parameter \c T is the type to be managed by the container.
54 //! The user can specify additional options and if no options are provided
55 //! default options are used.
57 //! The container supports the following options:
58 //! \c base_hook<>/member_hook<>/value_traits<>,
59 //! \c constant_time_size<>, \c size_type<> and
61 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
62 template<class T, class ...Options>
64 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
68 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, SplayTreeAlgorithms, HeaderHolder>
72 typedef ValueTraits value_traits;
74 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
75 , ConstantTimeSize, SplayTreeAlgorithms
76 , HeaderHolder> tree_type;
77 typedef tree_type implementation_defined;
80 typedef typename implementation_defined::pointer pointer;
81 typedef typename implementation_defined::const_pointer const_pointer;
82 typedef typename implementation_defined::value_type value_type;
83 typedef typename implementation_defined::key_type key_type;
84 typedef typename implementation_defined::key_of_value key_of_value;
85 typedef typename implementation_defined::reference reference;
86 typedef typename implementation_defined::const_reference const_reference;
87 typedef typename implementation_defined::difference_type difference_type;
88 typedef typename implementation_defined::size_type size_type;
89 typedef typename implementation_defined::value_compare value_compare;
90 typedef typename implementation_defined::key_compare key_compare;
91 typedef typename implementation_defined::iterator iterator;
92 typedef typename implementation_defined::const_iterator const_iterator;
93 typedef typename implementation_defined::reverse_iterator reverse_iterator;
94 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
95 typedef typename implementation_defined::node_traits node_traits;
96 typedef typename implementation_defined::node node;
97 typedef typename implementation_defined::node_ptr node_ptr;
98 typedef typename implementation_defined::const_node_ptr const_node_ptr;
99 typedef typename implementation_defined::node_algorithms node_algorithms;
101 static const bool constant_time_size = implementation_defined::constant_time_size;
106 BOOST_MOVABLE_BUT_NOT_COPYABLE(splaytree_impl)
112 typedef typename implementation_defined::insert_commit_data insert_commit_data;
114 //! @copydoc ::boost::intrusive::bstree::bstree()
119 //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
120 explicit splaytree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
121 : tree_type(cmp, v_traits)
124 //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
125 template<class Iterator>
126 splaytree_impl( bool unique, Iterator b, Iterator e
127 , const key_compare &cmp = key_compare()
128 , const value_traits &v_traits = value_traits())
129 : tree_type(cmp, v_traits)
132 this->insert_unique(b, e);
134 this->insert_equal(b, e);
137 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
138 splaytree_impl(BOOST_RV_REF(splaytree_impl) x)
139 : tree_type(BOOST_MOVE_BASE(tree_type, x))
142 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
143 splaytree_impl& operator=(BOOST_RV_REF(splaytree_impl) x)
144 { return static_cast<splaytree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
146 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
147 //! @copydoc ::boost::intrusive::bstree::~bstree()
150 //! @copydoc ::boost::intrusive::bstree::begin()
153 //! @copydoc ::boost::intrusive::bstree::begin()const
154 const_iterator begin() const;
156 //! @copydoc ::boost::intrusive::bstree::cbegin()const
157 const_iterator cbegin() const;
159 //! @copydoc ::boost::intrusive::bstree::end()
162 //! @copydoc ::boost::intrusive::bstree::end()const
163 const_iterator end() const;
165 //! @copydoc ::boost::intrusive::bstree::cend()const
166 const_iterator cend() const;
168 //! @copydoc ::boost::intrusive::bstree::rbegin()
169 reverse_iterator rbegin();
171 //! @copydoc ::boost::intrusive::bstree::rbegin()const
172 const_reverse_iterator rbegin() const;
174 //! @copydoc ::boost::intrusive::bstree::crbegin()const
175 const_reverse_iterator crbegin() const;
177 //! @copydoc ::boost::intrusive::bstree::rend()
178 reverse_iterator rend();
180 //! @copydoc ::boost::intrusive::bstree::rend()const
181 const_reverse_iterator rend() const;
183 //! @copydoc ::boost::intrusive::bstree::crend()const
184 const_reverse_iterator crend() const;
186 //! @copydoc ::boost::intrusive::bstree::root()
189 //! @copydoc ::boost::intrusive::bstree::root()const
190 const_iterator root() const;
192 //! @copydoc ::boost::intrusive::bstree::croot()const
193 const_iterator croot() const;
195 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
196 static splaytree_impl &container_from_end_iterator(iterator end_iterator);
198 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
199 static const splaytree_impl &container_from_end_iterator(const_iterator end_iterator);
201 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
202 static splaytree_impl &container_from_iterator(iterator it);
204 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
205 static const splaytree_impl &container_from_iterator(const_iterator it);
207 //! @copydoc ::boost::intrusive::bstree::key_comp()const
208 key_compare key_comp() const;
210 //! @copydoc ::boost::intrusive::bstree::value_comp()const
211 value_compare value_comp() const;
213 //! @copydoc ::boost::intrusive::bstree::empty()const
216 //! @copydoc ::boost::intrusive::bstree::size()const
217 size_type size() const;
219 //! @copydoc ::boost::intrusive::bstree::swap
220 void swap(splaytree_impl& other);
222 //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
223 //! Additional notes: it also copies the alpha factor from the source container.
224 template <class Cloner, class Disposer>
225 void clone_from(const splaytree_impl &src, Cloner cloner, Disposer disposer);
227 #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED
229 using tree_type::clone_from;
231 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
233 //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
234 template <class Cloner, class Disposer>
235 void clone_from(BOOST_RV_REF(splaytree_impl) src, Cloner cloner, Disposer disposer)
236 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); }
238 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
240 //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
241 iterator insert_equal(reference value);
243 //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
244 iterator insert_equal(const_iterator hint, reference value);
246 //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
247 template<class Iterator>
248 void insert_equal(Iterator b, Iterator e);
250 //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
251 std::pair<iterator, bool> insert_unique(reference value);
253 //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
254 iterator insert_unique(const_iterator hint, reference value);
256 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&)
257 std::pair<iterator, bool> insert_unique_check
258 (const key_type &key, insert_commit_data &commit_data);
260 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
261 std::pair<iterator, bool> insert_unique_check
262 (const_iterator hint, const key_type &key, insert_commit_data &commit_data);
264 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
265 template<class KeyType, class KeyTypeKeyCompare>
266 std::pair<iterator, bool> insert_unique_check
267 (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
269 //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
270 template<class KeyType, class KeyTypeKeyCompare>
271 std::pair<iterator, bool> insert_unique_check
272 (const_iterator hint, const KeyType &key
273 ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
275 //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
276 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data);
278 //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
279 template<class Iterator>
280 void insert_unique(Iterator b, Iterator e);
282 //! @copydoc ::boost::intrusive::bstree::insert_before
283 iterator insert_before(const_iterator pos, reference value);
285 //! @copydoc ::boost::intrusive::bstree::push_back
286 void push_back(reference value);
288 //! @copydoc ::boost::intrusive::bstree::push_front
289 void push_front(reference value);
291 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
292 iterator erase(const_iterator i);
294 //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
295 iterator erase(const_iterator b, const_iterator e);
297 //! @copydoc ::boost::intrusive::bstree::erase(const key_type &)
298 size_type erase(const key_type &key);
300 //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
301 template<class KeyType, class KeyTypeKeyCompare>
302 size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
304 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
305 template<class Disposer>
306 iterator erase_and_dispose(const_iterator i, Disposer disposer);
308 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
309 template<class Disposer>
310 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
312 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
313 template<class Disposer>
314 size_type erase_and_dispose(const key_type &key, Disposer disposer);
316 //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
317 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
318 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
320 //! @copydoc ::boost::intrusive::bstree::clear
323 //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
324 template<class Disposer>
325 void clear_and_dispose(Disposer disposer);
327 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
328 //! Additional note: non-const function, splaying is performed.
329 size_type count(const key_type &key);
331 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
332 //! Additional note: non-const function, splaying is performed.
333 template<class KeyType, class KeyTypeKeyCompare>
334 size_type count(const KeyType &key, KeyTypeKeyCompare comp);
336 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
337 //! Additional note: const function, no splaying is performed
338 size_type count(const key_type &key) const;
340 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
341 //! Additional note: const function, no splaying is performed
342 template<class KeyType, class KeyTypeKeyCompare>
343 size_type count(const KeyType &key, KeyTypeKeyCompare comp) const;
345 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
346 //! Additional note: non-const function, splaying is performed.
347 iterator lower_bound(const key_type &key);
349 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
350 //! Additional note: const function, no splaying is performed
351 const_iterator lower_bound(const key_type &key) const;
353 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
354 //! Additional note: non-const function, splaying is performed for the first
355 //! element of the equal range of "key"
356 template<class KeyType, class KeyTypeKeyCompare>
357 iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp);
359 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
360 //! Additional note: const function, no splaying is performed
361 template<class KeyType, class KeyTypeKeyCompare>
362 const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const;
364 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
365 //! Additional note: non-const function, splaying is performed for the first
366 //! element of the equal range of "value"
367 iterator upper_bound(const key_type &key);
369 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
370 //! Additional note: const function, no splaying is performed
371 const_iterator upper_bound(const key_type &key) const;
373 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
374 //! Additional note: non-const function, splaying is performed for the first
375 //! element of the equal range of "key"
376 template<class KeyType, class KeyTypeKeyCompare>
377 iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp);
379 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
380 //! Additional note: const function, no splaying is performed
381 template<class KeyType, class KeyTypeKeyCompare>
382 const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const;
384 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
385 //! Additional note: non-const function, splaying is performed for the first
386 //! element of the equal range of "value"
387 iterator find(const key_type &key);
389 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
390 //! Additional note: const function, no splaying is performed
391 const_iterator find(const key_type &key) const;
393 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
394 //! Additional note: non-const function, splaying is performed for the first
395 //! element of the equal range of "key"
396 template<class KeyType, class KeyTypeKeyCompare>
397 iterator find(const KeyType &key, KeyTypeKeyCompare comp);
399 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
400 //! Additional note: const function, no splaying is performed
401 template<class KeyType, class KeyTypeKeyCompare>
402 const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const;
404 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
405 //! Additional note: non-const function, splaying is performed for the first
406 //! element of the equal range of "value"
407 std::pair<iterator, iterator> equal_range(const key_type &key);
409 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
410 //! Additional note: const function, no splaying is performed
411 std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const;
413 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
414 //! Additional note: non-const function, splaying is performed for the first
415 //! element of the equal range of "key"
416 template<class KeyType, class KeyTypeKeyCompare>
417 std::pair<iterator, iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp);
419 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
420 //! Additional note: const function, no splaying is performed
421 template<class KeyType, class KeyTypeKeyCompare>
422 std::pair<const_iterator, const_iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp) const;
424 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
425 std::pair<iterator,iterator> bounded_range
426 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
428 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
429 template<class KeyType, class KeyTypeKeyCompare>
430 std::pair<iterator,iterator> bounded_range
431 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
433 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
434 std::pair<const_iterator, const_iterator> bounded_range
435 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
437 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
438 template<class KeyType, class KeyTypeKeyCompare>
439 std::pair<const_iterator, const_iterator> bounded_range
440 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
442 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
443 static iterator s_iterator_to(reference value);
445 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
446 static const_iterator s_iterator_to(const_reference value);
448 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
449 iterator iterator_to(reference value);
451 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
452 const_iterator iterator_to(const_reference value) const;
454 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
455 static void init_node(reference value);
457 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
458 pointer unlink_leftmost_without_rebalance();
460 //! @copydoc ::boost::intrusive::bstree::replace_node
461 void replace_node(iterator replace_this, reference with_this);
463 //! @copydoc ::boost::intrusive::bstree::remove_node
464 void remove_node(reference value);
466 //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
467 template<class T, class ...Options2>
468 void merge_unique(splaytree<T, Options2...> &);
470 //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
471 template<class T, class ...Options2>
472 void merge_equal(splaytree<T, Options2...> &);
474 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
476 //! <b>Requires</b>: i must be a valid iterator of *this.
478 //! <b>Effects</b>: Rearranges the container so that the element pointed by i
479 //! is placed as the root of the tree, improving future searches of this value.
481 //! <b>Complexity</b>: Amortized logarithmic.
483 //! <b>Throws</b>: Nothing.
484 void splay_up(iterator i)
485 { return node_algorithms::splay_up(i.pointed_node(), tree_type::header_ptr()); }
487 //! <b>Effects</b>: Rearranges the container so that if *this stores an element
488 //! with a key equivalent to value the element is placed as the root of the
489 //! tree. If the element is not present returns the last node compared with the key.
490 //! If the tree is empty, end() is returned.
492 //! <b>Complexity</b>: Amortized logarithmic.
494 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty.
496 //! <b>Throws</b>: If the comparison functor throws.
497 template<class KeyType, class KeyTypeKeyCompare>
498 iterator splay_down(const KeyType &key, KeyTypeKeyCompare comp)
500 detail::key_nodeptr_comp<value_compare, value_traits>
501 key_node_comp(comp, &this->get_value_traits());
502 node_ptr r = node_algorithms::splay_down(tree_type::header_ptr(), key, key_node_comp);
503 return iterator(r, this->priv_value_traits_ptr());
506 //! <b>Effects</b>: Rearranges the container so that if *this stores an element
507 //! with a key equivalent to value the element is placed as the root of the
510 //! <b>Complexity</b>: Amortized logarithmic.
512 //! <b>Returns</b>: An iterator to the new root of the tree, end() if the tree is empty.
514 //! <b>Throws</b>: If the predicate throws.
515 iterator splay_down(const key_type &key)
516 { return this->splay_down(key, this->key_comp()); }
518 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
519 //! @copydoc ::boost::intrusive::bstree::rebalance
522 //! @copydoc ::boost::intrusive::bstree::rebalance_subtree
523 iterator rebalance_subtree(iterator root);
525 friend bool operator< (const splaytree_impl &x, const splaytree_impl &y);
527 friend bool operator==(const splaytree_impl &x, const splaytree_impl &y);
529 friend bool operator!= (const splaytree_impl &x, const splaytree_impl &y);
531 friend bool operator>(const splaytree_impl &x, const splaytree_impl &y);
533 friend bool operator<=(const splaytree_impl &x, const splaytree_impl &y);
535 friend bool operator>=(const splaytree_impl &x, const splaytree_impl &y);
537 friend void swap(splaytree_impl &x, splaytree_impl &y);
539 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
542 //! Helper metafunction to define a \c splaytree that yields to the same type when the
543 //! same options (either explicitly or implicitly) are used.
544 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
545 template<class T, class ...Options>
547 template<class T, class O1 = void, class O2 = void
548 , class O3 = void, class O4 = void
549 , class O5 = void, class O6 = void>
551 struct make_splaytree
554 typedef typename pack_options
555 < splaytree_defaults,
556 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
557 O1, O2, O3, O4, O5, O6
561 >::type packed_options;
563 typedef typename detail::get_value_traits
564 <T, typename packed_options::proto_value_traits>::type value_traits;
566 typedef splaytree_impl
568 , typename packed_options::key_of_value
569 , typename packed_options::compare
570 , typename packed_options::size_type
571 , packed_options::constant_time_size
572 , typename packed_options::header_holder_type
573 > implementation_defined;
575 typedef implementation_defined type;
579 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
581 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
582 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
584 template<class T, class ...Options>
587 : public make_splaytree<T,
588 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
589 O1, O2, O3, O4, O5, O6
595 typedef typename make_splaytree
597 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
598 O1, O2, O3, O4, O5, O6
603 BOOST_MOVABLE_BUT_NOT_COPYABLE(splaytree)
606 typedef typename Base::key_compare key_compare;
607 typedef typename Base::value_traits value_traits;
608 typedef typename Base::iterator iterator;
609 typedef typename Base::const_iterator const_iterator;
610 typedef typename Base::reverse_iterator reverse_iterator;
611 typedef typename Base::const_reverse_iterator const_reverse_iterator;
613 //Assert if passed value traits are compatible with the type
614 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
620 explicit splaytree( const key_compare &cmp, const value_traits &v_traits = value_traits())
621 : Base(cmp, v_traits)
624 template<class Iterator>
625 splaytree( bool unique, Iterator b, Iterator e
626 , const key_compare &cmp = key_compare()
627 , const value_traits &v_traits = value_traits())
628 : Base(unique, b, e, cmp, v_traits)
631 splaytree(BOOST_RV_REF(splaytree) x)
632 : Base(BOOST_MOVE_BASE(Base, x))
635 splaytree& operator=(BOOST_RV_REF(splaytree) x)
636 { return static_cast<splaytree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
638 template <class Cloner, class Disposer>
639 void clone_from(const splaytree &src, Cloner cloner, Disposer disposer)
640 { Base::clone_from(src, cloner, disposer); }
642 template <class Cloner, class Disposer>
643 void clone_from(BOOST_RV_REF(splaytree) src, Cloner cloner, Disposer disposer)
644 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
646 static splaytree &container_from_end_iterator(iterator end_iterator)
647 { return static_cast<splaytree &>(Base::container_from_end_iterator(end_iterator)); }
649 static const splaytree &container_from_end_iterator(const_iterator end_iterator)
650 { return static_cast<const splaytree &>(Base::container_from_end_iterator(end_iterator)); }
652 static splaytree &container_from_iterator(iterator it)
653 { return static_cast<splaytree &>(Base::container_from_iterator(it)); }
655 static const splaytree &container_from_iterator(const_iterator it)
656 { return static_cast<const splaytree &>(Base::container_from_iterator(it)); }
661 } //namespace intrusive
664 #include <boost/intrusive/detail/config_end.hpp>
666 #endif //BOOST_INTRUSIVE_SPLAYTREE_HPP