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