1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2008-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_TREAP_HPP
13#define BOOST_INTRUSIVE_TREAP_HPP
14
15#include <boost/intrusive/detail/config_begin.hpp>
16#include <boost/intrusive/intrusive_fwd.hpp>
17
18#include <boost/intrusive/detail/assert.hpp>
19#include <boost/intrusive/bs_set_hook.hpp>
20#include <boost/intrusive/bstree.hpp>
21#include <boost/intrusive/detail/tree_node.hpp>
22#include <boost/intrusive/detail/ebo_functor_holder.hpp>
23#include <boost/intrusive/pointer_traits.hpp>
24#include <boost/intrusive/detail/get_value_traits.hpp>
25#include <boost/intrusive/detail/mpl.hpp>
26#include <boost/intrusive/treap_algorithms.hpp>
27#include <boost/intrusive/link_mode.hpp>
28#include <boost/intrusive/priority_compare.hpp>
29#include <boost/intrusive/detail/node_cloner_disposer.hpp>
30#include <boost/intrusive/detail/key_nodeptr_comp.hpp>
31
32#include <boost/static_assert.hpp>
33#include <boost/move/utility_core.hpp>
34#include <boost/move/adl_move_swap.hpp>
35
36#include <cstddef>
37#include <boost/intrusive/detail/minimal_less_equal_header.hpp>
38#include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
39
40#if defined(BOOST_HAS_PRAGMA_ONCE)
41# pragma once
42#endif
43
44namespace boost {
45namespace intrusive {
46
47/// @cond
48
49struct treap_defaults
50 : bstree_defaults
51{
52 typedef void priority;
53};
54
55/// @endcond
56
57//! The class template treap is an intrusive treap container that
58//! is used to construct intrusive set and multiset containers. The no-throw
59//! guarantee holds only, if the key_compare object and priority_compare object
60//! don't throw.
61//!
62//! The template parameter \c T is the type to be managed by the container.
63//! The user can specify additional options and if no options are provided
64//! default options are used.
65//!
66//! The container supports the following options:
67//! \c base_hook<>/member_hook<>/value_traits<>,
68//! \c constant_time_size<>, \c size_type<>,
69//! \c compare<> and \c priority_compare<>
70#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
71template<class T, class ...Options>
72#else
73template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
74#endif
75class treap_impl
76 /// @cond
77 : public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>
78 //Use public inheritance to avoid MSVC bugs with closures
79 , public detail::ebo_functor_holder
80 < typename get_prio
81 < VoidOrPrioComp
82 , typename bstree_impl
83 <ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, BsTreeAlgorithms, HeaderHolder>::value_type>::type
84 >
85 /// @endcond
86{
87 public:
88 typedef ValueTraits value_traits;
89 /// @cond
90 typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
91 , ConstantTimeSize, BsTreeAlgorithms
92 , HeaderHolder> tree_type;
93 typedef tree_type implementation_defined;
94 typedef get_prio
95 < VoidOrPrioComp
96 , typename tree_type::value_type> get_prio_type;
97
98 typedef detail::ebo_functor_holder
99 <typename get_prio_type::type> prio_base;
100
101 /// @endcond
102
103 typedef typename implementation_defined::pointer pointer;
104 typedef typename implementation_defined::const_pointer const_pointer;
105 typedef typename implementation_defined::value_type value_type;
106 typedef typename implementation_defined::key_type key_type;
107 typedef typename implementation_defined::key_of_value key_of_value;
108 typedef typename implementation_defined::reference reference;
109 typedef typename implementation_defined::const_reference const_reference;
110 typedef typename implementation_defined::difference_type difference_type;
111 typedef typename implementation_defined::size_type size_type;
112 typedef typename implementation_defined::value_compare value_compare;
113 typedef typename implementation_defined::key_compare key_compare;
114 typedef typename implementation_defined::iterator iterator;
115 typedef typename implementation_defined::const_iterator const_iterator;
116 typedef typename implementation_defined::reverse_iterator reverse_iterator;
117 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
118 typedef typename implementation_defined::node_traits node_traits;
119 typedef typename implementation_defined::node node;
120 typedef typename implementation_defined::node_ptr node_ptr;
121 typedef typename implementation_defined::const_node_ptr const_node_ptr;
122 typedef BOOST_INTRUSIVE_IMPDEF(treap_algorithms<node_traits>) node_algorithms;
123 typedef BOOST_INTRUSIVE_IMPDEF(typename get_prio_type::type) priority_compare;
124
125 static const bool constant_time_size = implementation_defined::constant_time_size;
126 static const bool stateful_value_traits = implementation_defined::stateful_value_traits;
127 static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
128
129 typedef detail::key_nodeptr_comp<priority_compare, value_traits> value_node_prio_comp_t;
130
131 template<class KeyPrioComp>
132 detail::key_nodeptr_comp<KeyPrioComp, value_traits> key_node_prio_comp(KeyPrioComp keypriocomp) const
133 { return detail::key_nodeptr_comp<KeyPrioComp, value_traits>(keypriocomp, &this->get_value_traits()); }
134
135 value_node_prio_comp_t value_node_prio_comp() const
136 { return this->key_node_prio_comp(this->priv_pcomp()); }
137
138 /// @cond
139 private:
140
141 //noncopyable
142 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_impl)
143
144 const priority_compare &priv_pcomp() const
145 { return static_cast<const prio_base&>(*this).get(); }
146
147 priority_compare &priv_pcomp()
148 { return static_cast<prio_base&>(*this).get(); }
149
150 /// @endcond
151
152 public:
153 typedef typename node_algorithms::insert_commit_data insert_commit_data;
154
155 //! <b>Effects</b>: Constructs an empty container.
156 //!
157 //! <b>Complexity</b>: Constant.
158 //!
159 //! <b>Throws</b>: If value_traits::node_traits::node
160 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
161 //! or the copy constructor of the value_compare/priority_compare objects throw. Basic guarantee.
162 explicit treap_impl( const key_compare &cmp = key_compare()
163 , const priority_compare &pcmp = priority_compare()
164 , const value_traits &v_traits = value_traits())
165 : tree_type(cmp, v_traits), prio_base(pcmp)
166 {}
167
168 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
169 //! cmp must be a comparison function that induces a strict weak ordering.
170 //!
171 //! <b>Effects</b>: Constructs an empty container and inserts elements from
172 //! [b, e).
173 //!
174 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
175 //! comp and otherwise N * log N, where N is the distance between first and last.
176 //!
177 //! <b>Throws</b>: If value_traits::node_traits::node
178 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
179 //! or the copy constructor/operator() of the key_compare/priority_compare objects
180 //! throw. Basic guarantee.
181 template<class Iterator>
182 treap_impl( bool unique, Iterator b, Iterator e
183 , const key_compare &cmp = key_compare()
184 , const priority_compare &pcmp = priority_compare()
185 , const value_traits &v_traits = value_traits())
186 : tree_type(cmp, v_traits), prio_base(pcmp)
187 {
188 if(unique)
189 this->insert_unique(b, e);
190 else
191 this->insert_equal(b, e);
192 }
193
194 //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
195 treap_impl(BOOST_RV_REF(treap_impl) x)
196 : tree_type(BOOST_MOVE_BASE(tree_type, x))
197 , prio_base(::boost::move(x.priv_pcomp()))
198 {}
199
200 //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
201 treap_impl& operator=(BOOST_RV_REF(treap_impl) x)
202 { this->swap(x); return *this; }
203
204 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
205 //! @copydoc ::boost::intrusive::bstree::~bstree()
206 ~treap_impl();
207
208 //! @copydoc ::boost::intrusive::bstree::begin()
209 iterator begin();
210
211 //! @copydoc ::boost::intrusive::bstree::begin()const
212 const_iterator begin() const;
213
214 //! @copydoc ::boost::intrusive::bstree::cbegin()const
215 const_iterator cbegin() const;
216
217 //! @copydoc ::boost::intrusive::bstree::end()
218 iterator end();
219
220 //! @copydoc ::boost::intrusive::bstree::end()const
221 const_iterator end() const;
222
223 //! @copydoc ::boost::intrusive::bstree::cend()const
224 const_iterator cend() const;
225 #endif
226
227 //! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the treap.
228 //!
229 //! <b>Complexity</b>: Constant.
230 //!
231 //! <b>Throws</b>: Nothing.
232 iterator top()
233 { return this->tree_type::root(); }
234
235 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap..
236 //!
237 //! <b>Complexity</b>: Constant.
238 //!
239 //! <b>Throws</b>: Nothing.
240 const_iterator top() const
241 { return this->ctop(); }
242
243 //! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the treap..
244 //!
245 //! <b>Complexity</b>: Constant.
246 //!
247 //! <b>Throws</b>: Nothing.
248 const_iterator ctop() const
249 { return this->tree_type::root(); }
250
251 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
252 //! @copydoc ::boost::intrusive::bstree::rbegin()
253 reverse_iterator rbegin();
254
255 //! @copydoc ::boost::intrusive::bstree::rbegin()const
256 const_reverse_iterator rbegin() const;
257
258 //! @copydoc ::boost::intrusive::bstree::crbegin()const
259 const_reverse_iterator crbegin() const;
260
261 //! @copydoc ::boost::intrusive::bstree::rend()
262 reverse_iterator rend();
263
264 //! @copydoc ::boost::intrusive::bstree::rend()const
265 const_reverse_iterator rend() const;
266
267 //! @copydoc ::boost::intrusive::bstree::crend()const
268 const_reverse_iterator crend() const;
269 #endif
270
271 //! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the
272 //! reversed treap.
273 //!
274 //! <b>Complexity</b>: Constant.
275 //!
276 //! <b>Throws</b>: Nothing.
277 reverse_iterator rtop()
278 { return reverse_iterator(this->top()); }
279
280 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec
281 //! of the reversed treap.
282 //!
283 //! <b>Complexity</b>: Constant.
284 //!
285 //! <b>Throws</b>: Nothing.
286 const_reverse_iterator rtop() const
287 { return const_reverse_iterator(this->top()); }
288
289 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object
290 //! of the reversed treap.
291 //!
292 //! <b>Complexity</b>: Constant.
293 //!
294 //! <b>Throws</b>: Nothing.
295 const_reverse_iterator crtop() const
296 { return const_reverse_iterator(this->top()); }
297
298 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
299 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
300 static treap_impl &container_from_end_iterator(iterator end_iterator);
301
302 //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
303 static const treap_impl &container_from_end_iterator(const_iterator end_iterator);
304
305 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
306 static treap_impl &container_from_iterator(iterator it);
307
308 //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
309 static const treap_impl &container_from_iterator(const_iterator it);
310
311 //! @copydoc ::boost::intrusive::bstree::key_comp()const
312 key_compare key_comp() const;
313
314 //! @copydoc ::boost::intrusive::bstree::value_comp()const
315 value_compare value_comp() const;
316
317 //! @copydoc ::boost::intrusive::bstree::empty()const
318 bool empty() const;
319
320 //! @copydoc ::boost::intrusive::bstree::size()const
321 size_type size() const;
322 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
323
324 //! <b>Effects</b>: Returns the priority_compare object used by the container.
325 //!
326 //! <b>Complexity</b>: Constant.
327 //!
328 //! <b>Throws</b>: If priority_compare copy-constructor throws.
329 priority_compare priority_comp() const
330 { return this->priv_pcomp(); }
331
332 //! <b>Effects</b>: Swaps the contents of two treaps.
333 //!
334 //! <b>Complexity</b>: Constant.
335 //!
336 //! <b>Throws</b>: If the comparison functor's swap call throws.
337 void swap(treap_impl& other)
338 {
339 tree_type::swap(other);
340 //This can throw
341 ::boost::adl_move_swap(this->priv_pcomp(), other.priv_pcomp());
342 }
343
344 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
345 //! Cloner should yield to nodes equivalent to the original nodes.
346 //!
347 //! <b>Effects</b>: Erases all the elements from *this
348 //! calling Disposer::operator()(pointer), clones all the
349 //! elements from src calling Cloner::operator()(const_reference )
350 //! and inserts them on *this. Copies the predicate from the source container.
351 //!
352 //! If cloner throws, all cloned elements are unlinked and disposed
353 //! calling Disposer::operator()(pointer).
354 //!
355 //! <b>Complexity</b>: Linear to erased plus inserted elements.
356 //!
357 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
358 template <class Cloner, class Disposer>
359 void clone_from(const treap_impl &src, Cloner cloner, Disposer disposer)
360 {
361 tree_type::clone_from(src, cloner, disposer);
362 this->priv_pcomp() = src.priv_pcomp();
363 }
364
365 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
366 //! Cloner should yield to nodes equivalent to the original nodes.
367 //!
368 //! <b>Effects</b>: Erases all the elements from *this
369 //! calling Disposer::operator()(pointer), clones all the
370 //! elements from src calling Cloner::operator()(reference)
371 //! and inserts them on *this. Copies the predicate from the source container.
372 //!
373 //! If cloner throws, all cloned elements are unlinked and disposed
374 //! calling Disposer::operator()(pointer).
375 //!
376 //! <b>Complexity</b>: Linear to erased plus inserted elements.
377 //!
378 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
379 template <class Cloner, class Disposer>
380 void clone_from(BOOST_RV_REF(treap_impl) src, Cloner cloner, Disposer disposer)
381 {
382 tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);
383 this->priv_pcomp() = ::boost::move(src.priv_pcomp());
384 }
385
386 //! <b>Requires</b>: value must be an lvalue
387 //!
388 //! <b>Effects</b>: Inserts value into the container before the upper bound.
389 //!
390 //! <b>Complexity</b>: Average complexity for insert element is at
391 //! most logarithmic.
392 //!
393 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee.
394 //!
395 //! <b>Note</b>: Does not affect the validity of iterators and references.
396 //! No copy-constructors are called.
397 iterator insert_equal(reference value)
398 {
399 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
400 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
401 iterator ret
402 ( node_algorithms::insert_equal_upper_bound
403 ( this->tree_type::header_ptr()
404 , to_insert
405 , this->key_node_comp(this->key_comp())
406 , this->value_node_prio_comp())
407 , this->priv_value_traits_ptr());
408 this->tree_type::sz_traits().increment();
409 return ret;
410 }
411
412 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
413 //! a valid iterator.
414 //!
415 //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to
416 //! where it will be inserted. If "hint" is the upper_bound
417 //! the insertion takes constant time (two comparisons in the worst case)
418 //!
419 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
420 //! constant time if t is inserted immediately before hint.
421 //!
422 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw. Strong guarantee.
423 //!
424 //! <b>Note</b>: Does not affect the validity of iterators and references.
425 //! No copy-constructors are called.
426 iterator insert_equal(const_iterator hint, reference value)
427 {
428 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
429 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
430 iterator ret
431 (node_algorithms::insert_equal
432 ( this->tree_type::header_ptr()
433 , hint.pointed_node()
434 , to_insert
435 , this->key_node_comp(this->key_comp())
436 , this->value_node_prio_comp())
437 , this->priv_value_traits_ptr());
438 this->tree_type::sz_traits().increment();
439 return ret;
440 }
441
442 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
443 //! of type value_type.
444 //!
445 //! <b>Effects</b>: Inserts a each element of a range into the container
446 //! before the upper bound of the key of each element.
447 //!
448 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
449 //! size of the range. However, it is linear in N if the range is already sorted
450 //! by key_comp().
451 //!
452 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
453 //! Strong guarantee.
454 //!
455 //! <b>Note</b>: Does not affect the validity of iterators and references.
456 //! No copy-constructors are called.
457 template<class Iterator>
458 void insert_equal(Iterator b, Iterator e)
459 {
460 iterator iend(this->end());
461 for (; b != e; ++b)
462 this->insert_equal(iend, *b);
463 }
464
465 //! <b>Requires</b>: value must be an lvalue
466 //!
467 //! <b>Effects</b>: Inserts value into the container if the value
468 //! is not already present.
469 //!
470 //! <b>Complexity</b>: Average complexity for insert element is at
471 //! most logarithmic.
472 //!
473 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
474 //! Strong guarantee.
475 //!
476 //! <b>Note</b>: Does not affect the validity of iterators and references.
477 //! No copy-constructors are called.
478 std::pair<iterator, bool> insert_unique(reference value)
479 {
480 insert_commit_data commit_data;
481 std::pair<iterator, bool> ret = this->insert_unique_check
482 (value, this->comp(), this->priv_pcomp(), commit_data);
483 if(!ret.second)
484 return ret;
485 return std::pair<iterator, bool> (this->insert_unique_commit(value, commit_data), true);
486 }
487
488 //! <b>Requires</b>: value must be an lvalue, and "hint" must be
489 //! a valid iterator
490 //!
491 //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint
492 //! to where it will be inserted.
493 //!
494 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
495 //! constant time (two comparisons in the worst case)
496 //! if t is inserted immediately before hint.
497 //!
498 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
499 //! Strong guarantee.
500 //!
501 //! <b>Note</b>: Does not affect the validity of iterators and references.
502 //! No copy-constructors are called.
503 iterator insert_unique(const_iterator hint, reference value)
504 {
505 insert_commit_data commit_data;
506 std::pair<iterator, bool> ret = this->insert_unique_check
507 (hint, value, this->comp(), this->priv_pcomp(), commit_data);
508 if(!ret.second)
509 return ret.first;
510 return this->insert_unique_commit(value, commit_data);
511 }
512
513 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
514 //! of type value_type.
515 //!
516 //! <b>Effects</b>: Tries to insert each element of a range into the container.
517 //!
518 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
519 //! size of the range. However, it is linear in N if the range is already sorted
520 //! by key_comp().
521 //!
522 //! <b>Throws</b>: If the internal key_compare or priority_compare functions throw.
523 //! Strong guarantee.
524 //!
525 //! <b>Note</b>: Does not affect the validity of iterators and references.
526 //! No copy-constructors are called.
527 template<class Iterator>
528 void insert_unique(Iterator b, Iterator e)
529 {
530 if(this->empty()){
531 iterator iend(this->end());
532 for (; b != e; ++b)
533 this->insert_unique(iend, *b);
534 }
535 else{
536 for (; b != e; ++b)
537 this->insert_unique(*b);
538 }
539 }
540
541 //! <b>Requires</b>: comp must be a comparison function that induces
542 //! the same strict weak ordering as key_compare.
543 //! key_value_pcomp must be a comparison function that induces
544 //! the same strict weak ordering as priority_compare. The difference is that
545 //! key_value_pcomp and comp compare an arbitrary key with the contained values.
546 //!
547 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
548 //! a user provided key instead of the value itself.
549 //!
550 //! <b>Returns</b>: If there is an equivalent value
551 //! returns a pair containing an iterator to the already present value
552 //! and false. If the value can be inserted returns true in the returned
553 //! pair boolean and fills "commit_data" that is meant to be used with
554 //! the "insert_commit" function.
555 //!
556 //! <b>Complexity</b>: Average complexity is at most logarithmic.
557 //!
558 //! <b>Throws</b>: If the comp or key_value_pcomp
559 //! ordering functions throw. Strong guarantee.
560 //!
561 //! <b>Notes</b>: This function is used to improve performance when constructing
562 //! a value_type is expensive: if there is an equivalent value
563 //! the constructed object must be discarded. Many times, the part of the
564 //! node that is used to impose the order is much cheaper to construct
565 //! than the value_type and this function offers the possibility to use that
566 //! part to check if the insertion will be successful.
567 //!
568 //! If the check is successful, the user can construct the value_type and use
569 //! "insert_commit" to insert the object in constant-time. This gives a total
570 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
571 //!
572 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
573 //! objects are inserted or erased from the container.
574 template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
575 std::pair<iterator, bool> insert_unique_check
576 ( const KeyType &key, KeyTypeKeyCompare comp
577 , KeyValuePrioCompare key_value_pcomp, insert_commit_data &commit_data)
578 {
579 std::pair<node_ptr, bool> const ret =
580 (node_algorithms::insert_unique_check
581 ( this->tree_type::header_ptr(), key
582 , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data));
583 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
584 }
585
586 //! <b>Requires</b>: comp must be a comparison function that induces
587 //! the same strict weak ordering as key_compare.
588 //! key_value_pcomp must be a comparison function that induces
589 //! the same strict weak ordering as priority_compare. The difference is that
590 //! key_value_pcomp and comp compare an arbitrary key with the contained values.
591 //!
592 //! <b>Effects</b>: Checks if a value can be inserted in the container, using
593 //! a user provided key instead of the value itself, using "hint"
594 //! as a hint to where it will be inserted.
595 //!
596 //! <b>Returns</b>: If there is an equivalent value
597 //! returns a pair containing an iterator to the already present value
598 //! and false. If the value can be inserted returns true in the returned
599 //! pair boolean and fills "commit_data" that is meant to be used with
600 //! the "insert_commit" function.
601 //!
602 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
603 //! constant time if t is inserted immediately before hint.
604 //!
605 //! <b>Throws</b>: If the comp or key_value_pcomp
606 //! ordering functions throw. Strong guarantee.
607 //!
608 //! <b>Notes</b>: This function is used to improve performance when constructing
609 //! a value_type is expensive: if there is an equivalent value
610 //! the constructed object must be discarded. Many times, the part of the
611 //! constructing that is used to impose the order is much cheaper to construct
612 //! than the value_type and this function offers the possibility to use that key
613 //! to check if the insertion will be successful.
614 //!
615 //! If the check is successful, the user can construct the value_type and use
616 //! "insert_commit" to insert the object in constant-time. This can give a total
617 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
618 //!
619 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
620 //! objects are inserted or erased from the container.
621 template<class KeyType, class KeyTypeKeyCompare, class KeyValuePrioCompare>
622 std::pair<iterator, bool> insert_unique_check
623 ( const_iterator hint, const KeyType &key
624 , KeyTypeKeyCompare comp
625 , KeyValuePrioCompare key_value_pcomp
626 , insert_commit_data &commit_data)
627 {
628 std::pair<node_ptr, bool> const ret =
629 (node_algorithms::insert_unique_check
630 ( this->tree_type::header_ptr(), hint.pointed_node(), key
631 , this->key_node_comp(comp), this->key_node_prio_comp(key_value_pcomp), commit_data));
632 return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second);
633 }
634
635 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
636 //! must have been obtained from a previous call to "insert_check".
637 //! No objects should have been inserted or erased from the container between
638 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
639 //!
640 //! <b>Effects</b>: Inserts the value in the avl_set using the information obtained
641 //! from the "commit_data" that a previous "insert_check" filled.
642 //!
643 //! <b>Returns</b>: An iterator to the newly inserted object.
644 //!
645 //! <b>Complexity</b>: Constant time.
646 //!
647 //! <b>Throws</b>: Nothing
648 //!
649 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
650 //! previously executed to fill "commit_data". No value should be inserted or
651 //! erased between the "insert_check" and "insert_commit" calls.
652 iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
653 {
654 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
655 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
656 node_algorithms::insert_unique_commit(this->tree_type::header_ptr(), to_insert, commit_data);
657 this->tree_type::sz_traits().increment();
658 return iterator(to_insert, this->priv_value_traits_ptr());
659 }
660
661 //! <b>Requires</b>: value must be an lvalue, "pos" must be
662 //! a valid iterator (or end) and must be the succesor of value
663 //! once inserted according to the predicate
664 //!
665 //! <b>Effects</b>: Inserts x into the container before "pos".
666 //!
667 //! <b>Complexity</b>: Constant time.
668 //!
669 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
670 //!
671 //! <b>Note</b>: This function does not check preconditions so if "pos" is not
672 //! the successor of "value" container ordering invariant will be broken.
673 //! This is a low-level function to be used only for performance reasons
674 //! by advanced users.
675 iterator insert_before(const_iterator pos, reference value)
676 {
677 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
678 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
679 iterator ret
680 ( node_algorithms::insert_before
681 ( this->tree_type::header_ptr(), pos.pointed_node(), to_insert, this->value_node_prio_comp())
682 , this->priv_value_traits_ptr());
683 this->tree_type::sz_traits().increment();
684 return ret;
685 }
686
687 //! <b>Requires</b>: value must be an lvalue, and it must be no less
688 //! than the greatest inserted key
689 //!
690 //! <b>Effects</b>: Inserts x into the container in the last position.
691 //!
692 //! <b>Complexity</b>: Constant time.
693 //!
694 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
695 //!
696 //! <b>Note</b>: This function does not check preconditions so if value is
697 //! less than the greatest inserted key container ordering invariant will be broken.
698 //! This function is slightly more efficient than using "insert_before".
699 //! This is a low-level function to be used only for performance reasons
700 //! by advanced users.
701 void push_back(reference value)
702 {
703 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
704 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
705 node_algorithms::push_back(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp());
706 this->tree_type::sz_traits().increment();
707 }
708
709 //! <b>Requires</b>: value must be an lvalue, and it must be no greater
710 //! than the minimum inserted key
711 //!
712 //! <b>Effects</b>: Inserts x into the container in the first position.
713 //!
714 //! <b>Complexity</b>: Constant time.
715 //!
716 //! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
717 //!
718 //! <b>Note</b>: This function does not check preconditions so if value is
719 //! greater than the minimum inserted key container ordering invariant will be broken.
720 //! This function is slightly more efficient than using "insert_before".
721 //! This is a low-level function to be used only for performance reasons
722 //! by advanced users.
723 void push_front(reference value)
724 {
725 node_ptr to_insert(this->get_value_traits().to_node_ptr(value));
726 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert));
727 node_algorithms::push_front(this->tree_type::header_ptr(), to_insert, this->value_node_prio_comp());
728 this->tree_type::sz_traits().increment();
729 }
730
731 //! <b>Effects</b>: Erases the element pointed to by i.
732 //!
733 //! <b>Complexity</b>: Average complexity for erase element is constant time.
734 //!
735 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
736 //!
737 //! <b>Note</b>: Invalidates the iterators (but not the references)
738 //! to the erased elements. No destructors are called.
739 iterator erase(const_iterator i)
740 {
741 const_iterator ret(i);
742 ++ret;
743 node_ptr to_erase(i.pointed_node());
744 BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase));
745 node_algorithms::erase(this->tree_type::header_ptr(), to_erase, this->value_node_prio_comp());
746 this->tree_type::sz_traits().decrement();
747 if(safemode_or_autounlink)
748 node_algorithms::init(to_erase);
749 return ret.unconst();
750 }
751
752 //! <b>Effects</b>: Erases the range pointed to by b end e.
753 //!
754 //! <b>Complexity</b>: Average complexity for erase range is at most
755 //! O(log(size() + N)), where N is the number of elements in the range.
756 //!
757 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
758 //!
759 //! <b>Note</b>: Invalidates the iterators (but not the references)
760 //! to the erased elements. No destructors are called.
761 iterator erase(const_iterator b, const_iterator e)
762 { size_type n; return private_erase(b, e, n); }
763
764 //! <b>Effects</b>: Erases all the elements with the given value.
765 //!
766 //! <b>Returns</b>: The number of erased elements.
767 //!
768 //! <b>Complexity</b>: O(log(size() + N).
769 //!
770 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
771 //!
772 //! <b>Note</b>: Invalidates the iterators (but not the references)
773 //! to the erased elements. No destructors are called.
774 size_type erase(const key_type &key)
775 { return this->erase(key, this->key_comp()); }
776
777 //! <b>Effects</b>: Erases all the elements with the given key.
778 //! according to the comparison functor "comp".
779 //!
780 //! <b>Returns</b>: The number of erased elements.
781 //!
782 //! <b>Complexity</b>: O(log(size() + N).
783 //!
784 //! <b>Throws</b>: if the internal priority_compare function throws.
785 //! Equivalent guarantee to <i>while(beg != end) erase(beg++);</i>
786 //!
787 //! <b>Note</b>: Invalidates the iterators (but not the references)
788 //! to the erased elements. No destructors are called.
789 template<class KeyType, class KeyTypeKeyCompare>
790 BOOST_INTRUSIVE_DOC1ST(size_type
791 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
792 erase(const KeyType& key, KeyTypeKeyCompare comp)
793 {
794 std::pair<iterator,iterator> p = this->equal_range(key, comp);
795 size_type n;
796 private_erase(p.first, p.second, n);
797 return n;
798 }
799
800 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
801 //!
802 //! <b>Effects</b>: Erases the element pointed to by i.
803 //! Disposer::operator()(pointer) is called for the removed element.
804 //!
805 //! <b>Complexity</b>: Average complexity for erase element is constant time.
806 //!
807 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
808 //!
809 //! <b>Note</b>: Invalidates the iterators
810 //! to the erased elements.
811 template<class Disposer>
812 iterator erase_and_dispose(const_iterator i, Disposer disposer)
813 {
814 node_ptr to_erase(i.pointed_node());
815 iterator ret(this->erase(i));
816 disposer(this->get_value_traits().to_value_ptr(to_erase));
817 return ret;
818 }
819
820 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
821 template<class Disposer>
822 iterator erase_and_dispose(iterator i, Disposer disposer)
823 { return this->erase_and_dispose(const_iterator(i), disposer); }
824 #endif
825
826 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
827 //!
828 //! <b>Effects</b>: Erases the range pointed to by b end e.
829 //! Disposer::operator()(pointer) is called for the removed elements.
830 //!
831 //! <b>Complexity</b>: Average complexity for erase range is at most
832 //! O(log(size() + N)), where N is the number of elements in the range.
833 //!
834 //! <b>Throws</b>: if the internal priority_compare function throws. Strong guarantee.
835 //!
836 //! <b>Note</b>: Invalidates the iterators
837 //! to the erased elements.
838 template<class Disposer>
839 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
840 { size_type n; return private_erase(b, e, n, disposer); }
841
842 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
843 //!
844 //! <b>Effects</b>: Erases all the elements with the given value.
845 //! Disposer::operator()(pointer) is called for the removed elements.
846 //!
847 //! <b>Returns</b>: The number of erased elements.
848 //!
849 //! <b>Complexity</b>: O(log(size() + N).
850 //!
851 //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken.
852 //! The safest thing would be to clear or destroy the container.
853 //!
854 //! <b>Note</b>: Invalidates the iterators (but not the references)
855 //! to the erased elements. No destructors are called.
856 template<class Disposer>
857 size_type erase_and_dispose(const key_type &key, Disposer disposer)
858 {
859 std::pair<iterator,iterator> p = this->equal_range(key);
860 size_type n;
861 private_erase(p.first, p.second, n, disposer);
862 return n;
863 }
864
865 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
866 //!
867 //! <b>Effects</b>: Erases all the elements with the given key.
868 //! according to the comparison functor "comp".
869 //! Disposer::operator()(pointer) is called for the removed elements.
870 //!
871 //! <b>Returns</b>: The number of erased elements.
872 //!
873 //! <b>Complexity</b>: O(log(size() + N).
874 //!
875 //! <b>Throws</b>: if the priority_compare function throws then weak guarantee and heap invariants are broken.
876 //! The safest thing would be to clear or destroy the container.
877 //!
878 //! <b>Note</b>: Invalidates the iterators
879 //! to the erased elements.
880 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
881 BOOST_INTRUSIVE_DOC1ST(size_type
882 , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type)
883 erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer)
884 {
885 std::pair<iterator,iterator> p = this->equal_range(key, comp);
886 size_type n;
887 private_erase(p.first, p.second, n, disposer);
888 return n;
889 }
890
891 //! <b>Effects</b>: Erases all of the elements.
892 //!
893 //! <b>Complexity</b>: Linear to the number of elements on the container.
894 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
895 //!
896 //! <b>Throws</b>: Nothing.
897 //!
898 //! <b>Note</b>: Invalidates the iterators (but not the references)
899 //! to the erased elements. No destructors are called.
900 void clear()
901 { tree_type::clear(); }
902
903 //! <b>Effects</b>: Erases all of the elements calling disposer(p) for
904 //! each node to be erased.
905 //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)),
906 //! where N is the number of elements in the container.
907 //!
908 //! <b>Throws</b>: Nothing.
909 //!
910 //! <b>Note</b>: Invalidates the iterators (but not the references)
911 //! to the erased elements. Calls N times to disposer functor.
912 template<class Disposer>
913 void clear_and_dispose(Disposer disposer)
914 {
915 node_algorithms::clear_and_dispose(this->tree_type::header_ptr()
916 , detail::node_disposer<Disposer, value_traits, TreapAlgorithms>(disposer, &this->get_value_traits()));
917 node_algorithms::init_header(this->tree_type::header_ptr());
918 this->tree_type::sz_traits().set_size(0);
919 }
920
921 //! @copydoc ::boost::intrusive::bstree::check(ExtraChecker)const
922 template <class ExtraChecker>
923 void check(ExtraChecker extra_checker) const
924 {
925 tree_type::check(detail::treap_node_extra_checker
926 <ValueTraits, value_node_prio_comp_t, ExtraChecker>(this->value_node_prio_comp(), extra_checker));
927 }
928
929 //! @copydoc ::boost::intrusive::bstree::check()const
930 void check() const
931 { check(detail::empty_node_checker<ValueTraits>()); }
932
933 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
934 //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
935 size_type count(const key_type &key) const;
936
937 //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
938 template<class KeyType, class KeyTypeKeyCompare>
939 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
940
941 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
942 iterator lower_bound(const key_type &key);
943
944 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
945 template<class KeyType, class KeyTypeKeyCompare>
946 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
947
948 //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
949 const_iterator lower_bound(const key_type &key) const;
950
951 //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
952 template<class KeyType, class KeyTypeKeyCompare>
953 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
954
955 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
956 iterator upper_bound(const key_type &key);
957
958 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
959 template<class KeyType, class KeyTypeKeyCompare>
960 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
961
962 //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
963 const_iterator upper_bound(const key_type &key) const;
964
965 //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
966 template<class KeyType, class KeyTypeKeyCompare>
967 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
968
969 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
970 iterator find(const key_type &key);
971
972 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
973 template<class KeyType, class KeyTypeKeyCompare>
974 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
975
976 //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
977 const_iterator find(const key_type &key) const;
978
979 //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
980 template<class KeyType, class KeyTypeKeyCompare>
981 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
982
983 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
984 std::pair<iterator,iterator> equal_range(const key_type &key);
985
986 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
987 template<class KeyType, class KeyTypeKeyCompare>
988 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
989
990 //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
991 std::pair<const_iterator, const_iterator>
992 equal_range(const key_type &key) const;
993
994 //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
995 template<class KeyType, class KeyTypeKeyCompare>
996 std::pair<const_iterator, const_iterator>
997 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
998
999 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
1000 std::pair<iterator,iterator> bounded_range
1001 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
1002
1003 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
1004 template<class KeyType, class KeyTypeKeyCompare>
1005 std::pair<iterator,iterator> bounded_range
1006 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
1007
1008 //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
1009 std::pair<const_iterator, const_iterator>
1010 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
1011
1012 //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
1013 template<class KeyType, class KeyTypeKeyCompare>
1014 std::pair<const_iterator, const_iterator> bounded_range
1015 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
1016
1017 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
1018 static iterator s_iterator_to(reference value);
1019
1020 //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
1021 static const_iterator s_iterator_to(const_reference value);
1022
1023 //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
1024 iterator iterator_to(reference value);
1025
1026 //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
1027 const_iterator iterator_to(const_reference value) const;
1028
1029 //! @copydoc ::boost::intrusive::bstree::init_node(reference)
1030 static void init_node(reference value);
1031
1032 //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
1033 pointer unlink_leftmost_without_rebalance();
1034
1035 //! @copydoc ::boost::intrusive::bstree::replace_node
1036 void replace_node(iterator replace_this, reference with_this);
1037
1038 //! @copydoc ::boost::intrusive::bstree::remove_node
1039 void remove_node(reference value);
1040
1041 friend bool operator< (const treap_impl &x, const treap_impl &y);
1042
1043 friend bool operator==(const treap_impl &x, const treap_impl &y);
1044
1045 friend bool operator!= (const treap_impl &x, const treap_impl &y);
1046
1047 friend bool operator>(const treap_impl &x, const treap_impl &y);
1048
1049 friend bool operator<=(const treap_impl &x, const treap_impl &y);
1050
1051 friend bool operator>=(const treap_impl &x, const treap_impl &y);
1052
1053 friend void swap(treap_impl &x, treap_impl &y);
1054
1055 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1056
1057 /// @cond
1058 private:
1059 template<class Disposer>
1060 iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer)
1061 {
1062 for(n = 0; b != e; ++n)
1063 this->erase_and_dispose(b++, disposer);
1064 return b.unconst();
1065 }
1066
1067 iterator private_erase(const_iterator b, const_iterator e, size_type &n)
1068 {
1069 for(n = 0; b != e; ++n)
1070 this->erase(b++);
1071 return b.unconst();
1072 }
1073 /// @endcond
1074};
1075
1076
1077//! Helper metafunction to define a \c treap that yields to the same type when the
1078//! same options (either explicitly or implicitly) are used.
1079#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1080template<class T, class ...Options>
1081#else
1082template<class T, class O1 = void, class O2 = void
1083 , class O3 = void, class O4 = void
1084 , class O5 = void, class O6 = void>
1085#endif
1086struct make_treap
1087{
1088 typedef typename pack_options
1089 < treap_defaults,
1090 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1091 O1, O2, O3, O4, O5, O6
1092 #else
1093 Options...
1094 #endif
1095 >::type packed_options;
1096
1097 typedef typename detail::get_value_traits
1098 <T, typename packed_options::proto_value_traits>::type value_traits;
1099
1100 typedef treap_impl
1101 < value_traits
1102 , typename packed_options::key_of_value
1103 , typename packed_options::compare
1104 , typename packed_options::priority
1105 , typename packed_options::size_type
1106 , packed_options::constant_time_size
1107 , typename packed_options::header_holder_type
1108 > implementation_defined;
1109 /// @endcond
1110 typedef implementation_defined type;
1111};
1112
1113#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1114
1115#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1116template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
1117#else
1118template<class T, class ...Options>
1119#endif
1120class treap
1121 : public make_treap<T,
1122 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1123 O1, O2, O3, O4, O5, O6
1124 #else
1125 Options...
1126 #endif
1127 >::type
1128{
1129 typedef typename make_treap
1130 <T,
1131 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1132 O1, O2, O3, O4, O5, O6
1133 #else
1134 Options...
1135 #endif
1136 >::type Base;
1137 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap)
1138
1139 public:
1140 typedef typename Base::key_compare key_compare;
1141 typedef typename Base::priority_compare priority_compare;
1142 typedef typename Base::value_traits value_traits;
1143 typedef typename Base::iterator iterator;
1144 typedef typename Base::const_iterator const_iterator;
1145 typedef typename Base::reverse_iterator reverse_iterator;
1146 typedef typename Base::const_reverse_iterator const_reverse_iterator;
1147
1148 //Assert if passed value traits are compatible with the type
1149 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1150
1151 explicit treap( const key_compare &cmp = key_compare()
1152 , const priority_compare &pcmp = priority_compare()
1153 , const value_traits &v_traits = value_traits())
1154 : Base(cmp, pcmp, v_traits)
1155 {}
1156
1157 template<class Iterator>
1158 treap( bool unique, Iterator b, Iterator e
1159 , const key_compare &cmp = key_compare()
1160 , const priority_compare &pcmp = priority_compare()
1161 , const value_traits &v_traits = value_traits())
1162 : Base(unique, b, e, cmp, pcmp, v_traits)
1163 {}
1164
1165 treap(BOOST_RV_REF(treap) x)
1166 : Base(BOOST_MOVE_BASE(Base, x))
1167 {}
1168
1169 treap& operator=(BOOST_RV_REF(treap) x)
1170 { return static_cast<treap&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
1171
1172 template <class Cloner, class Disposer>
1173 void clone_from(const treap &src, Cloner cloner, Disposer disposer)
1174 { Base::clone_from(src, cloner, disposer); }
1175
1176 template <class Cloner, class Disposer>
1177 void clone_from(BOOST_RV_REF(treap) src, Cloner cloner, Disposer disposer)
1178 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
1179
1180 static treap &container_from_end_iterator(iterator end_iterator)
1181 { return static_cast<treap &>(Base::container_from_end_iterator(end_iterator)); }
1182
1183 static const treap &container_from_end_iterator(const_iterator end_iterator)
1184 { return static_cast<const treap &>(Base::container_from_end_iterator(end_iterator)); }
1185
1186 static treap &container_from_iterator(iterator it)
1187 { return static_cast<treap &>(Base::container_from_iterator(it)); }
1188
1189 static const treap &container_from_iterator(const_iterator it)
1190 { return static_cast<const treap &>(Base::container_from_iterator(it)); }
1191};
1192
1193#endif
1194
1195} //namespace intrusive
1196} //namespace boost
1197
1198#include <boost/intrusive/detail/config_end.hpp>
1199
1200#endif //BOOST_INTRUSIVE_TREAP_HPP
1201

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