1
/////////////////////////////////////////////////////////////////////////////
3
// (C) Copyright Ion Gaztanaga 2007-2009
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_TRIE_SET_HPP
13
#define BOOST_INTRUSIVE_TRIE_SET_HPP
15
#include <boost/intrusive/detail/config_begin.hpp>
16
#include <boost/intrusive/intrusive_fwd.hpp>
17
#include <boost/intrusive/treap.hpp>
18
#include <boost/intrusive/detail/mpl.hpp>
19
#include <boost/move/move.hpp>
25
//! The class template treap_set is an intrusive container, that mimics most of
26
//! the interface of std::set as described in the C++ standard.
28
//! The template parameter \c T is the type to be managed by the container.
29
//! The user can specify additional options and if no options are provided
30
//! default options are used.
32
//! The container supports the following options:
33
//! \c base_hook<>/member_hook<>/value_traits<>,
34
//! \c constant_time_size<>, \c size_type<>,
35
//! \c compare<> and \c priority_compare<>
36
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
37
template<class T, class ...Options>
39
template<class Config>
44
typedef treap_impl<Config> tree_type;
47
BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set_impl)
49
typedef tree_type implementation_defined;
53
typedef typename implementation_defined::value_type value_type;
54
typedef typename implementation_defined::value_traits value_traits;
55
typedef typename implementation_defined::pointer pointer;
56
typedef typename implementation_defined::const_pointer const_pointer;
57
typedef typename implementation_defined::reference reference;
58
typedef typename implementation_defined::const_reference const_reference;
59
typedef typename implementation_defined::difference_type difference_type;
60
typedef typename implementation_defined::size_type size_type;
61
typedef typename implementation_defined::value_compare value_compare;
62
typedef typename implementation_defined::priority_compare priority_compare;
63
typedef typename implementation_defined::key_compare key_compare;
64
typedef typename implementation_defined::iterator iterator;
65
typedef typename implementation_defined::const_iterator const_iterator;
66
typedef typename implementation_defined::reverse_iterator reverse_iterator;
67
typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
68
typedef typename implementation_defined::insert_commit_data insert_commit_data;
69
typedef typename implementation_defined::node_traits node_traits;
70
typedef typename implementation_defined::node node;
71
typedef typename implementation_defined::node_ptr node_ptr;
72
typedef typename implementation_defined::const_node_ptr const_node_ptr;
73
typedef typename implementation_defined::node_algorithms node_algorithms;
75
static const bool constant_time_size = Config::constant_time_size;
83
//! <b>Effects</b>: Constructs an empty treap_set.
85
//! <b>Complexity</b>: Constant.
87
//! <b>Throws</b>: If value_traits::node_traits::node
88
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
89
//! or the copy constructor of the value_compare object throws.
90
treap_set_impl( const value_compare &cmp = value_compare()
91
, const priority_compare &pcmp = priority_compare()
92
, const value_traits &v_traits = value_traits())
93
: tree_(cmp, pcmp, v_traits)
96
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
97
//! cmp must be a comparison function that induces a strict weak ordering.
99
//! <b>Effects</b>: Constructs an empty treap_set and inserts elements from
102
//! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
103
//! comp and otherwise N * log N, where N is std::distance(last, first).
105
//! <b>Throws</b>: If value_traits::node_traits::node
106
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
107
//! or the copy constructor/operator() of the value_compare object throws.
108
template<class Iterator>
109
treap_set_impl( Iterator b, Iterator e
110
, const value_compare &cmp = value_compare()
111
, const priority_compare &pcmp = priority_compare()
112
, const value_traits &v_traits = value_traits())
113
: tree_(true, b, e, cmp, pcmp, v_traits)
116
//! <b>Effects</b>: to-do
118
treap_set_impl(BOOST_RV_REF(treap_set_impl) x)
119
: tree_(::boost::move(x.tree_))
122
//! <b>Effects</b>: to-do
124
treap_set_impl& operator=(BOOST_RV_REF(treap_set_impl) x)
125
{ tree_ = ::boost::move(x.tree_); return *this; }
127
//! <b>Effects</b>: Detaches all elements from this. The objects in the treap_set
128
//! are not deleted (i.e. no destructors are called).
130
//! <b>Complexity</b>: Linear to the number of elements on the container.
131
//! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
133
//! <b>Throws</b>: Nothing.
137
//! <b>Effects</b>: Returns an iterator pointing to the beginning of the treap_set.
139
//! <b>Complexity</b>: Constant.
141
//! <b>Throws</b>: Nothing.
143
{ return tree_.begin(); }
145
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the treap_set.
147
//! <b>Complexity</b>: Constant.
149
//! <b>Throws</b>: Nothing.
150
const_iterator begin() const
151
{ return tree_.begin(); }
153
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the treap_set.
155
//! <b>Complexity</b>: Constant.
157
//! <b>Throws</b>: Nothing.
158
const_iterator cbegin() const
159
{ return tree_.cbegin(); }
161
//! <b>Effects</b>: Returns an iterator pointing to the end of the treap_set.
163
//! <b>Complexity</b>: Constant.
165
//! <b>Throws</b>: Nothing.
167
{ return tree_.end(); }
169
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the treap_set.
171
//! <b>Complexity</b>: Constant.
173
//! <b>Throws</b>: Nothing.
174
const_iterator end() const
175
{ return tree_.end(); }
177
//! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the tree.
179
//! <b>Complexity</b>: Constant.
181
//! <b>Throws</b>: Nothing.
183
{ return tree_.top(); }
185
//! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the tree..
187
//! <b>Complexity</b>: Constant.
189
//! <b>Throws</b>: Nothing.
190
const_iterator top() const
191
{ return this->ctop(); }
193
//! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the tree..
195
//! <b>Complexity</b>: Constant.
197
//! <b>Throws</b>: Nothing.
198
const_iterator ctop() const
199
{ return tree_.ctop(); }
201
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the treap_set.
203
//! <b>Complexity</b>: Constant.
205
//! <b>Throws</b>: Nothing.
206
const_iterator cend() const
207
{ return tree_.cend(); }
209
//! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
210
//! reversed treap_set.
212
//! <b>Complexity</b>: Constant.
214
//! <b>Throws</b>: Nothing.
215
reverse_iterator rbegin()
216
{ return tree_.rbegin(); }
218
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
219
//! of the reversed treap_set.
221
//! <b>Complexity</b>: Constant.
223
//! <b>Throws</b>: Nothing.
224
const_reverse_iterator rbegin() const
225
{ return tree_.rbegin(); }
227
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
228
//! of the reversed treap_set.
230
//! <b>Complexity</b>: Constant.
232
//! <b>Throws</b>: Nothing.
233
const_reverse_iterator crbegin() const
234
{ return tree_.crbegin(); }
236
//! <b>Effects</b>: Returns a reverse_iterator pointing to the end
237
//! of the reversed treap_set.
239
//! <b>Complexity</b>: Constant.
241
//! <b>Throws</b>: Nothing.
242
reverse_iterator rend()
243
{ return tree_.rend(); }
245
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
246
//! of the reversed treap_set.
248
//! <b>Complexity</b>: Constant.
250
//! <b>Throws</b>: Nothing.
251
const_reverse_iterator rend() const
252
{ return tree_.rend(); }
254
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
255
//! of the reversed treap_set.
257
//! <b>Complexity</b>: Constant.
259
//! <b>Throws</b>: Nothing.
260
const_reverse_iterator crend() const
261
{ return tree_.crend(); }
263
//! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the
266
//! <b>Complexity</b>: Constant.
268
//! <b>Throws</b>: Nothing.
269
reverse_iterator rtop()
270
{ return tree_.rtop(); }
272
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec
273
//! of the reversed tree.
275
//! <b>Complexity</b>: Constant.
277
//! <b>Throws</b>: Nothing.
278
const_reverse_iterator rtop() const
279
{ return tree_.crtop(); }
281
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object
282
//! of the reversed tree.
284
//! <b>Complexity</b>: Constant.
286
//! <b>Throws</b>: Nothing.
287
const_reverse_iterator crtop() const
288
{ return tree_.crtop(); }
290
//! <b>Precondition</b>: end_iterator must be a valid end iterator
293
//! <b>Effects</b>: Returns a const reference to the treap_set associated to the end iterator
295
//! <b>Throws</b>: Nothing.
297
//! <b>Complexity</b>: Constant.
298
static treap_set_impl &container_from_end_iterator(iterator end_iterator)
300
return *detail::parent_from_member<treap_set_impl, tree_type>
301
( &tree_type::container_from_end_iterator(end_iterator)
302
, &treap_set_impl::tree_);
305
//! <b>Precondition</b>: end_iterator must be a valid end const_iterator
308
//! <b>Effects</b>: Returns a const reference to the treap_set associated to the end iterator
310
//! <b>Throws</b>: Nothing.
312
//! <b>Complexity</b>: Constant.
313
static const treap_set_impl &container_from_end_iterator(const_iterator end_iterator)
315
return *detail::parent_from_member<treap_set_impl, tree_type>
316
( &tree_type::container_from_end_iterator(end_iterator)
317
, &treap_set_impl::tree_);
320
//! <b>Precondition</b>: it must be a valid iterator of set.
322
//! <b>Effects</b>: Returns a reference to the set associated to the iterator
324
//! <b>Throws</b>: Nothing.
326
//! <b>Complexity</b>: Logarithmic.
327
static treap_set_impl &container_from_iterator(iterator it)
329
return *detail::parent_from_member<treap_set_impl, tree_type>
330
( &tree_type::container_from_iterator(it)
331
, &treap_set_impl::tree_);
334
//! <b>Precondition</b>: it must be a valid const_iterator of set.
336
//! <b>Effects</b>: Returns a const reference to the set associated to the iterator
338
//! <b>Throws</b>: Nothing.
340
//! <b>Complexity</b>: Logarithmic.
341
static const treap_set_impl &container_from_iterator(const_iterator it)
343
return *detail::parent_from_member<treap_set_impl, tree_type>
344
( &tree_type::container_from_iterator(it)
345
, &treap_set_impl::tree_);
348
//! <b>Effects</b>: Returns the key_compare object used by the treap_set.
350
//! <b>Complexity</b>: Constant.
352
//! <b>Throws</b>: If key_compare copy-constructor throws.
353
key_compare key_comp() const
354
{ return tree_.value_comp(); }
356
//! <b>Effects</b>: Returns the value_compare object used by the treap_set.
358
//! <b>Complexity</b>: Constant.
360
//! <b>Throws</b>: If value_compare copy-constructor throws.
361
value_compare value_comp() const
362
{ return tree_.value_comp(); }
364
//! <b>Effects</b>: Returns the priority_compare object used by the treap_set.
366
//! <b>Complexity</b>: Constant.
368
//! <b>Throws</b>: If priority_compare copy-constructor throws.
369
priority_compare priority_comp() const
370
{ return tree_.priority_comp(); }
372
//! <b>Effects</b>: Returns true if the container is empty.
374
//! <b>Complexity</b>: Constant.
376
//! <b>Throws</b>: Nothing.
378
{ return tree_.empty(); }
380
//! <b>Effects</b>: Returns the number of elements stored in the treap_set.
382
//! <b>Complexity</b>: Linear to elements contained in *this if,
383
//! constant-time size option is enabled. Constant-time otherwise.
385
//! <b>Throws</b>: Nothing.
386
size_type size() const
387
{ return tree_.size(); }
389
//! <b>Effects</b>: Swaps the contents of two sets.
391
//! <b>Complexity</b>: Constant.
393
//! <b>Throws</b>: If the swap() call for the comparison functor
394
//! found using ADL throws. Strong guarantee.
395
void swap(treap_set_impl& other)
396
{ tree_.swap(other.tree_); }
398
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
399
//! Cloner should yield to nodes equivalent to the original nodes.
401
//! <b>Effects</b>: Erases all the elements from *this
402
//! calling Disposer::operator()(pointer), clones all the
403
//! elements from src calling Cloner::operator()(const_reference )
404
//! and inserts them on *this. Copies the predicate from the source container.
406
//! If cloner throws, all cloned elements are unlinked and disposed
407
//! calling Disposer::operator()(pointer).
409
//! <b>Complexity</b>: Linear to erased plus inserted elements.
411
//! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
412
template <class Cloner, class Disposer>
413
void clone_from(const treap_set_impl &src, Cloner cloner, Disposer disposer)
414
{ tree_.clone_from(src.tree_, cloner, disposer); }
416
//! <b>Requires</b>: value must be an lvalue
418
//! <b>Effects</b>: Tries to inserts value into the treap_set.
420
//! <b>Returns</b>: If the value
421
//! is not already present inserts it and returns a pair containing the
422
//! iterator to the new value and true. If there is an equivalent value
423
//! returns a pair containing an iterator to the already present value
426
//! <b>Complexity</b>: Average complexity for insert element is at
427
//! most logarithmic.
429
//! <b>Throws</b>: If the internal value_compare or priority_compare ordering function throw.
430
//! Strong guarantee.
432
//! <b>Note</b>: Does not affect the validity of iterators and references.
433
//! No copy-constructors are called.
434
std::pair<iterator, bool> insert(reference value)
435
{ return tree_.insert_unique(value); }
437
//! <b>Requires</b>: value must be an lvalue
439
//! <b>Effects</b>: Tries to to insert x into the treap_set, using "hint"
440
//! as a hint to where it will be inserted.
442
//! <b>Returns</b>: An iterator that points to the position where the
443
//! new element was inserted into the treap_set.
445
//! <b>Complexity</b>: Logarithmic in general, but it's amortized
446
//! constant time if t is inserted immediately before hint.
448
//! <b>Throws</b>: If the internal value_compare or priority_compare ordering
449
//! functions throw. Strong guarantee.
451
//! <b>Note</b>: Does not affect the validity of iterators and references.
452
//! No copy-constructors are called.
453
iterator insert(const_iterator hint, reference value)
454
{ return tree_.insert_unique(hint, value); }
456
//! <b>Requires</b>: key_value_comp must be a comparison function that induces
457
//! the same strict weak ordering as value_compare.
458
//! key_value_pcomp must be a comparison function that induces
459
//! the same strict weak ordering as priority_compare. The difference is that
460
//! key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.
462
//! <b>Effects</b>: Checks if a value can be inserted in the treap_set, using
463
//! a user provided key instead of the value itself.
465
//! <b>Returns</b>: If there is an equivalent value
466
//! returns a pair containing an iterator to the already present value
467
//! and false. If the value can be inserted returns true in the returned
468
//! pair boolean and fills "commit_data" that is meant to be used with
469
//! the "insert_commit" function.
471
//! <b>Complexity</b>: Average complexity is at most logarithmic.
473
//! <b>Throws</b>: If key_value_comp or key_value_pcomp ordering function throw.
474
//! Strong guarantee.
476
//! <b>Notes</b>: This function is used to improve performance when constructing
477
//! a value_type is expensive: if there is an equivalent value
478
//! the constructed object must be discarded. Many times, the part of the
479
//! node that is used to impose the order is much cheaper to construct
480
//! than the value_type and this function offers the possibility to use that
481
//! part to check if the insertion will be successful.
483
//! If the check is successful, the user can construct the value_type and use
484
//! "insert_commit" to insert the object in constant-time. This gives a total
485
//! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
487
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
488
//! objects are inserted or erased from the treap_set.
489
template<class KeyType, class KeyValueCompare, class KeyValuePriorityCompare>
490
std::pair<iterator, bool> insert_check
491
( const KeyType &key, KeyValueCompare key_value_comp, KeyValuePriorityCompare key_value_pcomp
492
, insert_commit_data &commit_data)
493
{ return tree_.insert_unique_check(key, key_value_comp, key_value_pcomp, commit_data); }
495
//! <b>Requires</b>: key_value_comp must be a comparison function that induces
496
//! the same strict weak ordering as value_compare.
497
//! key_value_pcomp must be a comparison function that induces
498
//! the same strict weak ordering as priority_compare. The difference is that
499
//! key_value_pcomp and key_value_comp compare an arbitrary key with the contained values.
501
//! <b>Effects</b>: Checks if a value can be inserted in the treap_set, using
502
//! a user provided key instead of the value itself, using "hint"
503
//! as a hint to where it will be inserted.
505
//! <b>Returns</b>: If there is an equivalent value
506
//! returns a pair containing an iterator to the already present value
507
//! and false. If the value can be inserted returns true in the returned
508
//! pair boolean and fills "commit_data" that is meant to be used with
509
//! the "insert_commit" function.
511
//! <b>Complexity</b>: Logarithmic in general, but it's amortized
512
//! constant time if t is inserted immediately before hint.
514
//! <b>Throws</b>: If key_value_comp or key_value_pcomp ordering function throw.
515
//! Strong guarantee.
517
//! <b>Notes</b>: This function is used to improve performance when constructing
518
//! a value_type is expensive: if there is an equivalent value
519
//! the constructed object must be discarded. Many times, the part of the
520
//! constructing that is used to impose the order is much cheaper to construct
521
//! than the value_type and this function offers the possibility to use that key
522
//! to check if the insertion will be successful.
524
//! If the check is successful, the user can construct the value_type and use
525
//! "insert_commit" to insert the object in constant-time. This can give a total
526
//! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
528
//! "commit_data" remains valid for a subsequent "insert_commit" only if no more
529
//! objects are inserted or erased from the treap_set.
530
template<class KeyType, class KeyValueCompare, class KeyValuePriorityCompare>
531
std::pair<iterator, bool> insert_check
532
( const_iterator hint, const KeyType &key
533
, KeyValueCompare key_value_comp, KeyValuePriorityCompare key_value_pcomp
534
, insert_commit_data &commit_data)
535
{ return tree_.insert_unique_check(hint, key, key_value_comp, key_value_pcomp, commit_data); }
537
//! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
538
//! must have been obtained from a previous call to "insert_check".
539
//! No objects should have been inserted or erased from the treap_set between
540
//! the "insert_check" that filled "commit_data" and the call to "insert_commit".
542
//! <b>Effects</b>: Inserts the value in the treap_set using the information obtained
543
//! from the "commit_data" that a previous "insert_check" filled.
545
//! <b>Returns</b>: An iterator to the newly inserted object.
547
//! <b>Complexity</b>: Constant time.
549
//! <b>Throws</b>: Nothing.
551
//! <b>Notes</b>: This function has only sense if a "insert_check" has been
552
//! previously executed to fill "commit_data". No value should be inserted or
553
//! erased between the "insert_check" and "insert_commit" calls.
554
iterator insert_commit(reference value, const insert_commit_data &commit_data)
555
{ return tree_.insert_unique_commit(value, commit_data); }
557
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue
558
//! of type value_type.
560
//! <b>Effects</b>: Inserts a range into the treap_set.
562
//! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
563
//! size of the range. However, it is linear in N if the range is already sorted
566
//! <b>Throws</b>: If the internal value_compare or priority_compare ordering function
567
//! throw. Basic guarantee.
569
//! <b>Note</b>: Does not affect the validity of iterators and references.
570
//! No copy-constructors are called.
571
template<class Iterator>
572
void insert(Iterator b, Iterator e)
573
{ tree_.insert_unique(b, e); }
575
//! <b>Requires</b>: value must be an lvalue, "pos" must be
576
//! a valid iterator (or end) and must be the succesor of value
577
//! once inserted according to the predicate. "value" must not be equal to any
578
//! inserted key according to the predicate.
580
//! <b>Effects</b>: Inserts x into the treap before "pos".
582
//! <b>Complexity</b>: Constant time.
584
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
586
//! <b>Note</b>: This function does not check preconditions so if "pos" is not
587
//! the successor of "value" treap ordering invariant will be broken.
588
//! This is a low-level function to be used only for performance reasons
589
//! by advanced users.
590
iterator insert_before(const_iterator pos, reference value)
591
{ return tree_.insert_before(pos, value); }
593
//! <b>Requires</b>: value must be an lvalue, and it must be greater than
594
//! any inserted key according to the predicate.
596
//! <b>Effects</b>: Inserts x into the treap in the last position.
598
//! <b>Complexity</b>: Constant time.
600
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
602
//! <b>Note</b>: This function does not check preconditions so if value is
603
//! less than the greatest inserted key treap ordering invariant will be broken.
604
//! This function is slightly more efficient than using "insert_before".
605
//! This is a low-level function to be used only for performance reasons
606
//! by advanced users.
607
void push_back(reference value)
608
{ tree_.push_back(value); }
610
//! <b>Requires</b>: value must be an lvalue, and it must be less
611
//! than any inserted key according to the predicate.
613
//! <b>Effects</b>: Inserts x into the treap in the first position.
615
//! <b>Complexity</b>: Constant time.
617
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
619
//! <b>Note</b>: This function does not check preconditions so if value is
620
//! greater than the minimum inserted key treap ordering invariant will be broken.
621
//! This function is slightly more efficient than using "insert_before".
622
//! This is a low-level function to be used only for performance reasons
623
//! by advanced users.
624
void push_front(reference value)
625
{ tree_.push_front(value); }
627
//! <b>Effects</b>: Erases the element pointed to by pos.
629
//! <b>Complexity</b>: Average complexity is constant time.
631
//! <b>Returns</b>: An iterator to the element after the erased element.
633
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
635
//! <b>Note</b>: Invalidates the iterators (but not the references)
636
//! to the erased elements. No destructors are called.
637
iterator erase(const_iterator i)
638
{ return tree_.erase(i); }
640
//! <b>Effects</b>: Erases the range pointed to by b end e.
642
//! <b>Complexity</b>: Average complexity for erase range is at most
643
//! O(log(size() + N)), where N is the number of elements in the range.
645
//! <b>Returns</b>: An iterator to the element after the erased elements.
647
//! <b>Throws</b>: If the internal priority_compare function throws. Basic guarantee.
649
//! <b>Note</b>: Invalidates the iterators (but not the references)
650
//! to the erased elements. No destructors are called.
651
iterator erase(const_iterator b, const_iterator e)
652
{ return tree_.erase(b, e); }
654
//! <b>Effects</b>: Erases all the elements with the given value.
656
//! <b>Returns</b>: The number of erased elements.
658
//! <b>Complexity</b>: O(log(size()) + this->count(value)).
660
//! <b>Throws</b>: If internal value_compare or priority_compare
661
//! ordering functions throw. Basic guarantee.
663
//! <b>Note</b>: Invalidates the iterators (but not the references)
664
//! to the erased elements. No destructors are called.
665
size_type erase(const_reference value)
666
{ return tree_.erase(value); }
668
//! <b>Effects</b>: Erases all the elements that compare equal with
669
//! the given key and the given comparison functor.
671
//! <b>Returns</b>: The number of erased elements.
673
//! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
675
//! <b>Throws</b>: If comp or internal priority_compare
676
//! ordering functions throw. Basic guarantee.
678
//! <b>Note</b>: Invalidates the iterators (but not the references)
679
//! to the erased elements. No destructors are called.
680
template<class KeyType, class KeyValueCompare>
681
size_type erase(const KeyType& key, KeyValueCompare comp
683
, typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
686
{ return tree_.erase(key, comp); }
688
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
690
//! <b>Effects</b>: Erases the element pointed to by pos.
691
//! Disposer::operator()(pointer) is called for the removed element.
693
//! <b>Complexity</b>: Average complexity for erase element is constant time.
695
//! <b>Returns</b>: An iterator to the element after the erased element.
697
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
699
//! <b>Note</b>: Invalidates the iterators
700
//! to the erased elements.
701
template<class Disposer>
702
iterator erase_and_dispose(const_iterator i, Disposer disposer)
703
{ return tree_.erase_and_dispose(i, disposer); }
705
#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
706
template<class Disposer>
707
iterator erase_and_dispose(iterator i, Disposer disposer)
708
{ return this->erase_and_dispose(const_iterator(i), disposer); }
711
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
713
//! <b>Effects</b>: Erases the range pointed to by b end e.
714
//! Disposer::operator()(pointer) is called for the removed elements.
716
//! <b>Complexity</b>: Average complexity for erase range is at most
717
//! O(log(size() + N)), where N is the number of elements in the range.
719
//! <b>Returns</b>: An iterator to the element after the erased elements.
721
//! <b>Throws</b>: If the internal priority_compare function throws. Basic guarantee.
723
//! <b>Note</b>: Invalidates the iterators
724
//! to the erased elements.
725
template<class Disposer>
726
iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
727
{ return tree_.erase_and_dispose(b, e, disposer); }
729
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
731
//! <b>Effects</b>: Erases all the elements with the given value.
732
//! Disposer::operator()(pointer) is called for the removed elements.
734
//! <b>Throws</b>: If the internal value_compare ordering function throws.
736
//! <b>Complexity</b>: O(log(size() + this->count(value)). Basic guarantee.
738
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
740
//! <b>Note</b>: Invalidates the iterators (but not the references)
741
//! to the erased elements. No destructors are called.
742
template<class Disposer>
743
size_type erase_and_dispose(const_reference value, Disposer disposer)
744
{ return tree_.erase_and_dispose(value, disposer); }
746
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
748
//! <b>Effects</b>: Erases all the elements with the given key.
749
//! according to the comparison functor "comp".
750
//! Disposer::operator()(pointer) is called for the removed elements.
752
//! <b>Returns</b>: The number of erased elements.
754
//! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
756
//! <b>Throws</b>: If comp or internal priority_compare ordering functions throw.
759
//! <b>Note</b>: Invalidates the iterators
760
//! to the erased elements.
761
template<class KeyType, class KeyValueCompare, class Disposer>
762
size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
764
, typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
767
{ return tree_.erase_and_dispose(key, comp, disposer); }
769
//! <b>Effects</b>: Erases all the elements of the container.
771
//! <b>Complexity</b>: Linear to the number of elements on the container.
772
//! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
774
//! <b>Throws</b>: Nothing.
776
//! <b>Note</b>: Invalidates the iterators (but not the references)
777
//! to the erased elements. No destructors are called.
779
{ return tree_.clear(); }
781
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
783
//! <b>Effects</b>: Erases all the elements of the container.
785
//! <b>Complexity</b>: Linear to the number of elements on the container.
786
//! Disposer::operator()(pointer) is called for the removed elements.
788
//! <b>Throws</b>: Nothing.
790
//! <b>Note</b>: Invalidates the iterators (but not the references)
791
//! to the erased elements. No destructors are called.
792
template<class Disposer>
793
void clear_and_dispose(Disposer disposer)
794
{ return tree_.clear_and_dispose(disposer); }
796
//! <b>Effects</b>: Returns the number of contained elements with the given key
798
//! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
799
//! to number of objects with the given key.
801
//! <b>Throws</b>: If the internal value_compare ordering function throws.
802
size_type count(const_reference value) const
803
{ return tree_.find(value) != end(); }
805
//! <b>Effects</b>: Returns the number of contained elements with the same key
806
//! compared with the given comparison functor.
808
//! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
809
//! to number of objects with the given key.
811
//! <b>Throws</b>: If comp ordering function throws.
812
template<class KeyType, class KeyValueCompare>
813
size_type count(const KeyType& key, KeyValueCompare comp) const
814
{ return tree_.find(key, comp) != end(); }
816
//! <b>Effects</b>: Returns an iterator to the first element whose
817
//! key is not less than k or end() if that element does not exist.
819
//! <b>Complexity</b>: Logarithmic.
821
//! <b>Throws</b>: If the internal value_compare ordering function throws.
822
iterator lower_bound(const_reference value)
823
{ return tree_.lower_bound(value); }
825
//! <b>Requires</b>: comp must imply the same element order as
826
//! value_compare. Usually key is the part of the value_type
827
//! that is used in the ordering functor.
829
//! <b>Effects</b>: Returns an iterator to the first element whose
830
//! key according to the comparison functor is not less than k or
831
//! end() if that element does not exist.
833
//! <b>Complexity</b>: Logarithmic.
835
//! <b>Throws</b>: If comp ordering function throws.
837
//! <b>Note</b>: This function is used when constructing a value_type
838
//! is expensive and the value_type can be compared with a cheaper
839
//! key type. Usually this key is part of the value_type.
840
template<class KeyType, class KeyValueCompare>
841
iterator lower_bound(const KeyType& key, KeyValueCompare comp)
842
{ return tree_.lower_bound(key, comp); }
844
//! <b>Effects</b>: Returns a const iterator to the first element whose
845
//! key is not less than k or end() if that element does not exist.
847
//! <b>Complexity</b>: Logarithmic.
849
//! <b>Throws</b>: If the internal value_compare ordering function throws.
850
const_iterator lower_bound(const_reference value) const
851
{ return tree_.lower_bound(value); }
853
//! <b>Requires</b>: comp must imply the same element order as
854
//! value_compare. Usually key is the part of the value_type
855
//! that is used in the ordering functor.
857
//! <b>Effects</b>: Returns a const_iterator to the first element whose
858
//! key according to the comparison functor is not less than k or
859
//! end() if that element does not exist.
861
//! <b>Complexity</b>: Logarithmic.
863
//! <b>Throws</b>: If comp ordering function throws.
865
//! <b>Note</b>: This function is used when constructing a value_type
866
//! is expensive and the value_type can be compared with a cheaper
867
//! key type. Usually this key is part of the value_type.
868
template<class KeyType, class KeyValueCompare>
869
const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
870
{ return tree_.lower_bound(key, comp); }
872
//! <b>Effects</b>: Returns an iterator to the first element whose
873
//! key is greater than k or end() if that element does not exist.
875
//! <b>Complexity</b>: Logarithmic.
877
//! <b>Throws</b>: If the internal value_compare ordering function throws.
878
iterator upper_bound(const_reference value)
879
{ return tree_.upper_bound(value); }
881
//! <b>Requires</b>: comp must imply the same element order as
882
//! value_compare. Usually key is the part of the value_type
883
//! that is used in the ordering functor.
885
//! <b>Effects</b>: Returns an iterator to the first element whose
886
//! key according to the comparison functor is greater than key or
887
//! end() if that element does not exist.
889
//! <b>Complexity</b>: Logarithmic.
891
//! <b>Throws</b>: If comp ordering function throws.
893
//! <b>Note</b>: This function is used when constructing a value_type
894
//! is expensive and the value_type can be compared with a cheaper
895
//! key type. Usually this key is part of the value_type.
896
template<class KeyType, class KeyValueCompare>
897
iterator upper_bound(const KeyType& key, KeyValueCompare comp)
898
{ return tree_.upper_bound(key, comp); }
900
//! <b>Effects</b>: Returns an iterator to the first element whose
901
//! key is greater than k or end() if that element does not exist.
903
//! <b>Complexity</b>: Logarithmic.
905
//! <b>Throws</b>: If the internal value_compare ordering function throws.
906
const_iterator upper_bound(const_reference value) const
907
{ return tree_.upper_bound(value); }
909
//! <b>Requires</b>: comp must imply the same element order as
910
//! value_compare. Usually key is the part of the value_type
911
//! that is used in the ordering functor.
913
//! <b>Effects</b>: Returns a const_iterator to the first element whose
914
//! key according to the comparison functor is greater than key or
915
//! end() if that element does not exist.
917
//! <b>Complexity</b>: Logarithmic.
919
//! <b>Throws</b>: If comp ordering function throws.
921
//! <b>Note</b>: This function is used when constructing a value_type
922
//! is expensive and the value_type can be compared with a cheaper
923
//! key type. Usually this key is part of the value_type.
924
template<class KeyType, class KeyValueCompare>
925
const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
926
{ return tree_.upper_bound(key, comp); }
928
//! <b>Effects</b>: Finds an iterator to the first element whose value is
929
//! "value" or end() if that element does not exist.
931
//! <b>Complexity</b>: Logarithmic.
933
//! <b>Throws</b>: If the internal value_compare ordering function throws.
934
iterator find(const_reference value)
935
{ return tree_.find(value); }
937
//! <b>Requires</b>: comp must imply the same element order as
938
//! value_compare. Usually key is the part of the value_type
939
//! that is used in the ordering functor.
941
//! <b>Effects</b>: Finds an iterator to the first element whose key is
942
//! "key" according to the comparison functor or end() if that element
945
//! <b>Complexity</b>: Logarithmic.
947
//! <b>Throws</b>: If comp ordering function throws.
949
//! <b>Note</b>: This function is used when constructing a value_type
950
//! is expensive and the value_type can be compared with a cheaper
951
//! key type. Usually this key is part of the value_type.
952
template<class KeyType, class KeyValueCompare>
953
iterator find(const KeyType& key, KeyValueCompare comp)
954
{ return tree_.find(key, comp); }
956
//! <b>Effects</b>: Finds a const_iterator to the first element whose value is
957
//! "value" or end() if that element does not exist.
959
//! <b>Complexity</b>: Logarithmic.
961
//! <b>Throws</b>: If the internal value_compare ordering function throws.
962
const_iterator find(const_reference value) const
963
{ return tree_.find(value); }
965
//! <b>Requires</b>: comp must imply the same element order as
966
//! value_compare. Usually key is the part of the value_type
967
//! that is used in the ordering functor.
969
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
970
//! "key" according to the comparison functor or end() if that element
973
//! <b>Complexity</b>: Logarithmic.
975
//! <b>Throws</b>: If comp ordering function throws.
977
//! <b>Note</b>: This function is used when constructing a value_type
978
//! is expensive and the value_type can be compared with a cheaper
979
//! key type. Usually this key is part of the value_type.
980
template<class KeyType, class KeyValueCompare>
981
const_iterator find(const KeyType& key, KeyValueCompare comp) const
982
{ return tree_.find(key, comp); }
984
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
985
//! an empty range that indicates the position where those elements would be
986
//! if they there is no elements with key k.
988
//! <b>Complexity</b>: Logarithmic.
990
//! <b>Throws</b>: If the internal value_compare ordering function throws.
991
std::pair<iterator,iterator> equal_range(const_reference value)
992
{ return tree_.equal_range(value); }
994
//! <b>Requires</b>: comp must imply the same element order as
995
//! value_compare. Usually key is the part of the value_type
996
//! that is used in the ordering functor.
998
//! <b>Effects</b>: Finds a range containing all elements whose key is k
999
//! according to the comparison functor or an empty range
1000
//! that indicates the position where those elements would be
1001
//! if they there is no elements with key k.
1003
//! <b>Complexity</b>: Logarithmic.
1005
//! <b>Throws</b>: If comp ordering function throws.
1007
//! <b>Note</b>: This function is used when constructing a value_type
1008
//! is expensive and the value_type can be compared with a cheaper
1009
//! key type. Usually this key is part of the value_type.
1010
template<class KeyType, class KeyValueCompare>
1011
std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
1012
{ return tree_.equal_range(key, comp); }
1014
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
1015
//! an empty range that indicates the position where those elements would be
1016
//! if they there is no elements with key k.
1018
//! <b>Complexity</b>: Logarithmic.
1020
//! <b>Throws</b>: If the internal value_compare ordering function throws.
1021
std::pair<const_iterator, const_iterator>
1022
equal_range(const_reference value) const
1023
{ return tree_.equal_range(value); }
1025
//! <b>Requires</b>: comp must imply the same element order as
1026
//! value_compare. Usually key is the part of the value_type
1027
//! that is used in the ordering functor.
1029
//! <b>Effects</b>: Finds a range containing all elements whose key is k
1030
//! according to the comparison functor or an empty range
1031
//! that indicates the position where those elements would be
1032
//! if they there is no elements with key k.
1034
//! <b>Complexity</b>: Logarithmic.
1036
//! <b>Throws</b>: If comp ordering function throws.
1038
//! <b>Note</b>: This function is used when constructing a value_type
1039
//! is expensive and the value_type can be compared with a cheaper
1040
//! key type. Usually this key is part of the value_type.
1041
template<class KeyType, class KeyValueCompare>
1042
std::pair<const_iterator, const_iterator>
1043
equal_range(const KeyType& key, KeyValueCompare comp) const
1044
{ return tree_.equal_range(key, comp); }
1046
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_set of
1047
//! appropriate type. Otherwise the behavior is undefined.
1049
//! <b>Effects</b>: Returns: a valid iterator i belonging to the treap_set
1050
//! that points to the value
1052
//! <b>Complexity</b>: Constant.
1054
//! <b>Throws</b>: Nothing.
1056
//! <b>Note</b>: This static function is available only if the <i>value traits</i>
1058
static iterator s_iterator_to(reference value)
1059
{ return tree_type::s_iterator_to(value); }
1061
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_set of
1062
//! appropriate type. Otherwise the behavior is undefined.
1064
//! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1065
//! treap_set that points to the value
1067
//! <b>Complexity</b>: Constant.
1069
//! <b>Throws</b>: Nothing.
1071
//! <b>Note</b>: This static function is available only if the <i>value traits</i>
1073
static const_iterator s_iterator_to(const_reference value)
1074
{ return tree_type::s_iterator_to(value); }
1076
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_set of
1077
//! appropriate type. Otherwise the behavior is undefined.
1079
//! <b>Effects</b>: Returns: a valid iterator i belonging to the treap_set
1080
//! that points to the value
1082
//! <b>Complexity</b>: Constant.
1084
//! <b>Throws</b>: Nothing.
1085
iterator iterator_to(reference value)
1086
{ return tree_.iterator_to(value); }
1088
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_set of
1089
//! appropriate type. Otherwise the behavior is undefined.
1091
//! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1092
//! treap_set that points to the value
1094
//! <b>Complexity</b>: Constant.
1096
//! <b>Throws</b>: Nothing.
1097
const_iterator iterator_to(const_reference value) const
1098
{ return tree_.iterator_to(value); }
1100
//! <b>Requires</b>: value shall not be in a treap_set/treap_multiset.
1102
//! <b>Effects</b>: init_node puts the hook of a value in a well-known default
1105
//! <b>Throws</b>: Nothing.
1107
//! <b>Complexity</b>: Constant time.
1109
//! <b>Note</b>: This function puts the hook in the well-known default state
1110
//! used by auto_unlink and safe hooks.
1111
static void init_node(reference value)
1112
{ tree_type::init_node(value); }
1114
//! <b>Effects</b>: Unlinks the leftmost node from the tree.
1116
//! <b>Complexity</b>: Average complexity is constant time.
1118
//! <b>Throws</b>: Nothing.
1120
//! <b>Notes</b>: This function breaks the tree and the tree can
1121
//! only be used for more unlink_leftmost_without_rebalance calls.
1122
//! This function is normally used to achieve a step by step
1123
//! controlled destruction of the tree.
1124
pointer unlink_leftmost_without_rebalance()
1125
{ return tree_.unlink_leftmost_without_rebalance(); }
1127
//! <b>Requires</b>: replace_this must be a valid iterator of *this
1128
//! and with_this must not be inserted in any tree.
1130
//! <b>Effects</b>: Replaces replace_this in its position in the
1131
//! tree with with_this. The tree does not need to be rebalanced.
1133
//! <b>Complexity</b>: Constant.
1135
//! <b>Throws</b>: Nothing.
1137
//! <b>Note</b>: This function will break container ordering invariants if
1138
//! with_this is not equivalent to *replace_this according to the
1139
//! ordering rules. This function is faster than erasing and inserting
1140
//! the node, since no rebalancing or comparison is needed.
1141
void replace_node(iterator replace_this, reference with_this)
1142
{ tree_.replace_node(replace_this, with_this); }
1144
//! <b>Effects</b>: Rebalances the tree.
1146
//! <b>Throws</b>: Nothing.
1148
//! <b>Complexity</b>: Linear.
1150
{ tree_.rebalance(); }
1152
//! <b>Requires</b>: old_root is a node of a tree.
1154
//! <b>Effects</b>: Rebalances the subtree rooted at old_root.
1156
//! <b>Returns</b>: The new root of the subtree.
1158
//! <b>Throws</b>: Nothing.
1160
//! <b>Complexity</b>: Linear to the elements in the subtree.
1161
iterator rebalance_subtree(iterator root)
1162
{ return tree_.rebalance_subtree(root); }
1164
//! <b>Returns</b>: The balance factor (alpha) used in this tree
1166
//! <b>Throws</b>: Nothing.
1168
//! <b>Complexity</b>: Constant.
1169
float balance_factor() const
1170
{ return tree_.balance_factor(); }
1172
//! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
1174
//! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
1175
//! the tree if the new balance factor is stricter (less) than the old factor.
1177
//! <b>Throws</b>: Nothing.
1179
//! <b>Complexity</b>: Linear to the elements in the subtree.
1180
void balance_factor(float new_alpha)
1181
{ tree_.balance_factor(new_alpha); }
1184
friend bool operator==(const treap_set_impl &x, const treap_set_impl &y)
1185
{ return x.tree_ == y.tree_; }
1187
friend bool operator<(const treap_set_impl &x, const treap_set_impl &y)
1188
{ return x.tree_ < y.tree_; }
1192
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1193
template<class T, class ...Options>
1195
template<class Config>
1197
inline bool operator!=
1198
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1199
(const treap_set_impl<T, Options...> &x, const treap_set_impl<T, Options...> &y)
1201
(const treap_set_impl<Config> &x, const treap_set_impl<Config> &y)
1203
{ return !(x == y); }
1205
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1206
template<class T, class ...Options>
1208
template<class Config>
1210
inline bool operator>
1211
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1212
(const treap_set_impl<T, Options...> &x, const treap_set_impl<T, Options...> &y)
1214
(const treap_set_impl<Config> &x, const treap_set_impl<Config> &y)
1218
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1219
template<class T, class ...Options>
1221
template<class Config>
1223
inline bool operator<=
1224
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1225
(const treap_set_impl<T, Options...> &x, const treap_set_impl<T, Options...> &y)
1227
(const treap_set_impl<Config> &x, const treap_set_impl<Config> &y)
1229
{ return !(y < x); }
1231
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1232
template<class T, class ...Options>
1234
template<class Config>
1236
inline bool operator>=
1237
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1238
(const treap_set_impl<T, Options...> &x, const treap_set_impl<T, Options...> &y)
1240
(const treap_set_impl<Config> &x, const treap_set_impl<Config> &y)
1242
{ return !(x < y); }
1244
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1245
template<class T, class ...Options>
1247
template<class Config>
1250
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1251
(treap_set_impl<T, Options...> &x, treap_set_impl<T, Options...> &y)
1253
(treap_set_impl<Config> &x, treap_set_impl<Config> &y)
1257
//! Helper metafunction to define a \c treap_set that yields to the same type when the
1258
//! same options (either explicitly or implicitly) are used.
1259
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1260
template<class T, class ...Options>
1262
template<class T, class O1 = none, class O2 = none
1263
, class O3 = none, class O4 = none>
1265
struct make_treap_set
1268
typedef treap_set_impl
1269
< typename make_treap_opt<T,
1270
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1276
> implementation_defined;
1278
typedef implementation_defined type;
1281
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1283
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1284
template<class T, class O1, class O2, class O3, class O4>
1286
template<class T, class ...Options>
1289
: public make_treap_set<T,
1290
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1297
typedef typename make_treap_set
1299
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1305
BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set)
1308
typedef typename Base::value_compare value_compare;
1309
typedef typename Base::priority_compare priority_compare;
1310
typedef typename Base::value_traits value_traits;
1311
typedef typename Base::iterator iterator;
1312
typedef typename Base::const_iterator const_iterator;
1314
//Assert if passed value traits are compatible with the type
1315
BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1317
treap_set( const value_compare &cmp = value_compare()
1318
, const priority_compare &pcmp = priority_compare()
1319
, const value_traits &v_traits = value_traits())
1320
: Base(cmp, pcmp, v_traits)
1323
template<class Iterator>
1324
treap_set( Iterator b, Iterator e
1325
, const value_compare &cmp = value_compare()
1326
, const priority_compare &pcmp = priority_compare()
1327
, const value_traits &v_traits = value_traits())
1328
: Base(b, e, cmp, pcmp, v_traits)
1331
treap_set(BOOST_RV_REF(treap_set) x)
1332
: Base(::boost::move(static_cast<Base&>(x)))
1335
treap_set& operator=(BOOST_RV_REF(treap_set) x)
1336
{ this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
1338
static treap_set &container_from_end_iterator(iterator end_iterator)
1339
{ return static_cast<treap_set &>(Base::container_from_end_iterator(end_iterator)); }
1341
static const treap_set &container_from_end_iterator(const_iterator end_iterator)
1342
{ return static_cast<const treap_set &>(Base::container_from_end_iterator(end_iterator)); }
1344
static treap_set &container_from_iterator(iterator it)
1345
{ return static_cast<treap_set &>(Base::container_from_iterator(it)); }
1347
static const treap_set &container_from_iterator(const_iterator it)
1348
{ return static_cast<const treap_set &>(Base::container_from_iterator(it)); }
1353
//! The class template treap_multiset is an intrusive container, that mimics most of
1354
//! the interface of std::treap_multiset as described in the C++ standard.
1356
//! The template parameter \c T is the type to be managed by the container.
1357
//! The user can specify additional options and if no options are provided
1358
//! default options are used.
1360
//! The container supports the following options:
1361
//! \c base_hook<>/member_hook<>/value_traits<>,
1362
//! \c constant_time_size<>, \c size_type<>,
1363
//! \c compare<> and \c priority_compare<>
1364
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1365
template<class T, class ...Options>
1367
template<class Config>
1369
class treap_multiset_impl
1372
typedef treap_impl<Config> tree_type;
1374
BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset_impl)
1375
typedef tree_type implementation_defined;
1379
typedef typename implementation_defined::value_type value_type;
1380
typedef typename implementation_defined::value_traits value_traits;
1381
typedef typename implementation_defined::pointer pointer;
1382
typedef typename implementation_defined::const_pointer const_pointer;
1383
typedef typename implementation_defined::reference reference;
1384
typedef typename implementation_defined::const_reference const_reference;
1385
typedef typename implementation_defined::difference_type difference_type;
1386
typedef typename implementation_defined::size_type size_type;
1387
typedef typename implementation_defined::value_compare value_compare;
1388
typedef typename implementation_defined::priority_compare priority_compare;
1389
typedef typename implementation_defined::key_compare key_compare;
1390
typedef typename implementation_defined::iterator iterator;
1391
typedef typename implementation_defined::const_iterator const_iterator;
1392
typedef typename implementation_defined::reverse_iterator reverse_iterator;
1393
typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
1394
typedef typename implementation_defined::insert_commit_data insert_commit_data;
1395
typedef typename implementation_defined::node_traits node_traits;
1396
typedef typename implementation_defined::node node;
1397
typedef typename implementation_defined::node_ptr node_ptr;
1398
typedef typename implementation_defined::const_node_ptr const_node_ptr;
1399
typedef typename implementation_defined::node_algorithms node_algorithms;
1401
static const bool constant_time_size = Config::constant_time_size;
1409
//! <b>Effects</b>: Constructs an empty treap_multiset.
1411
//! <b>Complexity</b>: Constant.
1413
//! <b>Throws</b>: If value_traits::node_traits::node
1414
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1415
//! or the copy constructor of the value_compare/priority_compare objects throw.
1416
treap_multiset_impl( const value_compare &cmp = value_compare()
1417
, const priority_compare &pcmp = priority_compare()
1418
, const value_traits &v_traits = value_traits())
1419
: tree_(cmp, pcmp, v_traits)
1422
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
1423
//! cmp must be a comparison function that induces a strict weak ordering.
1425
//! <b>Effects</b>: Constructs an empty treap_multiset and inserts elements from
1428
//! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
1429
//! comp and otherwise N * log N, where N is the distance between first and last
1431
//! <b>Throws</b>: If value_traits::node_traits::node
1432
//! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1433
//! or the copy constructor/operator() of the value_compare/priority_compare objects throw.
1434
template<class Iterator>
1435
treap_multiset_impl( Iterator b, Iterator e
1436
, const value_compare &cmp = value_compare()
1437
, const priority_compare &pcmp = priority_compare()
1438
, const value_traits &v_traits = value_traits())
1439
: tree_(false, b, e, cmp, pcmp, v_traits)
1442
//! <b>Effects</b>: to-do
1444
treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x)
1445
: tree_(::boost::move(x.tree_))
1448
//! <b>Effects</b>: to-do
1450
treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x)
1451
{ tree_ = ::boost::move(x.tree_); return *this; }
1453
//! <b>Effects</b>: Detaches all elements from this. The objects in the treap_multiset
1454
//! are not deleted (i.e. no destructors are called).
1456
//! <b>Complexity</b>: Linear to the number of elements on the container.
1457
//! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1459
//! <b>Throws</b>: Nothing.
1460
~treap_multiset_impl()
1463
//! <b>Effects</b>: Returns an iterator pointing to the beginning of the treap_multiset.
1465
//! <b>Complexity</b>: Constant.
1467
//! <b>Throws</b>: Nothing.
1469
{ return tree_.begin(); }
1471
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the treap_multiset.
1473
//! <b>Complexity</b>: Constant.
1475
//! <b>Throws</b>: Nothing.
1476
const_iterator begin() const
1477
{ return tree_.begin(); }
1479
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the treap_multiset.
1481
//! <b>Complexity</b>: Constant.
1483
//! <b>Throws</b>: Nothing.
1484
const_iterator cbegin() const
1485
{ return tree_.cbegin(); }
1487
//! <b>Effects</b>: Returns an iterator pointing to the end of the treap_multiset.
1489
//! <b>Complexity</b>: Constant.
1491
//! <b>Throws</b>: Nothing.
1493
{ return tree_.end(); }
1495
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the treap_multiset.
1497
//! <b>Complexity</b>: Constant.
1499
//! <b>Throws</b>: Nothing.
1500
const_iterator end() const
1501
{ return tree_.end(); }
1503
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the treap_multiset.
1505
//! <b>Complexity</b>: Constant.
1507
//! <b>Throws</b>: Nothing.
1508
const_iterator cend() const
1509
{ return tree_.cend(); }
1511
//! <b>Effects</b>: Returns an iterator pointing to the highest priority object of the tree.
1513
//! <b>Complexity</b>: Constant.
1515
//! <b>Throws</b>: Nothing.
1517
{ return tree_.top(); }
1519
//! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the tree..
1521
//! <b>Complexity</b>: Constant.
1523
//! <b>Throws</b>: Nothing.
1524
const_iterator top() const
1525
{ return this->ctop(); }
1527
//! <b>Effects</b>: Returns a const_iterator pointing to the highest priority object of the tree..
1529
//! <b>Complexity</b>: Constant.
1531
//! <b>Throws</b>: Nothing.
1532
const_iterator ctop() const
1533
{ return tree_.ctop(); }
1535
//! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
1536
//! reversed treap_multiset.
1538
//! <b>Complexity</b>: Constant.
1540
//! <b>Throws</b>: Nothing.
1541
reverse_iterator rbegin()
1542
{ return tree_.rbegin(); }
1544
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1545
//! of the reversed treap_multiset.
1547
//! <b>Complexity</b>: Constant.
1549
//! <b>Throws</b>: Nothing.
1550
const_reverse_iterator rbegin() const
1551
{ return tree_.rbegin(); }
1553
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1554
//! of the reversed treap_multiset.
1556
//! <b>Complexity</b>: Constant.
1558
//! <b>Throws</b>: Nothing.
1559
const_reverse_iterator crbegin() const
1560
{ return tree_.crbegin(); }
1562
//! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1563
//! of the reversed treap_multiset.
1565
//! <b>Complexity</b>: Constant.
1567
//! <b>Throws</b>: Nothing.
1568
reverse_iterator rend()
1569
{ return tree_.rend(); }
1571
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1572
//! of the reversed treap_multiset.
1574
//! <b>Complexity</b>: Constant.
1576
//! <b>Throws</b>: Nothing.
1577
const_reverse_iterator rend() const
1578
{ return tree_.rend(); }
1580
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1581
//! of the reversed treap_multiset.
1583
//! <b>Complexity</b>: Constant.
1585
//! <b>Throws</b>: Nothing.
1586
const_reverse_iterator crend() const
1587
{ return tree_.crend(); }
1589
//! <b>Effects</b>: Returns a reverse_iterator pointing to the highest priority object of the
1592
//! <b>Complexity</b>: Constant.
1594
//! <b>Throws</b>: Nothing.
1595
reverse_iterator rtop()
1596
{ return tree_.rtop(); }
1598
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority objec
1599
//! of the reversed tree.
1601
//! <b>Complexity</b>: Constant.
1603
//! <b>Throws</b>: Nothing.
1604
const_reverse_iterator rtop() const
1605
{ return tree_.crtop(); }
1607
//! <b>Effects</b>: Returns a const_reverse_iterator pointing to the highest priority object
1608
//! of the reversed tree.
1610
//! <b>Complexity</b>: Constant.
1612
//! <b>Throws</b>: Nothing.
1613
const_reverse_iterator crtop() const
1614
{ return tree_.crtop(); }
1616
//! <b>Precondition</b>: end_iterator must be a valid end iterator
1617
//! of treap_multiset.
1619
//! <b>Effects</b>: Returns a const reference to the treap_multiset associated to the end iterator
1621
//! <b>Throws</b>: Nothing.
1623
//! <b>Complexity</b>: Constant.
1624
static treap_multiset_impl &container_from_end_iterator(iterator end_iterator)
1626
return *detail::parent_from_member<treap_multiset_impl, tree_type>
1627
( &tree_type::container_from_end_iterator(end_iterator)
1628
, &treap_multiset_impl::tree_);
1631
//! <b>Precondition</b>: end_iterator must be a valid end const_iterator
1632
//! of treap_multiset.
1634
//! <b>Effects</b>: Returns a const reference to the treap_multiset associated to the end iterator
1636
//! <b>Throws</b>: Nothing.
1638
//! <b>Complexity</b>: Constant.
1639
static const treap_multiset_impl &container_from_end_iterator(const_iterator end_iterator)
1641
return *detail::parent_from_member<treap_multiset_impl, tree_type>
1642
( &tree_type::container_from_end_iterator(end_iterator)
1643
, &treap_multiset_impl::tree_);
1646
//! <b>Precondition</b>: it must be a valid iterator of multiset.
1648
//! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
1650
//! <b>Throws</b>: Nothing.
1652
//! <b>Complexity</b>: Constant.
1653
static treap_multiset_impl &container_from_iterator(iterator it)
1655
return *detail::parent_from_member<treap_multiset_impl, tree_type>
1656
( &tree_type::container_from_iterator(it)
1657
, &treap_multiset_impl::tree_);
1660
//! <b>Precondition</b>: it must be a valid const_iterator of multiset.
1662
//! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
1664
//! <b>Throws</b>: Nothing.
1666
//! <b>Complexity</b>: Constant.
1667
static const treap_multiset_impl &container_from_iterator(const_iterator it)
1669
return *detail::parent_from_member<treap_multiset_impl, tree_type>
1670
( &tree_type::container_from_iterator(it)
1671
, &treap_multiset_impl::tree_);
1674
//! <b>Effects</b>: Returns the key_compare object used by the treap_multiset.
1676
//! <b>Complexity</b>: Constant.
1678
//! <b>Throws</b>: If key_compare copy-constructor throws.
1679
key_compare key_comp() const
1680
{ return tree_.value_comp(); }
1682
//! <b>Effects</b>: Returns the value_compare object used by the treap_multiset.
1684
//! <b>Complexity</b>: Constant.
1686
//! <b>Throws</b>: If value_compare copy-constructor throws.
1687
value_compare value_comp() const
1688
{ return tree_.value_comp(); }
1690
//! <b>Effects</b>: Returns the priority_compare object used by the treap_multiset.
1692
//! <b>Complexity</b>: Constant.
1694
//! <b>Throws</b>: If priority_compare copy-constructor throws.
1695
priority_compare priority_comp() const
1696
{ return tree_.priority_comp(); }
1698
//! <b>Effects</b>: Returns true if the container is empty.
1700
//! <b>Complexity</b>: Constant.
1702
//! <b>Throws</b>: Nothing.
1704
{ return tree_.empty(); }
1706
//! <b>Effects</b>: Returns the number of elements stored in the treap_multiset.
1708
//! <b>Complexity</b>: Linear to elements contained in *this if,
1709
//! constant-time size option is enabled. Constant-time otherwise.
1711
//! <b>Throws</b>: Nothing.
1712
size_type size() const
1713
{ return tree_.size(); }
1715
//! <b>Effects</b>: Swaps the contents of two treap_multisets.
1717
//! <b>Complexity</b>: Constant.
1719
//! <b>Throws</b>: If the swap() call for the comparison functor
1720
//! found using ADL throws. Strong guarantee.
1721
void swap(treap_multiset_impl& other)
1722
{ tree_.swap(other.tree_); }
1724
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1725
//! Cloner should yield to nodes equivalent to the original nodes.
1727
//! <b>Effects</b>: Erases all the elements from *this
1728
//! calling Disposer::operator()(pointer), clones all the
1729
//! elements from src calling Cloner::operator()(const_reference )
1730
//! and inserts them on *this. Copies the predicate from the source container.
1732
//! If cloner throws, all cloned elements are unlinked and disposed
1733
//! calling Disposer::operator()(pointer).
1735
//! <b>Complexity</b>: Linear to erased plus inserted elements.
1737
//! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
1738
template <class Cloner, class Disposer>
1739
void clone_from(const treap_multiset_impl &src, Cloner cloner, Disposer disposer)
1740
{ tree_.clone_from(src.tree_, cloner, disposer); }
1742
//! <b>Requires</b>: value must be an lvalue
1744
//! <b>Effects</b>: Inserts value into the treap_multiset.
1746
//! <b>Returns</b>: An iterator that points to the position where the new
1747
//! element was inserted.
1749
//! <b>Complexity</b>: Average complexity for insert element is at
1750
//! most logarithmic.
1752
//! <b>Throws</b>: If the internal value_compare or priority_compare ordering
1753
//! function throws. Strong guarantee.
1755
//! <b>Note</b>: Does not affect the validity of iterators and references.
1756
//! No copy-constructors are called.
1757
iterator insert(reference value)
1758
{ return tree_.insert_equal(value); }
1760
//! <b>Requires</b>: value must be an lvalue
1762
//! <b>Effects</b>: Inserts x into the treap_multiset, using pos as a hint to
1763
//! where it will be inserted.
1765
//! <b>Returns</b>: An iterator that points to the position where the new
1766
//! element was inserted.
1768
//! <b>Complexity</b>: Logarithmic in general, but it is amortized
1769
//! constant time if t is inserted immediately before hint.
1771
//! <b>Throws</b>: If internal value_compare or priority_compare ordering functions throw.
1772
//! Strong guarantee.
1774
//! <b>Note</b>: Does not affect the validity of iterators and references.
1775
//! No copy-constructors are called.
1776
iterator insert(const_iterator hint, reference value)
1777
{ return tree_.insert_equal(hint, value); }
1779
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue
1780
//! of type value_type.
1782
//! <b>Effects</b>: Inserts a range into the treap_multiset.
1784
//! <b>Returns</b>: An iterator that points to the position where the new
1785
//! element was inserted.
1787
//! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
1788
//! size of the range. However, it is linear in N if the range is already sorted
1789
//! by value_comp().
1791
//! <b>Throws</b>: If internal value_compare or priority_compare ordering functions throw.
1792
//! Basic guarantee.
1794
//! <b>Note</b>: Does not affect the validity of iterators and references.
1795
//! No copy-constructors are called.
1796
template<class Iterator>
1797
void insert(Iterator b, Iterator e)
1798
{ tree_.insert_equal(b, e); }
1800
//! <b>Requires</b>: value must be an lvalue, "pos" must be
1801
//! a valid iterator (or end) and must be the succesor of value
1802
//! once inserted according to the predicate
1804
//! <b>Effects</b>: Inserts x into the treap before "pos".
1806
//! <b>Complexity</b>: Constant time.
1808
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
1810
//! <b>Note</b>: This function does not check preconditions so if "pos" is not
1811
//! the successor of "value" treap ordering invariant will be broken.
1812
//! This is a low-level function to be used only for performance reasons
1813
//! by advanced users.
1814
iterator insert_before(const_iterator pos, reference value)
1815
{ return tree_.insert_before(pos, value); }
1817
//! <b>Requires</b>: value must be an lvalue, and it must be no less
1818
//! than the greatest inserted key.
1820
//! <b>Effects</b>: Inserts x into the treap in the last position.
1822
//! <b>Complexity</b>: Constant time.
1824
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
1826
//! <b>Note</b>: This function does not check preconditions so if value is
1827
//! less than the greatest inserted key treap ordering invariant will be broken.
1828
//! This function is slightly more efficient than using "insert_before".
1829
//! This is a low-level function to be used only for performance reasons
1830
//! by advanced users.
1831
void push_back(reference value)
1832
{ tree_.push_back(value); }
1834
//! <b>Requires</b>: value must be an lvalue, and it must be no greater
1835
//! than the minimum inserted key
1837
//! <b>Effects</b>: Inserts x into the treap in the first position.
1839
//! <b>Complexity</b>: Constant time.
1841
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
1843
//! <b>Note</b>: This function does not check preconditions so if value is
1844
//! greater than the minimum inserted key treap ordering invariant will be broken.
1845
//! This function is slightly more efficient than using "insert_before".
1846
//! This is a low-level function to be used only for performance reasons
1847
//! by advanced users.
1848
void push_front(reference value)
1849
{ tree_.push_front(value); }
1851
//! <b>Effects</b>: Erases the element pointed to by pos.
1853
//! <b>Complexity</b>: Average complexity is constant time.
1855
//! <b>Returns</b>: An iterator to the element after the erased element.
1857
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
1859
//! <b>Note</b>: Invalidates the iterators (but not the references)
1860
//! to the erased elements. No destructors are called.
1861
iterator erase(const_iterator i)
1862
{ return tree_.erase(i); }
1864
//! <b>Effects</b>: Erases the range pointed to by b end e.
1866
//! <b>Returns</b>: An iterator to the element after the erased elements.
1868
//! <b>Complexity</b>: Average complexity for erase range is at most
1869
//! O(log(size() + N)), where N is the number of elements in the range.
1871
//! <b>Throws</b>: If the internal priority_compare function throws. Basic guarantee.
1873
//! <b>Note</b>: Invalidates the iterators (but not the references)
1874
//! to the erased elements. No destructors are called.
1875
iterator erase(const_iterator b, const_iterator e)
1876
{ return tree_.erase(b, e); }
1878
//! <b>Effects</b>: Erases all the elements with the given value.
1880
//! <b>Returns</b>: The number of erased elements.
1882
//! <b>Complexity</b>: O(log(size() + this->count(value)).
1884
//! <b>Throws</b>: If the internal value_compare or priority_compare ordering
1885
//! functiona throw. Basic guarantee.
1887
//! <b>Note</b>: Invalidates the iterators (but not the references)
1888
//! to the erased elements. No destructors are called.
1889
size_type erase(const_reference value)
1890
{ return tree_.erase(value); }
1892
//! <b>Effects</b>: Erases all the elements that compare equal with
1893
//! the given key and the given comparison functor.
1895
//! <b>Returns</b>: The number of erased elements.
1897
//! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
1899
//! <b>Throws</b>: If comp or internal priority_compare ordering functions throw. Basic guarantee.
1901
//! <b>Note</b>: Invalidates the iterators (but not the references)
1902
//! to the erased elements. No destructors are called.
1903
template<class KeyType, class KeyValueCompare>
1904
size_type erase(const KeyType& key, KeyValueCompare comp
1906
, typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
1909
{ return tree_.erase(key, comp); }
1911
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1913
//! <b>Returns</b>: An iterator to the element after the erased element.
1915
//! <b>Effects</b>: Erases the element pointed to by pos.
1916
//! Disposer::operator()(pointer) is called for the removed element.
1918
//! <b>Complexity</b>: Average complexity for erase element is constant time.
1920
//! <b>Throws</b>: If the internal priority_compare function throws. Strong guarantee.
1922
//! <b>Note</b>: Invalidates the iterators
1923
//! to the erased elements.
1924
template<class Disposer>
1925
iterator erase_and_dispose(const_iterator i, Disposer disposer)
1926
{ return tree_.erase_and_dispose(i, disposer); }
1928
#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1929
template<class Disposer>
1930
iterator erase_and_dispose(iterator i, Disposer disposer)
1931
{ return this->erase_and_dispose(const_iterator(i), disposer); }
1934
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1936
//! <b>Returns</b>: An iterator to the element after the erased elements.
1938
//! <b>Effects</b>: Erases the range pointed to by b end e.
1939
//! Disposer::operator()(pointer) is called for the removed elements.
1941
//! <b>Complexity</b>: Average complexity for erase range is at most
1942
//! O(log(size() + N)), where N is the number of elements in the range.
1944
//! <b>Throws</b>: If the internal priority_compare function throws. Basic guarantee.
1946
//! <b>Note</b>: Invalidates the iterators
1947
//! to the erased elements.
1948
template<class Disposer>
1949
iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
1950
{ return tree_.erase_and_dispose(b, e, disposer); }
1952
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1954
//! <b>Effects</b>: Erases all the elements with the given value.
1955
//! Disposer::operator()(pointer) is called for the removed elements.
1957
//! <b>Returns</b>: The number of erased elements.
1959
//! <b>Complexity</b>: O(log(size() + this->count(value)).
1961
//! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
1963
//! <b>Note</b>: Invalidates the iterators (but not the references)
1964
//! to the erased elements. No destructors are called.
1965
template<class Disposer>
1966
size_type erase_and_dispose(const_reference value, Disposer disposer)
1967
{ return tree_.erase_and_dispose(value, disposer); }
1969
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1971
//! <b>Effects</b>: Erases all the elements with the given key.
1972
//! according to the comparison functor "comp".
1973
//! Disposer::operator()(pointer) is called for the removed elements.
1975
//! <b>Returns</b>: The number of erased elements.
1977
//! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
1979
//! <b>Throws</b>: If comp or internal priority_compare ordering functions throw. Basic guarantee.
1981
//! <b>Note</b>: Invalidates the iterators
1982
//! to the erased elements.
1983
template<class KeyType, class KeyValueCompare, class Disposer>
1984
size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
1986
, typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
1989
{ return tree_.erase_and_dispose(key, comp, disposer); }
1991
//! <b>Effects</b>: Erases all the elements of the container.
1993
//! <b>Complexity</b>: Linear to the number of elements on the container.
1994
//! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1996
//! <b>Throws</b>: Nothing.
1998
//! <b>Note</b>: Invalidates the iterators (but not the references)
1999
//! to the erased elements. No destructors are called.
2001
{ return tree_.clear(); }
2003
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
2005
//! <b>Effects</b>: Erases all the elements of the container.
2007
//! <b>Complexity</b>: Linear to the number of elements on the container.
2008
//! Disposer::operator()(pointer) is called for the removed elements.
2010
//! <b>Throws</b>: Nothing.
2012
//! <b>Note</b>: Invalidates the iterators (but not the references)
2013
//! to the erased elements. No destructors are called.
2014
template<class Disposer>
2015
void clear_and_dispose(Disposer disposer)
2016
{ return tree_.clear_and_dispose(disposer); }
2018
//! <b>Effects</b>: Returns the number of contained elements with the given key
2020
//! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
2021
//! to number of objects with the given key.
2023
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2024
size_type count(const_reference value) const
2025
{ return tree_.count(value); }
2027
//! <b>Effects</b>: Returns the number of contained elements with the same key
2028
//! compared with the given comparison functor.
2030
//! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
2031
//! to number of objects with the given key.
2033
//! <b>Throws</b>: If comp ordering function throws.
2034
template<class KeyType, class KeyValueCompare>
2035
size_type count(const KeyType& key, KeyValueCompare comp) const
2036
{ return tree_.count(key, comp); }
2038
//! <b>Effects</b>: Returns an iterator to the first element whose
2039
//! key is not less than k or end() if that element does not exist.
2041
//! <b>Complexity</b>: Logarithmic.
2043
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2044
iterator lower_bound(const_reference value)
2045
{ return tree_.lower_bound(value); }
2047
//! <b>Requires</b>: comp must imply the same element order as
2048
//! value_compare. Usually key is the part of the value_type
2049
//! that is used in the ordering functor.
2051
//! <b>Effects</b>: Returns an iterator to the first element whose
2052
//! key according to the comparison functor is not less than k or
2053
//! end() if that element does not exist.
2055
//! <b>Complexity</b>: Logarithmic.
2057
//! <b>Throws</b>: If comp ordering function throws.
2059
//! <b>Note</b>: This function is used when constructing a value_type
2060
//! is expensive and the value_type can be compared with a cheaper
2061
//! key type. Usually this key is part of the value_type.
2062
template<class KeyType, class KeyValueCompare>
2063
iterator lower_bound(const KeyType& key, KeyValueCompare comp)
2064
{ return tree_.lower_bound(key, comp); }
2066
//! <b>Effects</b>: Returns a const iterator to the first element whose
2067
//! key is not less than k or end() if that element does not exist.
2069
//! <b>Complexity</b>: Logarithmic.
2071
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2072
const_iterator lower_bound(const_reference value) const
2073
{ return tree_.lower_bound(value); }
2075
//! <b>Requires</b>: comp must imply the same element order as
2076
//! value_compare. Usually key is the part of the value_type
2077
//! that is used in the ordering functor.
2079
//! <b>Effects</b>: Returns a const_iterator to the first element whose
2080
//! key according to the comparison functor is not less than k or
2081
//! end() if that element does not exist.
2083
//! <b>Complexity</b>: Logarithmic.
2085
//! <b>Throws</b>: If comp ordering function throws.
2087
//! <b>Note</b>: This function is used when constructing a value_type
2088
//! is expensive and the value_type can be compared with a cheaper
2089
//! key type. Usually this key is part of the value_type.
2090
template<class KeyType, class KeyValueCompare>
2091
const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
2092
{ return tree_.lower_bound(key, comp); }
2094
//! <b>Effects</b>: Returns an iterator to the first element whose
2095
//! key is greater than k or end() if that element does not exist.
2097
//! <b>Complexity</b>: Logarithmic.
2099
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2100
iterator upper_bound(const_reference value)
2101
{ return tree_.upper_bound(value); }
2103
//! <b>Requires</b>: comp must imply the same element order as
2104
//! value_compare. Usually key is the part of the value_type
2105
//! that is used in the ordering functor.
2107
//! <b>Effects</b>: Returns an iterator to the first element whose
2108
//! key according to the comparison functor is greater than key or
2109
//! end() if that element does not exist.
2111
//! <b>Complexity</b>: Logarithmic.
2113
//! <b>Throws</b>: If comp ordering function throws.
2115
//! <b>Note</b>: This function is used when constructing a value_type
2116
//! is expensive and the value_type can be compared with a cheaper
2117
//! key type. Usually this key is part of the value_type.
2118
template<class KeyType, class KeyValueCompare>
2119
iterator upper_bound(const KeyType& key, KeyValueCompare comp)
2120
{ return tree_.upper_bound(key, comp); }
2122
//! <b>Effects</b>: Returns an iterator to the first element whose
2123
//! key is greater than k or end() if that element does not exist.
2125
//! <b>Complexity</b>: Logarithmic.
2127
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2128
const_iterator upper_bound(const_reference value) const
2129
{ return tree_.upper_bound(value); }
2131
//! <b>Requires</b>: comp must imply the same element order as
2132
//! value_compare. Usually key is the part of the value_type
2133
//! that is used in the ordering functor.
2135
//! <b>Effects</b>: Returns a const_iterator to the first element whose
2136
//! key according to the comparison functor is greater than key or
2137
//! end() if that element does not exist.
2139
//! <b>Complexity</b>: Logarithmic.
2141
//! <b>Throws</b>: If comp ordering function throws.
2143
//! <b>Note</b>: This function is used when constructing a value_type
2144
//! is expensive and the value_type can be compared with a cheaper
2145
//! key type. Usually this key is part of the value_type.
2146
template<class KeyType, class KeyValueCompare>
2147
const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
2148
{ return tree_.upper_bound(key, comp); }
2150
//! <b>Effects</b>: Finds an iterator to the first element whose value is
2151
//! "value" or end() if that element does not exist.
2153
//! <b>Complexity</b>: Logarithmic.
2155
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2156
iterator find(const_reference value)
2157
{ return tree_.find(value); }
2159
//! <b>Requires</b>: comp must imply the same element order as
2160
//! value_compare. Usually key is the part of the value_type
2161
//! that is used in the ordering functor.
2163
//! <b>Effects</b>: Finds an iterator to the first element whose key is
2164
//! "key" according to the comparison functor or end() if that element
2167
//! <b>Complexity</b>: Logarithmic.
2169
//! <b>Throws</b>: If comp ordering function throws.
2171
//! <b>Note</b>: This function is used when constructing a value_type
2172
//! is expensive and the value_type can be compared with a cheaper
2173
//! key type. Usually this key is part of the value_type.
2174
template<class KeyType, class KeyValueCompare>
2175
iterator find(const KeyType& key, KeyValueCompare comp)
2176
{ return tree_.find(key, comp); }
2178
//! <b>Effects</b>: Finds a const_iterator to the first element whose value is
2179
//! "value" or end() if that element does not exist.
2181
//! <b>Complexity</b>: Logarithmic.
2183
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2184
const_iterator find(const_reference value) const
2185
{ return tree_.find(value); }
2187
//! <b>Requires</b>: comp must imply the same element order as
2188
//! value_compare. Usually key is the part of the value_type
2189
//! that is used in the ordering functor.
2191
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
2192
//! "key" according to the comparison functor or end() if that element
2195
//! <b>Complexity</b>: Logarithmic.
2197
//! <b>Throws</b>: If comp ordering function throws.
2199
//! <b>Note</b>: This function is used when constructing a value_type
2200
//! is expensive and the value_type can be compared with a cheaper
2201
//! key type. Usually this key is part of the value_type.
2202
template<class KeyType, class KeyValueCompare>
2203
const_iterator find(const KeyType& key, KeyValueCompare comp) const
2204
{ return tree_.find(key, comp); }
2206
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
2207
//! an empty range that indicates the position where those elements would be
2208
//! if they there is no elements with key k.
2210
//! <b>Complexity</b>: Logarithmic.
2212
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2213
std::pair<iterator,iterator> equal_range(const_reference value)
2214
{ return tree_.equal_range(value); }
2216
//! <b>Requires</b>: comp must imply the same element order as
2217
//! value_compare. Usually key is the part of the value_type
2218
//! that is used in the ordering functor.
2220
//! <b>Effects</b>: Finds a range containing all elements whose key is k
2221
//! according to the comparison functor or an empty range
2222
//! that indicates the position where those elements would be
2223
//! if they there is no elements with key k.
2225
//! <b>Complexity</b>: Logarithmic.
2227
//! <b>Throws</b>: If comp ordering function throws.
2229
//! <b>Note</b>: This function is used when constructing a value_type
2230
//! is expensive and the value_type can be compared with a cheaper
2231
//! key type. Usually this key is part of the value_type.
2232
template<class KeyType, class KeyValueCompare>
2233
std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
2234
{ return tree_.equal_range(key, comp); }
2236
//! <b>Effects</b>: Finds a range containing all elements whose key is k or
2237
//! an empty range that indicates the position where those elements would be
2238
//! if they there is no elements with key k.
2240
//! <b>Complexity</b>: Logarithmic.
2242
//! <b>Throws</b>: If the internal value_compare ordering function throws.
2243
std::pair<const_iterator, const_iterator>
2244
equal_range(const_reference value) const
2245
{ return tree_.equal_range(value); }
2247
//! <b>Requires</b>: comp must imply the same element order as
2248
//! value_compare. Usually key is the part of the value_type
2249
//! that is used in the ordering functor.
2251
//! <b>Effects</b>: Finds a range containing all elements whose key is k
2252
//! according to the comparison functor or an empty range
2253
//! that indicates the position where those elements would be
2254
//! if they there is no elements with key k.
2256
//! <b>Complexity</b>: Logarithmic.
2258
//! <b>Throws</b>: If comp ordering function throws.
2260
//! <b>Note</b>: This function is used when constructing a value_type
2261
//! is expensive and the value_type can be compared with a cheaper
2262
//! key type. Usually this key is part of the value_type.
2263
template<class KeyType, class KeyValueCompare>
2264
std::pair<const_iterator, const_iterator>
2265
equal_range(const KeyType& key, KeyValueCompare comp) const
2266
{ return tree_.equal_range(key, comp); }
2268
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_multiset of
2269
//! appropriate type. Otherwise the behavior is undefined.
2271
//! <b>Effects</b>: Returns: a valid iterator i belonging to the treap_multiset
2272
//! that points to the value
2274
//! <b>Complexity</b>: Constant.
2276
//! <b>Throws</b>: Nothing.
2278
//! <b>Note</b>: This static function is available only if the <i>value traits</i>
2280
static iterator s_iterator_to(reference value)
2281
{ return tree_type::s_iterator_to(value); }
2283
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_multiset of
2284
//! appropriate type. Otherwise the behavior is undefined.
2286
//! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
2287
//! treap_multiset that points to the value
2289
//! <b>Complexity</b>: Constant.
2291
//! <b>Throws</b>: Nothing.
2293
//! <b>Note</b>: This static function is available only if the <i>value traits</i>
2295
static const_iterator s_iterator_to(const_reference value)
2296
{ return tree_type::s_iterator_to(value); }
2298
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_multiset of
2299
//! appropriate type. Otherwise the behavior is undefined.
2301
//! <b>Effects</b>: Returns: a valid iterator i belonging to the treap_multiset
2302
//! that points to the value
2304
//! <b>Complexity</b>: Constant.
2306
//! <b>Throws</b>: Nothing.
2307
iterator iterator_to(reference value)
2308
{ return tree_.iterator_to(value); }
2310
//! <b>Requires</b>: value must be an lvalue and shall be in a treap_multiset of
2311
//! appropriate type. Otherwise the behavior is undefined.
2313
//! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
2314
//! treap_multiset that points to the value
2316
//! <b>Complexity</b>: Constant.
2318
//! <b>Throws</b>: Nothing.
2319
const_iterator iterator_to(const_reference value) const
2320
{ return tree_.iterator_to(value); }
2322
//! <b>Requires</b>: value shall not be in a treap_multiset/treap_multiset.
2324
//! <b>Effects</b>: init_node puts the hook of a value in a well-known default
2327
//! <b>Throws</b>: Nothing.
2329
//! <b>Complexity</b>: Constant time.
2331
//! <b>Note</b>: This function puts the hook in the well-known default state
2332
//! used by auto_unlink and safe hooks.
2333
static void init_node(reference value)
2334
{ tree_type::init_node(value); }
2336
//! <b>Effects</b>: Unlinks the leftmost node from the tree.
2338
//! <b>Complexity</b>: Average complexity is constant time.
2340
//! <b>Throws</b>: Nothing.
2342
//! <b>Notes</b>: This function breaks the tree and the tree can
2343
//! only be used for more unlink_leftmost_without_rebalance calls.
2344
//! This function is normally used to achieve a step by step
2345
//! controlled destruction of the tree.
2346
pointer unlink_leftmost_without_rebalance()
2347
{ return tree_.unlink_leftmost_without_rebalance(); }
2349
//! <b>Requires</b>: replace_this must be a valid iterator of *this
2350
//! and with_this must not be inserted in any tree.
2352
//! <b>Effects</b>: Replaces replace_this in its position in the
2353
//! tree with with_this. The tree does not need to be rebalanced.
2355
//! <b>Complexity</b>: Constant.
2357
//! <b>Throws</b>: Nothing.
2359
//! <b>Note</b>: This function will break container ordering invariants if
2360
//! with_this is not equivalent to *replace_this according to the
2361
//! ordering rules. This function is faster than erasing and inserting
2362
//! the node, since no rebalancing or comparison is needed.
2363
void replace_node(iterator replace_this, reference with_this)
2364
{ tree_.replace_node(replace_this, with_this); }
2366
//! <b>Effects</b>: Rebalances the tree.
2368
//! <b>Throws</b>: Nothing.
2370
//! <b>Complexity</b>: Linear.
2372
{ tree_.rebalance(); }
2374
//! <b>Requires</b>: old_root is a node of a tree.
2376
//! <b>Effects</b>: Rebalances the subtree rooted at old_root.
2378
//! <b>Returns</b>: The new root of the subtree.
2380
//! <b>Throws</b>: Nothing.
2382
//! <b>Complexity</b>: Linear to the elements in the subtree.
2383
iterator rebalance_subtree(iterator root)
2384
{ return tree_.rebalance_subtree(root); }
2386
//! <b>Returns</b>: The balance factor (alpha) used in this tree
2388
//! <b>Throws</b>: Nothing.
2390
//! <b>Complexity</b>: Constant.
2391
float balance_factor() const
2392
{ return tree_.balance_factor(); }
2394
//! <b>Requires</b>: new_alpha must be a value between 0.5 and 1.0
2396
//! <b>Effects</b>: Establishes a new balance factor (alpha) and rebalances
2397
//! the tree if the new balance factor is stricter (less) than the old factor.
2399
//! <b>Throws</b>: Nothing.
2401
//! <b>Complexity</b>: Linear to the elements in the subtree.
2402
void balance_factor(float new_alpha)
2403
{ tree_.balance_factor(new_alpha); }
2406
friend bool operator==(const treap_multiset_impl &x, const treap_multiset_impl &y)
2407
{ return x.tree_ == y.tree_; }
2409
friend bool operator<(const treap_multiset_impl &x, const treap_multiset_impl &y)
2410
{ return x.tree_ < y.tree_; }
2414
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2415
template<class T, class ...Options>
2417
template<class Config>
2419
inline bool operator!=
2420
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2421
(const treap_multiset_impl<T, Options...> &x, const treap_multiset_impl<T, Options...> &y)
2423
(const treap_multiset_impl<Config> &x, const treap_multiset_impl<Config> &y)
2425
{ return !(x == y); }
2427
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2428
template<class T, class ...Options>
2430
template<class Config>
2432
inline bool operator>
2433
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2434
(const treap_multiset_impl<T, Options...> &x, const treap_multiset_impl<T, Options...> &y)
2436
(const treap_multiset_impl<Config> &x, const treap_multiset_impl<Config> &y)
2440
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2441
template<class T, class ...Options>
2443
template<class Config>
2445
inline bool operator<=
2446
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2447
(const treap_multiset_impl<T, Options...> &x, const treap_multiset_impl<T, Options...> &y)
2449
(const treap_multiset_impl<Config> &x, const treap_multiset_impl<Config> &y)
2451
{ return !(y < x); }
2453
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2454
template<class T, class ...Options>
2456
template<class Config>
2458
inline bool operator>=
2459
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2460
(const treap_multiset_impl<T, Options...> &x, const treap_multiset_impl<T, Options...> &y)
2462
(const treap_multiset_impl<Config> &x, const treap_multiset_impl<Config> &y)
2464
{ return !(x < y); }
2466
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2467
template<class T, class ...Options>
2469
template<class Config>
2472
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2473
(treap_multiset_impl<T, Options...> &x, treap_multiset_impl<T, Options...> &y)
2475
(treap_multiset_impl<Config> &x, treap_multiset_impl<Config> &y)
2479
//! Helper metafunction to define a \c treap_multiset that yields to the same type when the
2480
//! same options (either explicitly or implicitly) are used.
2481
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2482
template<class T, class ...Options>
2484
template<class T, class O1 = none, class O2 = none
2485
, class O3 = none, class O4 = none>
2487
struct make_treap_multiset
2490
typedef treap_multiset_impl
2491
< typename make_treap_opt<T,
2492
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2498
> implementation_defined;
2500
typedef implementation_defined type;
2503
#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2505
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2506
template<class T, class O1, class O2, class O3, class O4>
2508
template<class T, class ...Options>
2510
class treap_multiset
2511
: public make_treap_multiset<T,
2512
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2519
typedef typename make_treap_multiset
2521
#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2528
BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset)
2531
typedef typename Base::value_compare value_compare;
2532
typedef typename Base::priority_compare priority_compare;
2533
typedef typename Base::value_traits value_traits;
2534
typedef typename Base::iterator iterator;
2535
typedef typename Base::const_iterator const_iterator;
2537
//Assert if passed value traits are compatible with the type
2538
BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
2540
treap_multiset( const value_compare &cmp = value_compare()
2541
, const priority_compare &pcmp = priority_compare()
2542
, const value_traits &v_traits = value_traits())
2543
: Base(cmp, pcmp, v_traits)
2546
template<class Iterator>
2547
treap_multiset( Iterator b, Iterator e
2548
, const value_compare &cmp = value_compare()
2549
, const priority_compare &pcmp = priority_compare()
2550
, const value_traits &v_traits = value_traits())
2551
: Base(b, e, cmp, pcmp, v_traits)
2554
treap_multiset(BOOST_RV_REF(treap_multiset) x)
2555
: Base(::boost::move(static_cast<Base&>(x)))
2558
treap_multiset& operator=(BOOST_RV_REF(treap_multiset) x)
2559
{ this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
2561
static treap_multiset &container_from_end_iterator(iterator end_iterator)
2562
{ return static_cast<treap_multiset &>(Base::container_from_end_iterator(end_iterator)); }
2564
static const treap_multiset &container_from_end_iterator(const_iterator end_iterator)
2565
{ return static_cast<const treap_multiset &>(Base::container_from_end_iterator(end_iterator)); }
2567
static treap_multiset &container_from_iterator(iterator it)
2568
{ return static_cast<treap_multiset &>(Base::container_from_iterator(it)); }
2570
static const treap_multiset &container_from_iterator(const_iterator it)
2571
{ return static_cast<const treap_multiset &>(Base::container_from_iterator(it)); }
2576
} //namespace intrusive
2579
#include <boost/intrusive/detail/config_end.hpp>
2581
#endif //BOOST_INTRUSIVE_TRIE_SET_HPP