]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/boost/intrusive/treap_set.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
update ceph source to reef 18.1.2
[ceph.git] / ceph / src / boost / boost / intrusive / treap_set.hpp
CommitLineData
7c673cae
FG		 1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2007-2014
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9// See http://www.boost.org/libs/intrusive for documentation.
10//
11/////////////////////////////////////////////////////////////////////////////
12#ifndef BOOST_INTRUSIVE_TREAP_SET_HPP
13#define BOOST_INTRUSIVE_TREAP_SET_HPP
14
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/utility_core.hpp>
20#include <boost/static_assert.hpp>
21
22#if defined(BOOST_HAS_PRAGMA_ONCE)
23# pragma once
24#endif
25
26namespace boost {
27namespace intrusive {
28
29#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
92f5a8d4 30template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
7c673cae
FG		 31class treap_multiset_impl;
32#endif
33
34//! The class template treap_set is an intrusive container, that mimics most of
35//! the interface of std::set as described in the C++ standard.
36//!
37//! The template parameter \c T is the type to be managed by the container.
38//! The user can specify additional options and if no options are provided
39//! default options are used.
40//!
41//! The container supports the following options:
42//! \c base_hook<>/member_hook<>/value_traits<>,
43//! \c constant_time_size<>, \c size_type<>,
92f5a8d4 44//! \c compare<>, \c priority<> and \c priority_of_value<>
7c673cae
FG		 45#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
46template<class T, class ...Options>
47#else
92f5a8d4 48template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
7c673cae
FG		 49#endif
50class treap_set_impl
51#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
92f5a8d4 52 : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
7c673cae
FG		 53#endif
54{
55 /// @cond
56 public:
92f5a8d4 57 typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
7c673cae
FG		 58 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set_impl)
59
60 typedef tree_type implementation_defined;
61 /// @endcond
62
63 public:
64 typedef typename implementation_defined::value_type value_type;
65 typedef typename implementation_defined::value_traits value_traits;
66 typedef typename implementation_defined::key_type key_type;
67 typedef typename implementation_defined::key_of_value key_of_value;
68 typedef typename implementation_defined::pointer pointer;
69 typedef typename implementation_defined::const_pointer const_pointer;
70 typedef typename implementation_defined::reference reference;
71 typedef typename implementation_defined::const_reference const_reference;
72 typedef typename implementation_defined::difference_type difference_type;
73 typedef typename implementation_defined::size_type size_type;
74 typedef typename implementation_defined::value_compare value_compare;
75 typedef typename implementation_defined::key_compare key_compare;
92f5a8d4 76 typedef typename implementation_defined::priority_type priority_type;
7c673cae
FG		 77 typedef typename implementation_defined::priority_compare priority_compare;
78 typedef typename implementation_defined::iterator iterator;
79 typedef typename implementation_defined::const_iterator const_iterator;
80 typedef typename implementation_defined::reverse_iterator reverse_iterator;
81 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
82 typedef typename implementation_defined::insert_commit_data insert_commit_data;
83 typedef typename implementation_defined::node_traits node_traits;
84 typedef typename implementation_defined::node node;
85 typedef typename implementation_defined::node_ptr node_ptr;
86 typedef typename implementation_defined::const_node_ptr const_node_ptr;
87 typedef typename implementation_defined::node_algorithms node_algorithms;
88
89 static const bool constant_time_size = implementation_defined::constant_time_size;
90
91 public:
92 //! @copydoc ::boost::intrusive::treap::treap()
93 treap_set_impl()
94 : tree_type()
95 {}
96
97 //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
98 explicit treap_set_impl( const key_compare &cmp
99 , const priority_compare &pcmp = priority_compare()
100 , const value_traits &v_traits = value_traits())
101 : tree_type(cmp, pcmp, v_traits)
102 {}
103
104 //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
105 template<class Iterator>
106 treap_set_impl( Iterator b, Iterator e
107 , const key_compare &cmp = key_compare()
108 , const priority_compare &pcmp = priority_compare()
109 , const value_traits &v_traits = value_traits())
110 : tree_type(true, b, e, cmp, pcmp, v_traits)
111 {}
112
113 //! <b>Effects</b>: to-do
114 //!
115 treap_set_impl(BOOST_RV_REF(treap_set_impl) x)
116 : tree_type(BOOST_MOVE_BASE(tree_type, x))
117 {}
118
119 //! <b>Effects</b>: to-do
120 //!
121 treap_set_impl& operator=(BOOST_RV_REF(treap_set_impl) x)
122 { return static_cast<treap_set_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
123
124 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
125 //! @copydoc ::boost::intrusive::treap::~treap()
126 ~treap_set_impl();
127
128 //! @copydoc ::boost::intrusive::treap::begin()
1e59de90 129 iterator begin() BOOST_NOEXCEPT;
7c673cae
FG		 130
131 //! @copydoc ::boost::intrusive::treap::begin()const
1e59de90 132 const_iterator begin() const BOOST_NOEXCEPT;
7c673cae
FG		 133
134 //! @copydoc ::boost::intrusive::treap::cbegin()const
1e59de90 135 const_iterator cbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 136
137 //! @copydoc ::boost::intrusive::treap::end()
1e59de90 138 iterator end() BOOST_NOEXCEPT;
7c673cae
FG		 139
140 //! @copydoc ::boost::intrusive::treap::end()const
1e59de90 141 const_iterator end() const BOOST_NOEXCEPT;
7c673cae
FG		 142
143 //! @copydoc ::boost::intrusive::treap::cend()const
1e59de90 144 const_iterator cend() const BOOST_NOEXCEPT;
7c673cae
FG		 145
146 //! @copydoc ::boost::intrusive::treap::rbegin()
1e59de90 147 reverse_iterator rbegin() BOOST_NOEXCEPT;
7c673cae
FG		 148
149 //! @copydoc ::boost::intrusive::treap::rbegin()const
1e59de90 150 const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 151
152 //! @copydoc ::boost::intrusive::treap::crbegin()const
1e59de90 153 const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 154
155 //! @copydoc ::boost::intrusive::treap::rend()
1e59de90 156 reverse_iterator rend() BOOST_NOEXCEPT;
7c673cae
FG		 157
158 //! @copydoc ::boost::intrusive::treap::rend()const
1e59de90 159 const_reverse_iterator rend() const BOOST_NOEXCEPT;
7c673cae
FG		 160
161 //! @copydoc ::boost::intrusive::treap::crend()const
1e59de90 162 const_reverse_iterator crend() const BOOST_NOEXCEPT;
7c673cae
FG		 163
164 //! @copydoc ::boost::intrusive::treap::root()
1e59de90 165 iterator root() BOOST_NOEXCEPT;
7c673cae
FG		 166
167 //! @copydoc ::boost::intrusive::treap::root()const
1e59de90 168 const_iterator root() const BOOST_NOEXCEPT;
7c673cae
FG		 169
170 //! @copydoc ::boost::intrusive::treap::croot()const
1e59de90 171 const_iterator croot() const BOOST_NOEXCEPT;
7c673cae
FG		 172
173 //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
1e59de90 174 static treap_set_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
7c673cae
FG		 175
176 //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
1e59de90 177 static const treap_set_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
7c673cae
FG		 178
179 //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
1e59de90 180 static treap_set_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
7c673cae
FG		 181
182 //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
1e59de90 183 static const treap_set_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
7c673cae
FG		 184
185 //! @copydoc ::boost::intrusive::treap::key_comp()const
186 key_compare key_comp() const;
187
188 //! @copydoc ::boost::intrusive::treap::value_comp()const
189 value_compare value_comp() const;
190
191 //! @copydoc ::boost::intrusive::treap::empty()const
1e59de90 192 bool empty() const BOOST_NOEXCEPT;
7c673cae
FG		 193
194 //! @copydoc ::boost::intrusive::treap::size()const
1e59de90 195 size_type size() const BOOST_NOEXCEPT;
7c673cae
FG		 196
197 //! @copydoc ::boost::intrusive::treap::swap
198 void swap(treap_set_impl& other);
199
200 //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
201 template <class Cloner, class Disposer>
202 void clone_from(const treap_set_impl &src, Cloner cloner, Disposer disposer);
203
204 #else
205
206 using tree_type::clone_from;
207
208 #endif
209
210 //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
211 template <class Cloner, class Disposer>
212 void clone_from(BOOST_RV_REF(treap_set_impl) src, Cloner cloner, Disposer disposer)
213 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); }
214
215 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
216
217 //! @copydoc ::boost::intrusive::treap::top()
1e59de90 218 BOOST_INTRUSIVE_FORCEINLINE iterator top() BOOST_NOEXCEPT;
7c673cae
FG		 219
220 //! @copydoc ::boost::intrusive::treap::top()const
1e59de90 221 BOOST_INTRUSIVE_FORCEINLINE const_iterator top() const BOOST_NOEXCEPT;
7c673cae
FG		 222
223 //! @copydoc ::boost::intrusive::treap::ctop()const
1e59de90 224 BOOST_INTRUSIVE_FORCEINLINE const_iterator ctop() const BOOST_NOEXCEPT;
7c673cae
FG		 225
226 //! @copydoc ::boost::intrusive::treap::rtop()
1e59de90 227 BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rtop() BOOST_NOEXCEPT;
7c673cae
FG		 228
229 //! @copydoc ::boost::intrusive::treap::rtop()const
1e59de90 230 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rtop() const BOOST_NOEXCEPT;
7c673cae
FG		 231
232 //! @copydoc ::boost::intrusive::treap::crtop()const
1e59de90 233 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crtop() const BOOST_NOEXCEPT;
7c673cae
FG		 234
235 //! @copydoc ::boost::intrusive::treap::crtop() const
236 priority_compare priority_comp() const;
237 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
238
239 //! @copydoc ::boost::intrusive::treap::insert_unique(reference)
240 std::pair<iterator, bool> insert(reference value)
241 { return tree_type::insert_unique(value); }
242
243 //! @copydoc ::boost::intrusive::treap::insert_unique(const_iterator,reference)
244 iterator insert(const_iterator hint, reference value)
245 { return tree_type::insert_unique(hint, value); }
246
92f5a8d4
TL		 247 //! @copydoc ::boost::intrusive::treap::insert_unique_check(const key_type&,const priority_type &,insert_commit_data&)
248 std::pair<iterator, bool> insert_check( const key_type &key, const priority_type &prio, insert_commit_data &commit_data)
249 { return tree_type::insert_unique_check(key, prio, commit_data); }
7c673cae 250
92f5a8d4 251 //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const key_type&,const priority_type &,insert_commit_data&)
7c673cae 252 std::pair<iterator, bool> insert_check
92f5a8d4
TL		 253 ( const_iterator hint, const key_type &key, const priority_type &prio, insert_commit_data &commit_data)
254 { return tree_type::insert_unique_check(hint, key, prio, commit_data); }
7c673cae 255
92f5a8d4
TL		 256 //! @copydoc ::boost::intrusive::treap::insert_unique_check(const KeyType&,KeyTypeKeyCompare,PrioValuePrioCompare,insert_commit_data&)
257 template<class KeyType, class KeyTypeKeyCompare, class PrioType, class PrioValuePrioCompare>
7c673cae 258 std::pair<iterator, bool> insert_check
92f5a8d4 259 ( const KeyType &key, KeyTypeKeyCompare comp, const PrioType &prio, PrioValuePrioCompare pcomp
7c673cae 260 , insert_commit_data &commit_data)
92f5a8d4 261 { return tree_type::insert_unique_check(key, comp, prio, pcomp, commit_data); }
7c673cae 262
92f5a8d4
TL		 263 //! @copydoc ::boost::intrusive::treap::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,PrioValuePrioCompare,insert_commit_data&)
264 template<class KeyType, class KeyTypeKeyCompare, class PrioType, class PrioValuePrioCompare>
7c673cae 265 std::pair<iterator, bool> insert_check
92f5a8d4
TL		 266 ( const_iterator hint
267 , const KeyType &key, KeyTypeKeyCompare comp
268 , const PrioType &prio, PrioValuePrioCompare pcomp
7c673cae 269 , insert_commit_data &commit_data)
92f5a8d4 270 { return tree_type::insert_unique_check(hint, key, comp, prio, pcomp, commit_data); }
7c673cae
FG		 271
272 //! @copydoc ::boost::intrusive::treap::insert_unique(Iterator,Iterator)
273 template<class Iterator>
274 void insert(Iterator b, Iterator e)
275 { tree_type::insert_unique(b, e); }
276
277 //! @copydoc ::boost::intrusive::treap::insert_unique_commit
1e59de90 278 iterator insert_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
7c673cae
FG		 279 { return tree_type::insert_unique_commit(value, commit_data); }
280
281 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
282 //! @copydoc ::boost::intrusive::treap::insert_before
1e59de90 283 iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
7c673cae
FG		 284
285 //! @copydoc ::boost::intrusive::treap::push_back
1e59de90 286 void push_back(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 287
288 //! @copydoc ::boost::intrusive::treap::push_front
1e59de90 289 void push_front(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 290
291 //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
1e59de90 292 iterator erase(const_iterator i) BOOST_NOEXCEPT;
7c673cae
FG		 293
294 //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
1e59de90 295 iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
7c673cae
FG		 296
297 //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
298 size_type erase(const key_type &key);
299
300 //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
301 template<class KeyType, class KeyTypeKeyCompare>
302 size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
303
304 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
305 template<class Disposer>
1e59de90 306 iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 307
308 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
309 template<class Disposer>
1e59de90 310 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 311
312 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
313 template<class Disposer>
314 size_type erase_and_dispose(const key_type &key, Disposer disposer);
315
316 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
317 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
318 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
319
320 //! @copydoc ::boost::intrusive::treap::clear
1e59de90 321 void clear() BOOST_NOEXCEPT;
7c673cae
FG		 322
323 //! @copydoc ::boost::intrusive::treap::clear_and_dispose
324 template<class Disposer>
1e59de90 325 void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 326
327 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
328
329 //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
330 size_type count(const key_type &key) const
331 { return static_cast<size_type>(this->tree_type::find(key) != this->tree_type::cend()); }
332
333 //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
334 template<class KeyType, class KeyTypeKeyCompare>
335 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const
336 { return static_cast<size_type>(this->tree_type::find(key, comp) != this->tree_type::cend()); }
337
338 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
339
340 //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
341 iterator lower_bound(const key_type &key);
342
343 //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
344 template<class KeyType, class KeyTypeKeyCompare>
345 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
346
347 //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
348 const_iterator lower_bound(const key_type &key) const;
349
350 //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
351 template<class KeyType, class KeyTypeKeyCompare>
352 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
353
354 //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
355 iterator upper_bound(const key_type &key);
356
357 //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
358 template<class KeyType, class KeyTypeKeyCompare>
359 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
360
361 //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
362 const_iterator upper_bound(const key_type &key) const;
363
364 //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
365 template<class KeyType, class KeyTypeKeyCompare>
366 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
367
368 //! @copydoc ::boost::intrusive::treap::find(const key_type &)
369 iterator find(const key_type &key);
370
371 //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
372 template<class KeyType, class KeyTypeKeyCompare>
373 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
374
375 //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
376 const_iterator find(const key_type &key) const;
377
378 //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
379 template<class KeyType, class KeyTypeKeyCompare>
380 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
381
382 #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
383
384 //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
385 std::pair<iterator,iterator> equal_range(const key_type &key)
386 { return this->tree_type::lower_bound_range(key); }
387
388 //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
389 template<class KeyType, class KeyTypeKeyCompare>
390 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp)
391 { return this->tree_type::equal_range(key, comp); }
392
393 //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
394 std::pair<const_iterator, const_iterator>
395 equal_range(const key_type &key) const
396 { return this->tree_type::lower_bound_range(key); }
397
398 //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
399 template<class KeyType, class KeyTypeKeyCompare>
400 std::pair<const_iterator, const_iterator>
401 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const
402 { return this->tree_type::equal_range(key, comp); }
403
404 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
405
406 //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
407 std::pair<iterator,iterator> bounded_range
408 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
409
410 //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
411 template<class KeyType, class KeyTypeKeyCompare>
412 std::pair<iterator,iterator> bounded_range
413 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
414
415 //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
416 std::pair<const_iterator, const_iterator>
417 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
418
419 //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
420 template<class KeyType, class KeyTypeKeyCompare>
421 std::pair<const_iterator, const_iterator> bounded_range
422 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
423
424 //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
1e59de90 425 static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 426
427 //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
1e59de90 428 static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
7c673cae
FG		 429
430 //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
1e59de90 431 iterator iterator_to(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 432
433 //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
1e59de90 434 const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
7c673cae
FG		 435
436 //! @copydoc ::boost::intrusive::treap::init_node(reference)
1e59de90 437 static void init_node(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 438
439 //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
1e59de90 440 pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
7c673cae
FG		 441
442 //! @copydoc ::boost::intrusive::treap::replace_node
1e59de90 443 void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
7c673cae
FG		 444
445 //! @copydoc ::boost::intrusive::treap::remove_node
1e59de90 446 void remove_node(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 447
448
449 //! @copydoc ::boost::intrusive::treap::merge_unique
450 template<class ...Options2>
451 void merge(treap_set<T, Options2...> &source);
452
453 //! @copydoc ::boost::intrusive::treap::merge_unique
454 template<class ...Options2>
455 void merge(treap_multiset<T, Options2...> &source);
456
457 #else
458
459 template<class Compare2>
92f5a8d4 460 void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
7c673cae
FG		 461 { return tree_type::merge_unique(source); }
462
463 template<class Compare2>
92f5a8d4 464 void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
7c673cae
FG		 465 { return tree_type::merge_unique(source); }
466
467 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
468};
469
470
471//! Helper metafunction to define a \c treap_set that yields to the same type when the
472//! same options (either explicitly or implicitly) are used.
473#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
474template<class T, class ...Options>
475#else
476template<class T, class O1 = void, class O2 = void
477 , class O3 = void, class O4 = void
92f5a8d4
TL		 478 , class O5 = void, class O6 = void
479 , class O7 = void>
7c673cae
FG		 480#endif
481struct make_treap_set
482{
483 typedef typename pack_options
484 < treap_defaults,
485 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 486 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 487 #else
488 Options...
489 #endif
490 >::type packed_options;
491
492 typedef typename detail::get_value_traits
493 <T, typename packed_options::proto_value_traits>::type value_traits;
494
495 typedef treap_set_impl
496 < value_traits
497 , typename packed_options::key_of_value
498 , typename packed_options::compare
92f5a8d4 499 , typename packed_options::priority_of_value
7c673cae
FG		 500 , typename packed_options::priority
501 , typename packed_options::size_type
502 , packed_options::constant_time_size
503 , typename packed_options::header_holder_type
504 > implementation_defined;
505 /// @endcond
506 typedef implementation_defined type;
507};
508
509#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
510
511#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 512template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7>
7c673cae
FG		 513#else
514template<class T, class ...Options>
515#endif
516class treap_set
517 : public make_treap_set<T,
518 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 519 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 520 #else
521 Options...
522 #endif
523 >::type
524{
525 typedef typename make_treap_set
526 <T,
527 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 528 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 529 #else
530 Options...
531 #endif
532 >::type Base;
533 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_set)
534
535 public:
536 typedef typename Base::key_compare key_compare;
537 typedef typename Base::priority_compare priority_compare;
538 typedef typename Base::value_traits value_traits;
539 typedef typename Base::iterator iterator;
540 typedef typename Base::const_iterator const_iterator;
541
542 //Assert if passed value traits are compatible with the type
543 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
544
92f5a8d4 545 BOOST_INTRUSIVE_FORCEINLINE treap_set()
7c673cae
FG		 546 : Base()
547 {}
548
92f5a8d4 549 BOOST_INTRUSIVE_FORCEINLINE explicit treap_set( const key_compare &cmp
7c673cae
FG		 550 , const priority_compare &pcmp = priority_compare()
551 , const value_traits &v_traits = value_traits())
552 : Base(cmp, pcmp, v_traits)
553 {}
554
555 template<class Iterator>
92f5a8d4 556 BOOST_INTRUSIVE_FORCEINLINE treap_set( Iterator b, Iterator e
7c673cae
FG		 557 , const key_compare &cmp = key_compare()
558 , const priority_compare &pcmp = priority_compare()
559 , const value_traits &v_traits = value_traits())
560 : Base(b, e, cmp, pcmp, v_traits)
561 {}
562
92f5a8d4 563 BOOST_INTRUSIVE_FORCEINLINE treap_set(BOOST_RV_REF(treap_set) x)
7c673cae
FG		 564 : Base(BOOST_MOVE_BASE(Base, x))
565 {}
566
92f5a8d4 567 BOOST_INTRUSIVE_FORCEINLINE treap_set& operator=(BOOST_RV_REF(treap_set) x)
7c673cae
FG		 568 { return static_cast<treap_set &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
569
570 template <class Cloner, class Disposer>
92f5a8d4 571 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const treap_set &src, Cloner cloner, Disposer disposer)
7c673cae
FG		 572 { Base::clone_from(src, cloner, disposer); }
573
574 template <class Cloner, class Disposer>
92f5a8d4 575 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(treap_set) src, Cloner cloner, Disposer disposer)
7c673cae
FG		 576 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
577
1e59de90 578 BOOST_INTRUSIVE_FORCEINLINE static treap_set &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
7c673cae
FG		 579 { return static_cast<treap_set &>(Base::container_from_end_iterator(end_iterator)); }
580
1e59de90 581 BOOST_INTRUSIVE_FORCEINLINE static const treap_set &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
7c673cae
FG		 582 { return static_cast<const treap_set &>(Base::container_from_end_iterator(end_iterator)); }
583
1e59de90 584 BOOST_INTRUSIVE_FORCEINLINE static treap_set &container_from_iterator(iterator it) BOOST_NOEXCEPT
7c673cae
FG		 585 { return static_cast<treap_set &>(Base::container_from_iterator(it)); }
586
1e59de90 587 BOOST_INTRUSIVE_FORCEINLINE static const treap_set &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
7c673cae
FG		 588 { return static_cast<const treap_set &>(Base::container_from_iterator(it)); }
589};
590
591#endif
592
593//! The class template treap_multiset is an intrusive container, that mimics most of
594//! the interface of std::treap_multiset as described in the C++ standard.
595//!
596//! The template parameter \c T is the type to be managed by the container.
597//! The user can specify additional options and if no options are provided
598//! default options are used.
599//!
600//! The container supports the following options:
601//! \c base_hook<>/member_hook<>/value_traits<>,
602//! \c constant_time_size<>, \c size_type<>,
92f5a8d4 603//! \c compare<>, \c priority<> and \c priority_of_value<>
7c673cae
FG		 604#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
605template<class T, class ...Options>
606#else
92f5a8d4 607template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class VoidOrPrioOfValue, class VoidOrPrioComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
7c673cae
FG		 608#endif
609class treap_multiset_impl
610#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
92f5a8d4 611 : public treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder>
7c673cae
FG		 612#endif
613{
614 /// @cond
92f5a8d4 615 typedef treap_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> tree_type;
7c673cae
FG		 616 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset_impl)
617
618 typedef tree_type implementation_defined;
619 /// @endcond
620
621 public:
622 typedef typename implementation_defined::value_type value_type;
623 typedef typename implementation_defined::value_traits value_traits;
624 typedef typename implementation_defined::key_type key_type;
625 typedef typename implementation_defined::key_of_value key_of_value;
626 typedef typename implementation_defined::pointer pointer;
627 typedef typename implementation_defined::const_pointer const_pointer;
628 typedef typename implementation_defined::reference reference;
629 typedef typename implementation_defined::const_reference const_reference;
630 typedef typename implementation_defined::difference_type difference_type;
631 typedef typename implementation_defined::size_type size_type;
632 typedef typename implementation_defined::value_compare value_compare;
633 typedef typename implementation_defined::key_compare key_compare;
92f5a8d4 634 typedef typename implementation_defined::priority_type priority_type;
7c673cae
FG		 635 typedef typename implementation_defined::priority_compare priority_compare;
636 typedef typename implementation_defined::iterator iterator;
637 typedef typename implementation_defined::const_iterator const_iterator;
638 typedef typename implementation_defined::reverse_iterator reverse_iterator;
639 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
640 typedef typename implementation_defined::insert_commit_data insert_commit_data;
641 typedef typename implementation_defined::node_traits node_traits;
642 typedef typename implementation_defined::node node;
643 typedef typename implementation_defined::node_ptr node_ptr;
644 typedef typename implementation_defined::const_node_ptr const_node_ptr;
645 typedef typename implementation_defined::node_algorithms node_algorithms;
646
647 static const bool constant_time_size = implementation_defined::constant_time_size;
648
649 public:
650
651 //! @copydoc ::boost::intrusive::treap::treap()
652 treap_multiset_impl()
653 : tree_type()
654 {}
655
656 //! @copydoc ::boost::intrusive::treap::treap(const key_compare &,const priority_compare &,const value_traits &)
657 explicit treap_multiset_impl( const key_compare &cmp
658 , const priority_compare &pcmp = priority_compare()
659 , const value_traits &v_traits = value_traits())
660 : tree_type(cmp, pcmp, v_traits)
661 {}
662
663 //! @copydoc ::boost::intrusive::treap::treap(bool,Iterator,Iterator,const key_compare &,const priority_compare &,const value_traits &)
664 template<class Iterator>
665 treap_multiset_impl( Iterator b, Iterator e
666 , const key_compare &cmp = key_compare()
667 , const priority_compare &pcmp = priority_compare()
668 , const value_traits &v_traits = value_traits())
669 : tree_type(false, b, e, cmp, pcmp, v_traits)
670 {}
671
672 //! <b>Effects</b>: to-do
673 //!
674 treap_multiset_impl(BOOST_RV_REF(treap_multiset_impl) x)
675 : tree_type(BOOST_MOVE_BASE(tree_type, x))
676 {}
677
678 //! <b>Effects</b>: to-do
679 //!
680 treap_multiset_impl& operator=(BOOST_RV_REF(treap_multiset_impl) x)
681 { return static_cast<treap_multiset_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
682
683 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
684 //! @copydoc ::boost::intrusive::treap::~treap()
685 ~treap_multiset_impl();
686
687 //! @copydoc ::boost::intrusive::treap::begin()
1e59de90 688 iterator begin() BOOST_NOEXCEPT;
7c673cae
FG		 689
690 //! @copydoc ::boost::intrusive::treap::begin()const
1e59de90 691 const_iterator begin() const BOOST_NOEXCEPT;
7c673cae
FG		 692
693 //! @copydoc ::boost::intrusive::treap::cbegin()const
1e59de90 694 const_iterator cbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 695
696 //! @copydoc ::boost::intrusive::treap::end()
1e59de90 697 iterator end() BOOST_NOEXCEPT;
7c673cae
FG		 698
699 //! @copydoc ::boost::intrusive::treap::end()const
1e59de90 700 const_iterator end() const BOOST_NOEXCEPT;
7c673cae
FG		 701
702 //! @copydoc ::boost::intrusive::treap::cend()const
1e59de90 703 const_iterator cend() const BOOST_NOEXCEPT;
7c673cae
FG		 704
705 //! @copydoc ::boost::intrusive::treap::rbegin()
1e59de90 706 reverse_iterator rbegin() BOOST_NOEXCEPT;
7c673cae
FG		 707
708 //! @copydoc ::boost::intrusive::treap::rbegin()const
1e59de90 709 const_reverse_iterator rbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 710
711 //! @copydoc ::boost::intrusive::treap::crbegin()const
1e59de90 712 const_reverse_iterator crbegin() const BOOST_NOEXCEPT;
7c673cae
FG		 713
714 //! @copydoc ::boost::intrusive::treap::rend()
1e59de90 715 reverse_iterator rend() BOOST_NOEXCEPT;
7c673cae
FG		 716
717 //! @copydoc ::boost::intrusive::treap::rend()const
1e59de90 718 const_reverse_iterator rend() const BOOST_NOEXCEPT;
7c673cae
FG		 719
720 //! @copydoc ::boost::intrusive::treap::crend()const
1e59de90 721 const_reverse_iterator crend() const BOOST_NOEXCEPT;
7c673cae
FG		 722
723 //! @copydoc ::boost::intrusive::treap::root()
1e59de90 724 iterator root() BOOST_NOEXCEPT;
7c673cae
FG		 725
726 //! @copydoc ::boost::intrusive::treap::root()const
1e59de90 727 const_iterator root() const BOOST_NOEXCEPT;
7c673cae
FG		 728
729 //! @copydoc ::boost::intrusive::treap::croot()const
1e59de90 730 const_iterator croot() const BOOST_NOEXCEPT;
7c673cae
FG		 731
732 //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(iterator)
1e59de90 733 static treap_multiset_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT;
7c673cae
FG		 734
735 //! @copydoc ::boost::intrusive::treap::container_from_end_iterator(const_iterator)
1e59de90 736 static const treap_multiset_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT;
7c673cae
FG		 737
738 //! @copydoc ::boost::intrusive::treap::container_from_iterator(iterator)
1e59de90 739 static treap_multiset_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT;
7c673cae
FG		 740
741 //! @copydoc ::boost::intrusive::treap::container_from_iterator(const_iterator)
1e59de90 742 static const treap_multiset_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT;
7c673cae
FG		 743
744 //! @copydoc ::boost::intrusive::treap::key_comp()const
745 key_compare key_comp() const;
746
747 //! @copydoc ::boost::intrusive::treap::value_comp()const
748 value_compare value_comp() const;
749
750 //! @copydoc ::boost::intrusive::treap::empty()const
1e59de90 751 bool empty() const BOOST_NOEXCEPT;
7c673cae
FG		 752
753 //! @copydoc ::boost::intrusive::treap::size()const
1e59de90 754 size_type size() const BOOST_NOEXCEPT;
7c673cae
FG		 755
756 //! @copydoc ::boost::intrusive::treap::swap
757 void swap(treap_multiset_impl& other);
758
759 //! @copydoc ::boost::intrusive::treap::clone_from(const treap&,Cloner,Disposer)
760 template <class Cloner, class Disposer>
761 void clone_from(const treap_multiset_impl &src, Cloner cloner, Disposer disposer);
762
763 #else
764
765 using tree_type::clone_from;
766
767 #endif
768
769 //! @copydoc ::boost::intrusive::treap::clone_from(treap&&,Cloner,Disposer)
770 template <class Cloner, class Disposer>
771 void clone_from(BOOST_RV_REF(treap_multiset_impl) src, Cloner cloner, Disposer disposer)
772 { tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer); }
773
774 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
775
776 //! @copydoc ::boost::intrusive::treap::top()
1e59de90 777 BOOST_INTRUSIVE_FORCEINLINE iterator top() BOOST_NOEXCEPT;
7c673cae
FG		 778
779 //! @copydoc ::boost::intrusive::treap::top()const
1e59de90 780 BOOST_INTRUSIVE_FORCEINLINE const_iterator top() const BOOST_NOEXCEPT;
7c673cae
FG		 781
782 //! @copydoc ::boost::intrusive::treap::ctop()const
1e59de90 783 BOOST_INTRUSIVE_FORCEINLINE const_iterator ctop() const BOOST_NOEXCEPT;
7c673cae
FG		 784
785 //! @copydoc ::boost::intrusive::treap::rtop()
1e59de90 786 BOOST_INTRUSIVE_FORCEINLINE reverse_iterator rtop() BOOST_NOEXCEPT;
7c673cae
FG		 787
788 //! @copydoc ::boost::intrusive::treap::rtop()const
1e59de90 789 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator rtop() const BOOST_NOEXCEPT;
7c673cae
FG		 790
791 //! @copydoc ::boost::intrusive::treap::crtop()const
1e59de90 792 BOOST_INTRUSIVE_FORCEINLINE const_reverse_iterator crtop() const BOOST_NOEXCEPT;
7c673cae
FG		 793
794 //! @copydoc ::boost::intrusive::treap::crtop() const
795 priority_compare priority_comp() const;
796 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
797
798 //! @copydoc ::boost::intrusive::treap::insert_equal(reference)
799 iterator insert(reference value)
800 { return tree_type::insert_equal(value); }
801
802 //! @copydoc ::boost::intrusive::treap::insert_equal(const_iterator,reference)
803 iterator insert(const_iterator hint, reference value)
804 { return tree_type::insert_equal(hint, value); }
805
806 //! @copydoc ::boost::intrusive::treap::insert_equal(Iterator,Iterator)
807 template<class Iterator>
808 void insert(Iterator b, Iterator e)
809 { tree_type::insert_equal(b, e); }
810
811 #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
812 //! @copydoc ::boost::intrusive::treap::insert_before
1e59de90 813 iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT;
7c673cae
FG		 814
815 //! @copydoc ::boost::intrusive::treap::push_back
1e59de90 816 void push_back(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 817
818 //! @copydoc ::boost::intrusive::treap::push_front
1e59de90 819 void push_front(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 820
821 //! @copydoc ::boost::intrusive::treap::erase(const_iterator)
1e59de90 822 iterator erase(const_iterator i) BOOST_NOEXCEPT;
7c673cae
FG		 823
824 //! @copydoc ::boost::intrusive::treap::erase(const_iterator,const_iterator)
1e59de90 825 iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT;
7c673cae
FG		 826
827 //! @copydoc ::boost::intrusive::treap::erase(const key_type &)
828 size_type erase(const key_type &key);
829
830 //! @copydoc ::boost::intrusive::treap::erase(const KeyType&,KeyTypeKeyCompare)
831 template<class KeyType, class KeyTypeKeyCompare>
832 size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
833
834 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,Disposer)
835 template<class Disposer>
1e59de90 836 iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 837
838 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const_iterator,const_iterator,Disposer)
839 template<class Disposer>
1e59de90 840 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 841
842 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const key_type &, Disposer)
843 template<class Disposer>
844 size_type erase_and_dispose(const key_type &key, Disposer disposer);
845
846 //! @copydoc ::boost::intrusive::treap::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
847 template<class KeyType, class KeyTypeKeyCompare, class Disposer>
848 size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
849
850 //! @copydoc ::boost::intrusive::treap::clear
1e59de90 851 void clear() BOOST_NOEXCEPT;
7c673cae
FG		 852
853 //! @copydoc ::boost::intrusive::treap::clear_and_dispose
854 template<class Disposer>
1e59de90 855 void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT;
7c673cae
FG		 856
857 //! @copydoc ::boost::intrusive::treap::count(const key_type &)const
858 size_type count(const key_type &key) const;
859
860 //! @copydoc ::boost::intrusive::treap::count(const KeyType&,KeyTypeKeyCompare)const
861 template<class KeyType, class KeyTypeKeyCompare>
862 size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
863
864 //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)
865 iterator lower_bound(const key_type &key);
866
867 //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)
868 template<class KeyType, class KeyTypeKeyCompare>
869 iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
870
871 //! @copydoc ::boost::intrusive::treap::lower_bound(const key_type &)const
872 const_iterator lower_bound(const key_type &key) const;
873
874 //! @copydoc ::boost::intrusive::treap::lower_bound(const KeyType&,KeyTypeKeyCompare)const
875 template<class KeyType, class KeyTypeKeyCompare>
876 const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
877
878 //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)
879 iterator upper_bound(const key_type &key);
880
881 //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)
882 template<class KeyType, class KeyTypeKeyCompare>
883 iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
884
885 //! @copydoc ::boost::intrusive::treap::upper_bound(const key_type &)const
886 const_iterator upper_bound(const key_type &key) const;
887
888 //! @copydoc ::boost::intrusive::treap::upper_bound(const KeyType&,KeyTypeKeyCompare)const
889 template<class KeyType, class KeyTypeKeyCompare>
890 const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
891
892 //! @copydoc ::boost::intrusive::treap::find(const key_type &)
893 iterator find(const key_type &key);
894
895 //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)
896 template<class KeyType, class KeyTypeKeyCompare>
897 iterator find(const KeyType& key, KeyTypeKeyCompare comp);
898
899 //! @copydoc ::boost::intrusive::treap::find(const key_type &)const
900 const_iterator find(const key_type &key) const;
901
902 //! @copydoc ::boost::intrusive::treap::find(const KeyType&,KeyTypeKeyCompare)const
903 template<class KeyType, class KeyTypeKeyCompare>
904 const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
905
906 //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)
907 std::pair<iterator,iterator> equal_range(const key_type &key);
908
909 //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)
910 template<class KeyType, class KeyTypeKeyCompare>
911 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
912
913 //! @copydoc ::boost::intrusive::treap::equal_range(const key_type &)const
914 std::pair<const_iterator, const_iterator>
915 equal_range(const key_type &key) const;
916
917 //! @copydoc ::boost::intrusive::treap::equal_range(const KeyType&,KeyTypeKeyCompare)const
918 template<class KeyType, class KeyTypeKeyCompare>
919 std::pair<const_iterator, const_iterator>
920 equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
921
922 //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)
923 std::pair<iterator,iterator> bounded_range
924 (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed);
925
926 //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
927 template<class KeyType, class KeyTypeKeyCompare>
928 std::pair<iterator,iterator> bounded_range
929 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
930
931 //! @copydoc ::boost::intrusive::treap::bounded_range(const key_type &,const key_type &,bool,bool)const
932 std::pair<const_iterator, const_iterator>
933 bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
934
935 //! @copydoc ::boost::intrusive::treap::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
936 template<class KeyType, class KeyTypeKeyCompare>
937 std::pair<const_iterator, const_iterator> bounded_range
938 (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
939
940 //! @copydoc ::boost::intrusive::treap::s_iterator_to(reference)
1e59de90 941 static iterator s_iterator_to(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 942
943 //! @copydoc ::boost::intrusive::treap::s_iterator_to(const_reference)
1e59de90 944 static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT;
7c673cae
FG		 945
946 //! @copydoc ::boost::intrusive::treap::iterator_to(reference)
1e59de90 947 iterator iterator_to(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 948
949 //! @copydoc ::boost::intrusive::treap::iterator_to(const_reference)const
1e59de90 950 const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
7c673cae
FG		 951
952 //! @copydoc ::boost::intrusive::treap::init_node(reference)
1e59de90 953 static void init_node(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 954
955 //! @copydoc ::boost::intrusive::treap::unlink_leftmost_without_rebalance
1e59de90 956 pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT;
7c673cae
FG		 957
958 //! @copydoc ::boost::intrusive::treap::replace_node
1e59de90 959 void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT;
7c673cae
FG		 960
961 //! @copydoc ::boost::intrusive::treap::remove_node
1e59de90 962 void remove_node(reference value) BOOST_NOEXCEPT;
7c673cae
FG		 963
964 //! @copydoc ::boost::intrusive::treap::merge_unique
965 template<class ...Options2>
966 void merge(treap_multiset<T, Options2...> &source);
967
968 //! @copydoc ::boost::intrusive::treap::merge_unique
969 template<class ...Options2>
970 void merge(treap_set<T, Options2...> &source);
971
972 #else
973
974 template<class Compare2>
92f5a8d4 975 void merge(treap_multiset_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
7c673cae
FG		 976 { return tree_type::merge_equal(source); }
977
978 template<class Compare2>
92f5a8d4 979 void merge(treap_set_impl<ValueTraits, VoidOrKeyOfValue, Compare2, VoidOrPrioOfValue, VoidOrPrioComp, SizeType, ConstantTimeSize, HeaderHolder> &source)
7c673cae
FG		 980 { return tree_type::merge_equal(source); }
981
982 #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
983};
984
985
986//! Helper metafunction to define a \c treap_multiset that yields to the same type when the
987//! same options (either explicitly or implicitly) are used.
988#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
989template<class T, class ...Options>
990#else
991template<class T, class O1 = void, class O2 = void
992 , class O3 = void, class O4 = void
92f5a8d4
TL		 993 , class O5 = void, class O6 = void
994 , class O7 = void>
7c673cae
FG		 995#endif
996struct make_treap_multiset
997{
998 typedef typename pack_options
999 < treap_defaults,
1000 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 1001 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 1002 #else
1003 Options...
1004 #endif
1005 >::type packed_options;
1006
1007 typedef typename detail::get_value_traits
1008 <T, typename packed_options::proto_value_traits>::type value_traits;
1009
1010 typedef treap_multiset_impl
1011 < value_traits
1012 , typename packed_options::key_of_value
1013 , typename packed_options::compare
92f5a8d4 1014 , typename packed_options::priority_of_value
7c673cae
FG		 1015 , typename packed_options::priority
1016 , typename packed_options::size_type
1017 , packed_options::constant_time_size
1018 , typename packed_options::header_holder_type
1019 > implementation_defined;
1020 /// @endcond
1021 typedef implementation_defined type;
1022};
1023
1024#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1025
1026#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 1027template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7>
7c673cae
FG		 1028#else
1029template<class T, class ...Options>
1030#endif
1031class treap_multiset
1032 : public make_treap_multiset<T,
1033 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 1034 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 1035 #else
1036 Options...
1037 #endif
1038 >::type
1039{
1040 typedef typename make_treap_multiset
1041 <T,
1042 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
92f5a8d4 1043 O1, O2, O3, O4, O5, O6, O7
7c673cae
FG		 1044 #else
1045 Options...
1046 #endif
1047 >::type Base;
1048 BOOST_MOVABLE_BUT_NOT_COPYABLE(treap_multiset)
1049
1050 public:
1051 typedef typename Base::key_compare key_compare;
1052 typedef typename Base::priority_compare priority_compare;
1053 typedef typename Base::value_traits value_traits;
1054 typedef typename Base::iterator iterator;
1055 typedef typename Base::const_iterator const_iterator;
1056
1057 //Assert if passed value traits are compatible with the type
1058 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1059
92f5a8d4 1060 BOOST_INTRUSIVE_FORCEINLINE treap_multiset()
7c673cae
FG		 1061 : Base()
1062 {}
1063
92f5a8d4 1064 BOOST_INTRUSIVE_FORCEINLINE explicit treap_multiset( const key_compare &cmp
7c673cae
FG		 1065 , const priority_compare &pcmp = priority_compare()
1066 , const value_traits &v_traits = value_traits())
1067 : Base(cmp, pcmp, v_traits)
1068 {}
1069
1070 template<class Iterator>
92f5a8d4 1071 BOOST_INTRUSIVE_FORCEINLINE treap_multiset( Iterator b, Iterator e
7c673cae
FG		 1072 , const key_compare &cmp = key_compare()
1073 , const priority_compare &pcmp = priority_compare()
1074 , const value_traits &v_traits = value_traits())
1075 : Base(b, e, cmp, pcmp, v_traits)
1076 {}
1077
92f5a8d4 1078 BOOST_INTRUSIVE_FORCEINLINE treap_multiset(BOOST_RV_REF(treap_multiset) x)
7c673cae
FG		 1079 : Base(BOOST_MOVE_BASE(Base, x))
1080 {}
1081
92f5a8d4 1082 BOOST_INTRUSIVE_FORCEINLINE treap_multiset& operator=(BOOST_RV_REF(treap_multiset) x)
7c673cae
FG		 1083 { return static_cast<treap_multiset &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
1084
1085 template <class Cloner, class Disposer>
92f5a8d4 1086 BOOST_INTRUSIVE_FORCEINLINE void clone_from(const treap_multiset &src, Cloner cloner, Disposer disposer)
7c673cae
FG		 1087 { Base::clone_from(src, cloner, disposer); }
1088
1089 template <class Cloner, class Disposer>
92f5a8d4 1090 BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(treap_multiset) src, Cloner cloner, Disposer disposer)
7c673cae
FG		 1091 { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
1092
1e59de90 1093 BOOST_INTRUSIVE_FORCEINLINE static treap_multiset &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT
7c673cae
FG		 1094 { return static_cast<treap_multiset &>(Base::container_from_end_iterator(end_iterator)); }
1095
1e59de90 1096 BOOST_INTRUSIVE_FORCEINLINE static const treap_multiset &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT
7c673cae
FG		 1097 { return static_cast<const treap_multiset &>(Base::container_from_end_iterator(end_iterator)); }
1098
1e59de90 1099 BOOST_INTRUSIVE_FORCEINLINE static treap_multiset &container_from_iterator(iterator it) BOOST_NOEXCEPT
7c673cae
FG		 1100 { return static_cast<treap_multiset &>(Base::container_from_iterator(it)); }
1101
1e59de90 1102 BOOST_INTRUSIVE_FORCEINLINE static const treap_multiset &container_from_iterator(const_iterator it) BOOST_NOEXCEPT
7c673cae
FG		 1103 { return static_cast<const treap_multiset &>(Base::container_from_iterator(it)); }
1104};
1105
1106#endif
1107
1108} //namespace intrusive
1109} //namespace boost
1110
1111#include <boost/intrusive/detail/config_end.hpp>
1112
1113#endif //BOOST_INTRUSIVE_TREAP_SET_HPP
Ceph