1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // |
3 | // (C) Copyright Ion Gaztanaga 2013-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_BSTREE_HPP |
13 | #define BOOST_INTRUSIVE_BSTREE_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/intrusive_fwd.hpp> |
20 | #include <boost/intrusive/bs_set_hook.hpp> |
21 | #include <boost/intrusive/detail/tree_node.hpp> |
22 | #include <boost/intrusive/detail/tree_iterator.hpp> |
23 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> |
24 | #include <boost/intrusive/detail/mpl.hpp> |
25 | #include <boost/intrusive/pointer_traits.hpp> |
26 | #include <boost/intrusive/detail/is_stateful_value_traits.hpp> |
27 | #include <boost/intrusive/detail/empty_node_checker.hpp> |
28 | #include <boost/intrusive/detail/default_header_holder.hpp> |
29 | #include <boost/intrusive/detail/reverse_iterator.hpp> |
30 | #include <boost/intrusive/detail/exception_disposer.hpp> |
31 | #include <boost/intrusive/detail/node_cloner_disposer.hpp> |
32 | #include <boost/intrusive/detail/key_nodeptr_comp.hpp> |
33 | #include <boost/intrusive/detail/simple_disposers.hpp> |
34 | #include <boost/intrusive/detail/size_holder.hpp> |
35 | #include <boost/intrusive/detail/algo_type.hpp> |
36 | #include <boost/intrusive/detail/algorithm.hpp> |
37 | #include <boost/intrusive/detail/tree_value_compare.hpp> |
38 | |
39 | #include <boost/intrusive/detail/get_value_traits.hpp> |
40 | #include <boost/intrusive/bstree_algorithms.hpp> |
41 | #include <boost/intrusive/link_mode.hpp> |
42 | #include <boost/intrusive/parent_from_member.hpp> |
43 | #include <boost/move/utility_core.hpp> |
44 | #include <boost/move/adl_move_swap.hpp> |
45 | |
46 | #include <boost/intrusive/detail/minimal_pair_header.hpp> |
47 | #include <cstddef> //size_t... |
48 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal_to |
49 | |
50 | #if defined(BOOST_HAS_PRAGMA_ONCE) |
51 | # pragma once |
52 | #endif |
53 | |
54 | namespace boost { |
55 | namespace intrusive { |
56 | |
57 | /// @cond |
58 | |
59 | struct default_bstree_hook_applier |
60 | { template <class T> struct apply{ typedef typename T::default_bstree_hook type; }; }; |
61 | |
62 | template<> |
63 | struct is_default_hook_tag<default_bstree_hook_applier> |
64 | { static const bool value = true; }; |
65 | |
66 | struct bstree_defaults |
67 | { |
68 | typedef default_bstree_hook_applier proto_value_traits; |
69 | static const bool constant_time_size = true; |
70 | typedef std::size_t size_type; |
71 | typedef void compare; |
72 | typedef void key_of_value; |
73 | static const bool floating_point = true; //For sgtree |
74 | typedef void priority; //For treap |
75 | typedef void ; |
76 | }; |
77 | |
78 | template<class ValueTraits, algo_types AlgoType, typename HeaderHolder> |
79 | struct bstbase3 |
80 | { |
81 | typedef ValueTraits value_traits; |
82 | typedef typename value_traits::node_traits node_traits; |
83 | typedef typename node_traits::node node_type; |
84 | typedef typename get_algo<AlgoType, node_traits>::type node_algorithms; |
85 | typedef typename node_traits::node_ptr node_ptr; |
86 | typedef typename node_traits::const_node_ptr const_node_ptr; |
87 | typedef tree_iterator<value_traits, false> iterator; |
88 | typedef tree_iterator<value_traits, true> const_iterator; |
89 | typedef boost::intrusive::reverse_iterator<iterator> reverse_iterator; |
90 | typedef boost::intrusive::reverse_iterator<const_iterator> const_reverse_iterator; |
91 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; |
92 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; |
93 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; |
94 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; |
95 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; |
96 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; |
97 | typedef typename detail::get_header_holder_type |
98 | < value_traits,HeaderHolder >::type ; |
99 | |
100 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; |
101 | static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; |
102 | static const bool has_container_from_iterator = |
103 | detail::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; |
104 | |
105 | struct holder_t : public ValueTraits |
106 | { |
107 | inline explicit holder_t(const ValueTraits &vtraits) |
108 | : ValueTraits(vtraits) |
109 | {} |
110 | header_holder_type root; |
111 | } holder; |
112 | |
113 | static bstbase3 &get_tree_base_from_end_iterator(const const_iterator &end_iterator) |
114 | { |
115 | BOOST_INTRUSIVE_STATIC_ASSERT(has_container_from_iterator); |
116 | node_ptr p = end_iterator.pointed_node(); |
117 | header_holder_type* h = header_holder_type::get_holder(p); |
118 | holder_t *holder = get_parent_from_member<holder_t, header_holder_type>(h, &holder_t::root); |
119 | bstbase3 *base = get_parent_from_member<bstbase3, holder_t> (holder, &bstbase3::holder); |
120 | return *base; |
121 | } |
122 | |
123 | inline bstbase3(const ValueTraits &vtraits) |
124 | : holder(vtraits) |
125 | { |
126 | node_algorithms::init_header(this->header_ptr()); |
127 | } |
128 | |
129 | inline node_ptr () |
130 | { return holder.root.get_node(); } |
131 | |
132 | inline const_node_ptr () const |
133 | { return holder.root.get_node(); } |
134 | |
135 | inline const value_traits &get_value_traits() const |
136 | { return this->holder; } |
137 | |
138 | inline value_traits &get_value_traits() |
139 | { return this->holder; } |
140 | |
141 | typedef typename boost::intrusive::value_traits_pointers |
142 | <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; |
143 | |
144 | inline const_value_traits_ptr priv_value_traits_ptr() const |
145 | { return pointer_traits<const_value_traits_ptr>::pointer_to(this->get_value_traits()); } |
146 | |
147 | inline iterator begin() BOOST_NOEXCEPT |
148 | { return iterator(node_algorithms::begin_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
149 | |
150 | inline const_iterator begin() const BOOST_NOEXCEPT |
151 | { return cbegin(); } |
152 | |
153 | inline const_iterator cbegin() const BOOST_NOEXCEPT |
154 | { return const_iterator(node_algorithms::begin_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
155 | |
156 | inline iterator end() BOOST_NOEXCEPT |
157 | { return iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
158 | |
159 | inline const_iterator end() const BOOST_NOEXCEPT |
160 | { return cend(); } |
161 | |
162 | inline const_iterator cend() const BOOST_NOEXCEPT |
163 | { return const_iterator(node_algorithms::end_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
164 | |
165 | inline iterator root() |
166 | { return iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
167 | |
168 | inline const_iterator root() const |
169 | { return croot(); } |
170 | |
171 | inline const_iterator croot() const |
172 | { return const_iterator(node_algorithms::root_node(this->header_ptr()), this->priv_value_traits_ptr()); } |
173 | |
174 | inline reverse_iterator rbegin() |
175 | { return reverse_iterator(end()); } |
176 | |
177 | inline const_reverse_iterator rbegin() const |
178 | { return const_reverse_iterator(end()); } |
179 | |
180 | inline const_reverse_iterator crbegin() const |
181 | { return const_reverse_iterator(end()); } |
182 | |
183 | inline reverse_iterator rend() |
184 | { return reverse_iterator(begin()); } |
185 | |
186 | inline const_reverse_iterator rend() const |
187 | { return const_reverse_iterator(begin()); } |
188 | |
189 | inline const_reverse_iterator crend() const |
190 | { return const_reverse_iterator(begin()); } |
191 | |
192 | void replace_node(iterator replace_this, reference with_this) |
193 | { |
194 | node_algorithms::replace_node( get_value_traits().to_node_ptr(*replace_this) |
195 | , this->header_ptr() |
196 | , get_value_traits().to_node_ptr(with_this)); |
197 | BOOST_IF_CONSTEXPR(safemode_or_autounlink) |
198 | node_algorithms::init(replace_this.pointed_node()); |
199 | } |
200 | |
201 | inline void rebalance() BOOST_NOEXCEPT |
202 | { node_algorithms::rebalance(this->header_ptr()); } |
203 | |
204 | iterator rebalance_subtree(iterator r) BOOST_NOEXCEPT |
205 | { return iterator(node_algorithms::rebalance_subtree(r.pointed_node()), this->priv_value_traits_ptr()); } |
206 | |
207 | static iterator s_iterator_to(reference value) BOOST_NOEXCEPT |
208 | { |
209 | BOOST_INTRUSIVE_STATIC_ASSERT((!stateful_value_traits)); |
210 | return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr()); |
211 | } |
212 | |
213 | static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT |
214 | { |
215 | BOOST_INTRUSIVE_STATIC_ASSERT((!stateful_value_traits)); |
216 | return const_iterator (value_traits::to_node_ptr(*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value))), const_value_traits_ptr()); |
217 | } |
218 | |
219 | iterator iterator_to(reference value) BOOST_NOEXCEPT |
220 | { return iterator (this->get_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); } |
221 | |
222 | const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT |
223 | { return const_iterator (this->get_value_traits().to_node_ptr(*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value))), this->priv_value_traits_ptr()); } |
224 | |
225 | inline static void init_node(reference value) |
226 | { node_algorithms::init(value_traits::to_node_ptr(value)); } |
227 | |
228 | }; |
229 | |
230 | template<class Less, class T> |
231 | struct get_compare |
232 | { |
233 | typedef Less type; |
234 | }; |
235 | |
236 | template<class T> |
237 | struct get_compare<void, T> |
238 | { |
239 | typedef ::std::less<T> type; |
240 | }; |
241 | |
242 | template<class KeyOfValue, class T> |
243 | struct get_key_of_value |
244 | { |
245 | typedef KeyOfValue type; |
246 | }; |
247 | |
248 | template<class T> |
249 | struct get_key_of_value<void, T> |
250 | { |
251 | typedef ::boost::intrusive::detail::identity<T> type; |
252 | }; |
253 | |
254 | template<class ValuePtr, class VoidOrKeyOfValue, class VoidOrKeyComp> |
255 | struct bst_key_types |
256 | { |
257 | typedef typename |
258 | boost::movelib::pointer_element<ValuePtr>::type value_type; |
259 | typedef typename get_key_of_value |
260 | < VoidOrKeyOfValue, value_type>::type key_of_value; |
261 | typedef typename key_of_value::type key_type; |
262 | typedef typename get_compare< VoidOrKeyComp |
263 | , key_type |
264 | >::type key_compare; |
265 | typedef tree_value_compare |
266 | <ValuePtr, key_compare, key_of_value> value_compare; |
267 | }; |
268 | |
269 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, algo_types AlgoType, typename HeaderHolder> |
270 | struct bstbase2 |
271 | //Put the (possibly empty) functor in the first position to get EBO in MSVC |
272 | //Use public inheritance to avoid MSVC bugs with closures |
273 | : public detail::ebo_functor_holder |
274 | < typename bst_key_types |
275 | < typename ValueTraits::pointer |
276 | , VoidOrKeyOfValue |
277 | , VoidOrKeyComp |
278 | |
279 | >::value_compare |
280 | > |
281 | , public bstbase3<ValueTraits, AlgoType, HeaderHolder> |
282 | { |
283 | typedef bstbase3<ValueTraits, AlgoType, HeaderHolder> ; |
284 | typedef bst_key_types< typename ValueTraits::pointer |
285 | , VoidOrKeyOfValue |
286 | , VoidOrKeyComp> key_types; |
287 | typedef typename treeheader_t::value_traits value_traits; |
288 | typedef typename treeheader_t::node_algorithms node_algorithms; |
289 | typedef typename ValueTraits::value_type value_type; |
290 | typedef typename key_types::key_type key_type; |
291 | typedef typename key_types::key_of_value key_of_value; |
292 | typedef typename key_types::key_compare key_compare; |
293 | typedef typename key_types::value_compare value_compare; |
294 | typedef typename treeheader_t::iterator iterator; |
295 | typedef typename treeheader_t::const_iterator const_iterator; |
296 | typedef typename treeheader_t::node_ptr node_ptr; |
297 | typedef typename treeheader_t::const_node_ptr const_node_ptr; |
298 | |
299 | bstbase2(const key_compare &comp, const ValueTraits &vtraits) |
300 | : detail::ebo_functor_holder<value_compare>(value_compare(comp)), treeheader_t(vtraits) |
301 | {} |
302 | |
303 | const value_compare &get_comp() const |
304 | { return this->get(); } |
305 | |
306 | value_compare &get_comp() |
307 | { return this->get(); } |
308 | |
309 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; |
310 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; |
311 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; |
312 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; |
313 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; |
314 | typedef typename node_algorithms::insert_commit_data insert_commit_data; |
315 | |
316 | inline value_compare value_comp() const |
317 | { return this->get_comp(); } |
318 | |
319 | inline key_compare key_comp() const |
320 | { return this->get_comp().key_comp(); } |
321 | |
322 | //lower_bound |
323 | inline iterator lower_bound(const key_type &key) |
324 | { return this->lower_bound(key, this->key_comp()); } |
325 | |
326 | inline const_iterator lower_bound(const key_type &key) const |
327 | { return this->lower_bound(key, this->key_comp()); } |
328 | |
329 | template<class KeyType, class KeyTypeKeyCompare> |
330 | iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) |
331 | { |
332 | return iterator(node_algorithms::lower_bound |
333 | (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
334 | } |
335 | |
336 | template<class KeyType, class KeyTypeKeyCompare> |
337 | const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const |
338 | { |
339 | return const_iterator(node_algorithms::lower_bound |
340 | (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
341 | } |
342 | |
343 | //upper_bound |
344 | inline iterator upper_bound(const key_type &key) |
345 | { return this->upper_bound(key, this->key_comp()); } |
346 | |
347 | template<class KeyType, class KeyTypeKeyCompare> |
348 | iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) |
349 | { |
350 | return iterator(node_algorithms::upper_bound |
351 | (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
352 | } |
353 | |
354 | inline const_iterator upper_bound(const key_type &key) const |
355 | { return this->upper_bound(key, this->key_comp()); } |
356 | |
357 | template<class KeyType, class KeyTypeKeyCompare> |
358 | const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const |
359 | { |
360 | return const_iterator(node_algorithms::upper_bound |
361 | (this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
362 | } |
363 | |
364 | template<class KeyTypeKeyCompare> |
365 | struct key_node_comp_ret |
366 | { typedef detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value> type; }; |
367 | |
368 | template<class KeyTypeKeyCompare> |
369 | inline typename key_node_comp_ret<KeyTypeKeyCompare>::type key_node_comp(KeyTypeKeyCompare comp) const |
370 | { |
371 | return detail::key_nodeptr_comp<KeyTypeKeyCompare, value_traits, key_of_value>(comp, &this->get_value_traits()); |
372 | } |
373 | |
374 | //find |
375 | inline iterator find(const key_type &key) |
376 | { return this->find(key, this->key_comp()); } |
377 | |
378 | template<class KeyType, class KeyTypeKeyCompare> |
379 | iterator find(const KeyType &key, KeyTypeKeyCompare comp) |
380 | { |
381 | return iterator |
382 | (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
383 | } |
384 | |
385 | inline const_iterator find(const key_type &key) const |
386 | { return this->find(key, this->key_comp()); } |
387 | |
388 | template<class KeyType, class KeyTypeKeyCompare> |
389 | const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const |
390 | { |
391 | return const_iterator |
392 | (node_algorithms::find(this->header_ptr(), key, this->key_node_comp(comp)), this->priv_value_traits_ptr()); |
393 | } |
394 | |
395 | //equal_range |
396 | inline std::pair<iterator,iterator> equal_range(const key_type &key) |
397 | { return this->equal_range(key, this->key_comp()); } |
398 | |
399 | template<class KeyType, class KeyTypeKeyCompare> |
400 | std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp) |
401 | { |
402 | std::pair<node_ptr, node_ptr> ret = |
403 | node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp)); |
404 | return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) |
405 | , iterator(ret.second, this->priv_value_traits_ptr())); |
406 | } |
407 | |
408 | inline std::pair<const_iterator, const_iterator> |
409 | equal_range(const key_type &key) const |
410 | { return this->equal_range(key, this->key_comp()); } |
411 | |
412 | template<class KeyType, class KeyTypeKeyCompare> |
413 | std::pair<const_iterator, const_iterator> |
414 | equal_range(const KeyType &key, KeyTypeKeyCompare comp) const |
415 | { |
416 | std::pair<node_ptr, node_ptr> ret = |
417 | node_algorithms::equal_range(this->header_ptr(), key, this->key_node_comp(comp)); |
418 | return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) |
419 | , const_iterator(ret.second, this->priv_value_traits_ptr())); |
420 | } |
421 | |
422 | //lower_bound_range |
423 | inline std::pair<iterator,iterator> lower_bound_range(const key_type &key) |
424 | { return this->lower_bound_range(key, this->key_comp()); } |
425 | |
426 | template<class KeyType, class KeyTypeKeyCompare> |
427 | std::pair<iterator,iterator> lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp) |
428 | { |
429 | std::pair<node_ptr, node_ptr> ret = |
430 | node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp)); |
431 | return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) |
432 | , iterator(ret.second, this->priv_value_traits_ptr())); |
433 | } |
434 | |
435 | inline std::pair<const_iterator, const_iterator> |
436 | lower_bound_range(const key_type &key) const |
437 | { return this->lower_bound_range(key, this->key_comp()); } |
438 | |
439 | template<class KeyType, class KeyTypeKeyCompare> |
440 | std::pair<const_iterator, const_iterator> |
441 | lower_bound_range(const KeyType &key, KeyTypeKeyCompare comp) const |
442 | { |
443 | std::pair<node_ptr, node_ptr> ret = |
444 | node_algorithms::lower_bound_range(this->header_ptr(), key, this->key_node_comp(comp)); |
445 | return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) |
446 | , const_iterator(ret.second, this->priv_value_traits_ptr())); |
447 | } |
448 | |
449 | //bounded_range |
450 | inline std::pair<iterator,iterator> bounded_range |
451 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) |
452 | { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); } |
453 | |
454 | template<class KeyType, class KeyTypeKeyCompare> |
455 | std::pair<iterator,iterator> bounded_range |
456 | (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) |
457 | { |
458 | std::pair<node_ptr, node_ptr> ret = |
459 | node_algorithms::bounded_range |
460 | (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed); |
461 | return std::pair<iterator, iterator>( iterator(ret.first, this->priv_value_traits_ptr()) |
462 | , iterator(ret.second, this->priv_value_traits_ptr())); |
463 | } |
464 | |
465 | inline std::pair<const_iterator,const_iterator> bounded_range |
466 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const |
467 | { return this->bounded_range(lower_key, upper_key, this->key_comp(), left_closed, right_closed); } |
468 | |
469 | template<class KeyType, class KeyTypeKeyCompare> |
470 | std::pair<const_iterator,const_iterator> bounded_range |
471 | (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const |
472 | { |
473 | std::pair<node_ptr, node_ptr> ret = |
474 | node_algorithms::bounded_range |
475 | (this->header_ptr(), lower_key, upper_key, this->key_node_comp(comp), left_closed, right_closed); |
476 | return std::pair<const_iterator, const_iterator>( const_iterator(ret.first, this->priv_value_traits_ptr()) |
477 | , const_iterator(ret.second, this->priv_value_traits_ptr())); |
478 | } |
479 | |
480 | //insert_unique_check |
481 | inline std::pair<iterator, bool> insert_unique_check |
482 | (const key_type &key, insert_commit_data &commit_data) |
483 | { return this->insert_unique_check(key, this->key_comp(), commit_data); } |
484 | |
485 | inline std::pair<iterator, bool> insert_unique_check |
486 | (const_iterator hint, const key_type &key, insert_commit_data &commit_data) |
487 | { return this->insert_unique_check(hint, key, this->key_comp(), commit_data); } |
488 | |
489 | template<class KeyType, class KeyTypeKeyCompare> |
490 | BOOST_INTRUSIVE_DOC1ST(std::pair<iterator BOOST_INTRUSIVE_I bool> |
491 | , typename detail::disable_if_convertible |
492 | <KeyType BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I |
493 | std::pair<iterator BOOST_INTRUSIVE_I bool> >::type) |
494 | insert_unique_check |
495 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) |
496 | { |
497 | std::pair<node_ptr, bool> ret = |
498 | (node_algorithms::insert_unique_check |
499 | (this->header_ptr(), key, this->key_node_comp(comp), commit_data)); |
500 | return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); |
501 | } |
502 | |
503 | template<class KeyType, class KeyTypeKeyCompare> |
504 | std::pair<iterator, bool> insert_unique_check |
505 | (const_iterator hint, const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data) |
506 | { |
507 | std::pair<node_ptr, bool> ret = |
508 | (node_algorithms::insert_unique_check |
509 | (this->header_ptr(), hint.pointed_node(), key, this->key_node_comp(comp), commit_data)); |
510 | return std::pair<iterator, bool>(iterator(ret.first, this->priv_value_traits_ptr()), ret.second); |
511 | } |
512 | }; |
513 | |
514 | //Due to MSVC's EBO implementation, to save space and maintain the ABI, we must put the non-empty size member |
515 | //in the first position, but if size is not going to be stored then we'll use an specialization |
516 | //that doesn't inherit from size_holder |
517 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder> |
518 | struct bstbase_hack |
519 | : public detail::size_holder<ConstantTimeSize, SizeType> |
520 | , public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> |
521 | { |
522 | typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type; |
523 | typedef typename base_type::key_compare key_compare; |
524 | typedef typename base_type::value_compare value_compare; |
525 | typedef SizeType size_type; |
526 | typedef typename base_type::node_traits node_traits; |
527 | typedef typename get_algo |
528 | <AlgoType, node_traits>::type algo_type; |
529 | |
530 | inline bstbase_hack(const key_compare & comp, const ValueTraits &vtraits) |
531 | : base_type(comp, vtraits) |
532 | { |
533 | this->sz_traits().set_size(size_type(0)); |
534 | } |
535 | |
536 | typedef detail::size_holder<ConstantTimeSize, SizeType> size_traits; |
537 | |
538 | inline size_traits &sz_traits() |
539 | { return static_cast<size_traits &>(*this); } |
540 | |
541 | inline const size_traits &sz_traits() const |
542 | { return static_cast<const size_traits &>(*this); } |
543 | }; |
544 | |
545 | //Specialization for ConstantTimeSize == false |
546 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, algo_types AlgoType, typename HeaderHolder> |
547 | struct bstbase_hack<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, false, SizeType, AlgoType, HeaderHolder> |
548 | : public bstbase2 < ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> |
549 | { |
550 | typedef bstbase2< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, AlgoType, HeaderHolder> base_type; |
551 | typedef typename base_type::value_compare value_compare; |
552 | typedef typename base_type::key_compare key_compare; |
553 | inline bstbase_hack(const key_compare & comp, const ValueTraits &vtraits) |
554 | : base_type(comp, vtraits) |
555 | {} |
556 | |
557 | typedef detail::size_holder<false, SizeType> size_traits; |
558 | |
559 | inline size_traits sz_traits() const |
560 | { return size_traits(); } |
561 | }; |
562 | |
563 | //This class will |
564 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, bool ConstantTimeSize, class SizeType, algo_types AlgoType, typename HeaderHolder> |
565 | struct bstbase |
566 | : public bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> |
567 | { |
568 | typedef bstbase_hack< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> base_type; |
569 | typedef ValueTraits value_traits; |
570 | typedef typename base_type::value_compare value_compare; |
571 | typedef typename base_type::key_compare key_compare; |
572 | typedef typename base_type::const_reference const_reference; |
573 | typedef typename base_type::reference reference; |
574 | typedef typename base_type::iterator iterator; |
575 | typedef typename base_type::const_iterator const_iterator; |
576 | typedef typename base_type::node_traits node_traits; |
577 | typedef typename get_algo |
578 | <AlgoType, node_traits>::type node_algorithms; |
579 | typedef SizeType size_type; |
580 | |
581 | inline bstbase(const key_compare & comp, const ValueTraits &vtraits) |
582 | : base_type(comp, vtraits) |
583 | {} |
584 | |
585 | //Detach all inserted nodes. This will add exception safety to bstree_impl |
586 | //constructors inserting elements. |
587 | ~bstbase() |
588 | { |
589 | if(is_safe_autounlink<value_traits::link_mode>::value){ |
590 | node_algorithms::clear_and_dispose |
591 | ( this->header_ptr() |
592 | , detail::node_disposer<detail::null_disposer, value_traits, AlgoType> |
593 | (detail::null_disposer(), &this->get_value_traits())); |
594 | node_algorithms::init(this->header_ptr()); |
595 | } |
596 | } |
597 | }; |
598 | |
599 | |
600 | /// @endcond |
601 | |
602 | //! The class template bstree is an unbalanced intrusive binary search tree |
603 | //! container. The no-throw guarantee holds only, if the key_compare object |
604 | //! doesn't throw. |
605 | //! |
606 | //! The complexity guarantees only hold if the tree is balanced, logarithmic |
607 | //! complexity would increase to linear if the tree is totally unbalanced. |
608 | //! |
609 | //! The template parameter \c T is the type to be managed by the container. |
610 | //! The user can specify additional options and if no options are provided |
611 | //! default options are used. |
612 | //! |
613 | //! The container supports the following options: |
614 | //! \c base_hook<>/member_hook<>/value_traits<>, |
615 | //! \c constant_time_size<>, \c size_type<> and |
616 | //! \c compare<>. |
617 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
618 | template<class T, class ...Options> |
619 | #else |
620 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, algo_types AlgoType, typename HeaderHolder> |
621 | #endif |
622 | class bstree_impl |
623 | : public bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> |
624 | { |
625 | public: |
626 | /// @cond |
627 | typedef bstbase<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, ConstantTimeSize, SizeType, AlgoType, HeaderHolder> data_type; |
628 | typedef tree_iterator<ValueTraits, false> iterator_type; |
629 | typedef tree_iterator<ValueTraits, true> const_iterator_type; |
630 | /// @endcond |
631 | |
632 | typedef BOOST_INTRUSIVE_IMPDEF(ValueTraits) value_traits; |
633 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::pointer) pointer; |
634 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::const_pointer) const_pointer; |
635 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::element_type) value_type; |
636 | typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_type) key_type; |
637 | typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_of_value) key_of_value; |
638 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<pointer>::reference) reference; |
639 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::reference) const_reference; |
640 | typedef BOOST_INTRUSIVE_IMPDEF(typename pointer_traits<const_pointer>::difference_type) difference_type; |
641 | typedef BOOST_INTRUSIVE_IMPDEF(SizeType) size_type; |
642 | typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::value_compare) value_compare; |
643 | typedef BOOST_INTRUSIVE_IMPDEF(typename data_type::key_compare) key_compare; |
644 | typedef BOOST_INTRUSIVE_IMPDEF(iterator_type) iterator; |
645 | typedef BOOST_INTRUSIVE_IMPDEF(const_iterator_type) const_iterator; |
646 | typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<iterator>) reverse_iterator; |
647 | typedef BOOST_INTRUSIVE_IMPDEF(boost::intrusive::reverse_iterator<const_iterator>) const_reverse_iterator; |
648 | typedef BOOST_INTRUSIVE_IMPDEF(typename value_traits::node_traits) node_traits; |
649 | typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node) node; |
650 | typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::node_ptr) node_ptr; |
651 | typedef BOOST_INTRUSIVE_IMPDEF(typename node_traits::const_node_ptr) const_node_ptr; |
652 | /// @cond |
653 | typedef typename get_algo<AlgoType, node_traits>::type algo_type; |
654 | /// @endcond |
655 | typedef BOOST_INTRUSIVE_IMPDEF(algo_type) node_algorithms; |
656 | |
657 | static const bool constant_time_size = ConstantTimeSize; |
658 | static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; |
659 | /// @cond |
660 | private: |
661 | |
662 | //noncopyable |
663 | BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree_impl) |
664 | |
665 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; |
666 | |
667 | //Constant-time size is incompatible with auto-unlink hooks! |
668 | BOOST_INTRUSIVE_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); |
669 | |
670 | |
671 | protected: |
672 | |
673 | |
674 | /// @endcond |
675 | |
676 | public: |
677 | |
678 | typedef typename node_algorithms::insert_commit_data insert_commit_data; |
679 | |
680 | //! <b>Effects</b>: Constructs an empty container. |
681 | //! |
682 | //! <b>Complexity</b>: Constant. |
683 | //! |
684 | //! <b>Throws</b>: If value_traits::node_traits::node |
685 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
686 | //! or the copy constructor of the key_compare object throws. Basic guarantee. |
687 | bstree_impl() |
688 | : data_type(key_compare(), value_traits()) |
689 | {} |
690 | |
691 | //! <b>Effects</b>: Constructs an empty container with given comparison and traits. |
692 | //! |
693 | //! <b>Complexity</b>: Constant. |
694 | //! |
695 | //! <b>Throws</b>: If value_traits::node_traits::node |
696 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
697 | //! or the copy constructor of the key_compare object throws. Basic guarantee. |
698 | explicit bstree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits()) |
699 | : data_type(cmp, v_traits) |
700 | {} |
701 | |
702 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. |
703 | //! cmp must be a comparison function that induces a strict weak ordering. |
704 | //! |
705 | //! <b>Effects</b>: Constructs an empty container and inserts elements from |
706 | //! [b, e). |
707 | //! |
708 | //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using |
709 | //! comp and otherwise N * log N, where N is the distance between first and last. |
710 | //! |
711 | //! <b>Throws</b>: If value_traits::node_traits::node |
712 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
713 | //! or the copy constructor/operator() of the key_compare object throws. Basic guarantee. |
714 | template<class Iterator> |
715 | bstree_impl( bool unique, Iterator b, Iterator e |
716 | , const key_compare &cmp = key_compare() |
717 | , const value_traits &v_traits = value_traits()) |
718 | : data_type(cmp, v_traits) |
719 | { |
720 | //bstbase releases elements in case of exceptions |
721 | if(unique) |
722 | this->insert_unique(b, e); |
723 | else |
724 | this->insert_equal(b, e); |
725 | } |
726 | |
727 | //! <b>Effects</b>: Constructs a container moving resources from another container. |
728 | //! Internal comparison object and value traits are move constructed and |
729 | //! nodes belonging to x (except the node representing the "end") are linked to *this. |
730 | //! |
731 | //! <b>Complexity</b>: Constant. |
732 | //! |
733 | //! <b>Throws</b>: If value_traits::node_traits::node's |
734 | //! move constructor throws (this does not happen with predefined Boost.Intrusive hooks) |
735 | //! or the move constructor of the comparison objet throws. |
736 | bstree_impl(BOOST_RV_REF(bstree_impl) x) |
737 | : data_type(::boost::move(x.get_comp()), ::boost::move(x.get_value_traits())) |
738 | { |
739 | this->swap(x); |
740 | } |
741 | |
742 | //! <b>Effects</b>: Equivalent to swap |
743 | //! |
744 | inline bstree_impl& operator=(BOOST_RV_REF(bstree_impl) x) |
745 | { this->swap(x); return *this; } |
746 | |
747 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
748 | //! <b>Effects</b>: Detaches all elements from this. The objects in the set |
749 | //! are not deleted (i.e. no destructors are called), but the nodes according to |
750 | //! the value_traits template parameter are reinitialized and thus can be reused. |
751 | //! |
752 | //! <b>Complexity</b>: Linear to elements contained in *this. |
753 | //! |
754 | //! <b>Throws</b>: Nothing. |
755 | ~bstree_impl() |
756 | {} |
757 | |
758 | //! <b>Effects</b>: Returns an iterator pointing to the beginning of the container. |
759 | //! |
760 | //! <b>Complexity</b>: Constant. |
761 | //! |
762 | //! <b>Throws</b>: Nothing. |
763 | iterator begin() BOOST_NOEXCEPT; |
764 | |
765 | //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the container. |
766 | //! |
767 | //! <b>Complexity</b>: Constant. |
768 | //! |
769 | //! <b>Throws</b>: Nothing. |
770 | const_iterator begin() const BOOST_NOEXCEPT; |
771 | |
772 | //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the container. |
773 | //! |
774 | //! <b>Complexity</b>: Constant. |
775 | //! |
776 | //! <b>Throws</b>: Nothing. |
777 | const_iterator cbegin() const BOOST_NOEXCEPT; |
778 | |
779 | //! <b>Effects</b>: Returns an iterator pointing to the end of the container. |
780 | //! |
781 | //! <b>Complexity</b>: Constant. |
782 | //! |
783 | //! <b>Throws</b>: Nothing. |
784 | iterator end() BOOST_NOEXCEPT; |
785 | |
786 | //! <b>Effects</b>: Returns a const_iterator pointing to the end of the container. |
787 | //! |
788 | //! <b>Complexity</b>: Constant. |
789 | //! |
790 | //! <b>Throws</b>: Nothing. |
791 | const_iterator end() const BOOST_NOEXCEPT; |
792 | |
793 | //! <b>Effects</b>: Returns a const_iterator pointing to the end of the container. |
794 | //! |
795 | //! <b>Complexity</b>: Constant. |
796 | //! |
797 | //! <b>Throws</b>: Nothing. |
798 | const_iterator cend() const BOOST_NOEXCEPT; |
799 | |
800 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the |
801 | //! reversed container. |
802 | //! |
803 | //! <b>Complexity</b>: Constant. |
804 | //! |
805 | //! <b>Throws</b>: Nothing. |
806 | reverse_iterator rbegin() BOOST_NOEXCEPT; |
807 | |
808 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning |
809 | //! of the reversed container. |
810 | //! |
811 | //! <b>Complexity</b>: Constant. |
812 | //! |
813 | //! <b>Throws</b>: Nothing. |
814 | const_reverse_iterator rbegin() const BOOST_NOEXCEPT; |
815 | |
816 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning |
817 | //! of the reversed container. |
818 | //! |
819 | //! <b>Complexity</b>: Constant. |
820 | //! |
821 | //! <b>Throws</b>: Nothing. |
822 | const_reverse_iterator crbegin() const BOOST_NOEXCEPT; |
823 | |
824 | //! <b>Effects</b>: Returns a reverse_iterator pointing to the end |
825 | //! of the reversed container. |
826 | //! |
827 | //! <b>Complexity</b>: Constant. |
828 | //! |
829 | //! <b>Throws</b>: Nothing. |
830 | reverse_iterator rend() BOOST_NOEXCEPT; |
831 | |
832 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end |
833 | //! of the reversed container. |
834 | //! |
835 | //! <b>Complexity</b>: Constant. |
836 | //! |
837 | //! <b>Throws</b>: Nothing. |
838 | const_reverse_iterator rend() const BOOST_NOEXCEPT; |
839 | |
840 | //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end |
841 | //! of the reversed container. |
842 | //! |
843 | //! <b>Complexity</b>: Constant. |
844 | //! |
845 | //! <b>Throws</b>: Nothing. |
846 | const_reverse_iterator crend() const BOOST_NOEXCEPT; |
847 | |
848 | //! <b>Effects</b>: Returns a iterator pointing to the root node of the container or end() if not present. |
849 | //! |
850 | //! <b>Complexity</b>: Constant. |
851 | //! |
852 | //! <b>Throws</b>: Nothing. |
853 | iterator root() BOOST_NOEXCEPT; |
854 | |
855 | //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present. |
856 | //! |
857 | //! <b>Complexity</b>: Constant. |
858 | //! |
859 | //! <b>Throws</b>: Nothing. |
860 | const_iterator root() const BOOST_NOEXCEPT; |
861 | |
862 | //! <b>Effects</b>: Returns a const_iterator pointing to the root node of the container or cend() if not present. |
863 | //! |
864 | //! <b>Complexity</b>: Constant. |
865 | //! |
866 | //! <b>Throws</b>: Nothing. |
867 | const_iterator croot() const BOOST_NOEXCEPT; |
868 | |
869 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
870 | |
871 | //! <b>Precondition</b>: end_iterator must be a valid end iterator |
872 | //! of the container. |
873 | //! |
874 | //! <b>Effects</b>: Returns a const reference to the container associated to the end iterator |
875 | //! |
876 | //! <b>Throws</b>: Nothing. |
877 | //! |
878 | //! <b>Complexity</b>: Constant. |
879 | static bstree_impl &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT |
880 | { |
881 | return static_cast<bstree_impl&> |
882 | (data_type::get_tree_base_from_end_iterator(end_iterator)); |
883 | } |
884 | |
885 | //! <b>Precondition</b>: end_iterator must be a valid end const_iterator |
886 | //! of the container. |
887 | //! |
888 | //! <b>Effects</b>: Returns a const reference to the container associated to the iterator |
889 | //! |
890 | //! <b>Throws</b>: Nothing. |
891 | //! |
892 | //! <b>Complexity</b>: Constant. |
893 | static const bstree_impl &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT |
894 | { |
895 | return static_cast<bstree_impl&> |
896 | (data_type::get_tree_base_from_end_iterator(end_iterator)); |
897 | } |
898 | |
899 | //! <b>Precondition</b>: it must be a valid iterator |
900 | //! of the container. |
901 | //! |
902 | //! <b>Effects</b>: Returns a const reference to the container associated to the iterator |
903 | //! |
904 | //! <b>Throws</b>: Nothing. |
905 | //! |
906 | //! <b>Complexity</b>: Logarithmic. |
907 | static bstree_impl &container_from_iterator(iterator it) BOOST_NOEXCEPT |
908 | { return container_from_end_iterator(it.end_iterator_from_it()); } |
909 | |
910 | //! <b>Precondition</b>: it must be a valid end const_iterator |
911 | //! of container. |
912 | //! |
913 | //! <b>Effects</b>: Returns a const reference to the container associated to the end iterator |
914 | //! |
915 | //! <b>Throws</b>: Nothing. |
916 | //! |
917 | //! <b>Complexity</b>: Logarithmic. |
918 | static const bstree_impl &container_from_iterator(const_iterator it) BOOST_NOEXCEPT |
919 | { return container_from_end_iterator(it.end_iterator_from_it()); } |
920 | |
921 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
922 | |
923 | //! <b>Effects</b>: Returns the key_compare object used by the container. |
924 | //! |
925 | //! <b>Complexity</b>: Constant. |
926 | //! |
927 | //! <b>Throws</b>: If key_compare copy-constructor throws. |
928 | key_compare key_comp() const; |
929 | |
930 | //! <b>Effects</b>: Returns the value_compare object used by the container. |
931 | //! |
932 | //! <b>Complexity</b>: Constant. |
933 | //! |
934 | //! <b>Throws</b>: If value_compare copy-constructor throws. |
935 | value_compare value_comp() const; |
936 | |
937 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
938 | |
939 | //! <b>Effects</b>: Returns true if the container is empty. |
940 | //! |
941 | //! <b>Complexity</b>: Constant. |
942 | //! |
943 | //! <b>Throws</b>: Nothing. |
944 | bool empty() const BOOST_NOEXCEPT |
945 | { |
946 | if(ConstantTimeSize){ |
947 | return !this->data_type::sz_traits().get_size(); |
948 | } |
949 | else{ |
950 | return algo_type::unique(this->header_ptr()); |
951 | } |
952 | } |
953 | |
954 | //! <b>Effects</b>: Returns the number of elements stored in the container. |
955 | //! |
956 | //! <b>Complexity</b>: Linear to elements contained in *this |
957 | //! if constant-time size option is disabled. Constant time otherwise. |
958 | //! |
959 | //! <b>Throws</b>: Nothing. |
960 | size_type size() const BOOST_NOEXCEPT |
961 | { |
962 | BOOST_IF_CONSTEXPR(constant_time_size) |
963 | return this->sz_traits().get_size(); |
964 | else{ |
965 | return (size_type)node_algorithms::size(this->header_ptr()); |
966 | } |
967 | } |
968 | |
969 | //! <b>Effects</b>: Swaps the contents of two containers. |
970 | //! |
971 | //! <b>Complexity</b>: Constant. |
972 | //! |
973 | //! <b>Throws</b>: If the comparison functor's swap call throws. |
974 | void swap(bstree_impl& other) |
975 | { |
976 | //This can throw |
977 | ::boost::adl_move_swap(this->get_comp(), other.get_comp()); |
978 | //These can't throw |
979 | node_algorithms::swap_tree(this->header_ptr(), node_ptr(other.header_ptr())); |
980 | this->sz_traits().swap(other.sz_traits()); |
981 | } |
982 | |
983 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
984 | //! Cloner should yield to nodes equivalent to the original nodes. |
985 | //! |
986 | //! <b>Effects</b>: Erases all the elements from *this |
987 | //! calling Disposer::operator()(pointer), clones all the |
988 | //! elements from src calling Cloner::operator()(const_reference ) |
989 | //! and inserts them on *this. Copies the predicate from the source container. |
990 | //! |
991 | //! If cloner throws, all cloned elements are unlinked and disposed |
992 | //! calling Disposer::operator()(pointer). |
993 | //! |
994 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
995 | //! |
996 | //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. |
997 | template <class Cloner, class Disposer> |
998 | void clone_from(const bstree_impl &src, Cloner cloner, Disposer disposer) |
999 | { |
1000 | this->clear_and_dispose(disposer); |
1001 | if(!src.empty()){ |
1002 | detail::exception_disposer<bstree_impl, Disposer> |
1003 | rollback(*this, disposer); |
1004 | node_algorithms::clone |
1005 | (src.header_ptr() |
1006 | ,this->header_ptr() |
1007 | ,detail::node_cloner <Cloner, value_traits, AlgoType>(cloner, &this->get_value_traits()) |
1008 | ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); |
1009 | this->sz_traits().set_size(src.sz_traits().get_size()); |
1010 | this->get_comp() = src.get_comp(); |
1011 | rollback.release(); |
1012 | } |
1013 | } |
1014 | |
1015 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1016 | //! Cloner should yield to nodes equivalent to the original nodes. |
1017 | //! |
1018 | //! <b>Effects</b>: Erases all the elements from *this |
1019 | //! calling Disposer::operator()(pointer), clones all the |
1020 | //! elements from src calling Cloner::operator()(reference) |
1021 | //! and inserts them on *this. Copies the predicate from the source container. |
1022 | //! |
1023 | //! If cloner throws, all cloned elements are unlinked and disposed |
1024 | //! calling Disposer::operator()(pointer). |
1025 | //! |
1026 | //! <b>Complexity</b>: Linear to erased plus inserted elements. |
1027 | //! |
1028 | //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee. |
1029 | //! |
1030 | //! <b>Note</b>: This version can modify the source container, useful to implement |
1031 | //! move semantics. |
1032 | template <class Cloner, class Disposer> |
1033 | void clone_from(BOOST_RV_REF(bstree_impl) src, Cloner cloner, Disposer disposer) |
1034 | { |
1035 | this->clear_and_dispose(disposer); |
1036 | if(!src.empty()){ |
1037 | detail::exception_disposer<bstree_impl, Disposer> |
1038 | rollback(*this, disposer); |
1039 | node_algorithms::clone |
1040 | (src.header_ptr() |
1041 | ,this->header_ptr() |
1042 | ,detail::node_cloner <Cloner, value_traits, AlgoType, false>(cloner, &this->get_value_traits()) |
1043 | ,detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); |
1044 | this->sz_traits().set_size(src.sz_traits().get_size()); |
1045 | this->get_comp() = src.get_comp(); |
1046 | rollback.release(); |
1047 | } |
1048 | } |
1049 | |
1050 | //! <b>Requires</b>: value must be an lvalue |
1051 | //! |
1052 | //! <b>Effects</b>: Inserts value into the container before the upper bound. |
1053 | //! |
1054 | //! <b>Complexity</b>: Average complexity for insert element is at |
1055 | //! most logarithmic. |
1056 | //! |
1057 | //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee. |
1058 | //! |
1059 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1060 | //! No copy-constructors are called. |
1061 | iterator insert_equal(reference value) |
1062 | { |
1063 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1064 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1065 | iterator ret(node_algorithms::insert_equal_upper_bound |
1066 | (this->header_ptr(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); |
1067 | this->sz_traits().increment(); |
1068 | return ret; |
1069 | } |
1070 | |
1071 | //! <b>Requires</b>: value must be an lvalue, and "hint" must be |
1072 | //! a valid iterator. |
1073 | //! |
1074 | //! <b>Effects</b>: Inserts x into the container, using "hint" as a hint to |
1075 | //! where it will be inserted. If "hint" is the upper_bound |
1076 | //! the insertion takes constant time (two comparisons in the worst case) |
1077 | //! |
1078 | //! <b>Complexity</b>: Logarithmic in general, but it is amortized |
1079 | //! constant time if t is inserted immediately before hint. |
1080 | //! |
1081 | //! <b>Throws</b>: If the internal key_compare ordering function throws. Strong guarantee. |
1082 | //! |
1083 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1084 | //! No copy-constructors are called. |
1085 | iterator insert_equal(const_iterator hint, reference value) |
1086 | { |
1087 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1088 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1089 | iterator ret(node_algorithms::insert_equal |
1090 | (this->header_ptr(), hint.pointed_node(), to_insert, this->key_node_comp(this->key_comp())), this->priv_value_traits_ptr()); |
1091 | this->sz_traits().increment(); |
1092 | return ret; |
1093 | } |
1094 | |
1095 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue |
1096 | //! of type value_type. |
1097 | //! |
1098 | //! <b>Effects</b>: Inserts a each element of a range into the container |
1099 | //! before the upper bound of the key of each element. |
1100 | //! |
1101 | //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the |
1102 | //! size of the range. However, it is linear in N if the range is already sorted |
1103 | //! by value_comp(). |
1104 | //! |
1105 | //! <b>Throws</b>: If the comparison functor call throws. |
1106 | //! |
1107 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1108 | //! No copy-constructors are called. |
1109 | template<class Iterator> |
1110 | void insert_equal(Iterator b, Iterator e) |
1111 | { |
1112 | iterator iend(this->end()); |
1113 | for (; b != e; ++b) |
1114 | this->insert_equal(iend, *b); |
1115 | } |
1116 | |
1117 | //! <b>Requires</b>: value must be an lvalue |
1118 | //! |
1119 | //! <b>Effects</b>: Inserts value into the container if the value |
1120 | //! is not already present. |
1121 | //! |
1122 | //! <b>Complexity</b>: Average complexity for insert element is at |
1123 | //! most logarithmic. |
1124 | //! |
1125 | //! <b>Throws</b>: If the comparison functor call throws. |
1126 | //! |
1127 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1128 | //! No copy-constructors are called. |
1129 | std::pair<iterator, bool> insert_unique(reference value) |
1130 | { |
1131 | insert_commit_data commit_data; |
1132 | std::pair<node_ptr, bool> ret = |
1133 | (node_algorithms::insert_unique_check |
1134 | (this->header_ptr(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); |
1135 | return std::pair<iterator, bool> |
1136 | ( ret.second ? this->insert_unique_commit(value, commit_data) |
1137 | : iterator(ret.first, this->priv_value_traits_ptr()) |
1138 | , ret.second); |
1139 | } |
1140 | |
1141 | //! <b>Requires</b>: value must be an lvalue, and "hint" must be |
1142 | //! a valid iterator |
1143 | //! |
1144 | //! <b>Effects</b>: Tries to insert x into the container, using "hint" as a hint |
1145 | //! to where it will be inserted. |
1146 | //! |
1147 | //! <b>Complexity</b>: Logarithmic in general, but it is amortized |
1148 | //! constant time (two comparisons in the worst case) |
1149 | //! if t is inserted immediately before hint. |
1150 | //! |
1151 | //! <b>Throws</b>: If the comparison functor call throws. |
1152 | //! |
1153 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1154 | //! No copy-constructors are called. |
1155 | iterator insert_unique(const_iterator hint, reference value) |
1156 | { |
1157 | insert_commit_data commit_data; |
1158 | std::pair<node_ptr, bool> ret = |
1159 | (node_algorithms::insert_unique_check |
1160 | (this->header_ptr(), hint.pointed_node(), key_of_value()(value), this->key_node_comp(this->key_comp()), commit_data)); |
1161 | return ret.second ? this->insert_unique_commit(value, commit_data) |
1162 | : iterator(ret.first, this->priv_value_traits_ptr()); |
1163 | } |
1164 | |
1165 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue |
1166 | //! of type value_type. |
1167 | //! |
1168 | //! <b>Effects</b>: Tries to insert each element of a range into the container. |
1169 | //! |
1170 | //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the |
1171 | //! size of the range. However, it is linear in N if the range is already sorted |
1172 | //! by value_comp(). |
1173 | //! |
1174 | //! <b>Throws</b>: If the comparison functor call throws. |
1175 | //! |
1176 | //! <b>Note</b>: Does not affect the validity of iterators and references. |
1177 | //! No copy-constructors are called. |
1178 | template<class Iterator> |
1179 | void insert_unique(Iterator b, Iterator e) |
1180 | { |
1181 | if(this->empty()){ |
1182 | iterator iend(this->end()); |
1183 | for (; b != e; ++b) |
1184 | this->insert_unique(iend, *b); |
1185 | } |
1186 | else{ |
1187 | for (; b != e; ++b) |
1188 | this->insert_unique(*b); |
1189 | } |
1190 | } |
1191 | |
1192 | #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
1193 | |
1194 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
1195 | //! a user provided key instead of the value itself. |
1196 | //! |
1197 | //! <b>Returns</b>: If there is an equivalent value |
1198 | //! returns a pair containing an iterator to the already present value |
1199 | //! and false. If the value can be inserted returns true in the returned |
1200 | //! pair boolean and fills "commit_data" that is meant to be used with |
1201 | //! the "insert_commit" function. |
1202 | //! |
1203 | //! <b>Complexity</b>: Average complexity is at most logarithmic. |
1204 | //! |
1205 | //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. |
1206 | std::pair<iterator, bool> insert_unique_check(const key_type &key, insert_commit_data &commit_data); |
1207 | |
1208 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
1209 | //! a user provided key instead of the value itself, using "hint" |
1210 | //! as a hint to where it will be inserted. |
1211 | //! |
1212 | //! <b>Returns</b>: If there is an equivalent value |
1213 | //! returns a pair containing an iterator to the already present value |
1214 | //! and false. If the value can be inserted returns true in the returned |
1215 | //! pair boolean and fills "commit_data" that is meant to be used with |
1216 | //! the "insert_commit" function. |
1217 | //! |
1218 | //! <b>Complexity</b>: Logarithmic in general, but it's amortized |
1219 | //! constant time if t is inserted immediately before hint. |
1220 | //! |
1221 | //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. |
1222 | std::pair<iterator, bool> insert_unique_check(const_iterator hint, const key_type &key, insert_commit_data &commit_data); |
1223 | |
1224 | //! <b>Requires</b>: comp must be a comparison function that induces |
1225 | //! the same strict weak ordering as key_compare. The difference is that |
1226 | //! comp compares an arbitrary key with the contained values. |
1227 | //! |
1228 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
1229 | //! a user provided key instead of the value itself. |
1230 | //! |
1231 | //! <b>Returns</b>: If there is an equivalent value |
1232 | //! returns a pair containing an iterator to the already present value |
1233 | //! and false. If the value can be inserted returns true in the returned |
1234 | //! pair boolean and fills "commit_data" that is meant to be used with |
1235 | //! the "insert_commit" function. |
1236 | //! |
1237 | //! <b>Complexity</b>: Average complexity is at most logarithmic. |
1238 | //! |
1239 | //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. |
1240 | //! |
1241 | //! <b>Notes</b>: This function is used to improve performance when constructing |
1242 | //! a value_type is expensive: if there is an equivalent value |
1243 | //! the constructed object must be discarded. Many times, the part of the |
1244 | //! node that is used to impose the order is much cheaper to construct |
1245 | //! than the value_type and this function offers the possibility to use that |
1246 | //! part to check if the insertion will be successful. |
1247 | //! |
1248 | //! If the check is successful, the user can construct the value_type and use |
1249 | //! "insert_commit" to insert the object in constant-time. This gives a total |
1250 | //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)). |
1251 | //! |
1252 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more |
1253 | //! objects are inserted or erased from the container. |
1254 | template<class KeyType, class KeyTypeKeyCompare> |
1255 | std::pair<iterator, bool> insert_unique_check |
1256 | (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
1257 | |
1258 | //! <b>Requires</b>: comp must be a comparison function that induces |
1259 | //! the same strict weak ordering as key_compare. The difference is that |
1260 | //! comp compares an arbitrary key with the contained values. |
1261 | //! |
1262 | //! <b>Effects</b>: Checks if a value can be inserted in the container, using |
1263 | //! a user provided key instead of the value itself, using "hint" |
1264 | //! as a hint to where it will be inserted. |
1265 | //! |
1266 | //! <b>Returns</b>: If there is an equivalent value |
1267 | //! returns a pair containing an iterator to the already present value |
1268 | //! and false. If the value can be inserted returns true in the returned |
1269 | //! pair boolean and fills "commit_data" that is meant to be used with |
1270 | //! the "insert_commit" function. |
1271 | //! |
1272 | //! <b>Complexity</b>: Logarithmic in general, but it's amortized |
1273 | //! constant time if t is inserted immediately before hint. |
1274 | //! |
1275 | //! <b>Throws</b>: If the comp ordering function throws. Strong guarantee. |
1276 | //! |
1277 | //! <b>Notes</b>: This function is used to improve performance when constructing |
1278 | //! a value_type is expensive: if there is an equivalent value |
1279 | //! the constructed object must be discarded. Many times, the part of the |
1280 | //! constructing that is used to impose the order is much cheaper to construct |
1281 | //! than the value_type and this function offers the possibility to use that key |
1282 | //! to check if the insertion will be successful. |
1283 | //! |
1284 | //! If the check is successful, the user can construct the value_type and use |
1285 | //! "insert_commit" to insert the object in constant-time. This can give a total |
1286 | //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)). |
1287 | //! |
1288 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more |
1289 | //! objects are inserted or erased from the container. |
1290 | template<class KeyType, class KeyTypeKeyCompare> |
1291 | std::pair<iterator, bool> insert_unique_check |
1292 | (const_iterator hint, const KeyType &key |
1293 | ,KeyTypeKeyCompare comp, insert_commit_data &commit_data); |
1294 | |
1295 | #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
1296 | |
1297 | //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data |
1298 | //! must have been obtained from a previous call to "insert_check". |
1299 | //! No objects should have been inserted or erased from the container between |
1300 | //! the "insert_check" that filled "commit_data" and the call to "insert_commit". |
1301 | //! |
1302 | //! <b>Effects</b>: Inserts the value in the container using the information obtained |
1303 | //! from the "commit_data" that a previous "insert_check" filled. |
1304 | //! |
1305 | //! <b>Returns</b>: An iterator to the newly inserted object. |
1306 | //! |
1307 | //! <b>Complexity</b>: Constant time. |
1308 | //! |
1309 | //! <b>Throws</b>: Nothing. |
1310 | //! |
1311 | //! <b>Notes</b>: This function has only sense if a "insert_check" has been |
1312 | //! previously executed to fill "commit_data". No value should be inserted or |
1313 | //! erased between the "insert_check" and "insert_commit" calls. |
1314 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT |
1315 | { |
1316 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1317 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1318 | |
1319 | #if !(defined(BOOST_DISABLE_ASSERTS) || ( defined(BOOST_ENABLE_ASSERT_DEBUG_HANDLER) && defined(NDEBUG) )) |
1320 | //Test insertion position is correct |
1321 | iterator p(commit_data.node, this->priv_value_traits_ptr()); |
1322 | if(!commit_data.link_left){ |
1323 | ++p; |
1324 | } |
1325 | //Check if the insertion point is correct to detect wrong |
1326 | //uses insert_unique_check |
1327 | BOOST_ASSERT(( p == this->end() || !this->get_comp()(*p, value) )); |
1328 | BOOST_ASSERT(( p == this->begin() || !this->get_comp()(value, *--p) )); |
1329 | #endif |
1330 | |
1331 | node_algorithms::insert_unique_commit |
1332 | (this->header_ptr(), to_insert, commit_data); |
1333 | this->sz_traits().increment(); |
1334 | return iterator(to_insert, this->priv_value_traits_ptr()); |
1335 | } |
1336 | |
1337 | //! <b>Requires</b>: value must be an lvalue, "pos" must be |
1338 | //! a valid iterator (or end) and must be the succesor of value |
1339 | //! once inserted according to the predicate |
1340 | //! |
1341 | //! <b>Effects</b>: Inserts x into the container before "pos". |
1342 | //! |
1343 | //! <b>Complexity</b>: Constant time. |
1344 | //! |
1345 | //! <b>Throws</b>: Nothing. |
1346 | //! |
1347 | //! <b>Note</b>: This function does not check preconditions so if "pos" is not |
1348 | //! the successor of "value" container ordering invariant will be broken. |
1349 | //! This is a low-level function to be used only for performance reasons |
1350 | //! by advanced users. |
1351 | iterator insert_before(const_iterator pos, reference value) BOOST_NOEXCEPT |
1352 | { |
1353 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1354 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1355 | this->sz_traits().increment(); |
1356 | return iterator(node_algorithms::insert_before |
1357 | (this->header_ptr(), pos.pointed_node(), to_insert), this->priv_value_traits_ptr()); |
1358 | } |
1359 | |
1360 | //! <b>Requires</b>: value must be an lvalue, and it must be no less |
1361 | //! than the greatest inserted key |
1362 | //! |
1363 | //! <b>Effects</b>: Inserts x into the container in the last position. |
1364 | //! |
1365 | //! <b>Complexity</b>: Constant time. |
1366 | //! |
1367 | //! <b>Throws</b>: Nothing. |
1368 | //! |
1369 | //! <b>Note</b>: This function does not check preconditions so if value is |
1370 | //! less than the greatest inserted key container ordering invariant will be broken. |
1371 | //! This function is slightly more efficient than using "insert_before". |
1372 | //! This is a low-level function to be used only for performance reasons |
1373 | //! by advanced users. |
1374 | void push_back(reference value) BOOST_NOEXCEPT |
1375 | { |
1376 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1377 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1378 | this->sz_traits().increment(); |
1379 | node_algorithms::push_back(this->header_ptr(), to_insert); |
1380 | } |
1381 | |
1382 | //! <b>Requires</b>: value must be an lvalue, and it must be no greater |
1383 | //! than the minimum inserted key |
1384 | //! |
1385 | //! <b>Effects</b>: Inserts x into the container in the first position. |
1386 | //! |
1387 | //! <b>Complexity</b>: Constant time. |
1388 | //! |
1389 | //! <b>Throws</b>: Nothing. |
1390 | //! |
1391 | //! <b>Note</b>: This function does not check preconditions so if value is |
1392 | //! greater than the minimum inserted key container ordering invariant will be broken. |
1393 | //! This function is slightly more efficient than using "insert_before". |
1394 | //! This is a low-level function to be used only for performance reasons |
1395 | //! by advanced users. |
1396 | void push_front(reference value) BOOST_NOEXCEPT |
1397 | { |
1398 | node_ptr to_insert(this->get_value_traits().to_node_ptr(value)); |
1399 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(to_insert)); |
1400 | this->sz_traits().increment(); |
1401 | node_algorithms::push_front(this->header_ptr(), to_insert); |
1402 | } |
1403 | |
1404 | //! <b>Effects</b>: Erases the element pointed to by i. |
1405 | //! |
1406 | //! <b>Complexity</b>: Average complexity for erase element is constant time. |
1407 | //! |
1408 | //! <b>Throws</b>: Nothing. |
1409 | //! |
1410 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1411 | //! to the erased elements. No destructors are called. |
1412 | iterator erase(const_iterator i) BOOST_NOEXCEPT |
1413 | { |
1414 | const_iterator ret(i); |
1415 | ++ret; |
1416 | node_ptr to_erase(i.pointed_node()); |
1417 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(to_erase)); |
1418 | node_algorithms::erase(this->header_ptr(), to_erase); |
1419 | this->sz_traits().decrement(); |
1420 | BOOST_IF_CONSTEXPR(safemode_or_autounlink) |
1421 | node_algorithms::init(to_erase); |
1422 | return ret.unconst(); |
1423 | } |
1424 | |
1425 | //! <b>Effects</b>: Erases the range pointed to by b end e. |
1426 | //! |
1427 | //! <b>Complexity</b>: Average complexity for erase range is at most |
1428 | //! O(log(size() + N)), where N is the number of elements in the range. |
1429 | //! |
1430 | //! <b>Throws</b>: Nothing. |
1431 | //! |
1432 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1433 | //! to the erased elements. No destructors are called. |
1434 | iterator erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT |
1435 | { size_type n; return this->private_erase(b, e, n); } |
1436 | |
1437 | //! <b>Effects</b>: Erases all the elements with the given value. |
1438 | //! |
1439 | //! <b>Returns</b>: The number of erased elements. |
1440 | //! |
1441 | //! <b>Complexity</b>: O(log(size() + N). |
1442 | //! |
1443 | //! <b>Throws</b>: Nothing. |
1444 | //! |
1445 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1446 | //! to the erased elements. No destructors are called. |
1447 | size_type erase(const key_type &key) BOOST_NOEXCEPT |
1448 | { return this->erase(key, this->key_comp()); } |
1449 | |
1450 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1451 | //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), |
1452 | //! with nk the key_type of a value_type inserted into `*this`. |
1453 | //! |
1454 | //! <b>Effects</b>: Erases all the elements with the given key. |
1455 | //! according to the comparison functor "comp". |
1456 | //! |
1457 | //! <b>Returns</b>: The number of erased elements. |
1458 | //! |
1459 | //! <b>Complexity</b>: O(log(size() + N). |
1460 | //! |
1461 | //! <b>Throws</b>: Nothing. |
1462 | //! |
1463 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1464 | //! to the erased elements. No destructors are called. |
1465 | template<class KeyType, class KeyTypeKeyCompare> |
1466 | BOOST_INTRUSIVE_DOC1ST(size_type |
1467 | , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) |
1468 | erase(const KeyType& key, KeyTypeKeyCompare comp) |
1469 | { |
1470 | std::pair<iterator,iterator> p = this->equal_range(key, comp); |
1471 | size_type n; |
1472 | this->private_erase(p.first, p.second, n); |
1473 | return n; |
1474 | } |
1475 | |
1476 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1477 | //! |
1478 | //! <b>Effects</b>: Erases the element pointed to by i. |
1479 | //! Disposer::operator()(pointer) is called for the removed element. |
1480 | //! |
1481 | //! <b>Complexity</b>: Average complexity for erase element is constant time. |
1482 | //! |
1483 | //! <b>Throws</b>: Nothing. |
1484 | //! |
1485 | //! <b>Note</b>: Invalidates the iterators |
1486 | //! to the erased elements. |
1487 | template<class Disposer> |
1488 | iterator erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT |
1489 | { |
1490 | node_ptr to_erase(i.pointed_node()); |
1491 | iterator ret(this->erase(i)); |
1492 | disposer(this->get_value_traits().to_value_ptr(to_erase)); |
1493 | return ret; |
1494 | } |
1495 | |
1496 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1497 | //! |
1498 | //! <b>Effects</b>: Erases all the elements with the given value. |
1499 | //! Disposer::operator()(pointer) is called for the removed elements. |
1500 | //! |
1501 | //! <b>Returns</b>: The number of erased elements. |
1502 | //! |
1503 | //! <b>Complexity</b>: O(log(size() + N). |
1504 | //! |
1505 | //! <b>Throws</b>: Nothing. |
1506 | //! |
1507 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1508 | //! to the erased elements. No destructors are called. |
1509 | template<class Disposer> |
1510 | size_type erase_and_dispose(const key_type &key, Disposer disposer) |
1511 | { |
1512 | std::pair<iterator,iterator> p = this->equal_range(key); |
1513 | size_type n; |
1514 | this->private_erase(p.first, p.second, n, disposer); |
1515 | return n; |
1516 | } |
1517 | |
1518 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1519 | //! |
1520 | //! <b>Effects</b>: Erases the range pointed to by b end e. |
1521 | //! Disposer::operator()(pointer) is called for the removed elements. |
1522 | //! |
1523 | //! <b>Complexity</b>: Average complexity for erase range is at most |
1524 | //! O(log(size() + N)), where N is the number of elements in the range. |
1525 | //! |
1526 | //! <b>Throws</b>: Nothing. |
1527 | //! |
1528 | //! <b>Note</b>: Invalidates the iterators |
1529 | //! to the erased elements. |
1530 | template<class Disposer> |
1531 | iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT |
1532 | { size_type n; return this->private_erase(b, e, n, disposer); } |
1533 | |
1534 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1535 | //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk) |
1536 | //! and nk the key_type of a value_type inserted into `*this`. |
1537 | //! |
1538 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. |
1539 | //! |
1540 | //! <b>Effects</b>: Erases all the elements with the given key. |
1541 | //! according to the comparison functor "comp". |
1542 | //! Disposer::operator()(pointer) is called for the removed elements. |
1543 | //! |
1544 | //! <b>Returns</b>: The number of erased elements. |
1545 | //! |
1546 | //! <b>Complexity</b>: O(log(size() + N). |
1547 | //! |
1548 | //! <b>Throws</b>: Nothing. |
1549 | //! |
1550 | //! <b>Note</b>: Invalidates the iterators |
1551 | //! to the erased elements. |
1552 | template<class KeyType, class KeyTypeKeyCompare, class Disposer> |
1553 | BOOST_INTRUSIVE_DOC1ST(size_type |
1554 | , typename detail::disable_if_convertible<KeyTypeKeyCompare BOOST_INTRUSIVE_I const_iterator BOOST_INTRUSIVE_I size_type>::type) |
1555 | erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer) |
1556 | { |
1557 | std::pair<iterator,iterator> p = this->equal_range(key, comp); |
1558 | size_type n; |
1559 | this->private_erase(p.first, p.second, n, disposer); |
1560 | return n; |
1561 | } |
1562 | |
1563 | //! <b>Effects</b>: Erases all of the elements. |
1564 | //! |
1565 | //! <b>Complexity</b>: Linear to the number of elements on the container. |
1566 | //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. |
1567 | //! |
1568 | //! <b>Throws</b>: Nothing. |
1569 | //! |
1570 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1571 | //! to the erased elements. No destructors are called. |
1572 | void clear() BOOST_NOEXCEPT |
1573 | { |
1574 | BOOST_IF_CONSTEXPR(safemode_or_autounlink){ |
1575 | this->clear_and_dispose(detail::null_disposer()); |
1576 | } |
1577 | else{ |
1578 | node_algorithms::init_header(this->header_ptr()); |
1579 | this->sz_traits().set_size(0); |
1580 | } |
1581 | } |
1582 | |
1583 | //! <b>Effects</b>: Erases all of the elements calling disposer(p) for |
1584 | //! each node to be erased. |
1585 | //! <b>Complexity</b>: Average complexity for is at most O(log(size() + N)), |
1586 | //! where N is the number of elements in the container. |
1587 | //! |
1588 | //! <b>Throws</b>: Nothing. |
1589 | //! |
1590 | //! <b>Note</b>: Invalidates the iterators (but not the references) |
1591 | //! to the erased elements. Calls N times to disposer functor. |
1592 | template<class Disposer> |
1593 | void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT |
1594 | { |
1595 | node_algorithms::clear_and_dispose(this->header_ptr() |
1596 | , detail::node_disposer<Disposer, value_traits, AlgoType>(disposer, &this->get_value_traits())); |
1597 | node_algorithms::init_header(this->header_ptr()); |
1598 | this->sz_traits().set_size(0); |
1599 | } |
1600 | |
1601 | //! <b>Effects</b>: Returns the number of contained elements with the given value |
1602 | //! |
1603 | //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal |
1604 | //! to number of objects with the given value. |
1605 | //! |
1606 | //! <b>Throws</b>: If `key_compare` throws. |
1607 | size_type count(const key_type &key) const |
1608 | { return size_type(this->count(key, this->key_comp())); } |
1609 | |
1610 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1611 | //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), |
1612 | //! and nk the key_type of a value_type inserted into `*this`. |
1613 | //! |
1614 | //! <b>Effects</b>: Returns the number of contained elements with the given key |
1615 | //! |
1616 | //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal |
1617 | //! to number of objects with the given key. |
1618 | //! |
1619 | //! <b>Throws</b>: If `comp` throws. |
1620 | template<class KeyType, class KeyTypeKeyCompare> |
1621 | size_type count(const KeyType &key, KeyTypeKeyCompare comp) const |
1622 | { |
1623 | std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); |
1624 | size_type n = 0; |
1625 | for(; ret.first != ret.second; ++ret.first){ ++n; } |
1626 | return n; |
1627 | } |
1628 | |
1629 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1630 | |
1631 | //Add non-const overloads to theoretically const members |
1632 | //as some algorithms have different behavior when non-const versions are used (like splay trees). |
1633 | size_type count(const key_type &key) |
1634 | { return size_type(this->count(key, this->key_comp())); } |
1635 | |
1636 | template<class KeyType, class KeyTypeKeyCompare> |
1637 | size_type count(const KeyType &key, KeyTypeKeyCompare comp) |
1638 | { |
1639 | std::pair<const_iterator, const_iterator> ret = this->equal_range(key, comp); |
1640 | size_type n = 0; |
1641 | for(; ret.first != ret.second; ++ret.first){ ++n; } |
1642 | return n; |
1643 | } |
1644 | |
1645 | #else //defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1646 | |
1647 | //! <b>Effects</b>: Returns an iterator to the first element whose |
1648 | //! key is not less than k or end() if that element does not exist. |
1649 | //! |
1650 | //! <b>Complexity</b>: Logarithmic. |
1651 | //! |
1652 | //! <b>Throws</b>: If `key_compare` throws. |
1653 | iterator lower_bound(const key_type &key); |
1654 | |
1655 | //! <b>Effects</b>: Returns an iterator to the first element whose |
1656 | //! key is not less than k or end() if that element does not exist. |
1657 | //! |
1658 | //! <b>Complexity</b>: Logarithmic. |
1659 | //! |
1660 | //! <b>Throws</b>: If `key_compare` throws. |
1661 | const_iterator lower_bound(const key_type &key) const; |
1662 | |
1663 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &) |
1664 | template<class KeyType, class KeyTypeKeyCompare> |
1665 | iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp); |
1666 | |
1667 | //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare) |
1668 | template<class KeyType, class KeyTypeKeyCompare> |
1669 | const_iterator lower_bound(const KeyType &key, KeyTypeKeyCompare comp) const; |
1670 | |
1671 | //! <b>Effects</b>: Returns an iterator to the first element whose |
1672 | //! key is greater than k or end() if that element does not exist. |
1673 | //! |
1674 | //! <b>Complexity</b>: Logarithmic. |
1675 | //! |
1676 | //! <b>Throws</b>: If `key_compare` throws. |
1677 | iterator upper_bound(const key_type &key); |
1678 | |
1679 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1680 | //! !comp(key, nk), with nk the key_type of a value_type inserted into `*this`. |
1681 | //! |
1682 | //! <b>Effects</b>: Returns an iterator to the first element whose |
1683 | //! key is greater than k according to comp or end() if that element |
1684 | //! does not exist. |
1685 | //! |
1686 | //! <b>Complexity</b>: Logarithmic. |
1687 | //! |
1688 | //! <b>Throws</b>: If `comp` throws. |
1689 | template<class KeyType, class KeyTypeKeyCompare> |
1690 | iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp); |
1691 | |
1692 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &) |
1693 | const_iterator upper_bound(const key_type &key) const; |
1694 | |
1695 | //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare) |
1696 | template<class KeyType, class KeyTypeKeyCompare> |
1697 | const_iterator upper_bound(const KeyType &key, KeyTypeKeyCompare comp) const; |
1698 | |
1699 | //! <b>Effects</b>: Finds an iterator to the first element whose key is |
1700 | //! k or end() if that element does not exist. |
1701 | //! |
1702 | //! <b>Complexity</b>: Logarithmic. |
1703 | //! |
1704 | //! <b>Throws</b>: If `key_compare` throws. |
1705 | iterator find(const key_type &key); |
1706 | |
1707 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1708 | //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), |
1709 | //! and nk the key_type of a value_type inserted into `*this`. |
1710 | //! |
1711 | //! <b>Effects</b>: Finds an iterator to the first element whose key is |
1712 | //! k or end() if that element does not exist. |
1713 | //! |
1714 | //! <b>Complexity</b>: Logarithmic. |
1715 | //! |
1716 | //! <b>Throws</b>: If `comp` throws. |
1717 | template<class KeyType, class KeyTypeKeyCompare> |
1718 | iterator find(const KeyType &key, KeyTypeKeyCompare comp); |
1719 | |
1720 | //! @copydoc ::boost::intrusive::bstree::find(const key_type &) |
1721 | const_iterator find(const key_type &key) const; |
1722 | |
1723 | //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare) |
1724 | template<class KeyType, class KeyTypeKeyCompare> |
1725 | const_iterator find(const KeyType &key, KeyTypeKeyCompare comp) const; |
1726 | |
1727 | //! <b>Effects</b>: Finds a range containing all elements whose key is k or |
1728 | //! an empty range that indicates the position where those elements would be |
1729 | //! if they there is no elements with key k. |
1730 | //! |
1731 | //! <b>Complexity</b>: Logarithmic. |
1732 | //! |
1733 | //! <b>Throws</b>: If `key_compare` throws. |
1734 | std::pair<iterator,iterator> equal_range(const key_type &key); |
1735 | |
1736 | //! <b>Requires</b>: key is a value such that `*this` is partitioned with respect to |
1737 | //! comp(nk, key) and !comp(key, nk), with comp(nk, key) implying !comp(key, nk), |
1738 | //! with nk the key_type of a value_type inserted into `*this`. |
1739 | //! |
1740 | //! <b>Effects</b>: Finds a range containing all elements whose key is k or |
1741 | //! an empty range that indicates the position where those elements would be |
1742 | //! if they there is no elements with key k. |
1743 | //! |
1744 | //! <b>Complexity</b>: Logarithmic. |
1745 | //! |
1746 | //! <b>Throws</b>: If `comp` throws. |
1747 | template<class KeyType, class KeyTypeKeyCompare> |
1748 | std::pair<iterator,iterator> equal_range(const KeyType &key, KeyTypeKeyCompare comp); |
1749 | |
1750 | //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &) |
1751 | std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const; |
1752 | |
1753 | //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare) |
1754 | template<class KeyType, class KeyTypeKeyCompare> |
1755 | std::pair<const_iterator, const_iterator> |
1756 | equal_range(const KeyType &key, KeyTypeKeyCompare comp) const; |
1757 | |
1758 | //! <b>Requires</b>: |
1759 | //! `upper_key` shall not precede `lower_key` according to key_compare. |
1760 | //! [key_comp()(upper_key, lower_key) shall be false] |
1761 | //! |
1762 | //! If `lower_key` is equivalent to `upper_key` |
1763 | //! [!key_comp()(upper_key, lower_key) && !key_comp()(lower_key, upper_key)] then |
1764 | //! ('left_closed' || 'right_closed') must be false. |
1765 | //! |
1766 | //! <b>Effects</b>: Returns an a pair with the following criteria: |
1767 | //! |
1768 | //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise |
1769 | //! |
1770 | //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise |
1771 | //! |
1772 | //! <b>Complexity</b>: Logarithmic. |
1773 | //! |
1774 | //! <b>Throws</b>: If `key_compare` throws. |
1775 | //! |
1776 | //! <b>Note</b>: This function can be more efficient than calling upper_bound |
1777 | //! and lower_bound for lower_value and upper_value. |
1778 | //! |
1779 | //! <b>Note</b>: Experimental function, the interface might change in future releases. |
1780 | std::pair<iterator,iterator> bounded_range |
1781 | (const key_type &lower_key, const key_type &upper_value, bool left_closed, bool right_closed); |
1782 | |
1783 | //! <b>Requires</b>: |
1784 | //! `lower_key` is a value such that `*this` is partitioned with respect to |
1785 | //! comp(nk, lower_key) if left_closed is true, with respect to !comp(lower_key, nk) otherwise. |
1786 | //! |
1787 | //! `upper_key` is a value such that `*this` is partitioned with respect to |
1788 | //! !comp(upper_key, nk) if right_closed is true, with respect to comp(nk, upper_key) otherwise. |
1789 | //! |
1790 | //! `upper_key` shall not precede `lower_key` according to comp |
1791 | //! [comp(upper_key, lower_key) shall be false] |
1792 | //! |
1793 | //! If `lower_key` is equivalent to `upper_key` |
1794 | //! [!comp(upper_key, lower_key) && !comp(lower_key, upper_key)] then |
1795 | //! ('left_closed' || 'right_closed') must be false. |
1796 | //! |
1797 | //! <b>Effects</b>: Returns an a pair with the following criteria: |
1798 | //! |
1799 | //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise |
1800 | //! |
1801 | //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise |
1802 | //! |
1803 | //! <b>Complexity</b>: Logarithmic. |
1804 | //! |
1805 | //! <b>Throws</b>: If `comp` throws. |
1806 | //! |
1807 | //! <b>Note</b>: This function can be more efficient than calling upper_bound |
1808 | //! and lower_bound for lower_key and upper_key. |
1809 | //! |
1810 | //! <b>Note</b>: Experimental function, the interface might change in future releases. |
1811 | template<class KeyType, class KeyTypeKeyCompare> |
1812 | std::pair<iterator,iterator> bounded_range |
1813 | (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed); |
1814 | |
1815 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool) |
1816 | std::pair<const_iterator,const_iterator> bounded_range |
1817 | (const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const; |
1818 | |
1819 | //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool) |
1820 | template<class KeyType, class KeyTypeKeyCompare> |
1821 | std::pair<const_iterator,const_iterator> bounded_range |
1822 | (const KeyType &lower_key, const KeyType &upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const; |
1823 | |
1824 | //! <b>Requires</b>: value must be an lvalue and shall be in a set of |
1825 | //! appropriate type. Otherwise the behavior is undefined. |
1826 | //! |
1827 | //! <b>Effects</b>: Returns: a valid iterator i belonging to the set |
1828 | //! that points to the value |
1829 | //! |
1830 | //! <b>Complexity</b>: Constant. |
1831 | //! |
1832 | //! <b>Throws</b>: Nothing. |
1833 | //! |
1834 | //! <b>Note</b>: This static function is available only if the <i>value traits</i> |
1835 | //! is stateless. |
1836 | static iterator s_iterator_to(reference value) BOOST_NOEXCEPT; |
1837 | |
1838 | //! <b>Requires</b>: value must be an lvalue and shall be in a set of |
1839 | //! appropriate type. Otherwise the behavior is undefined. |
1840 | //! |
1841 | //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the |
1842 | //! set that points to the value |
1843 | //! |
1844 | //! <b>Complexity</b>: Constant. |
1845 | //! |
1846 | //! <b>Throws</b>: Nothing. |
1847 | //! |
1848 | //! <b>Note</b>: This static function is available only if the <i>value traits</i> |
1849 | //! is stateless. |
1850 | static const_iterator s_iterator_to(const_reference value) BOOST_NOEXCEPT; |
1851 | |
1852 | //! <b>Requires</b>: value must be an lvalue and shall be in a set of |
1853 | //! appropriate type. Otherwise the behavior is undefined. |
1854 | //! |
1855 | //! <b>Effects</b>: Returns: a valid iterator i belonging to the set |
1856 | //! that points to the value |
1857 | //! |
1858 | //! <b>Complexity</b>: Constant. |
1859 | //! |
1860 | //! <b>Throws</b>: Nothing. |
1861 | iterator iterator_to(reference value) BOOST_NOEXCEPT; |
1862 | |
1863 | //! <b>Requires</b>: value must be an lvalue and shall be in a set of |
1864 | //! appropriate type. Otherwise the behavior is undefined. |
1865 | //! |
1866 | //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the |
1867 | //! set that points to the value |
1868 | //! |
1869 | //! <b>Complexity</b>: Constant. |
1870 | //! |
1871 | //! <b>Throws</b>: Nothing. |
1872 | const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT; |
1873 | |
1874 | //! <b>Requires</b>: value shall not be in a container. |
1875 | //! |
1876 | //! <b>Effects</b>: init_node puts the hook of a value in a well-known default |
1877 | //! state. |
1878 | //! |
1879 | //! <b>Throws</b>: Nothing. |
1880 | //! |
1881 | //! <b>Complexity</b>: Constant time. |
1882 | //! |
1883 | //! <b>Note</b>: This function puts the hook in the well-known default state |
1884 | //! used by auto_unlink and safe hooks. |
1885 | static void init_node(reference value) BOOST_NOEXCEPT; |
1886 | |
1887 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1888 | |
1889 | //! <b>Effects</b>: Unlinks the leftmost node from the container. |
1890 | //! |
1891 | //! <b>Complexity</b>: Average complexity is constant time. |
1892 | //! |
1893 | //! <b>Throws</b>: Nothing. |
1894 | //! |
1895 | //! <b>Notes</b>: This function breaks the container and the container can |
1896 | //! only be used for more unlink_leftmost_without_rebalance calls. |
1897 | //! This function is normally used to achieve a step by step |
1898 | //! controlled destruction of the container. |
1899 | pointer unlink_leftmost_without_rebalance() BOOST_NOEXCEPT |
1900 | { |
1901 | node_ptr to_be_disposed(node_algorithms::unlink_leftmost_without_rebalance |
1902 | (this->header_ptr())); |
1903 | if(!to_be_disposed) |
1904 | return 0; |
1905 | this->sz_traits().decrement(); |
1906 | BOOST_IF_CONSTEXPR(safemode_or_autounlink)//If this is commented does not work with normal_link |
1907 | node_algorithms::init(to_be_disposed); |
1908 | return this->get_value_traits().to_value_ptr(to_be_disposed); |
1909 | } |
1910 | |
1911 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1912 | |
1913 | //! <b>Requires</b>: replace_this must be a valid iterator of *this |
1914 | //! and with_this must not be inserted in any container. |
1915 | //! |
1916 | //! <b>Effects</b>: Replaces replace_this in its position in the |
1917 | //! container with with_this. The container does not need to be rebalanced. |
1918 | //! |
1919 | //! <b>Complexity</b>: Constant. |
1920 | //! |
1921 | //! <b>Throws</b>: Nothing. |
1922 | //! |
1923 | //! <b>Note</b>: This function will break container ordering invariants if |
1924 | //! with_this is not equivalent to *replace_this according to the |
1925 | //! ordering rules. This function is faster than erasing and inserting |
1926 | //! the node, since no rebalancing or comparison is needed. |
1927 | void replace_node(iterator replace_this, reference with_this) BOOST_NOEXCEPT; |
1928 | |
1929 | //! <b>Effects</b>: Rebalances the tree. |
1930 | //! |
1931 | //! <b>Throws</b>: Nothing. |
1932 | //! |
1933 | //! <b>Complexity</b>: Linear. |
1934 | void rebalance() BOOST_NOEXCEPT; |
1935 | |
1936 | //! <b>Requires</b>: old_root is a node of a tree. |
1937 | //! |
1938 | //! <b>Effects</b>: Rebalances the subtree rooted at old_root. |
1939 | //! |
1940 | //! <b>Returns</b>: The new root of the subtree. |
1941 | //! |
1942 | //! <b>Throws</b>: Nothing. |
1943 | //! |
1944 | //! <b>Complexity</b>: Linear to the elements in the subtree. |
1945 | iterator rebalance_subtree(iterator r) BOOST_NOEXCEPT; |
1946 | |
1947 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1948 | |
1949 | //! <b>Effects</b>: removes "value" from the container. |
1950 | //! |
1951 | //! <b>Throws</b>: Nothing. |
1952 | //! |
1953 | //! <b>Complexity</b>: Logarithmic time. |
1954 | //! |
1955 | //! <b>Note</b>: This static function is only usable with non-constant |
1956 | //! time size containers that have stateless comparison functors. |
1957 | //! |
1958 | //! If the user calls |
1959 | //! this function with a constant time size container or stateful comparison |
1960 | //! functor a compilation error will be issued. |
1961 | static void remove_node(reference value) BOOST_NOEXCEPT |
1962 | { |
1963 | BOOST_INTRUSIVE_STATIC_ASSERT((!constant_time_size)); |
1964 | node_ptr to_remove(value_traits::to_node_ptr(value)); |
1965 | node_algorithms::unlink(to_remove); |
1966 | BOOST_IF_CONSTEXPR(safemode_or_autounlink) |
1967 | node_algorithms::init(to_remove); |
1968 | } |
1969 | |
1970 | //! <b>Requires</b>: "source" container's Options can only can differ in the comparison |
1971 | //! function from *this. |
1972 | //! |
1973 | //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using |
1974 | //! the comparison object of *this. If there is an element in a with key equivalent to the |
1975 | //! key of an element from source, then that element is not extracted from source. |
1976 | //! |
1977 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer |
1978 | //! to those same elements but as members of *this. Iterators referring to the transferred |
1979 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, |
1980 | //! not into source. |
1981 | //! |
1982 | //! <b>Throws</b>: Nothing unless the comparison object throws. |
1983 | //! |
1984 | //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) |
1985 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
1986 | template<class T, class ...Options2> void merge_unique(bstree<T, Options2...> &); |
1987 | #else |
1988 | template<class Compare2> |
1989 | void merge_unique(bstree_impl |
1990 | <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) |
1991 | #endif |
1992 | { |
1993 | node_ptr it (node_algorithms::begin_node(source.header_ptr())) |
1994 | , itend(node_algorithms::end_node (source.header_ptr())); |
1995 | |
1996 | while(it != itend){ |
1997 | node_ptr const p(it); |
1998 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); |
1999 | it = node_algorithms::next_node(it); |
2000 | if( node_algorithms::transfer_unique(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p) ){ |
2001 | source.sz_traits().decrement(); |
2002 | this->sz_traits().increment(); |
2003 | } |
2004 | } |
2005 | } |
2006 | |
2007 | //! <b>Requires</b>: "source" container's Options can only can differ in the comparison |
2008 | //! function from *this. |
2009 | //! |
2010 | //! <b>Effects</b>: Extracts each element in source and insert it into a using |
2011 | //! the comparison object of *this. |
2012 | //! |
2013 | //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer |
2014 | //! to those same elements but as members of *this. Iterators referring to the transferred |
2015 | //! elements will continue to refer to their elements, but they now behave as iterators into *this, |
2016 | //! not into source. |
2017 | //! |
2018 | //! <b>Throws</b>: Nothing unless the comparison object throws. |
2019 | //! |
2020 | //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size()) |
2021 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) |
2022 | template<class T, class ...Options2> void merge_equal(bstree<T, Options2...> &); |
2023 | #else |
2024 | template<class Compare2> |
2025 | void merge_equal(bstree_impl |
2026 | <ValueTraits, VoidOrKeyOfValue, Compare2, SizeType, ConstantTimeSize, AlgoType, HeaderHolder> &source) |
2027 | #endif |
2028 | { |
2029 | node_ptr it (node_algorithms::begin_node(source.header_ptr())) |
2030 | , itend(node_algorithms::end_node (source.header_ptr())); |
2031 | |
2032 | while(it != itend){ |
2033 | node_ptr const p(it); |
2034 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || !node_algorithms::unique(p)); |
2035 | it = node_algorithms::next_node(it); |
2036 | node_algorithms::transfer_equal(this->header_ptr(), this->key_node_comp(this->key_comp()), source.header_ptr(), p); |
2037 | source.sz_traits().decrement(); |
2038 | this->sz_traits().increment(); |
2039 | } |
2040 | } |
2041 | |
2042 | //! <b>Effects</b>: Asserts the integrity of the container with additional checks provided by the user. |
2043 | //! |
2044 | //! <b>Complexity</b>: Linear time. |
2045 | //! |
2046 | //! <b>Note</b>: The method might not have effect when asserts are turned off (e.g., with NDEBUG). |
2047 | //! Experimental function, interface might change in future versions. |
2048 | template <class ExtraChecker> |
2049 | void check(ExtraChecker ) const |
2050 | { |
2051 | typedef detail::key_nodeptr_comp<key_compare, value_traits, key_of_value> nodeptr_comp_t; |
2052 | nodeptr_comp_t nodeptr_comp(this->key_comp(), &this->get_value_traits()); |
2053 | typedef typename get_node_checker<AlgoType, ValueTraits, nodeptr_comp_t, ExtraChecker>::type node_checker_t; |
2054 | typename node_checker_t::return_type checker_return; |
2055 | node_algorithms::check(this->header_ptr(), node_checker_t(nodeptr_comp, extra_checker), checker_return); |
2056 | BOOST_INTRUSIVE_INVARIANT_ASSERT(!constant_time_size || this->sz_traits().get_size() == checker_return.node_count); |
2057 | } |
2058 | |
2059 | //! <b>Effects</b>: Asserts the integrity of the container. |
2060 | //! |
2061 | //! <b>Complexity</b>: Linear time. |
2062 | //! |
2063 | //! <b>Note</b>: The method has no effect when asserts are turned off (e.g., with NDEBUG). |
2064 | //! Experimental function, interface might change in future versions. |
2065 | void check() const |
2066 | { |
2067 | check(detail::empty_node_checker<ValueTraits>()); |
2068 | } |
2069 | |
2070 | friend bool operator==(const bstree_impl &x, const bstree_impl &y) |
2071 | { |
2072 | if(constant_time_size && x.size() != y.size()){ |
2073 | return false; |
2074 | } |
2075 | return boost::intrusive::algo_equal(x.cbegin(), x.cend(), y.cbegin(), y.cend()); |
2076 | } |
2077 | |
2078 | friend bool operator!=(const bstree_impl &x, const bstree_impl &y) |
2079 | { return !(x == y); } |
2080 | |
2081 | friend bool operator<(const bstree_impl &x, const bstree_impl &y) |
2082 | { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } |
2083 | |
2084 | friend bool operator>(const bstree_impl &x, const bstree_impl &y) |
2085 | { return y < x; } |
2086 | |
2087 | friend bool operator<=(const bstree_impl &x, const bstree_impl &y) |
2088 | { return !(x > y); } |
2089 | |
2090 | friend bool operator>=(const bstree_impl &x, const bstree_impl &y) |
2091 | { return !(x < y); } |
2092 | |
2093 | friend void swap(bstree_impl &x, bstree_impl &y) |
2094 | { x.swap(y); } |
2095 | |
2096 | /// @cond |
2097 | private: |
2098 | template<class Disposer> |
2099 | iterator private_erase(const_iterator b, const_iterator e, size_type &n, Disposer disposer) |
2100 | { |
2101 | for(n = 0; b != e; ++n) |
2102 | this->erase_and_dispose(b++, disposer); |
2103 | return b.unconst(); |
2104 | } |
2105 | |
2106 | iterator private_erase(const_iterator b, const_iterator e, size_type &n) |
2107 | { |
2108 | for(n = 0; b != e; ++n) |
2109 | this->erase(b++); |
2110 | return b.unconst(); |
2111 | } |
2112 | /// @endcond |
2113 | }; |
2114 | |
2115 | //! Helper metafunction to define a \c bstree that yields to the same type when the |
2116 | //! same options (either explicitly or implicitly) are used. |
2117 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
2118 | template<class T, class ...Options> |
2119 | #else |
2120 | template<class T, class O1 = void, class O2 = void |
2121 | , class O3 = void, class O4 = void |
2122 | , class O5 = void, class O6 = void> |
2123 | #endif |
2124 | struct make_bstree |
2125 | { |
2126 | /// @cond |
2127 | typedef typename pack_options |
2128 | < bstree_defaults, |
2129 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
2130 | O1, O2, O3, O4, O5, O6 |
2131 | #else |
2132 | Options... |
2133 | #endif |
2134 | >::type packed_options; |
2135 | |
2136 | typedef typename detail::get_value_traits |
2137 | <T, typename packed_options::proto_value_traits>::type value_traits; |
2138 | |
2139 | typedef bstree_impl |
2140 | < value_traits |
2141 | , typename packed_options::key_of_value |
2142 | , typename packed_options::compare |
2143 | , typename packed_options::size_type |
2144 | , packed_options::constant_time_size |
2145 | , BsTreeAlgorithms |
2146 | , typename packed_options::header_holder_type |
2147 | > implementation_defined; |
2148 | /// @endcond |
2149 | typedef implementation_defined type; |
2150 | }; |
2151 | |
2152 | |
2153 | #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED |
2154 | |
2155 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
2156 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6> |
2157 | #else |
2158 | template<class T, class ...Options> |
2159 | #endif |
2160 | class bstree |
2161 | : public make_bstree<T, |
2162 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
2163 | O1, O2, O3, O4, O5, O6 |
2164 | #else |
2165 | Options... |
2166 | #endif |
2167 | >::type |
2168 | { |
2169 | typedef typename make_bstree |
2170 | <T, |
2171 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) |
2172 | O1, O2, O3, O4, O5, O6 |
2173 | #else |
2174 | Options... |
2175 | #endif |
2176 | >::type Base; |
2177 | BOOST_MOVABLE_BUT_NOT_COPYABLE(bstree) |
2178 | |
2179 | public: |
2180 | typedef typename Base::key_compare key_compare; |
2181 | typedef typename Base::value_traits value_traits; |
2182 | typedef typename Base::iterator iterator; |
2183 | typedef typename Base::const_iterator const_iterator; |
2184 | |
2185 | //Assert if passed value traits are compatible with the type |
2186 | BOOST_INTRUSIVE_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); |
2187 | |
2188 | inline bstree() |
2189 | : Base() |
2190 | {} |
2191 | |
2192 | inline explicit bstree( const key_compare &cmp, const value_traits &v_traits = value_traits()) |
2193 | : Base(cmp, v_traits) |
2194 | {} |
2195 | |
2196 | template<class Iterator> |
2197 | inline bstree( bool unique, Iterator b, Iterator e |
2198 | , const key_compare &cmp = key_compare() |
2199 | , const value_traits &v_traits = value_traits()) |
2200 | : Base(unique, b, e, cmp, v_traits) |
2201 | {} |
2202 | |
2203 | inline bstree(BOOST_RV_REF(bstree) x) |
2204 | : Base(BOOST_MOVE_BASE(Base, x)) |
2205 | {} |
2206 | |
2207 | inline bstree& operator=(BOOST_RV_REF(bstree) x) |
2208 | { return static_cast<bstree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } |
2209 | |
2210 | template <class Cloner, class Disposer> |
2211 | inline void clone_from(const bstree &src, Cloner cloner, Disposer disposer) |
2212 | { Base::clone_from(src, cloner, disposer); } |
2213 | |
2214 | template <class Cloner, class Disposer> |
2215 | inline void clone_from(BOOST_RV_REF(bstree) src, Cloner cloner, Disposer disposer) |
2216 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } |
2217 | |
2218 | inline static bstree &container_from_end_iterator(iterator end_iterator) BOOST_NOEXCEPT |
2219 | { return static_cast<bstree &>(Base::container_from_end_iterator(end_iterator)); } |
2220 | |
2221 | inline static const bstree &container_from_end_iterator(const_iterator end_iterator) BOOST_NOEXCEPT |
2222 | { return static_cast<const bstree &>(Base::container_from_end_iterator(end_iterator)); } |
2223 | |
2224 | inline static bstree &container_from_iterator(iterator it) BOOST_NOEXCEPT |
2225 | { return static_cast<bstree &>(Base::container_from_iterator(it)); } |
2226 | |
2227 | inline static const bstree &container_from_iterator(const_iterator it) BOOST_NOEXCEPT |
2228 | { return static_cast<const bstree &>(Base::container_from_iterator(it)); } |
2229 | }; |
2230 | |
2231 | #endif |
2232 | } //namespace intrusive |
2233 | } //namespace boost |
2234 | |
2235 | #include <boost/intrusive/detail/config_end.hpp> |
2236 | |
2237 | #endif //BOOST_INTRUSIVE_BSTREE_HPP |
2238 | |