ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1/////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Olaf Krzikalla 2004-2006.
4// (C) Copyright Ion Gaztanaga 2006-2012
5//
6// Distributed under the Boost Software License, Version 1.0.
7// (See accompanying file LICENSE_1_0.txt or copy at
8// http://www.boost.org/LICENSE_1_0.txt)
9//
10// See http://www.boost.org/libs/intrusive for documentation.
11//
12/////////////////////////////////////////////////////////////////////////////
13#ifndef BOOST_INTRUSIVE_SET_HPP
14#define BOOST_INTRUSIVE_SET_HPP
15
16#include <boost/intrusive/detail/config_begin.hpp>
17#include <boost/intrusive/intrusive_fwd.hpp>
18#include <boost/intrusive/detail/mpl.hpp>
19#include <boost/intrusive/rbtree.hpp>
20#include <iterator>
21#include <boost/move/move.hpp>
22
23namespace boost {
24namespace intrusive {
25
26//! The class template set is an intrusive container, that mimics most of
27//! the interface of std::set as described in the C++ standard.
28//!
29//! The template parameter \c T is the type to be managed by the container.
30//! The user can specify additional options and if no options are provided
31//! default options are used.
32//!
33//! The container supports the following options:
34//! \c base_hook<>/member_hook<>/value_traits<>,
35//! \c constant_time_size<>, \c size_type<> and
36//! \c compare<>.
37#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
38template<class T, class ...Options>
39#else
40template<class Config>
41#endif
42class set_impl
43{
44 /// @cond
45 typedef rbtree_impl<Config> tree_type;
46 BOOST_MOVABLE_BUT_NOT_COPYABLE(set_impl)
47
48 typedef tree_type implementation_defined;
49 /// @endcond
50
51 public:
52 typedef typename implementation_defined::value_type value_type;
53 typedef typename implementation_defined::value_traits value_traits;
54 typedef typename implementation_defined::pointer pointer;
55 typedef typename implementation_defined::const_pointer const_pointer;
56 typedef typename implementation_defined::reference reference;
57 typedef typename implementation_defined::const_reference const_reference;
58 typedef typename implementation_defined::difference_type difference_type;
59 typedef typename implementation_defined::size_type size_type;
60 typedef typename implementation_defined::value_compare value_compare;
61 typedef typename implementation_defined::key_compare key_compare;
62 typedef typename implementation_defined::iterator iterator;
63 typedef typename implementation_defined::const_iterator const_iterator;
64 typedef typename implementation_defined::reverse_iterator reverse_iterator;
65 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
66 typedef typename implementation_defined::insert_commit_data insert_commit_data;
67 typedef typename implementation_defined::node_traits node_traits;
68 typedef typename implementation_defined::node node;
69 typedef typename implementation_defined::node_ptr node_ptr;
70 typedef typename implementation_defined::const_node_ptr const_node_ptr;
71 typedef typename implementation_defined::node_algorithms node_algorithms;
72
73 static const bool constant_time_size = Config::constant_time_size;
74 //static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value;
75
76 /// @cond
77 private:
78 tree_type tree_;
79
80 protected:
81 node &prot_header_node(){ return tree_.prot_header_node(); }
82 node const &prot_header_node() const{ return tree_.prot_header_node(); }
83 void prot_set_size(size_type s){ tree_.prot_set_size(s); }
84 value_compare &prot_comp(){ return tree_.prot_comp(); }
85
86 /// @endcond
87
88 public:
89 //! <b>Effects</b>: Constructs an empty set.
90 //!
91 //! <b>Complexity</b>: Constant.
92 //!
93 //! <b>Throws</b>: If value_traits::node_traits::node
94 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
95 //! or the copy constructor of the value_compare object throws.
96 explicit set_impl( const value_compare &cmp = value_compare()
97 , const value_traits &v_traits = value_traits())
98 : tree_(cmp, v_traits)
99 {}
100
101 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
102 //! cmp must be a comparison function that induces a strict weak ordering.
103 //!
104 //! <b>Effects</b>: Constructs an empty set and inserts elements from
105 //! [b, e).
106 //!
107 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
108 //! comp and otherwise N * log N, where N is std::distance(last, first).
109 //!
110 //! <b>Throws</b>: If value_traits::node_traits::node
111 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
112 //! or the copy constructor/operator() of the value_compare object throws.
113 template<class Iterator>
114 set_impl( Iterator b, Iterator e
115 , const value_compare &cmp = value_compare()
116 , const value_traits &v_traits = value_traits())
117 : tree_(true, b, e, cmp, v_traits)
118 {}
119
120 //! <b>Effects</b>: to-do
121 //!
122 set_impl(BOOST_RV_REF(set_impl) x)
123 : tree_(::boost::move(x.tree_))
124 {}
125
126 //! <b>Effects</b>: to-do
127 //!
128 set_impl& operator=(BOOST_RV_REF(set_impl) x)
129 { tree_ = ::boost::move(x.tree_); return *this; }
130
131 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
132 //! are not deleted (i.e. no destructors are called).
133 //!
134 //! <b>Complexity</b>: Linear to the number of elements on the container.
135 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
136 //!
137 //! <b>Throws</b>: Nothing.
138 ~set_impl()
139 {}
140
141 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the set.
142 //!
143 //! <b>Complexity</b>: Constant.
144 //!
145 //! <b>Throws</b>: Nothing.
146 iterator begin()
147 { return tree_.begin(); }
148
149 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the set.
150 //!
151 //! <b>Complexity</b>: Constant.
152 //!
153 //! <b>Throws</b>: Nothing.
154 const_iterator begin() const
155 { return tree_.begin(); }
156
157 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the set.
158 //!
159 //! <b>Complexity</b>: Constant.
160 //!
161 //! <b>Throws</b>: Nothing.
162 const_iterator cbegin() const
163 { return tree_.cbegin(); }
164
165 //! <b>Effects</b>: Returns an iterator pointing to the end of the set.
166 //!
167 //! <b>Complexity</b>: Constant.
168 //!
169 //! <b>Throws</b>: Nothing.
170 iterator end()
171 { return tree_.end(); }
172
173 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the set.
174 //!
175 //! <b>Complexity</b>: Constant.
176 //!
177 //! <b>Throws</b>: Nothing.
178 const_iterator end() const
179 { return tree_.end(); }
180
181 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the set.
182 //!
183 //! <b>Complexity</b>: Constant.
184 //!
185 //! <b>Throws</b>: Nothing.
186 const_iterator cend() const
187 { return tree_.cend(); }
188
189 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
190 //! reversed set.
191 //!
192 //! <b>Complexity</b>: Constant.
193 //!
194 //! <b>Throws</b>: Nothing.
195 reverse_iterator rbegin()
196 { return tree_.rbegin(); }
197
198 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
199 //! of the reversed set.
200 //!
201 //! <b>Complexity</b>: Constant.
202 //!
203 //! <b>Throws</b>: Nothing.
204 const_reverse_iterator rbegin() const
205 { return tree_.rbegin(); }
206
207 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
208 //! of the reversed set.
209 //!
210 //! <b>Complexity</b>: Constant.
211 //!
212 //! <b>Throws</b>: Nothing.
213 const_reverse_iterator crbegin() const
214 { return tree_.crbegin(); }
215
216 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
217 //! of the reversed set.
218 //!
219 //! <b>Complexity</b>: Constant.
220 //!
221 //! <b>Throws</b>: Nothing.
222 reverse_iterator rend()
223 { return tree_.rend(); }
224
225 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
226 //! of the reversed set.
227 //!
228 //! <b>Complexity</b>: Constant.
229 //!
230 //! <b>Throws</b>: Nothing.
231 const_reverse_iterator rend() const
232 { return tree_.rend(); }
233
234 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
235 //! of the reversed set.
236 //!
237 //! <b>Complexity</b>: Constant.
238 //!
239 //! <b>Throws</b>: Nothing.
240 const_reverse_iterator crend() const
241 { return tree_.crend(); }
242
243 //! <b>Precondition</b>: end_iterator must be a valid end iterator
244 //! of set.
245 //!
246 //! <b>Effects</b>: Returns a reference to the set associated to the end iterator
247 //!
248 //! <b>Throws</b>: Nothing.
249 //!
250 //! <b>Complexity</b>: Constant.
251 static set_impl &container_from_end_iterator(iterator end_iterator)
252 {
253 return *detail::parent_from_member<set_impl, tree_type>
254 ( &tree_type::container_from_end_iterator(end_iterator)
255 , &set_impl::tree_);
256 }
257
258 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
259 //! of set.
260 //!
261 //! <b>Effects</b>: Returns a const reference to the set associated to the end iterator
262 //!
263 //! <b>Throws</b>: Nothing.
264 //!
265 //! <b>Complexity</b>: Constant.
266 static const set_impl &container_from_end_iterator(const_iterator end_iterator)
267 {
268 return *detail::parent_from_member<set_impl, tree_type>
269 ( &tree_type::container_from_end_iterator(end_iterator)
270 , &set_impl::tree_);
271 }
272
273 //! <b>Precondition</b>: it must be a valid iterator of set.
274 //!
275 //! <b>Effects</b>: Returns a reference to the set associated to the iterator
276 //!
277 //! <b>Throws</b>: Nothing.
278 //!
279 //! <b>Complexity</b>: Logarithmic.
280 static set_impl &container_from_iterator(iterator it)
281 {
282 return *detail::parent_from_member<set_impl, tree_type>
283 ( &tree_type::container_from_iterator(it)
284 , &set_impl::tree_);
285 }
286
287 //! <b>Precondition</b>: it must be a valid const_iterator of set.
288 //!
289 //! <b>Effects</b>: Returns a const reference to the set associated to the iterator
290 //!
291 //! <b>Throws</b>: Nothing.
292 //!
293 //! <b>Complexity</b>: Logarithmic.
294 static const set_impl &container_from_iterator(const_iterator it)
295 {
296 return *detail::parent_from_member<set_impl, tree_type>
297 ( &tree_type::container_from_iterator(it)
298 , &set_impl::tree_);
299 }
300
301 //! <b>Effects</b>: Returns the key_compare object used by the set.
302 //!
303 //! <b>Complexity</b>: Constant.
304 //!
305 //! <b>Throws</b>: If key_compare copy-constructor throws.
306 key_compare key_comp() const
307 { return tree_.value_comp(); }
308
309 //! <b>Effects</b>: Returns the value_compare object used by the set.
310 //!
311 //! <b>Complexity</b>: Constant.
312 //!
313 //! <b>Throws</b>: If value_compare copy-constructor throws.
314 value_compare value_comp() const
315 { return tree_.value_comp(); }
316
317 //! <b>Effects</b>: Returns true if the container is empty.
318 //!
319 //! <b>Complexity</b>: Constant.
320 //!
321 //! <b>Throws</b>: Nothing.
322 bool empty() const
323 { return tree_.empty(); }
324
325 //! <b>Effects</b>: Returns the number of elements stored in the set.
326 //!
327 //! <b>Complexity</b>: Linear to elements contained in *this if,
328 //! constant-time size option is enabled. Constant-time otherwise.
329 //!
330 //! <b>Throws</b>: Nothing.
331 size_type size() const
332 { return tree_.size(); }
333
334 //! <b>Effects</b>: Swaps the contents of two sets.
335 //!
336 //! <b>Complexity</b>: Constant.
337 //!
338 //! <b>Throws</b>: If the swap() call for the comparison functor
339 //! found using ADL throws. Strong guarantee.
340 void swap(set_impl& other)
341 { tree_.swap(other.tree_); }
342
343 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
344 //! Cloner should yield to nodes equivalent to the original nodes.
345 //!
346 //! <b>Effects</b>: Erases all the elements from *this
347 //! calling Disposer::operator()(pointer), clones all the
348 //! elements from src calling Cloner::operator()(const_reference )
349 //! and inserts them on *this. Copies the predicate from the source container.
350 //!
351 //! If cloner throws, all cloned elements are unlinked and disposed
352 //! calling Disposer::operator()(pointer).
353 //!
354 //! <b>Complexity</b>: Linear to erased plus inserted elements.
355 //!
356 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
357 template <class Cloner, class Disposer>
358 void clone_from(const set_impl &src, Cloner cloner, Disposer disposer)
359 { tree_.clone_from(src.tree_, cloner, disposer); }
360
361 //! <b>Requires</b>: value must be an lvalue
362 //!
363 //! <b>Effects</b>: Tries to inserts value into the set.
364 //!
365 //! <b>Returns</b>: If the value
366 //! is not already present inserts it and returns a pair containing the
367 //! iterator to the new value and true. If there is an equivalent value
368 //! returns a pair containing an iterator to the already present value
369 //! and false.
370 //!
371 //! <b>Complexity</b>: Average complexity for insert element is at
372 //! most logarithmic.
373 //!
374 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
375 //!
376 //! <b>Note</b>: Does not affect the validity of iterators and references.
377 //! No copy-constructors are called.
378 std::pair<iterator, bool> insert(reference value)
379 { return tree_.insert_unique(value); }
380
381 //! <b>Requires</b>: value must be an lvalue
382 //!
383 //! <b>Effects</b>: Tries to to insert x into the set, using "hint"
384 //! as a hint to where it will be inserted.
385 //!
386 //! <b>Returns</b>: An iterator that points to the position where the
387 //! new element was inserted into the set.
388 //!
389 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
390 //! constant time if t is inserted immediately before hint.
391 //!
392 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
393 //!
394 //! <b>Note</b>: Does not affect the validity of iterators and references.
395 //! No copy-constructors are called.
396 iterator insert(const_iterator hint, reference value)
397 { return tree_.insert_unique(hint, value); }
398
399 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
400 //! the same strict weak ordering as value_compare. The difference is that
401 //! key_value_comp compares an arbitrary key with the contained values.
402 //!
403 //! <b>Effects</b>: Checks if a value can be inserted in the set, using
404 //! a user provided key instead of the value itself.
405 //!
406 //! <b>Returns</b>: If there is an equivalent value
407 //! returns a pair containing an iterator to the already present value
408 //! and false. If the value can be inserted returns true in the returned
409 //! pair boolean and fills "commit_data" that is meant to be used with
410 //! the "insert_commit" function.
411 //!
412 //! <b>Complexity</b>: Average complexity is at most logarithmic.
413 //!
414 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
415 //!
416 //! <b>Notes</b>: This function is used to improve performance when constructing
417 //! a value_type is expensive: if there is an equivalent value
418 //! the constructed object must be discarded. Many times, the part of the
419 //! node that is used to impose the order is much cheaper to construct
420 //! than the value_type and this function offers the possibility to use that
421 //! part to check if the insertion will be successful.
422 //!
423 //! If the check is successful, the user can construct the value_type and use
424 //! "insert_commit" to insert the object in constant-time. This gives a total
425 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
426 //!
427 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
428 //! objects are inserted or erased from the set.
429 template<class KeyType, class KeyValueCompare>
430 std::pair<iterator, bool> insert_check
431 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
432 { return tree_.insert_unique_check(key, key_value_comp, commit_data); }
433
434 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
435 //! the same strict weak ordering as value_compare. The difference is that
436 //! key_value_comp compares an arbitrary key with the contained values.
437 //!
438 //! <b>Effects</b>: Checks if a value can be inserted in the set, using
439 //! a user provided key instead of the value itself, using "hint"
440 //! as a hint to where it will be inserted.
441 //!
442 //! <b>Returns</b>: If there is an equivalent value
443 //! returns a pair containing an iterator to the already present value
444 //! and false. If the value can be inserted returns true in the returned
445 //! pair boolean and fills "commit_data" that is meant to be used with
446 //! the "insert_commit" function.
447 //!
448 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
449 //! constant time if t is inserted immediately before hint.
450 //!
451 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
452 //!
453 //! <b>Notes</b>: This function is used to improve performance when constructing
454 //! a value_type is expensive: if there is an equivalent value
455 //! the constructed object must be discarded. Many times, the part of the
456 //! constructing that is used to impose the order is much cheaper to construct
457 //! than the value_type and this function offers the possibility to use that key
458 //! to check if the insertion will be successful.
459 //!
460 //! If the check is successful, the user can construct the value_type and use
461 //! "insert_commit" to insert the object in constant-time. This can give a total
462 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
463 //!
464 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
465 //! objects are inserted or erased from the set.
466 template<class KeyType, class KeyValueCompare>
467 std::pair<iterator, bool> insert_check
468 (const_iterator hint, const KeyType &key
469 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
470 { return tree_.insert_unique_check(hint, key, key_value_comp, commit_data); }
471
472 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
473 //! must have been obtained from a previous call to "insert_check".
474 //! No objects should have been inserted or erased from the set between
475 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
476 //!
477 //! <b>Effects</b>: Inserts the value in the set using the information obtained
478 //! from the "commit_data" that a previous "insert_check" filled.
479 //!
480 //! <b>Returns</b>: An iterator to the newly inserted object.
481 //!
482 //! <b>Complexity</b>: Constant time.
483 //!
484 //! <b>Throws</b>: Nothing.
485 //!
486 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
487 //! previously executed to fill "commit_data". No value should be inserted or
488 //! erased between the "insert_check" and "insert_commit" calls.
489 iterator insert_commit(reference value, const insert_commit_data &commit_data)
490 { return tree_.insert_unique_commit(value, commit_data); }
491
492 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
493 //! of type value_type.
494 //!
495 //! <b>Effects</b>: Inserts a range into the set.
496 //!
497 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
498 //! size of the range. However, it is linear in N if the range is already sorted
499 //! by value_comp().
500 //!
501 //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
502 //!
503 //! <b>Note</b>: Does not affect the validity of iterators and references.
504 //! No copy-constructors are called.
505 template<class Iterator>
506 void insert(Iterator b, Iterator e)
507 { tree_.insert_unique(b, e); }
508
509 //! <b>Requires</b>: value must be an lvalue, "pos" must be
510 //! a valid iterator (or end) and must be the succesor of value
511 //! once inserted according to the predicate. "value" must not be equal to any
512 //! inserted key according to the predicate.
513 //!
514 //! <b>Effects</b>: Inserts x into the tree before "pos".
515 //!
516 //! <b>Complexity</b>: Constant time.
517 //!
518 //! <b>Throws</b>: Nothing.
519 //!
520 //! <b>Note</b>: This function does not check preconditions so if "pos" is not
521 //! the successor of "value" or "value" is not unique tree ordering and uniqueness
522 //! invariants will be broken respectively.
523 //! This is a low-level function to be used only for performance reasons
524 //! by advanced users.
525 iterator insert_before(const_iterator pos, reference value)
526 { return tree_.insert_before(pos, value); }
527
528 //! <b>Requires</b>: value must be an lvalue, and it must be greater than
529 //! any inserted key according to the predicate.
530 //!
531 //! <b>Effects</b>: Inserts x into the tree in the last position.
532 //!
533 //! <b>Complexity</b>: Constant time.
534 //!
535 //! <b>Throws</b>: Nothing.
536 //!
537 //! <b>Note</b>: This function does not check preconditions so if value is
538 //! less than or equal to the greatest inserted key tree ordering invariant will be broken.
539 //! This function is slightly more efficient than using "insert_before".
540 //! This is a low-level function to be used only for performance reasons
541 //! by advanced users.
542 void push_back(reference value)
543 { tree_.push_back(value); }
544
545 //! <b>Requires</b>: value must be an lvalue, and it must be less
546 //! than any inserted key according to the predicate.
547 //!
548 //! <b>Effects</b>: Inserts x into the tree in the first position.
549 //!
550 //! <b>Complexity</b>: Constant time.
551 //!
552 //! <b>Throws</b>: Nothing.
553 //!
554 //! <b>Note</b>: This function does not check preconditions so if value is
555 //! greater than or equal to the the mimum inserted key tree ordering or uniqueness
556 //! invariants will be broken.
557 //! This function is slightly more efficient than using "insert_before".
558 //! This is a low-level function to be used only for performance reasons
559 //! by advanced users.
560 void push_front(reference value)
561 { tree_.push_front(value); }
562
563 //! <b>Effects</b>: Erases the element pointed to by pos.
564 //!
565 //! <b>Complexity</b>: Average complexity is constant time.
566 //!
567 //! <b>Returns</b>: An iterator to the element after the erased element.
568 //!
569 //! <b>Throws</b>: Nothing.
570 //!
571 //! <b>Note</b>: Invalidates the iterators (but not the references)
572 //! to the erased elements. No destructors are called.
573 iterator erase(const_iterator i)
574 { return tree_.erase(i); }
575
576 //! <b>Effects</b>: Erases the range pointed to by b end e.
577 //!
578 //! <b>Complexity</b>: Average complexity for erase range is at most
579 //! O(log(size() + N)), where N is the number of elements in the range.
580 //!
581 //! <b>Returns</b>: An iterator to the element after the erased elements.
582 //!
583 //! <b>Throws</b>: Nothing.
584 //!
585 //! <b>Note</b>: Invalidates the iterators (but not the references)
586 //! to the erased elements. No destructors are called.
587 iterator erase(const_iterator b, const_iterator e)
588 { return tree_.erase(b, e); }
589
590 //! <b>Effects</b>: Erases all the elements with the given value.
591 //!
592 //! <b>Returns</b>: The number of erased elements.
593 //!
594 //! <b>Complexity</b>: O(log(size()) + this->count(value)).
595 //!
596 //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
597 //!
598 //! <b>Note</b>: Invalidates the iterators (but not the references)
599 //! to the erased elements. No destructors are called.
600 size_type erase(const_reference value)
601 { return tree_.erase(value); }
602
603 //! <b>Effects</b>: Erases all the elements that compare equal with
604 //! the given key and the given comparison functor.
605 //!
606 //! <b>Returns</b>: The number of erased elements.
607 //!
608 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
609 //!
610 //! <b>Throws</b>: If the comp ordering function throws. Basic guarantee.
611 //!
612 //! <b>Note</b>: Invalidates the iterators (but not the references)
613 //! to the erased elements. No destructors are called.
614 template<class KeyType, class KeyValueCompare>
615 size_type erase(const KeyType& key, KeyValueCompare comp
616 /// @cond
617 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
618 /// @endcond
619 )
620 { return tree_.erase(key, comp); }
621
622 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
623 //!
624 //! <b>Effects</b>: Erases the element pointed to by pos.
625 //! Disposer::operator()(pointer) is called for the removed element.
626 //!
627 //! <b>Complexity</b>: Average complexity for erase element is constant time.
628 //!
629 //! <b>Returns</b>: An iterator to the element after the erased element.
630 //!
631 //! <b>Throws</b>: Nothing.
632 //!
633 //! <b>Note</b>: Invalidates the iterators
634 //! to the erased elements.
635 template<class Disposer>
636 iterator erase_and_dispose(const_iterator i, Disposer disposer)
637 { return tree_.erase_and_dispose(i, disposer); }
638
639 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
640 template<class Disposer>
641 iterator erase_and_dispose(iterator i, Disposer disposer)
642 { return this->erase_and_dispose(const_iterator(i), disposer); }
643 #endif
644
645 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
646 //!
647 //! <b>Effects</b>: Erases the range pointed to by b end e.
648 //! Disposer::operator()(pointer) is called for the removed elements.
649 //!
650 //! <b>Complexity</b>: Average complexity for erase range is at most
651 //! O(log(size() + N)), where N is the number of elements in the range.
652 //!
653 //! <b>Returns</b>: An iterator to the element after the erased elements.
654 //!
655 //! <b>Throws</b>: Nothing.
656 //!
657 //! <b>Note</b>: Invalidates the iterators
658 //! to the erased elements.
659 template<class Disposer>
660 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
661 { return tree_.erase_and_dispose(b, e, disposer); }
662
663 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
664 //!
665 //! <b>Effects</b>: Erases all the elements with the given value.
666 //! Disposer::operator()(pointer) is called for the removed elements.
667 //!
668 //! <b>Throws</b>: If the internal value_compare ordering function throws.
669 //!
670 //! <b>Complexity</b>: O(log(size() + this->count(value)). Basic guarantee.
671 //!
672 //! <b>Throws</b>: Nothing.
673 //!
674 //! <b>Note</b>: Invalidates the iterators (but not the references)
675 //! to the erased elements. No destructors are called.
676 template<class Disposer>
677 size_type erase_and_dispose(const_reference value, Disposer disposer)
678 { return tree_.erase_and_dispose(value, disposer); }
679
680 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
681 //!
682 //! <b>Effects</b>: Erases all the elements with the given key.
683 //! according to the comparison functor "comp".
684 //! Disposer::operator()(pointer) is called for the removed elements.
685 //!
686 //! <b>Returns</b>: The number of erased elements.
687 //!
688 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
689 //!
690 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
691 //!
692 //! <b>Note</b>: Invalidates the iterators
693 //! to the erased elements.
694 template<class KeyType, class KeyValueCompare, class Disposer>
695 size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
696 /// @cond
697 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
698 /// @endcond
699 )
700 { return tree_.erase_and_dispose(key, comp, disposer); }
701
702 //! <b>Effects</b>: Erases all the elements of the container.
703 //!
704 //! <b>Complexity</b>: Linear to the number of elements on the container.
705 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
706 //!
707 //! <b>Throws</b>: Nothing.
708 //!
709 //! <b>Note</b>: Invalidates the iterators (but not the references)
710 //! to the erased elements. No destructors are called.
711 void clear()
712 { return tree_.clear(); }
713
714 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
715 //!
716 //! <b>Effects</b>: Erases all the elements of the container.
717 //!
718 //! <b>Complexity</b>: Linear to the number of elements on the container.
719 //! Disposer::operator()(pointer) is called for the removed elements.
720 //!
721 //! <b>Throws</b>: Nothing.
722 //!
723 //! <b>Note</b>: Invalidates the iterators (but not the references)
724 //! to the erased elements. No destructors are called.
725 template<class Disposer>
726 void clear_and_dispose(Disposer disposer)
727 { return tree_.clear_and_dispose(disposer); }
728
729 //! <b>Effects</b>: Returns the number of contained elements with the given key
730 //!
731 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
732 //! to number of objects with the given key.
733 //!
734 //! <b>Throws</b>: If the internal value_compare ordering function throws.
735 size_type count(const_reference value) const
736 { return tree_.find(value) != end(); }
737
738 //! <b>Effects</b>: Returns the number of contained elements with the same key
739 //! compared with the given comparison functor.
740 //!
741 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
742 //! to number of objects with the given key.
743 //!
744 //! <b>Throws</b>: If comp ordering function throws.
745 template<class KeyType, class KeyValueCompare>
746 size_type count(const KeyType& key, KeyValueCompare comp) const
747 { return tree_.find(key, comp) != end(); }
748
749 //! <b>Effects</b>: Returns an iterator to the first element whose
750 //! key is not less than k or end() if that element does not exist.
751 //!
752 //! <b>Complexity</b>: Logarithmic.
753 //!
754 //! <b>Throws</b>: If the internal value_compare ordering function throws.
755 iterator lower_bound(const_reference value)
756 { return tree_.lower_bound(value); }
757
758 //! <b>Requires</b>: comp must imply the same element order as
759 //! value_compare. Usually key is the part of the value_type
760 //! that is used in the ordering functor.
761 //!
762 //! <b>Effects</b>: Returns an iterator to the first element whose
763 //! key according to the comparison functor is not less than k or
764 //! end() if that element does not exist.
765 //!
766 //! <b>Complexity</b>: Logarithmic.
767 //!
768 //! <b>Throws</b>: If comp ordering function throws.
769 //!
770 //! <b>Note</b>: This function is used when constructing a value_type
771 //! is expensive and the value_type can be compared with a cheaper
772 //! key type. Usually this key is part of the value_type.
773 template<class KeyType, class KeyValueCompare>
774 iterator lower_bound(const KeyType& key, KeyValueCompare comp)
775 { return tree_.lower_bound(key, comp); }
776
777 //! <b>Effects</b>: Returns a const iterator to the first element whose
778 //! key is not less than k or end() if that element does not exist.
779 //!
780 //! <b>Complexity</b>: Logarithmic.
781 //!
782 //! <b>Throws</b>: If the internal value_compare ordering function throws.
783 const_iterator lower_bound(const_reference value) const
784 { return tree_.lower_bound(value); }
785
786 //! <b>Requires</b>: comp must imply the same element order as
787 //! value_compare. Usually key is the part of the value_type
788 //! that is used in the ordering functor.
789 //!
790 //! <b>Effects</b>: Returns a const_iterator to the first element whose
791 //! key according to the comparison functor is not less than k or
792 //! end() if that element does not exist.
793 //!
794 //! <b>Complexity</b>: Logarithmic.
795 //!
796 //! <b>Throws</b>: If comp ordering function throws.
797 //!
798 //! <b>Note</b>: This function is used when constructing a value_type
799 //! is expensive and the value_type can be compared with a cheaper
800 //! key type. Usually this key is part of the value_type.
801 template<class KeyType, class KeyValueCompare>
802 const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
803 { return tree_.lower_bound(key, comp); }
804
805 //! <b>Effects</b>: Returns an iterator to the first element whose
806 //! key is greater than k or end() if that element does not exist.
807 //!
808 //! <b>Complexity</b>: Logarithmic.
809 //!
810 //! <b>Throws</b>: If the internal value_compare ordering function throws.
811 iterator upper_bound(const_reference value)
812 { return tree_.upper_bound(value); }
813
814 //! <b>Requires</b>: comp must imply the same element order as
815 //! value_compare. Usually key is the part of the value_type
816 //! that is used in the ordering functor.
817 //!
818 //! <b>Effects</b>: Returns an iterator to the first element whose
819 //! key according to the comparison functor is greater than key or
820 //! end() if that element does not exist.
821 //!
822 //! <b>Complexity</b>: Logarithmic.
823 //!
824 //! <b>Throws</b>: If comp ordering function throws.
825 //!
826 //! <b>Note</b>: This function is used when constructing a value_type
827 //! is expensive and the value_type can be compared with a cheaper
828 //! key type. Usually this key is part of the value_type.
829 template<class KeyType, class KeyValueCompare>
830 iterator upper_bound(const KeyType& key, KeyValueCompare comp)
831 { return tree_.upper_bound(key, comp); }
832
833 //! <b>Effects</b>: Returns an iterator to the first element whose
834 //! key is greater than k or end() if that element does not exist.
835 //!
836 //! <b>Complexity</b>: Logarithmic.
837 //!
838 //! <b>Throws</b>: If the internal value_compare ordering function throws.
839 const_iterator upper_bound(const_reference value) const
840 { return tree_.upper_bound(value); }
841
842 //! <b>Requires</b>: comp must imply the same element order as
843 //! value_compare. Usually key is the part of the value_type
844 //! that is used in the ordering functor.
845 //!
846 //! <b>Effects</b>: Returns a const_iterator to the first element whose
847 //! key according to the comparison functor is greater than key or
848 //! end() if that element does not exist.
849 //!
850 //! <b>Complexity</b>: Logarithmic.
851 //!
852 //! <b>Throws</b>: If comp ordering function throws.
853 //!
854 //! <b>Note</b>: This function is used when constructing a value_type
855 //! is expensive and the value_type can be compared with a cheaper
856 //! key type. Usually this key is part of the value_type.
857 template<class KeyType, class KeyValueCompare>
858 const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
859 { return tree_.upper_bound(key, comp); }
860
861 //! <b>Effects</b>: Finds an iterator to the first element whose value is
862 //! "value" or end() if that element does not exist.
863 //!
864 //! <b>Complexity</b>: Logarithmic.
865 //!
866 //! <b>Throws</b>: If the internal value_compare ordering function throws.
867 iterator find(const_reference value)
868 { return tree_.find(value); }
869
870 //! <b>Requires</b>: comp must imply the same element order as
871 //! value_compare. Usually key is the part of the value_type
872 //! that is used in the ordering functor.
873 //!
874 //! <b>Effects</b>: Finds an iterator to the first element whose key is
875 //! "key" according to the comparison functor or end() if that element
876 //! does not exist.
877 //!
878 //! <b>Complexity</b>: Logarithmic.
879 //!
880 //! <b>Throws</b>: If comp ordering function throws.
881 //!
882 //! <b>Note</b>: This function is used when constructing a value_type
883 //! is expensive and the value_type can be compared with a cheaper
884 //! key type. Usually this key is part of the value_type.
885 template<class KeyType, class KeyValueCompare>
886 iterator find(const KeyType& key, KeyValueCompare comp)
887 { return tree_.find(key, comp); }
888
889 //! <b>Effects</b>: Finds a const_iterator to the first element whose value is
890 //! "value" or end() if that element does not exist.
891 //!
892 //! <b>Complexity</b>: Logarithmic.
893 //!
894 //! <b>Throws</b>: If the internal value_compare ordering function throws.
895 const_iterator find(const_reference value) const
896 { return tree_.find(value); }
897
898 //! <b>Requires</b>: comp must imply the same element order as
899 //! value_compare. Usually key is the part of the value_type
900 //! that is used in the ordering functor.
901 //!
902 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
903 //! "key" according to the comparison functor or end() if that element
904 //! does not exist.
905 //!
906 //! <b>Complexity</b>: Logarithmic.
907 //!
908 //! <b>Throws</b>: If comp ordering function throws.
909 //!
910 //! <b>Note</b>: This function is used when constructing a value_type
911 //! is expensive and the value_type can be compared with a cheaper
912 //! key type. Usually this key is part of the value_type.
913 template<class KeyType, class KeyValueCompare>
914 const_iterator find(const KeyType& key, KeyValueCompare comp) const
915 { return tree_.find(key, comp); }
916
917 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
918 //! an empty range that indicates the position where those elements would be
919 //! if they there is no elements with key k.
920 //!
921 //! <b>Complexity</b>: Logarithmic.
922 //!
923 //! <b>Throws</b>: If the internal value_compare ordering function throws.
924 std::pair<iterator,iterator> equal_range(const_reference value)
925 { return tree_.equal_range(value); }
926
927 //! <b>Requires</b>: comp must imply the same element order as
928 //! value_compare. Usually key is the part of the value_type
929 //! that is used in the ordering functor.
930 //!
931 //! <b>Effects</b>: Finds a range containing all elements whose key is k
932 //! according to the comparison functor or an empty range
933 //! that indicates the position where those elements would be
934 //! if they there is no elements with key k.
935 //!
936 //! <b>Complexity</b>: Logarithmic.
937 //!
938 //! <b>Throws</b>: If comp ordering function throws.
939 //!
940 //! <b>Note</b>: This function is used when constructing a value_type
941 //! is expensive and the value_type can be compared with a cheaper
942 //! key type. Usually this key is part of the value_type.
943 template<class KeyType, class KeyValueCompare>
944 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
945 { return tree_.equal_range(key, comp); }
946
947 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
948 //! an empty range that indicates the position where those elements would be
949 //! if they there is no elements with key k.
950 //!
951 //! <b>Complexity</b>: Logarithmic.
952 //!
953 //! <b>Throws</b>: If the internal value_compare ordering function throws.
954 std::pair<const_iterator, const_iterator>
955 equal_range(const_reference value) const
956 { return tree_.equal_range(value); }
957
958 //! <b>Requires</b>: comp must imply the same element order as
959 //! value_compare. Usually key is the part of the value_type
960 //! that is used in the ordering functor.
961 //!
962 //! <b>Effects</b>: Finds a range containing all elements whose key is k
963 //! according to the comparison functor or an empty range
964 //! that indicates the position where those elements would be
965 //! if they there is no elements with key k.
966 //!
967 //! <b>Complexity</b>: Logarithmic.
968 //!
969 //! <b>Throws</b>: If comp ordering function throws.
970 //!
971 //! <b>Note</b>: This function is used when constructing a value_type
972 //! is expensive and the value_type can be compared with a cheaper
973 //! key type. Usually this key is part of the value_type.
974 template<class KeyType, class KeyValueCompare>
975 std::pair<const_iterator, const_iterator>
976 equal_range(const KeyType& key, KeyValueCompare comp) const
977 { return tree_.equal_range(key, comp); }
978
979 //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
980 //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
981 //!
982 //! <b>Effects</b>: Returns an a pair with the following criteria:
983 //!
984 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
985 //!
986 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
987 //!
988 //! <b>Complexity</b>: Logarithmic.
989 //!
990 //! <b>Throws</b>: If the predicate throws.
991 //!
992 //! <b>Note</b>: This function can be more efficient than calling upper_bound
993 //! and lower_bound for lower_value and upper_value.
994 std::pair<iterator,iterator> bounded_range
995 (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
996 { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
997
998 //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
999 //! ordering compatible with the strict weak ordering used to create the
1000 //! the tree.
1001 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
1002 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
1003 //!
1004 //! <b>Effects</b>: Returns an a pair with the following criteria:
1005 //!
1006 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
1007 //!
1008 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
1009 //!
1010 //! <b>Complexity</b>: Logarithmic.
1011 //!
1012 //! <b>Throws</b>: If "comp" throws.
1013 //!
1014 //! <b>Note</b>: This function can be more efficient than calling upper_bound
1015 //! and lower_bound for lower_key and upper_key.
1016 template<class KeyType, class KeyValueCompare>
1017 std::pair<iterator,iterator> bounded_range
1018 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
1019 { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
1020
1021 //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
1022 //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
1023 //!
1024 //! <b>Effects</b>: Returns an a pair with the following criteria:
1025 //!
1026 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
1027 //!
1028 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
1029 //!
1030 //! <b>Complexity</b>: Logarithmic.
1031 //!
1032 //! <b>Throws</b>: If the predicate throws.
1033 //!
1034 //! <b>Note</b>: This function can be more efficient than calling upper_bound
1035 //! and lower_bound for lower_value and upper_value.
1036 std::pair<const_iterator, const_iterator>
1037 bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
1038 { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
1039
1040 //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
1041 //! ordering compatible with the strict weak ordering used to create the
1042 //! the tree.
1043 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
1044 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
1045 //!
1046 //! <b>Effects</b>: Returns an a pair with the following criteria:
1047 //!
1048 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
1049 //!
1050 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
1051 //!
1052 //! <b>Complexity</b>: Logarithmic.
1053 //!
1054 //! <b>Throws</b>: If "comp" throws.
1055 //!
1056 //! <b>Note</b>: This function can be more efficient than calling upper_bound
1057 //! and lower_bound for lower_key and upper_key.
1058 template<class KeyType, class KeyValueCompare>
1059 std::pair<const_iterator, const_iterator>
1060 bounded_range
1061 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
1062 { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
1063
1064 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1065 //! appropriate type. Otherwise the behavior is undefined.
1066 //!
1067 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1068 //! that points to the value
1069 //!
1070 //! <b>Complexity</b>: Constant.
1071 //!
1072 //! <b>Throws</b>: Nothing.
1073 //!
1074 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1075 //! is stateless.
1076 static iterator s_iterator_to(reference value)
1077 { return tree_type::s_iterator_to(value); }
1078
1079 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1080 //! appropriate type. Otherwise the behavior is undefined.
1081 //!
1082 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1083 //! set that points to the value
1084 //!
1085 //! <b>Complexity</b>: Constant.
1086 //!
1087 //! <b>Throws</b>: Nothing.
1088 //!
1089 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
1090 //! is stateless.
1091 static const_iterator s_iterator_to(const_reference value)
1092 { return tree_type::s_iterator_to(value); }
1093
1094 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1095 //! appropriate type. Otherwise the behavior is undefined.
1096 //!
1097 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
1098 //! that points to the value
1099 //!
1100 //! <b>Complexity</b>: Constant.
1101 //!
1102 //! <b>Throws</b>: Nothing.
1103 iterator iterator_to(reference value)
1104 { return tree_.iterator_to(value); }
1105
1106 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
1107 //! appropriate type. Otherwise the behavior is undefined.
1108 //!
1109 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
1110 //! set that points to the value
1111 //!
1112 //! <b>Complexity</b>: Constant.
1113 //!
1114 //! <b>Throws</b>: Nothing.
1115 const_iterator iterator_to(const_reference value) const
1116 { return tree_.iterator_to(value); }
1117
1118 //! <b>Requires</b>: value shall not be in a set/multiset.
1119 //!
1120 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
1121 //! state.
1122 //!
1123 //! <b>Throws</b>: Nothing.
1124 //!
1125 //! <b>Complexity</b>: Constant time.
1126 //!
1127 //! <b>Note</b>: This function puts the hook in the well-known default state
1128 //! used by auto_unlink and safe hooks.
1129 static void init_node(reference value)
1130 { tree_type::init_node(value); }
1131
1132 //! <b>Effects</b>: Unlinks the leftmost node from the tree.
1133 //!
1134 //! <b>Complexity</b>: Average complexity is constant time.
1135 //!
1136 //! <b>Throws</b>: Nothing.
1137 //!
1138 //! <b>Notes</b>: This function breaks the tree and the tree can
1139 //! only be used for more unlink_leftmost_without_rebalance calls.
1140 //! This function is normally used to achieve a step by step
1141 //! controlled destruction of the tree.
1142 pointer unlink_leftmost_without_rebalance()
1143 { return tree_.unlink_leftmost_without_rebalance(); }
1144
1145 //! <b>Requires</b>: replace_this must be a valid iterator of *this
1146 //! and with_this must not be inserted in any tree.
1147 //!
1148 //! <b>Effects</b>: Replaces replace_this in its position in the
1149 //! tree with with_this. The tree does not need to be rebalanced.
1150 //!
1151 //! <b>Complexity</b>: Constant.
1152 //!
1153 //! <b>Throws</b>: Nothing.
1154 //!
1155 //! <b>Note</b>: This function will break container ordering invariants if
1156 //! with_this is not equivalent to *replace_this according to the
1157 //! ordering rules. This function is faster than erasing and inserting
1158 //! the node, since no rebalancing or comparison is needed.
1159 void replace_node(iterator replace_this, reference with_this)
1160 { tree_.replace_node(replace_this, with_this); }
1161
1162 /// @cond
1163 friend bool operator==(const set_impl &x, const set_impl &y)
1164 { return x.tree_ == y.tree_; }
1165
1166 friend bool operator<(const set_impl &x, const set_impl &y)
1167 { return x.tree_ < y.tree_; }
1168 /// @endcond
1169};
1170
1171#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1172template<class T, class ...Options>
1173#else
1174template<class Config>
1175#endif
1176inline bool operator!=
1177#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1178(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y)
1179#else
1180(const set_impl<Config> &x, const set_impl<Config> &y)
1181#endif
1182{ return !(x == y); }
1183
1184#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1185template<class T, class ...Options>
1186#else
1187template<class Config>
1188#endif
1189inline bool operator>
1190#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1191(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y)
1192#else
1193(const set_impl<Config> &x, const set_impl<Config> &y)
1194#endif
1195{ return y < x; }
1196
1197#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1198template<class T, class ...Options>
1199#else
1200template<class Config>
1201#endif
1202inline bool operator<=
1203#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1204(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y)
1205#else
1206(const set_impl<Config> &x, const set_impl<Config> &y)
1207#endif
1208{ return !(y < x); }
1209
1210#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1211template<class T, class ...Options>
1212#else
1213template<class Config>
1214#endif
1215inline bool operator>=
1216#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1217(const set_impl<T, Options...> &x, const set_impl<T, Options...> &y)
1218#else
1219(const set_impl<Config> &x, const set_impl<Config> &y)
1220#endif
1221{ return !(x < y); }
1222
1223#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1224template<class T, class ...Options>
1225#else
1226template<class Config>
1227#endif
1228inline void swap
1229#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1230(set_impl<T, Options...> &x, set_impl<T, Options...> &y)
1231#else
1232(set_impl<Config> &x, set_impl<Config> &y)
1233#endif
1234{ x.swap(y); }
1235
1236//! Helper metafunction to define a \c set that yields to the same type when the
1237//! same options (either explicitly or implicitly) are used.
1238#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1239template<class T, class ...Options>
1240#else
1241template<class T, class O1 = none, class O2 = none
1242 , class O3 = none, class O4 = none>
1243#endif
1244struct make_set
1245{
1246 /// @cond
1247 typedef set_impl
1248 < typename make_rbtree_opt<T,
1249 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1250 O1, O2, O3, O4
1251 #else
1252 Options...
1253 #endif
1254 >::type
1255 > implementation_defined;
1256 /// @endcond
1257 typedef implementation_defined type;
1258};
1259
1260#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
1261#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1262template<class T, class O1, class O2, class O3, class O4>
1263#else
1264template<class T, class ...Options>
1265#endif
1266class set
1267 : public make_set<T,
1268 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1269 O1, O2, O3, O4
1270 #else
1271 Options...
1272 #endif
1273 >::type
1274{
1275 typedef typename make_set
1276 <T,
1277 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
1278 O1, O2, O3, O4
1279 #else
1280 Options...
1281 #endif
1282 >::type Base;
1283
1284 BOOST_MOVABLE_BUT_NOT_COPYABLE(set)
1285 public:
1286 typedef typename Base::value_compare value_compare;
1287 typedef typename Base::value_traits value_traits;
1288 typedef typename Base::iterator iterator;
1289 typedef typename Base::const_iterator const_iterator;
1290
1291 //Assert if passed value traits are compatible with the type
1292 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
1293
1294 set( const value_compare &cmp = value_compare()
1295 , const value_traits &v_traits = value_traits())
1296 : Base(cmp, v_traits)
1297 {}
1298
1299 template<class Iterator>
1300 set( Iterator b, Iterator e
1301 , const value_compare &cmp = value_compare()
1302 , const value_traits &v_traits = value_traits())
1303 : Base(b, e, cmp, v_traits)
1304 {}
1305
1306 set(BOOST_RV_REF(set) x)
1307 : Base(::boost::move(static_cast<Base&>(x)))
1308 {}
1309
1310 set& operator=(BOOST_RV_REF(set) x)
1311 { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
1312
1313 static set &container_from_end_iterator(iterator end_iterator)
1314 { return static_cast<set &>(Base::container_from_end_iterator(end_iterator)); }
1315
1316 static const set &container_from_end_iterator(const_iterator end_iterator)
1317 { return static_cast<const set &>(Base::container_from_end_iterator(end_iterator)); }
1318
1319 static set &container_from_iterator(iterator it)
1320 { return static_cast<set &>(Base::container_from_iterator(it)); }
1321
1322 static const set &container_from_iterator(const_iterator it)
1323 { return static_cast<const set &>(Base::container_from_iterator(it)); }
1324};
1325
1326#endif
1327
1328//! The class template multiset is an intrusive container, that mimics most of
1329//! the interface of std::multiset as described in the C++ standard.
1330//!
1331//! The template parameter \c T is the type to be managed by the container.
1332//! The user can specify additional options and if no options are provided
1333//! default options are used.
1334//!
1335//! The container supports the following options:
1336//! \c base_hook<>/member_hook<>/value_traits<>,
1337//! \c constant_time_size<>, \c size_type<> and
1338//! \c compare<>.
1339#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1340template<class T, class ...Options>
1341#else
1342template<class Config>
1343#endif
1344class multiset_impl
1345{
1346 /// @cond
1347 typedef rbtree_impl<Config> tree_type;
1348
1349 BOOST_MOVABLE_BUT_NOT_COPYABLE(multiset_impl)
1350 typedef tree_type implementation_defined;
1351 /// @endcond
1352
1353 public:
1354 typedef typename implementation_defined::value_type value_type;
1355 typedef typename implementation_defined::value_traits value_traits;
1356 typedef typename implementation_defined::pointer pointer;
1357 typedef typename implementation_defined::const_pointer const_pointer;
1358 typedef typename implementation_defined::reference reference;
1359 typedef typename implementation_defined::const_reference const_reference;
1360 typedef typename implementation_defined::difference_type difference_type;
1361 typedef typename implementation_defined::size_type size_type;
1362 typedef typename implementation_defined::value_compare value_compare;
1363 typedef typename implementation_defined::key_compare key_compare;
1364 typedef typename implementation_defined::iterator iterator;
1365 typedef typename implementation_defined::const_iterator const_iterator;
1366 typedef typename implementation_defined::reverse_iterator reverse_iterator;
1367 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
1368 typedef typename implementation_defined::insert_commit_data insert_commit_data;
1369 typedef typename implementation_defined::node_traits node_traits;
1370 typedef typename implementation_defined::node node;
1371 typedef typename implementation_defined::node_ptr node_ptr;
1372 typedef typename implementation_defined::const_node_ptr const_node_ptr;
1373 typedef typename implementation_defined::node_algorithms node_algorithms;
1374
1375 static const bool constant_time_size = Config::constant_time_size;
1376 //static const bool stateful_value_traits = detail::is_stateful_value_traits<real_value_traits>::value;
1377
1378 /// @cond
1379 private:
1380 tree_type tree_;
1381
1382 protected:
1383 node &prot_header_node(){ return tree_.prot_header_node(); }
1384 node const &prot_header_node() const{ return tree_.prot_header_node(); }
1385 void prot_set_size(size_type s){ tree_.prot_set_size(s); }
1386 value_compare &prot_comp(){ return tree_.prot_comp(); }
1387 /// @endcond
1388
1389 public:
1390 //! <b>Effects</b>: Constructs an empty multiset.
1391 //!
1392 //! <b>Complexity</b>: Constant.
1393 //!
1394 //! <b>Throws</b>: If value_traits::node_traits::node
1395 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1396 //! or the copy constructor/operator() of the value_compare object throws.
1397 explicit multiset_impl( const value_compare &cmp = value_compare()
1398 , const value_traits &v_traits = value_traits())
1399 : tree_(cmp, v_traits)
1400 {}
1401
1402 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
1403 //! cmp must be a comparison function that induces a strict weak ordering.
1404 //!
1405 //! <b>Effects</b>: Constructs an empty multiset and inserts elements from
1406 //! [b, e).
1407 //!
1408 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
1409 //! comp and otherwise N * log N, where N is the distance between first and last
1410 //!
1411 //! <b>Throws</b>: If value_traits::node_traits::node
1412 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
1413 //! or the copy constructor/operator() of the value_compare object throws.
1414 template<class Iterator>
1415 multiset_impl( Iterator b, Iterator e
1416 , const value_compare &cmp = value_compare()
1417 , const value_traits &v_traits = value_traits())
1418 : tree_(false, b, e, cmp, v_traits)
1419 {}
1420
1421 //! <b>Effects</b>: to-do
1422 //!
1423 multiset_impl(BOOST_RV_REF(multiset_impl) x)
1424 : tree_(::boost::move(x.tree_))
1425 {}
1426
1427 //! <b>Effects</b>: to-do
1428 //!
1429 multiset_impl& operator=(BOOST_RV_REF(multiset_impl) x)
1430 { tree_ = ::boost::move(x.tree_); return *this; }
1431
1432 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
1433 //! are not deleted (i.e. no destructors are called).
1434 //!
1435 //! <b>Complexity</b>: Linear to the number of elements on the container.
1436 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1437 //!
1438 //! <b>Throws</b>: Nothing.
1439 ~multiset_impl()
1440 {}
1441
1442 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the multiset.
1443 //!
1444 //! <b>Complexity</b>: Constant.
1445 //!
1446 //! <b>Throws</b>: Nothing.
1447 iterator begin()
1448 { return tree_.begin(); }
1449
1450 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the multiset.
1451 //!
1452 //! <b>Complexity</b>: Constant.
1453 //!
1454 //! <b>Throws</b>: Nothing.
1455 const_iterator begin() const
1456 { return tree_.begin(); }
1457
1458 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the multiset.
1459 //!
1460 //! <b>Complexity</b>: Constant.
1461 //!
1462 //! <b>Throws</b>: Nothing.
1463 const_iterator cbegin() const
1464 { return tree_.cbegin(); }
1465
1466 //! <b>Effects</b>: Returns an iterator pointing to the end of the multiset.
1467 //!
1468 //! <b>Complexity</b>: Constant.
1469 //!
1470 //! <b>Throws</b>: Nothing.
1471 iterator end()
1472 { return tree_.end(); }
1473
1474 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the multiset.
1475 //!
1476 //! <b>Complexity</b>: Constant.
1477 //!
1478 //! <b>Throws</b>: Nothing.
1479 const_iterator end() const
1480 { return tree_.end(); }
1481
1482 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the multiset.
1483 //!
1484 //! <b>Complexity</b>: Constant.
1485 //!
1486 //! <b>Throws</b>: Nothing.
1487 const_iterator cend() const
1488 { return tree_.cend(); }
1489
1490 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
1491 //! reversed multiset.
1492 //!
1493 //! <b>Complexity</b>: Constant.
1494 //!
1495 //! <b>Throws</b>: Nothing.
1496 reverse_iterator rbegin()
1497 { return tree_.rbegin(); }
1498
1499 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1500 //! of the reversed multiset.
1501 //!
1502 //! <b>Complexity</b>: Constant.
1503 //!
1504 //! <b>Throws</b>: Nothing.
1505 const_reverse_iterator rbegin() const
1506 { return tree_.rbegin(); }
1507
1508 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1509 //! of the reversed multiset.
1510 //!
1511 //! <b>Complexity</b>: Constant.
1512 //!
1513 //! <b>Throws</b>: Nothing.
1514 const_reverse_iterator crbegin() const
1515 { return tree_.crbegin(); }
1516
1517 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1518 //! of the reversed multiset.
1519 //!
1520 //! <b>Complexity</b>: Constant.
1521 //!
1522 //! <b>Throws</b>: Nothing.
1523 reverse_iterator rend()
1524 { return tree_.rend(); }
1525
1526 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1527 //! of the reversed multiset.
1528 //!
1529 //! <b>Complexity</b>: Constant.
1530 //!
1531 //! <b>Throws</b>: Nothing.
1532 const_reverse_iterator rend() const
1533 { return tree_.rend(); }
1534
1535 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1536 //! of the reversed multiset.
1537 //!
1538 //! <b>Complexity</b>: Constant.
1539 //!
1540 //! <b>Throws</b>: Nothing.
1541 const_reverse_iterator crend() const
1542 { return tree_.crend(); }
1543
1544 //! <b>Precondition</b>: end_iterator must be a valid end iterator
1545 //! of multiset.
1546 //!
1547 //! <b>Effects</b>: Returns a const reference to the multiset associated to the end iterator
1548 //!
1549 //! <b>Throws</b>: Nothing.
1550 //!
1551 //! <b>Complexity</b>: Constant.
1552 static multiset_impl &container_from_end_iterator(iterator end_iterator)
1553 {
1554 return *detail::parent_from_member<multiset_impl, tree_type>
1555 ( &tree_type::container_from_end_iterator(end_iterator)
1556 , &multiset_impl::tree_);
1557 }
1558
1559 //! <b>Precondition</b>: end_iterator must be a valid end const_iterator
1560 //! of multiset.
1561 //!
1562 //! <b>Effects</b>: Returns a const reference to the multiset associated to the end iterator
1563 //!
1564 //! <b>Throws</b>: Nothing.
1565 //!
1566 //! <b>Complexity</b>: Constant.
1567 static const multiset_impl &container_from_end_iterator(const_iterator end_iterator)
1568 {
1569 return *detail::parent_from_member<multiset_impl, tree_type>
1570 ( &tree_type::container_from_end_iterator(end_iterator)
1571 , &multiset_impl::tree_);
1572 }
1573
1574 //! <b>Precondition</b>: it must be a valid iterator of multiset.
1575 //!
1576 //! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
1577 //!
1578 //! <b>Throws</b>: Nothing.
1579 //!
1580 //! <b>Complexity</b>: Logarithmic.
1581 static multiset_impl &container_from_iterator(iterator it)
1582 {
1583 return *detail::parent_from_member<multiset_impl, tree_type>
1584 ( &tree_type::container_from_iterator(it)
1585 , &multiset_impl::tree_);
1586 }
1587
1588 //! <b>Precondition</b>: it must be a valid const_iterator of multiset.
1589 //!
1590 //! <b>Effects</b>: Returns a const reference to the multiset associated to the iterator
1591 //!
1592 //! <b>Throws</b>: Nothing.
1593 //!
1594 //! <b>Complexity</b>: Logarithmic.
1595 static const multiset_impl &container_from_iterator(const_iterator it)
1596 {
1597 return *detail::parent_from_member<multiset_impl, tree_type>
1598 ( &tree_type::container_from_iterator(it)
1599 , &multiset_impl::tree_);
1600 }
1601
1602 //! <b>Effects</b>: Returns the key_compare object used by the multiset.
1603 //!
1604 //! <b>Complexity</b>: Constant.
1605 //!
1606 //! <b>Throws</b>: If key_compare copy-constructor throws.
1607 key_compare key_comp() const
1608 { return tree_.value_comp(); }
1609
1610 //! <b>Effects</b>: Returns the value_compare object used by the multiset.
1611 //!
1612 //! <b>Complexity</b>: Constant.
1613 //!
1614 //! <b>Throws</b>: If value_compare copy-constructor throws.
1615 value_compare value_comp() const
1616 { return tree_.value_comp(); }
1617
1618 //! <b>Effects</b>: Returns true if the container is empty.
1619 //!
1620 //! <b>Complexity</b>: Constant.
1621 //!
1622 //! <b>Throws</b>: Nothing.
1623 bool empty() const
1624 { return tree_.empty(); }
1625
1626 //! <b>Effects</b>: Returns the number of elements stored in the multiset.
1627 //!
1628 //! <b>Complexity</b>: Linear to elements contained in *this if,
1629 //! constant-time size option is enabled. Constant-time otherwise.
1630 //!
1631 //! <b>Throws</b>: Nothing.
1632 size_type size() const
1633 { return tree_.size(); }
1634
1635 //! <b>Effects</b>: Swaps the contents of two multisets.
1636 //!
1637 //! <b>Complexity</b>: Constant.
1638 //!
1639 //! <b>Throws</b>: If the swap() call for the comparison functor
1640 //! found using ADL throws. Strong guarantee.
1641 void swap(multiset_impl& other)
1642 { tree_.swap(other.tree_); }
1643
1644 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1645 //! Cloner should yield to nodes equivalent to the original nodes.
1646 //!
1647 //! <b>Effects</b>: Erases all the elements from *this
1648 //! calling Disposer::operator()(pointer), clones all the
1649 //! elements from src calling Cloner::operator()(const_reference )
1650 //! and inserts them on *this. Copies the predicate from the source container.
1651 //!
1652 //! If cloner throws, all cloned elements are unlinked and disposed
1653 //! calling Disposer::operator()(pointer).
1654 //!
1655 //! <b>Complexity</b>: Linear to erased plus inserted elements.
1656 //!
1657 //! <b>Throws</b>: If cloner throws or predicate copy assignment throws. Basic guarantee.
1658 template <class Cloner, class Disposer>
1659 void clone_from(const multiset_impl &src, Cloner cloner, Disposer disposer)
1660 { tree_.clone_from(src.tree_, cloner, disposer); }
1661
1662 //! <b>Requires</b>: value must be an lvalue
1663 //!
1664 //! <b>Effects</b>: Inserts value into the multiset.
1665 //!
1666 //! <b>Returns</b>: An iterator that points to the position where the new
1667 //! element was inserted.
1668 //!
1669 //! <b>Complexity</b>: Average complexity for insert element is at
1670 //! most logarithmic.
1671 //!
1672 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
1673 //!
1674 //! <b>Note</b>: Does not affect the validity of iterators and references.
1675 //! No copy-constructors are called.
1676 iterator insert(reference value)
1677 { return tree_.insert_equal(value); }
1678
1679 //! <b>Requires</b>: value must be an lvalue
1680 //!
1681 //! <b>Effects</b>: Inserts x into the multiset, using pos as a hint to
1682 //! where it will be inserted.
1683 //!
1684 //! <b>Returns</b>: An iterator that points to the position where the new
1685 //! element was inserted.
1686 //!
1687 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
1688 //! constant time if t is inserted immediately before hint.
1689 //!
1690 //! <b>Throws</b>: If the internal value_compare ordering function throws. Strong guarantee.
1691 //!
1692 //! <b>Note</b>: Does not affect the validity of iterators and references.
1693 //! No copy-constructors are called.
1694 iterator insert(const_iterator hint, reference value)
1695 { return tree_.insert_equal(hint, value); }
1696
1697 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
1698 //! of type value_type.
1699 //!
1700 //! <b>Effects</b>: Inserts a range into the multiset.
1701 //!
1702 //! <b>Returns</b>: An iterator that points to the position where the new
1703 //! element was inserted.
1704 //!
1705 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
1706 //! size of the range. However, it is linear in N if the range is already sorted
1707 //! by value_comp().
1708 //!
1709 //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
1710 //!
1711 //! <b>Note</b>: Does not affect the validity of iterators and references.
1712 //! No copy-constructors are called.
1713 template<class Iterator>
1714 void insert(Iterator b, Iterator e)
1715 { tree_.insert_equal(b, e); }
1716
1717 //! <b>Requires</b>: value must be an lvalue, "pos" must be
1718 //! a valid iterator (or end) and must be the succesor of value
1719 //! once inserted according to the predicate
1720 //!
1721 //! <b>Effects</b>: Inserts x into the tree before "pos".
1722 //!
1723 //! <b>Complexity</b>: Constant time.
1724 //!
1725 //! <b>Throws</b>: Nothing.
1726 //!
1727 //! <b>Note</b>: This function does not check preconditions so if "pos" is not
1728 //! the successor of "value" tree ordering invariant will be broken.
1729 //! This is a low-level function to be used only for performance reasons
1730 //! by advanced users.
1731 iterator insert_before(const_iterator pos, reference value)
1732 { return tree_.insert_before(pos, value); }
1733
1734 //! <b>Requires</b>: value must be an lvalue, and it must be no less
1735 //! than the greatest inserted key
1736 //!
1737 //! <b>Effects</b>: Inserts x into the tree in the last position.
1738 //!
1739 //! <b>Complexity</b>: Constant time.
1740 //!
1741 //! <b>Throws</b>: Nothing.
1742 //!
1743 //! <b>Note</b>: This function does not check preconditions so if value is
1744 //! less than the greatest inserted key tree ordering invariant will be broken.
1745 //! This function is slightly more efficient than using "insert_before".
1746 //! This is a low-level function to be used only for performance reasons
1747 //! by advanced users.
1748 void push_back(reference value)
1749 { tree_.push_back(value); }
1750
1751 //! <b>Requires</b>: value must be an lvalue, and it must be no greater
1752 //! than the minimum inserted key
1753 //!
1754 //! <b>Effects</b>: Inserts x into the tree in the first position.
1755 //!
1756 //! <b>Complexity</b>: Constant time.
1757 //!
1758 //! <b>Throws</b>: Nothing.
1759 //!
1760 //! <b>Note</b>: This function does not check preconditions so if value is
1761 //! greater than the minimum inserted key tree ordering invariant will be broken.
1762 //! This function is slightly more efficient than using "insert_before".
1763 //! This is a low-level function to be used only for performance reasons
1764 //! by advanced users.
1765 void push_front(reference value)
1766 { tree_.push_front(value); }
1767
1768 //! <b>Effects</b>: Erases the element pointed to by pos.
1769 //!
1770 //! <b>Complexity</b>: Average complexity is constant time.
1771 //!
1772 //! <b>Returns</b>: An iterator to the element after the erased element.
1773 //!
1774 //! <b>Throws</b>: Nothing.
1775 //!
1776 //! <b>Note</b>: Invalidates the iterators (but not the references)
1777 //! to the erased elements. No destructors are called.
1778 iterator erase(const_iterator i)
1779 { return tree_.erase(i); }
1780
1781 //! <b>Effects</b>: Erases the range pointed to by b end e.
1782 //!
1783 //! <b>Returns</b>: An iterator to the element after the erased elements.
1784 //!
1785 //! <b>Complexity</b>: Average complexity for erase range is at most
1786 //! O(log(size() + N)), where N is the number of elements in the range.
1787 //!
1788 //! <b>Throws</b>: Nothing.
1789 //!
1790 //! <b>Note</b>: Invalidates the iterators (but not the references)
1791 //! to the erased elements. No destructors are called.
1792 iterator erase(const_iterator b, iterator e)
1793 { return tree_.erase(b, e); }
1794
1795 //! <b>Effects</b>: Erases all the elements with the given value.
1796 //!
1797 //! <b>Returns</b>: The number of erased elements.
1798 //!
1799 //! <b>Complexity</b>: O(log(size() + this->count(value)).
1800 //!
1801 //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
1802 //!
1803 //! <b>Note</b>: Invalidates the iterators (but not the references)
1804 //! to the erased elements. No destructors are called.
1805 size_type erase(const_reference value)
1806 { return tree_.erase(value); }
1807
1808 //! <b>Effects</b>: Erases all the elements that compare equal with
1809 //! the given key and the given comparison functor.
1810 //!
1811 //! <b>Returns</b>: The number of erased elements.
1812 //!
1813 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
1814 //!
1815 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
1816 //!
1817 //! <b>Note</b>: Invalidates the iterators (but not the references)
1818 //! to the erased elements. No destructors are called.
1819 template<class KeyType, class KeyValueCompare>
1820 size_type erase(const KeyType& key, KeyValueCompare comp
1821 /// @cond
1822 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
1823 /// @endcond
1824 )
1825 { return tree_.erase(key, comp); }
1826
1827 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1828 //!
1829 //! <b>Returns</b>: An iterator to the element after the erased element.
1830 //!
1831 //! <b>Effects</b>: Erases the element pointed to by pos.
1832 //! Disposer::operator()(pointer) is called for the removed element.
1833 //!
1834 //! <b>Complexity</b>: Average complexity for erase element is constant time.
1835 //!
1836 //! <b>Throws</b>: Nothing.
1837 //!
1838 //! <b>Note</b>: Invalidates the iterators
1839 //! to the erased elements.
1840 template<class Disposer>
1841 iterator erase_and_dispose(const_iterator i, Disposer disposer)
1842 { return tree_.erase_and_dispose(i, disposer); }
1843
1844 #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
1845 template<class Disposer>
1846 iterator erase_and_dispose(iterator i, Disposer disposer)
1847 { return this->erase_and_dispose(const_iterator(i), disposer); }
1848 #endif
1849
1850 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1851 //!
1852 //! <b>Returns</b>: An iterator to the element after the erased elements.
1853 //!
1854 //! <b>Effects</b>: Erases the range pointed to by b end e.
1855 //! Disposer::operator()(pointer) is called for the removed elements.
1856 //!
1857 //! <b>Complexity</b>: Average complexity for erase range is at most
1858 //! O(log(size() + N)), where N is the number of elements in the range.
1859 //!
1860 //! <b>Throws</b>: Nothing.
1861 //!
1862 //! <b>Note</b>: Invalidates the iterators
1863 //! to the erased elements.
1864 template<class Disposer>
1865 iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
1866 { return tree_.erase_and_dispose(b, e, disposer); }
1867
1868 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1869 //!
1870 //! <b>Effects</b>: Erases all the elements with the given value.
1871 //! Disposer::operator()(pointer) is called for the removed elements.
1872 //!
1873 //! <b>Returns</b>: The number of erased elements.
1874 //!
1875 //! <b>Complexity</b>: O(log(size() + this->count(value)).
1876 //!
1877 //! <b>Throws</b>: If the internal value_compare ordering function throws. Basic guarantee.
1878 //!
1879 //! <b>Note</b>: Invalidates the iterators (but not the references)
1880 //! to the erased elements. No destructors are called.
1881 template<class Disposer>
1882 size_type erase_and_dispose(const_reference value, Disposer disposer)
1883 { return tree_.erase_and_dispose(value, disposer); }
1884
1885 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1886 //!
1887 //! <b>Effects</b>: Erases all the elements with the given key.
1888 //! according to the comparison functor "comp".
1889 //! Disposer::operator()(pointer) is called for the removed elements.
1890 //!
1891 //! <b>Returns</b>: The number of erased elements.
1892 //!
1893 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
1894 //!
1895 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
1896 //!
1897 //! <b>Note</b>: Invalidates the iterators
1898 //! to the erased elements.
1899 template<class KeyType, class KeyValueCompare, class Disposer>
1900 size_type erase_and_dispose(const KeyType& key, KeyValueCompare comp, Disposer disposer
1901 /// @cond
1902 , typename detail::enable_if_c<!detail::is_convertible<KeyValueCompare, const_iterator>::value >::type * = 0
1903 /// @endcond
1904 )
1905 { return tree_.erase_and_dispose(key, comp, disposer); }
1906
1907 //! <b>Effects</b>: Erases all the elements of the container.
1908 //!
1909 //! <b>Complexity</b>: Linear to the number of elements on the container.
1910 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
1911 //!
1912 //! <b>Throws</b>: Nothing.
1913 //!
1914 //! <b>Note</b>: Invalidates the iterators (but not the references)
1915 //! to the erased elements. No destructors are called.
1916 void clear()
1917 { return tree_.clear(); }
1918
1919 //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
1920 //!
1921 //! <b>Effects</b>: Erases all the elements of the container.
1922 //!
1923 //! <b>Complexity</b>: Linear to the number of elements on the container.
1924 //! Disposer::operator()(pointer) is called for the removed elements.
1925 //!
1926 //! <b>Throws</b>: Nothing.
1927 //!
1928 //! <b>Note</b>: Invalidates the iterators (but not the references)
1929 //! to the erased elements. No destructors are called.
1930 template<class Disposer>
1931 void clear_and_dispose(Disposer disposer)
1932 { return tree_.clear_and_dispose(disposer); }
1933
1934 //! <b>Effects</b>: Returns the number of contained elements with the given key
1935 //!
1936 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
1937 //! to number of objects with the given key.
1938 //!
1939 //! <b>Throws</b>: If the internal value_compare ordering function throws.
1940 size_type count(const_reference value) const
1941 { return tree_.count(value); }
1942
1943 //! <b>Effects</b>: Returns the number of contained elements with the same key
1944 //! compared with the given comparison functor.
1945 //!
1946 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
1947 //! to number of objects with the given key.
1948 //!
1949 //! <b>Throws</b>: If comp ordering function throws.
1950 template<class KeyType, class KeyValueCompare>
1951 size_type count(const KeyType& key, KeyValueCompare comp) const
1952 { return tree_.count(key, comp); }
1953
1954 //! <b>Effects</b>: Returns an iterator to the first element whose
1955 //! key is not less than k or end() if that element does not exist.
1956 //!
1957 //! <b>Complexity</b>: Logarithmic.
1958 //!
1959 //! <b>Throws</b>: If the internal value_compare ordering function throws.
1960 iterator lower_bound(const_reference value)
1961 { return tree_.lower_bound(value); }
1962
1963 //! <b>Requires</b>: comp must imply the same element order as
1964 //! value_compare. Usually key is the part of the value_type
1965 //! that is used in the ordering functor.
1966 //!
1967 //! <b>Effects</b>: Returns an iterator to the first element whose
1968 //! key according to the comparison functor is not less than k or
1969 //! end() if that element does not exist.
1970 //!
1971 //! <b>Complexity</b>: Logarithmic.
1972 //!
1973 //! <b>Throws</b>: If comp ordering function throws.
1974 //!
1975 //! <b>Note</b>: This function is used when constructing a value_type
1976 //! is expensive and the value_type can be compared with a cheaper
1977 //! key type. Usually this key is part of the value_type.
1978 template<class KeyType, class KeyValueCompare>
1979 iterator lower_bound(const KeyType& key, KeyValueCompare comp)
1980 { return tree_.lower_bound(key, comp); }
1981
1982 //! <b>Effects</b>: Returns a const iterator to the first element whose
1983 //! key is not less than k or end() if that element does not exist.
1984 //!
1985 //! <b>Complexity</b>: Logarithmic.
1986 //!
1987 //! <b>Throws</b>: If the internal value_compare ordering function throws.
1988 const_iterator lower_bound(const_reference value) const
1989 { return tree_.lower_bound(value); }
1990
1991 //! <b>Requires</b>: comp must imply the same element order as
1992 //! value_compare. Usually key is the part of the value_type
1993 //! that is used in the ordering functor.
1994 //!
1995 //! <b>Effects</b>: Returns a const_iterator to the first element whose
1996 //! key according to the comparison functor is not less than k or
1997 //! end() if that element does not exist.
1998 //!
1999 //! <b>Complexity</b>: Logarithmic.
2000 //!
2001 //! <b>Throws</b>: If comp ordering function throws.
2002 //!
2003 //! <b>Note</b>: This function is used when constructing a value_type
2004 //! is expensive and the value_type can be compared with a cheaper
2005 //! key type. Usually this key is part of the value_type.
2006 template<class KeyType, class KeyValueCompare>
2007 const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
2008 { return tree_.lower_bound(key, comp); }
2009
2010 //! <b>Effects</b>: Returns an iterator to the first element whose
2011 //! key is greater than k or end() if that element does not exist.
2012 //!
2013 //! <b>Complexity</b>: Logarithmic.
2014 //!
2015 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2016 iterator upper_bound(const_reference value)
2017 { return tree_.upper_bound(value); }
2018
2019 //! <b>Requires</b>: comp must imply the same element order as
2020 //! value_compare. Usually key is the part of the value_type
2021 //! that is used in the ordering functor.
2022 //!
2023 //! <b>Effects</b>: Returns an iterator to the first element whose
2024 //! key according to the comparison functor is greater than key or
2025 //! end() if that element does not exist.
2026 //!
2027 //! <b>Complexity</b>: Logarithmic.
2028 //!
2029 //! <b>Throws</b>: If comp ordering function throws.
2030 //!
2031 //! <b>Note</b>: This function is used when constructing a value_type
2032 //! is expensive and the value_type can be compared with a cheaper
2033 //! key type. Usually this key is part of the value_type.
2034 template<class KeyType, class KeyValueCompare>
2035 iterator upper_bound(const KeyType& key, KeyValueCompare comp)
2036 { return tree_.upper_bound(key, comp); }
2037
2038 //! <b>Effects</b>: Returns an iterator to the first element whose
2039 //! key is greater than k or end() if that element does not exist.
2040 //!
2041 //! <b>Complexity</b>: Logarithmic.
2042 //!
2043 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2044 const_iterator upper_bound(const_reference value) const
2045 { return tree_.upper_bound(value); }
2046
2047 //! <b>Requires</b>: comp must imply the same element order as
2048 //! value_compare. Usually key is the part of the value_type
2049 //! that is used in the ordering functor.
2050 //!
2051 //! <b>Effects</b>: Returns a const_iterator to the first element whose
2052 //! key according to the comparison functor is greater than key or
2053 //! end() if that element does not exist.
2054 //!
2055 //! <b>Complexity</b>: Logarithmic.
2056 //!
2057 //! <b>Throws</b>: If comp ordering function throws.
2058 //!
2059 //! <b>Note</b>: This function is used when constructing a value_type
2060 //! is expensive and the value_type can be compared with a cheaper
2061 //! key type. Usually this key is part of the value_type.
2062 template<class KeyType, class KeyValueCompare>
2063 const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
2064 { return tree_.upper_bound(key, comp); }
2065
2066 //! <b>Effects</b>: Finds an iterator to the first element whose value is
2067 //! "value" or end() if that element does not exist.
2068 //!
2069 //! <b>Complexity</b>: Logarithmic.
2070 //!
2071 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2072 iterator find(const_reference value)
2073 { return tree_.find(value); }
2074
2075 //! <b>Requires</b>: comp must imply the same element order as
2076 //! value_compare. Usually key is the part of the value_type
2077 //! that is used in the ordering functor.
2078 //!
2079 //! <b>Effects</b>: Finds an iterator to the first element whose key is
2080 //! "key" according to the comparison functor or end() if that element
2081 //! does not exist.
2082 //!
2083 //! <b>Complexity</b>: Logarithmic.
2084 //!
2085 //! <b>Throws</b>: If comp ordering function throws.
2086 //!
2087 //! <b>Note</b>: This function is used when constructing a value_type
2088 //! is expensive and the value_type can be compared with a cheaper
2089 //! key type. Usually this key is part of the value_type.
2090 template<class KeyType, class KeyValueCompare>
2091 iterator find(const KeyType& key, KeyValueCompare comp)
2092 { return tree_.find(key, comp); }
2093
2094 //! <b>Effects</b>: Finds a const_iterator to the first element whose value is
2095 //! "value" or end() if that element does not exist.
2096 //!
2097 //! <b>Complexity</b>: Logarithmic.
2098 //!
2099 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2100 const_iterator find(const_reference value) const
2101 { return tree_.find(value); }
2102
2103 //! <b>Requires</b>: comp must imply the same element order as
2104 //! value_compare. Usually key is the part of the value_type
2105 //! that is used in the ordering functor.
2106 //!
2107 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
2108 //! "key" according to the comparison functor or end() if that element
2109 //! does not exist.
2110 //!
2111 //! <b>Complexity</b>: Logarithmic.
2112 //!
2113 //! <b>Throws</b>: If comp ordering function throws.
2114 //!
2115 //! <b>Note</b>: This function is used when constructing a value_type
2116 //! is expensive and the value_type can be compared with a cheaper
2117 //! key type. Usually this key is part of the value_type.
2118 template<class KeyType, class KeyValueCompare>
2119 const_iterator find(const KeyType& key, KeyValueCompare comp) const
2120 { return tree_.find(key, comp); }
2121
2122 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
2123 //! an empty range that indicates the position where those elements would be
2124 //! if they there is no elements with key k.
2125 //!
2126 //! <b>Complexity</b>: Logarithmic.
2127 //!
2128 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2129 std::pair<iterator,iterator> equal_range(const_reference value)
2130 { return tree_.equal_range(value); }
2131
2132 //! <b>Requires</b>: comp must imply the same element order as
2133 //! value_compare. Usually key is the part of the value_type
2134 //! that is used in the ordering functor.
2135 //!
2136 //! <b>Effects</b>: Finds a range containing all elements whose key is k
2137 //! according to the comparison functor or an empty range
2138 //! that indicates the position where those elements would be
2139 //! if they there is no elements with key k.
2140 //!
2141 //! <b>Complexity</b>: Logarithmic.
2142 //!
2143 //! <b>Throws</b>: If comp ordering function throws.
2144 //!
2145 //! <b>Note</b>: This function is used when constructing a value_type
2146 //! is expensive and the value_type can be compared with a cheaper
2147 //! key type. Usually this key is part of the value_type.
2148 template<class KeyType, class KeyValueCompare>
2149 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
2150 { return tree_.equal_range(key, comp); }
2151
2152 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
2153 //! an empty range that indicates the position where those elements would be
2154 //! if they there is no elements with key k.
2155 //!
2156 //! <b>Complexity</b>: Logarithmic.
2157 //!
2158 //! <b>Throws</b>: If the internal value_compare ordering function throws.
2159 std::pair<const_iterator, const_iterator>
2160 equal_range(const_reference value) const
2161 { return tree_.equal_range(value); }
2162
2163 //! <b>Requires</b>: comp must imply the same element order as
2164 //! value_compare. Usually key is the part of the value_type
2165 //! that is used in the ordering functor.
2166 //!
2167 //! <b>Effects</b>: Finds a range containing all elements whose key is k
2168 //! according to the comparison functor or an empty range
2169 //! that indicates the position where those elements would be
2170 //! if they there is no elements with key k.
2171 //!
2172 //! <b>Complexity</b>: Logarithmic.
2173 //!
2174 //! <b>Throws</b>: If comp ordering function throws.
2175 //!
2176 //! <b>Note</b>: This function is used when constructing a value_type
2177 //! is expensive and the value_type can be compared with a cheaper
2178 //! key type. Usually this key is part of the value_type.
2179 template<class KeyType, class KeyValueCompare>
2180 std::pair<const_iterator, const_iterator>
2181 equal_range(const KeyType& key, KeyValueCompare comp) const
2182 { return tree_.equal_range(key, comp); }
2183
2184 //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
2185 //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
2186 //!
2187 //! <b>Effects</b>: Returns an a pair with the following criteria:
2188 //!
2189 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
2190 //!
2191 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
2192 //!
2193 //! <b>Complexity</b>: Logarithmic.
2194 //!
2195 //! <b>Throws</b>: If the predicate throws.
2196 //!
2197 //! <b>Note</b>: This function can be more efficient than calling upper_bound
2198 //! and lower_bound for lower_value and upper_value.
2199 std::pair<iterator,iterator> bounded_range
2200 (const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed)
2201 { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
2202
2203 //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
2204 //! ordering compatible with the strict weak ordering used to create the
2205 //! the tree.
2206 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
2207 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
2208 //!
2209 //! <b>Effects</b>: Returns an a pair with the following criteria:
2210 //!
2211 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
2212 //!
2213 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
2214 //!
2215 //! <b>Complexity</b>: Logarithmic.
2216 //!
2217 //! <b>Throws</b>: If "comp" throws.
2218 //!
2219 //! <b>Note</b>: This function can be more efficient than calling upper_bound
2220 //! and lower_bound for lower_key and upper_key.
2221 template<class KeyType, class KeyValueCompare>
2222 std::pair<iterator,iterator> bounded_range
2223 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed)
2224 { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
2225
2226 //! <b>Requires</b>: 'lower_value' must not be greater than 'upper_value'. If
2227 //! 'lower_value' == 'upper_value', ('left_closed' || 'right_closed') must be false.
2228 //!
2229 //! <b>Effects</b>: Returns an a pair with the following criteria:
2230 //!
2231 //! first = lower_bound(lower_key) if left_closed, upper_bound(lower_key) otherwise
2232 //!
2233 //! second = upper_bound(upper_key) if right_closed, lower_bound(upper_key) otherwise
2234 //!
2235 //! <b>Complexity</b>: Logarithmic.
2236 //!
2237 //! <b>Throws</b>: If the predicate throws.
2238 //!
2239 //! <b>Note</b>: This function can be more efficient than calling upper_bound
2240 //! and lower_bound for lower_value and upper_value.
2241 std::pair<const_iterator, const_iterator>
2242 bounded_range(const_reference lower_value, const_reference upper_value, bool left_closed, bool right_closed) const
2243 { return tree_.bounded_range(lower_value, upper_value, left_closed, right_closed); }
2244
2245 //! <b>Requires</b>: KeyValueCompare is a function object that induces a strict weak
2246 //! ordering compatible with the strict weak ordering used to create the
2247 //! the tree.
2248 //! 'lower_key' must not be greater than 'upper_key' according to 'comp'. If
2249 //! 'lower_key' == 'upper_key', ('left_closed' || 'right_closed') must be false.
2250 //!
2251 //! <b>Effects</b>: Returns an a pair with the following criteria:
2252 //!
2253 //! first = lower_bound(lower_key, comp) if left_closed, upper_bound(lower_key, comp) otherwise
2254 //!
2255 //! second = upper_bound(upper_key, comp) if right_closed, lower_bound(upper_key, comp) otherwise
2256 //!
2257 //! <b>Complexity</b>: Logarithmic.
2258 //!
2259 //! <b>Throws</b>: If "comp" throws.
2260 //!
2261 //! <b>Note</b>: This function can be more efficient than calling upper_bound
2262 //! and lower_bound for lower_key and upper_key.
2263 template<class KeyType, class KeyValueCompare>
2264 std::pair<const_iterator, const_iterator>
2265 bounded_range
2266 (const KeyType& lower_key, const KeyType& upper_key, KeyValueCompare comp, bool left_closed, bool right_closed) const
2267 { return tree_.bounded_range(lower_key, upper_key, comp, left_closed, right_closed); }
2268
2269 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
2270 //! appropriate type. Otherwise the behavior is undefined.
2271 //!
2272 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
2273 //! that points to the value
2274 //!
2275 //! <b>Complexity</b>: Constant.
2276 //!
2277 //! <b>Throws</b>: Nothing.
2278 //!
2279 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
2280 //! is stateless.
2281 static iterator s_iterator_to(reference value)
2282 { return tree_type::s_iterator_to(value); }
2283
2284 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
2285 //! appropriate type. Otherwise the behavior is undefined.
2286 //!
2287 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
2288 //! set that points to the value
2289 //!
2290 //! <b>Complexity</b>: Constant.
2291 //!
2292 //! <b>Throws</b>: Nothing.
2293 //!
2294 //! <b>Note</b>: This static function is available only if the <i>value traits</i>
2295 //! is stateless.
2296 static const_iterator s_iterator_to(const_reference value)
2297 { return tree_type::s_iterator_to(value); }
2298
2299 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
2300 //! appropriate type. Otherwise the behavior is undefined.
2301 //!
2302 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
2303 //! that points to the value
2304 //!
2305 //! <b>Complexity</b>: Constant.
2306 //!
2307 //! <b>Throws</b>: Nothing.
2308 iterator iterator_to(reference value)
2309 { return tree_.iterator_to(value); }
2310
2311 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
2312 //! appropriate type. Otherwise the behavior is undefined.
2313 //!
2314 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
2315 //! set that points to the value
2316 //!
2317 //! <b>Complexity</b>: Constant.
2318 //!
2319 //! <b>Throws</b>: Nothing.
2320 const_iterator iterator_to(const_reference value) const
2321 { return tree_.iterator_to(value); }
2322
2323 //! <b>Requires</b>: value shall not be in a set/multiset.
2324 //!
2325 //! <b>Effects</b>: init_node puts the hook of a value in a well-known default
2326 //! state.
2327 //!
2328 //! <b>Throws</b>: Nothing.
2329 //!
2330 //! <b>Complexity</b>: Constant time.
2331 //!
2332 //! <b>Note</b>: This function puts the hook in the well-known default state
2333 //! used by auto_unlink and safe hooks.
2334 static void init_node(reference value)
2335 { tree_type::init_node(value); }
2336
2337 //! <b>Effects</b>: Unlinks the leftmost node from the tree.
2338 //!
2339 //! <b>Complexity</b>: Average complexity is constant time.
2340 //!
2341 //! <b>Throws</b>: Nothing.
2342 //!
2343 //! <b>Notes</b>: This function breaks the tree and the tree can
2344 //! only be used for more unlink_leftmost_without_rebalance calls.
2345 //! This function is normally used to achieve a step by step
2346 //! controlled destruction of the tree.
2347 pointer unlink_leftmost_without_rebalance()
2348 { return tree_.unlink_leftmost_without_rebalance(); }
2349
2350 //! <b>Requires</b>: replace_this must be a valid iterator of *this
2351 //! and with_this must not be inserted in any tree.
2352 //!
2353 //! <b>Effects</b>: Replaces replace_this in its position in the
2354 //! tree with with_this. The tree does not need to be rebalanced.
2355 //!
2356 //! <b>Complexity</b>: Constant.
2357 //!
2358 //! <b>Throws</b>: Nothing.
2359 //!
2360 //! <b>Note</b>: This function will break container ordering invariants if
2361 //! with_this is not equivalent to *replace_this according to the
2362 //! ordering rules. This function is faster than erasing and inserting
2363 //! the node, since no rebalancing or comparison is needed.
2364 void replace_node(iterator replace_this, reference with_this)
2365 { tree_.replace_node(replace_this, with_this); }
2366
2367 //! <b>Effects</b>: removes "value" from the container.
2368 //!
2369 //! <b>Throws</b>: Nothing.
2370 //!
2371 //! <b>Complexity</b>: Logarithmic time.
2372 //!
2373 //! <b>Note</b>: This static function is only usable with non-constant
2374 //! time size containers that have stateless comparison functors.
2375 //!
2376 //! If the user calls
2377 //! this function with a constant time size container or stateful comparison
2378 //! functor a compilation error will be issued.
2379 static void remove_node(reference value)
2380 { tree_type::remove_node(value); }
2381
2382 /// @cond
2383 friend bool operator==(const multiset_impl &x, const multiset_impl &y)
2384 { return x.tree_ == y.tree_; }
2385
2386 friend bool operator<(const multiset_impl &x, const multiset_impl &y)
2387 { return x.tree_ < y.tree_; }
2388 /// @endcond
2389};
2390
2391#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2392template<class T, class ...Options>
2393#else
2394template<class Config>
2395#endif
2396inline bool operator!=
2397#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2398(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y)
2399#else
2400(const multiset_impl<Config> &x, const multiset_impl<Config> &y)
2401#endif
2402{ return !(x == y); }
2403
2404#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2405template<class T, class ...Options>
2406#else
2407template<class Config>
2408#endif
2409inline bool operator>
2410#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2411(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y)
2412#else
2413(const multiset_impl<Config> &x, const multiset_impl<Config> &y)
2414#endif
2415{ return y < x; }
2416
2417#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2418template<class T, class ...Options>
2419#else
2420template<class Config>
2421#endif
2422inline bool operator<=
2423#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2424(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y)
2425#else
2426(const multiset_impl<Config> &x, const multiset_impl<Config> &y)
2427#endif
2428{ return !(y < x); }
2429
2430#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2431template<class T, class ...Options>
2432#else
2433template<class Config>
2434#endif
2435inline bool operator>=
2436#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2437(const multiset_impl<T, Options...> &x, const multiset_impl<T, Options...> &y)
2438#else
2439(const multiset_impl<Config> &x, const multiset_impl<Config> &y)
2440#endif
2441{ return !(x < y); }
2442
2443#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2444template<class T, class ...Options>
2445#else
2446template<class Config>
2447#endif
2448inline void swap
2449#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
2450(multiset_impl<T, Options...> &x, multiset_impl<T, Options...> &y)
2451#else
2452(multiset_impl<Config> &x, multiset_impl<Config> &y)
2453#endif
2454{ x.swap(y); }
2455
2456//! Helper metafunction to define a \c multiset that yields to the same type when the
2457//! same options (either explicitly or implicitly) are used.
2458#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2459template<class T, class ...Options>
2460#else
2461template<class T, class O1 = none, class O2 = none
2462 , class O3 = none, class O4 = none>
2463#endif
2464struct make_multiset
2465{
2466 /// @cond
2467 typedef multiset_impl
2468 < typename make_rbtree_opt<T,
2469 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2470 O1, O2, O3, O4
2471 #else
2472 Options...
2473 #endif
2474 >::type
2475 > implementation_defined;
2476 /// @endcond
2477 typedef implementation_defined type;
2478};
2479
2480#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
2481
2482#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2483template<class T, class O1, class O2, class O3, class O4>
2484#else
2485template<class T, class ...Options>
2486#endif
2487class multiset
2488 : public make_multiset<T,
2489 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2490 O1, O2, O3, O4
2491 #else
2492 Options...
2493 #endif
2494 >::type
2495{
2496 typedef typename make_multiset<T,
2497 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
2498 O1, O2, O3, O4
2499 #else
2500 Options...
2501 #endif
2502 >::type Base;
2503
2504 BOOST_MOVABLE_BUT_NOT_COPYABLE(multiset)
2505
2506 public:
2507 typedef typename Base::value_compare value_compare;
2508 typedef typename Base::value_traits value_traits;
2509 typedef typename Base::iterator iterator;
2510 typedef typename Base::const_iterator const_iterator;
2511
2512 //Assert if passed value traits are compatible with the type
2513 BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
2514
2515 multiset( const value_compare &cmp = value_compare()
2516 , const value_traits &v_traits = value_traits())
2517 : Base(cmp, v_traits)
2518 {}
2519
2520 template<class Iterator>
2521 multiset( Iterator b, Iterator e
2522 , const value_compare &cmp = value_compare()
2523 , const value_traits &v_traits = value_traits())
2524 : Base(b, e, cmp, v_traits)
2525 {}
2526
2527 multiset(BOOST_RV_REF(multiset) x)
2528 : Base(::boost::move(static_cast<Base&>(x)))
2529 {}
2530
2531 multiset& operator=(BOOST_RV_REF(multiset) x)
2532 { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
2533
2534 static multiset &container_from_end_iterator(iterator end_iterator)
2535 { return static_cast<multiset &>(Base::container_from_end_iterator(end_iterator)); }
2536
2537 static const multiset &container_from_end_iterator(const_iterator end_iterator)
2538 { return static_cast<const multiset &>(Base::container_from_end_iterator(end_iterator)); }
2539
2540 static multiset &container_from_iterator(iterator it)
2541 { return static_cast<multiset &>(Base::container_from_iterator(it)); }
2542
2543 static const multiset &container_from_iterator(const_iterator it)
2544 { return static_cast<const multiset &>(Base::container_from_iterator(it)); }
2545};
2546
2547#endif
2548
2549} //namespace intrusive
2550} //namespace boost
2551
2552#include <boost/intrusive/detail/config_end.hpp>
2553
2554#endif //BOOST_INTRUSIVE_SET_HPP