1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
13 #ifndef BOOST_INTRUSIVE_ISET_HPP
\r
14 #define BOOST_INTRUSIVE_ISET_HPP
\r
16 #include <boost/intrusive/detail/config_begin.hpp>
\r
17 #include <boost/intrusive/detail/irbtree.hpp>
\r
21 namespace intrusive {
\r
23 //! The class template iset is an intrusive container, that mimics most of
\r
24 //! the interface of std::set as described in the C++ standard.
\r
26 //! The template parameter ValueTraits is called "value traits". It stores
\r
27 //! information and operations about the type to be stored in the container.
\r
29 //! The template parameter Compare, provides a function object that can compare two
\r
30 //! element values as sort keys to determine their relative order in the set.
\r
32 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType
\r
33 //! will be embedded in the class, that will keep track of the number of stored objects.
\r
34 //! This will allow constant-time O(1) size() member, instead of default O(N) size.
\r
35 template < class ValueTraits
\r
36 , class Compare = std::less<typename ValueTraits::value_type>
\r
37 , bool ConstantTimeSize = true
\r
38 , class SizeType = std::size_t>
\r
41 typedef detail::irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType> tree_type;
\r
49 iset &operator =(const iset&);
\r
51 typedef tree_type implementation_defined;
\r
54 typedef typename ValueTraits::value_type value_type;
\r
55 typedef typename ValueTraits::pointer pointer;
\r
56 typedef typename ValueTraits::const_pointer const_pointer;
\r
57 typedef value_type& reference;
\r
58 typedef const value_type& const_reference;
\r
59 typedef SizeType size_type;
\r
60 typedef typename std::iterator_traits
\r
61 <pointer>::difference_type difference_type;
\r
62 typedef value_type key_type;
\r
63 typedef Compare value_compare;
\r
64 typedef value_compare key_compare;
\r
65 typedef typename implementation_defined::iterator iterator;
\r
66 typedef typename implementation_defined::const_iterator const_iterator;
\r
67 typedef typename implementation_defined::reverse_iterator reverse_iterator;
\r
68 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
\r
69 typedef typename implementation_defined::insert_commit_data insert_commit_data;
\r
74 template <class V1, class P1, bool C1, class S1>
\r
75 friend bool operator==(const iset<V1, P1, C1, S1>& x, const iset<V1, P1, C1, S1>& y);
\r
77 template <class V1, class P1, bool C1, class S1>
\r
78 friend bool operator<(const iset<V1, P1, C1, S1>& x, const iset<V1, P1, C1, S1>& y);
\r
82 //! <b>Effects</b>: Constructs an empty set.
\r
84 //! <b>Complexity</b>: Constant.
\r
86 //! <b>Throws</b>: If value_traits::node_traits::node
\r
87 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
88 //! or the copy constructor of the Compare object throws.
\r
89 iset(const Compare &cmp = Compare())
\r
93 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
\r
94 //! cmp must be a comparison function that induces a strict weak ordering.
\r
96 //! <b>Effects</b>: Constructs an empty set and inserts elements from
\r
99 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
\r
100 //! comp and otherwise N * log N, where N is std::distance(last, first).
\r
102 //! <b>Throws</b>: If value_traits::node_traits::node
\r
103 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
104 //! or the copy constructor/operator() of the Compare object throws.
\r
105 template<class Iterator>
\r
106 iset(Iterator b, Iterator e, const Compare &cmp = Compare())
\r
107 : tree_(true, b, e, cmp)
\r
110 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
\r
111 //! are not deleted (i.e. no destructors are called).
\r
113 //! <b>Complexity</b>: O(log(size()) + size()) if it's a safe-mode or auto-unlink
\r
114 //! value. Otherwise constant.
\r
116 //! <b>Throws</b>: Nothing.
\r
120 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the set.
\r
122 //! <b>Complexity</b>: Constant.
\r
124 //! <b>Throws</b>: Nothing.
\r
126 { return tree_.begin(); }
\r
128 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the set.
\r
130 //! <b>Complexity</b>: Constant.
\r
132 //! <b>Throws</b>: Nothing.
\r
133 const_iterator begin() const
\r
134 { return tree_.begin(); }
\r
136 //! <b>Effects</b>: Returns an iterator pointing to the end of the set.
\r
138 //! <b>Complexity</b>: Constant.
\r
140 //! <b>Throws</b>: Nothing.
\r
142 { return tree_.end(); }
\r
144 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the set.
\r
146 //! <b>Complexity</b>: Constant.
\r
148 //! <b>Throws</b>: Nothing.
\r
149 const_iterator end() const
\r
150 { return tree_.end(); }
\r
152 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
\r
155 //! <b>Complexity</b>: Constant.
\r
157 //! <b>Throws</b>: Nothing.
\r
158 reverse_iterator rbegin()
\r
159 { return tree_.rbegin(); }
\r
161 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
\r
162 //! of the reversed set.
\r
164 //! <b>Complexity</b>: Constant.
\r
166 //! <b>Throws</b>: Nothing.
\r
167 const_reverse_iterator rbegin() const
\r
168 { return tree_.rbegin(); }
\r
170 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
\r
171 //! of the reversed set.
\r
173 //! <b>Complexity</b>: Constant.
\r
175 //! <b>Throws</b>: Nothing.
\r
176 reverse_iterator rend()
\r
177 { return tree_.rend(); }
\r
179 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
\r
180 //! of the reversed set.
\r
182 //! <b>Complexity</b>: Constant.
\r
184 //! <b>Throws</b>: Nothing.
\r
185 const_reverse_iterator rend() const
\r
186 { return tree_.rend(); }
\r
188 //! <b>Effects</b>: Returns the key_compare object used by the set.
\r
190 //! <b>Complexity</b>: Constant.
\r
192 //! <b>Throws</b>: If key_compare copy-constructor throws.
\r
193 key_compare key_comp() const
\r
194 { return tree_.value_comp(); }
\r
196 //! <b>Effects</b>: Returns the value_compare object used by the set.
\r
198 //! <b>Complexity</b>: Constant.
\r
200 //! <b>Throws</b>: If value_compare copy-constructor throws.
\r
201 value_compare value_comp() const
\r
202 { return tree_.value_comp(); }
\r
204 //! <b>Effects</b>: Returns true is the container is empty.
\r
206 //! <b>Complexity</b>: Constant.
\r
208 //! <b>Throws</b>: Nothing.
\r
210 { return tree_.empty(); }
\r
212 //! <b>Effects</b>: Returns the number of elements stored in the set.
\r
214 //! <b>Complexity</b>: Linear to elements contained in *this if,
\r
215 //! ConstantTimeSize is false. Constant-time otherwise.
\r
217 //! <b>Throws</b>: Nothing.
\r
218 size_type size() const
\r
219 { return tree_.size(); }
\r
221 //! <b>Effects</b>: Swaps the contents of two sets.
\r
223 //! <b>Complexity</b>: Constant.
\r
225 //! <b>Throws</b>: If the swap() call for the comparison functor
\r
226 //! found using ADL throws. Strong guarantee.
\r
227 void swap(iset& other)
\r
228 { tree_.swap(other.tree_); }
\r
230 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
232 //! <b>Effects</b>: Erases all the elements from *this
\r
233 //! calling Destroyer::operator()(pointer), clones all the
\r
234 //! elements from src calling Cloner::operator()(const value_type &)
\r
235 //! and inserts them on *this.
\r
237 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
238 //! calling Destroyer::operator()(pointer).
\r
240 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
242 //! <b>Throws</b>: If cloner throws.
\r
243 template <class Cloner, class Destroyer>
\r
244 void clone_from(const iset &src, Cloner cloner, Destroyer destroyer)
\r
245 { tree_.clone_from(src.tree_, cloner, destroyer); }
\r
247 //! <b>Requires</b>: value must be an lvalue
\r
249 //! <b>Effects</b>: Tries to inserts value into the set.
\r
251 //! <b>Returns</b>: If the value
\r
252 //! is not already present inserts it and returns a pair containing the
\r
253 //! iterator to the new value and true. If the value is already present
\r
254 //! returns a pair containing an iterator to the already present value
\r
257 //! <b>Complexity</b>: Average complexity for insert element is at
\r
258 //! most logarithmic.
\r
260 //! <b>Throws</b>: If the internal Compare ordering function throws. Strong guarantee.
\r
262 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
263 //! No copy-constructors are called.
\r
264 std::pair<iterator, bool> insert(value_type &value)
\r
265 { return tree_.insert_unique(value); }
\r
267 //! <b>Requires</b>: value must be an lvalue
\r
269 //! <b>Effects</b>: Tries to to insert x into the set, using "hint"
\r
270 //! as a hint to where it will be inserted.
\r
272 //! <b>Returns</b>: An iterator that points to the position where the
\r
273 //! new element was inserted into the set.
\r
275 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
\r
276 //! constant time if t is inserted immediately before hint.
\r
278 //! <b>Throws</b>: If the internal Compare ordering function throws. Strong guarantee.
\r
280 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
281 //! No copy-constructors are called.
\r
282 iterator insert(const_iterator hint, value_type &value)
\r
283 { return tree_.insert_unique(hint, value); }
\r
285 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
\r
286 //! the same strict weak ordering as value_compare. The difference is that
\r
287 //! key_value_comp compares an arbitrary key with the contained values.
\r
289 //! <b>Effects</b>: Checks if a value can be inserted in the set, using
\r
290 //! a user provided key instead of the value itself.
\r
292 //! <b>Returns</b>: If an equivalent value is already present
\r
293 //! returns a pair containing an iterator to the already present value
\r
294 //! and false. If the value can be inserted returns true in the returned
\r
295 //! pair boolean and fills "commit_data" that is meant to be used with
\r
296 //! the "insert_commit" function.
\r
298 //! <b>Complexity</b>: Average complexity is at most logarithmic.
\r
300 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
\r
302 //! <b>Notes</b>: This function is used to improve performance when constructing
\r
303 //! a value_type is expensive: if an equivalent value is already present
\r
304 //! the constructed object must be discarded. Many times, the part of the
\r
305 //! node that is used to impose the order is much cheaper to construct
\r
306 //! than the value_type and this function offers the possibility to use that
\r
307 //! part to check if the insertion will be successful.
\r
309 //! If the check is successful, the user can construct the value_type and use
\r
310 //! "insert_commit" to insert the object in constant-time. This gives a total
\r
311 //! logarithmic complexity to the insertion: check(O(log(N)) + commit(O(1)).
\r
313 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
\r
314 //! objects are inserted or erased from the set.
\r
315 template<class KeyType, class KeyValueCompare>
\r
316 std::pair<iterator, bool> insert_check
\r
317 (const KeyType &key, KeyValueCompare key_value_comp, insert_commit_data &commit_data)
\r
318 { return tree_.insert_unique_check(key, key_value_comp, commit_data); }
\r
320 //! <b>Requires</b>: key_value_comp must be a comparison function that induces
\r
321 //! the same strict weak ordering as value_compare. The difference is that
\r
322 //! key_value_comp compares an arbitrary key with the contained values.
\r
324 //! <b>Effects</b>: Checks if a value can be inserted in the set, using
\r
325 //! a user provided key instead of the value itself, using "hint"
\r
326 //! as a hint to where it will be inserted.
\r
328 //! <b>Returns</b>: If an equivalent value is already present
\r
329 //! returns a pair containing an iterator to the already present value
\r
330 //! and false. If the value can be inserted returns true in the returned
\r
331 //! pair boolean and fills "commit_data" that is meant to be used with
\r
332 //! the "insert_commit" function.
\r
334 //! <b>Complexity</b>: Logarithmic in general, but it's amortized
\r
335 //! constant time if t is inserted immediately before hint.
\r
337 //! <b>Throws</b>: If the key_value_comp ordering function throws. Strong guarantee.
\r
339 //! <b>Notes</b>: This function is used to improve performance when constructing
\r
340 //! a value_type is expensive: if the equivalent is already present
\r
341 //! the constructed object must be discarded. Many times, the part of the
\r
342 //! constructing that is used to impose the order is much cheaper to construct
\r
343 //! than the value_type and this function offers the possibility to use that key
\r
344 //! to check if the insertion will be successful.
\r
346 //! If the check is successful, the user can construct the value_type and use
\r
347 //! "insert_commit" to insert the object in constant-time. This can give a total
\r
348 //! constant-time complexity to the insertion: check(O(1)) + commit(O(1)).
\r
350 //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
\r
351 //! objects are inserted or erased from the set.
\r
352 template<class KeyType, class KeyValueCompare>
\r
353 std::pair<iterator, bool> insert_check
\r
354 (const_iterator hint, const KeyType &key
\r
355 ,KeyValueCompare key_value_comp, insert_commit_data &commit_data)
\r
356 { return tree_.insert_unique_check(hint, key, key_value_comp, commit_data); }
\r
358 //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
\r
359 //! must have been obtained from a previous call to "insert_check".
\r
360 //! No objects should have been inserted or erased from the set between
\r
361 //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
\r
363 //! <b>Effects</b>: Inserts the value in the set using the information obtained
\r
364 //! from the "commit_data" that a previous "insert_check" filled.
\r
366 //! <b>Returns</b>: An iterator to the newly inserted object.
\r
368 //! <b>Complexity</b>: Constant time.
\r
370 //! <b>Throws</b>: Nothing.
\r
372 //! <b>Notes</b>: This function has only sense if a "insert_check" has been
\r
373 //! previously executed to fill "commit_data". No value should be inserted or
\r
374 //! erased between the "insert_check" and "insert_commit" calls.
\r
375 iterator insert_commit(value_type &value, const insert_commit_data &commit_data)
\r
376 { return tree_.insert_unique_commit(value, commit_data); }
\r
378 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
379 //! of type value_type.
\r
381 //! <b>Effects</b>: Inserts a range into the set.
\r
383 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
\r
384 //! size of the range. However, it is linear in N if the range is already sorted
\r
385 //! by value_comp().
\r
387 //! <b>Throws</b>: If the internal Compare ordering function throws. Basic guarantee.
\r
389 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
390 //! No copy-constructors are called.
\r
391 template<class Iterator>
\r
392 void insert(Iterator b, Iterator e)
\r
393 { tree_.insert_unique(b, e); }
\r
395 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
397 //! <b>Complexity</b>: Average complexity is constant time.
\r
399 //! <b>Returns</b>: An iterator to the element after the erased element.
\r
401 //! <b>Throws</b>: Nothing.
\r
403 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
404 //! to the erased elements. No destructors are called.
\r
405 iterator erase(iterator i)
\r
406 { return tree_.erase(i); }
\r
408 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
410 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
411 //! O(log(size() + N)), where N is the number of elements in the range.
\r
413 //! <b>Returns</b>: An iterator to the element after the erased elements.
\r
415 //! <b>Throws</b>: Nothing.
\r
417 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
418 //! to the erased elements. No destructors are called.
\r
419 iterator erase(iterator b, iterator e)
\r
420 { return tree_.erase(b, e); }
\r
422 //! <b>Effects</b>: Erases all the elements with the given value.
\r
424 //! <b>Returns</b>: The number of erased elements.
\r
426 //! <b>Complexity</b>: O(log(size()) + this->count(value)).
\r
428 //! <b>Throws</b>: If the internal Compare ordering function throws. Basic guarantee.
\r
430 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
431 //! to the erased elements. No destructors are called.
\r
432 size_type erase(const value_type &value)
\r
433 { return tree_.erase(value); }
\r
435 //! <b>Effects</b>: Erases all the elements that compare equal with
\r
436 //! the given key and the given comparison functor.
\r
438 //! <b>Returns</b>: The number of erased elements.
\r
440 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
\r
442 //! <b>Throws</b>: If the comp ordering function throws. Basic guarantee.
\r
444 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
445 //! to the erased elements. No destructors are called.
\r
446 template<class KeyType, class KeyValueCompare>
\r
447 size_type erase(const KeyType& key, KeyValueCompare comp)
\r
448 { return tree_.erase(key, comp); }
\r
450 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
452 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
453 //! Destroyer::operator()(pointer) is called for the removed element.
\r
455 //! <b>Complexity</b>: Average complexity for erase element is constant time.
\r
457 //! <b>Returns</b>: An iterator to the element after the erased element.
\r
459 //! <b>Throws</b>: Nothing.
\r
461 //! <b>Note</b>: Invalidates the iterators
\r
462 //! to the erased elements.
\r
463 template<class Destroyer>
\r
464 iterator erase_and_destroy(iterator i, Destroyer destroyer)
\r
465 { return tree_.erase_and_destroy(i, destroyer); }
\r
467 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
469 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
470 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
472 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
473 //! O(log(size() + N)), where N is the number of elements in the range.
\r
475 //! <b>Returns</b>: An iterator to the element after the erased elements.
\r
477 //! <b>Throws</b>: Nothing.
\r
479 //! <b>Note</b>: Invalidates the iterators
\r
480 //! to the erased elements.
\r
481 template<class Destroyer>
\r
482 iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)
\r
483 { return tree_.erase_and_destroy(b, e, destroyer); }
\r
485 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
487 //! <b>Effects</b>: Erases all the elements with the given value.
\r
488 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
490 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
492 //! <b>Complexity</b>: O(log(size() + this->count(value)). Basic guarantee.
\r
494 //! <b>Throws</b>: Nothing.
\r
496 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
497 //! to the erased elements. No destructors are called.
\r
498 template<class Destroyer>
\r
499 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
500 { return tree_.erase_and_destroy(value, destroyer); }
\r
502 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
504 //! <b>Effects</b>: Erases all the elements with the given key.
\r
505 //! according to the comparison functor "comp".
\r
506 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
508 //! <b>Returns</b>: The number of erased elements.
\r
510 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
\r
512 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
\r
514 //! <b>Note</b>: Invalidates the iterators
\r
515 //! to the erased elements.
\r
516 template<class KeyType, class KeyValueCompare, class Destroyer>
\r
517 size_type erase_and_destroy(const KeyType& key, KeyValueCompare comp, Destroyer destroyer)
\r
518 { return tree_.erase_and_destroy(key, comp, destroyer); }
\r
520 //! <b>Effects</b>: Erases all the elements of the container.
\r
522 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
523 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
525 //! <b>Throws</b>: Nothing.
\r
527 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
528 //! to the erased elements. No destructors are called.
\r
530 { return tree_.clear(); }
\r
532 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
534 //! <b>Effects</b>: Erases all the elements of the container.
\r
536 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
537 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
539 //! <b>Throws</b>: Nothing.
\r
541 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
542 //! to the erased elements. No destructors are called.
\r
543 template<class Destroyer>
\r
544 void clear_and_destroy(Destroyer destroyer)
\r
545 { return tree_.clear_and_destroy(destroyer); }
\r
547 //! <b>Effects</b>: Returns the number of contained elements with the given key
\r
549 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
\r
550 //! to number of objects with the given key.
\r
552 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
553 size_type count(const value_type &value) const
\r
554 { return tree_.find(value) != end(); }
\r
556 //! <b>Effects</b>: Returns the number of contained elements with the same key
\r
557 //! compared with the given comparison functor.
\r
559 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
\r
560 //! to number of objects with the given key.
\r
562 //! <b>Throws</b>: If comp ordering function throws.
\r
563 template<class KeyType, class KeyValueCompare>
\r
564 size_type count(const KeyType& key, KeyValueCompare comp) const
\r
565 { return tree_.find(key, comp) != end(); }
\r
567 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
568 //! key is not less than k or end() if that element does not exist.
\r
570 //! <b>Complexity</b>: Logarithmic.
\r
572 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
573 iterator lower_bound(const value_type &value)
\r
574 { return tree_.lower_bound(value); }
\r
576 //! <b>Requires</b>: comp must imply the same element order as
\r
577 //! value_compare. Usually key is the part of the value_type
\r
578 //! that is used in the ordering functor.
\r
580 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
581 //! key according to the comparison functor is not less than k or
\r
582 //! end() if that element does not exist.
\r
584 //! <b>Complexity</b>: Logarithmic.
\r
586 //! <b>Throws</b>: If comp ordering function throws.
\r
588 //! <b>Note</b>: This function is used when constructing a value_type
\r
589 //! is expensive and the value_type can be compared with a cheaper
\r
590 //! key type. Usually this key is part of the value_type.
\r
591 template<class KeyType, class KeyValueCompare>
\r
592 iterator lower_bound(const KeyType& key, KeyValueCompare comp)
\r
593 { return tree_.lower_bound(key, comp); }
\r
595 //! <b>Effects</b>: Returns a const iterator to the first element whose
\r
596 //! key is not less than k or end() if that element does not exist.
\r
598 //! <b>Complexity</b>: Logarithmic.
\r
600 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
601 const_iterator lower_bound(const value_type &value) const
\r
602 { return tree_.lower_bound(value); }
\r
604 //! <b>Requires</b>: comp must imply the same element order as
\r
605 //! value_compare. Usually key is the part of the value_type
\r
606 //! that is used in the ordering functor.
\r
608 //! <b>Effects</b>: Returns a const_iterator to the first element whose
\r
609 //! key according to the comparison functor is not less than k or
\r
610 //! end() if that element does not exist.
\r
612 //! <b>Complexity</b>: Logarithmic.
\r
614 //! <b>Throws</b>: If comp ordering function throws.
\r
616 //! <b>Note</b>: This function is used when constructing a value_type
\r
617 //! is expensive and the value_type can be compared with a cheaper
\r
618 //! key type. Usually this key is part of the value_type.
\r
619 template<class KeyType, class KeyValueCompare>
\r
620 const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
\r
621 { return tree_.lower_bound(key, comp); }
\r
623 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
624 //! key is greater than k or end() if that element does not exist.
\r
626 //! <b>Complexity</b>: Logarithmic.
\r
628 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
629 iterator upper_bound(const value_type &value)
\r
630 { return tree_.upper_bound(value); }
\r
632 //! <b>Requires</b>: comp must imply the same element order as
\r
633 //! value_compare. Usually key is the part of the value_type
\r
634 //! that is used in the ordering functor.
\r
636 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
637 //! key according to the comparison functor is greater than key or
\r
638 //! end() if that element does not exist.
\r
640 //! <b>Complexity</b>: Logarithmic.
\r
642 //! <b>Throws</b>: If comp ordering function throws.
\r
644 //! <b>Note</b>: This function is used when constructing a value_type
\r
645 //! is expensive and the value_type can be compared with a cheaper
\r
646 //! key type. Usually this key is part of the value_type.
\r
647 template<class KeyType, class KeyValueCompare>
\r
648 iterator upper_bound(const KeyType& key, KeyValueCompare comp)
\r
649 { return tree_.upper_bound(key, comp); }
\r
651 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
652 //! key is greater than k or end() if that element does not exist.
\r
654 //! <b>Complexity</b>: Logarithmic.
\r
656 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
657 const_iterator upper_bound(const value_type &value) const
\r
658 { return tree_.upper_bound(value); }
\r
660 //! <b>Requires</b>: comp must imply the same element order as
\r
661 //! value_compare. Usually key is the part of the value_type
\r
662 //! that is used in the ordering functor.
\r
664 //! <b>Effects</b>: Returns a const_iterator to the first element whose
\r
665 //! key according to the comparison functor is greater than key or
\r
666 //! end() if that element does not exist.
\r
668 //! <b>Complexity</b>: Logarithmic.
\r
670 //! <b>Throws</b>: If comp ordering function throws.
\r
672 //! <b>Note</b>: This function is used when constructing a value_type
\r
673 //! is expensive and the value_type can be compared with a cheaper
\r
674 //! key type. Usually this key is part of the value_type.
\r
675 template<class KeyType, class KeyValueCompare>
\r
676 const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
\r
677 { return tree_.upper_bound(key, comp); }
\r
679 //! <b>Effects</b>: Finds an iterator to the first element whose value is
\r
680 //! "value" or end() if that element does not exist.
\r
682 //! <b>Complexity</b>: Logarithmic.
\r
684 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
685 iterator find(const value_type &value)
\r
686 { return tree_.find(value); }
\r
688 //! <b>Requires</b>: comp must imply the same element order as
\r
689 //! value_compare. Usually key is the part of the value_type
\r
690 //! that is used in the ordering functor.
\r
692 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
693 //! "key" according to the comparison functor or end() if that element
\r
694 //! does not exist.
\r
696 //! <b>Complexity</b>: Logarithmic.
\r
698 //! <b>Throws</b>: If comp ordering function throws.
\r
700 //! <b>Note</b>: This function is used when constructing a value_type
\r
701 //! is expensive and the value_type can be compared with a cheaper
\r
702 //! key type. Usually this key is part of the value_type.
\r
703 template<class KeyType, class KeyValueCompare>
\r
704 iterator find(const KeyType& key, KeyValueCompare comp)
\r
705 { return tree_.find(key, comp); }
\r
707 //! <b>Effects</b>: Finds a const_iterator to the first element whose value is
\r
708 //! "value" or end() if that element does not exist.
\r
710 //! <b>Complexity</b>: Logarithmic.
\r
712 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
713 const_iterator find(const value_type &value) const
\r
714 { return tree_.find(value); }
\r
716 //! <b>Requires</b>: comp must imply the same element order as
\r
717 //! value_compare. Usually key is the part of the value_type
\r
718 //! that is used in the ordering functor.
\r
720 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
721 //! "key" according to the comparison functor or end() if that element
\r
722 //! does not exist.
\r
724 //! <b>Complexity</b>: Logarithmic.
\r
726 //! <b>Throws</b>: If comp ordering function throws.
\r
728 //! <b>Note</b>: This function is used when constructing a value_type
\r
729 //! is expensive and the value_type can be compared with a cheaper
\r
730 //! key type. Usually this key is part of the value_type.
\r
731 template<class KeyType, class KeyValueCompare>
\r
732 const_iterator find(const KeyType& key, KeyValueCompare comp) const
\r
733 { return tree_.find(key, comp); }
\r
735 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
736 //! an empty range that indicates the position where those elements would be
\r
737 //! if they there is no elements with key k.
\r
739 //! <b>Complexity</b>: Logarithmic.
\r
741 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
742 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
743 { return tree_.equal_range(value); }
\r
745 //! <b>Requires</b>: comp must imply the same element order as
\r
746 //! value_compare. Usually key is the part of the value_type
\r
747 //! that is used in the ordering functor.
\r
749 //! <b>Effects</b>: Finds a range containing all elements whose key is k
\r
750 //! according to the comparison functor or an empty range
\r
751 //! that indicates the position where those elements would be
\r
752 //! if they there is no elements with key k.
\r
754 //! <b>Complexity</b>: Logarithmic.
\r
756 //! <b>Throws</b>: If comp ordering function throws.
\r
758 //! <b>Note</b>: This function is used when constructing a value_type
\r
759 //! is expensive and the value_type can be compared with a cheaper
\r
760 //! key type. Usually this key is part of the value_type.
\r
761 template<class KeyType, class KeyValueCompare>
\r
762 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
\r
763 { return tree_.equal_range(key, comp); }
\r
765 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
766 //! an empty range that indicates the position where those elements would be
\r
767 //! if they there is no elements with key k.
\r
769 //! <b>Complexity</b>: Logarithmic.
\r
771 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
772 std::pair<const_iterator, const_iterator>
\r
773 equal_range(const value_type &value) const
\r
774 { return tree_.equal_range(value); }
\r
776 //! <b>Requires</b>: comp must imply the same element order as
\r
777 //! value_compare. Usually key is the part of the value_type
\r
778 //! that is used in the ordering functor.
\r
780 //! <b>Effects</b>: Finds a range containing all elements whose key is k
\r
781 //! according to the comparison functor or an empty range
\r
782 //! that indicates the position where those elements would be
\r
783 //! if they there is no elements with key k.
\r
785 //! <b>Complexity</b>: Logarithmic.
\r
787 //! <b>Throws</b>: If comp ordering function throws.
\r
789 //! <b>Note</b>: This function is used when constructing a value_type
\r
790 //! is expensive and the value_type can be compared with a cheaper
\r
791 //! key type. Usually this key is part of the value_type.
\r
792 template<class KeyType, class KeyValueCompare>
\r
793 std::pair<const_iterator, const_iterator>
\r
794 equal_range(const KeyType& key, KeyValueCompare comp) const
\r
795 { return tree_.equal_range(key, comp); }
\r
797 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
798 //! appropriate type. Otherwise the behavior is undefined.
\r
800 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
\r
801 //! that points to the value
\r
803 //! <b>Complexity</b>: Constant.
\r
805 //! <b>Throws</b>: Nothing.
\r
806 static iterator current(value_type &value)
\r
807 { return tree_type::current(value); }
\r
809 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
810 //! appropriate type. Otherwise the behavior is undefined.
\r
812 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
\r
813 //! set that points to the value
\r
815 //! <b>Complexity</b>: Constant.
\r
817 //! <b>Throws</b>: Nothing.
\r
818 static const_iterator current(const value_type &value)
\r
819 { return tree_type::current(value); }
\r
821 friend bool operator==(const iset &x, const iset &y)
\r
822 { return x.tree_ == y.tree_; }
\r
824 friend bool operator<(const iset &x, const iset &y)
\r
825 { return x.tree_ < y.tree_; }
\r
828 template <class V, class P, bool C, class S>
\r
829 inline bool operator!=(const iset<V, P, C, S>& x, const iset<V, P, C, S>& y)
\r
830 { return !(x==y); }
\r
832 template <class V, class P, bool C, class S>
\r
833 inline bool operator>(const iset<V, P, C, S>& x, const iset<V, P, C, S>& y)
\r
836 template <class V, class P, bool C, class S>
\r
837 inline bool operator<=(const iset<V, P, C, S>& x, const iset<V, P, C, S>& y)
\r
838 { return !(y > x); }
\r
840 template <class V, class P, bool C, class S>
\r
841 inline bool operator>=(const iset<V, P, C, S>& x, const iset<V, P, C, S>& y)
\r
842 { return !(x < y); }
\r
844 template <class V, class P, bool C, class S>
\r
845 inline void swap(iset<V, P, C, S>& x, iset<V, P, C, S>& y)
\r
848 //! The class template imultiset is an intrusive container, that mimics most of
\r
849 //! the interface of std::multiset as described in the C++ standard.
\r
851 //! The template parameter ValueTraits is called "value traits". It stores
\r
852 //! information and operations about the type to be stored
\r
853 //! in ilist and what type of hook has been chosen to include it in the list.
\r
854 //! The value_traits class is supplied by the appropriate hook as a template subtype
\r
855 //! called "value_traits".
\r
857 //! The template parameter Compare, provides a function object that can compare two
\r
858 //! element values as sort keys to determine their relative order in the set.
\r
860 //! If the user specifies ConstantTimeSize as "true", a member of type SizeType
\r
861 //! will be embedded in the class, that will keep track of the number of stored objects.
\r
862 //! This will allow constant-time O(1) size() member, instead of default O(N) size.
\r
863 template < class ValueTraits
\r
864 , class Compare = std::less<typename ValueTraits::value_type>
\r
865 , bool ConstantTimeSize = true
\r
866 , class SizeType = std::size_t>
\r
869 typedef detail::irbtree<ValueTraits, Compare, ConstantTimeSize, SizeType> tree_type;
\r
873 imultiset (const imultiset&);
\r
877 imultiset &operator =(const imultiset&);
\r
879 typedef tree_type implementation_defined;
\r
882 typedef typename ValueTraits::value_type value_type;
\r
883 typedef typename ValueTraits::pointer pointer;
\r
884 typedef typename ValueTraits::const_pointer const_pointer;
\r
885 typedef value_type& reference;
\r
886 typedef const value_type& const_reference;
\r
887 typedef SizeType size_type;
\r
888 typedef typename std::iterator_traits
\r
889 <pointer>::difference_type difference_type;
\r
890 typedef value_type key_type;
\r
891 typedef Compare value_compare;
\r
892 typedef value_compare key_compare;
\r
893 typedef typename implementation_defined::iterator iterator;
\r
894 typedef typename implementation_defined::const_iterator const_iterator;
\r
895 typedef typename implementation_defined::reverse_iterator reverse_iterator;
\r
896 typedef typename implementation_defined::const_reverse_iterator const_reverse_iterator;
\r
897 typedef typename implementation_defined::insert_commit_data insert_commit_data;
\r
903 //! <b>Effects</b>: Constructs an empty multiset.
\r
905 //! <b>Complexity</b>: Constant.
\r
907 //! <b>Throws</b>: If value_traits::node_traits::node
\r
908 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
909 //! or the copy constructor/operator() of the Compare object throws.
\r
910 imultiset(const Compare &cmp = Compare())
\r
914 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type.
\r
915 //! cmp must be a comparison function that induces a strict weak ordering.
\r
917 //! <b>Effects</b>: Constructs an empty multiset and inserts elements from
\r
920 //! <b>Complexity</b>: Linear in N if [b, e) is already sorted using
\r
921 //! comp and otherwise N * log N, where N is last Ā first.
\r
923 //! <b>Throws</b>: If value_traits::node_traits::node
\r
924 //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
\r
925 //! or the copy constructor/operator() of the Compare object throws.
\r
926 template<class Iterator>
\r
927 imultiset(Iterator b, Iterator e, const Compare &cmp = Compare())
\r
928 : tree_(false, b, e, cmp)
\r
931 //! <b>Effects</b>: Detaches all elements from this. The objects in the set
\r
932 //! are not deleted (i.e. no destructors are called).
\r
934 //! <b>Complexity</b>: O(log(size()) + size()) if it's a safe-mode or
\r
935 //! auto-unlink value. Otherwise constant.
\r
937 //! <b>Throws</b>: Nothing.
\r
941 //! <b>Effects</b>: Returns an iterator pointing to the beginning of the multiset.
\r
943 //! <b>Complexity</b>: Constant.
\r
945 //! <b>Throws</b>: Nothing.
\r
947 { return tree_.begin(); }
\r
949 //! <b>Effects</b>: Returns a const_iterator pointing to the beginning of the multiset.
\r
951 //! <b>Complexity</b>: Constant.
\r
953 //! <b>Throws</b>: Nothing.
\r
954 const_iterator begin() const
\r
955 { return tree_.begin(); }
\r
957 //! <b>Effects</b>: Returns an iterator pointing to the end of the multiset.
\r
959 //! <b>Complexity</b>: Constant.
\r
961 //! <b>Throws</b>: Nothing.
\r
963 { return tree_.end(); }
\r
965 //! <b>Effects</b>: Returns a const_iterator pointing to the end of the multiset.
\r
967 //! <b>Complexity</b>: Constant.
\r
969 //! <b>Throws</b>: Nothing.
\r
970 const_iterator end() const
\r
971 { return tree_.end(); }
\r
973 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning of the
\r
974 //! reversed multiset.
\r
976 //! <b>Complexity</b>: Constant.
\r
978 //! <b>Throws</b>: Nothing.
\r
979 reverse_iterator rbegin()
\r
980 { return tree_.rbegin(); }
\r
982 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
\r
983 //! of the reversed multiset.
\r
985 //! <b>Complexity</b>: Constant.
\r
987 //! <b>Throws</b>: Nothing.
\r
988 const_reverse_iterator rbegin() const
\r
989 { return tree_.rbegin(); }
\r
991 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
\r
992 //! of the reversed multiset.
\r
994 //! <b>Complexity</b>: Constant.
\r
996 //! <b>Throws</b>: Nothing.
\r
997 reverse_iterator rend()
\r
998 { return tree_.rend(); }
\r
1000 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
\r
1001 //! of the reversed multiset.
\r
1003 //! <b>Complexity</b>: Constant.
\r
1005 //! <b>Throws</b>: Nothing.
\r
1006 const_reverse_iterator rend() const
\r
1007 { return tree_.rend(); }
\r
1009 //! <b>Effects</b>: Returns the key_compare object used by the multiset.
\r
1011 //! <b>Complexity</b>: Constant.
\r
1013 //! <b>Throws</b>: If key_compare copy-constructor throws.
\r
1014 key_compare key_comp() const
\r
1015 { return tree_.value_comp(); }
\r
1017 //! <b>Effects</b>: Returns the value_compare object used by the multiset.
\r
1019 //! <b>Complexity</b>: Constant.
\r
1021 //! <b>Throws</b>: If value_compare copy-constructor throws.
\r
1022 value_compare value_comp() const
\r
1023 { return tree_.value_comp(); }
\r
1025 //! <b>Effects</b>: Returns true is the container is empty.
\r
1027 //! <b>Complexity</b>: Constant.
\r
1029 //! <b>Throws</b>: Nothing.
\r
1030 bool empty() const
\r
1031 { return tree_.empty(); }
\r
1033 //! <b>Effects</b>: Returns the number of elements stored in the multiset.
\r
1035 //! <b>Complexity</b>: Linear to elements contained in *this if,
\r
1036 //! ConstantTimeSize is false. Constant-time otherwise.
\r
1038 //! <b>Throws</b>: Nothing.
\r
1039 size_type size() const
\r
1040 { return tree_.size(); }
\r
1042 //! <b>Effects</b>: Swaps the contents of two multisets.
\r
1044 //! <b>Complexity</b>: Constant.
\r
1046 //! <b>Throws</b>: If the swap() call for the comparison functor
\r
1047 //! found using ADL throws. Strong guarantee.
\r
1048 void swap(imultiset& other)
\r
1049 { tree_.swap(other.tree_); }
\r
1051 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1053 //! <b>Effects</b>: Erases all the elements from *this
\r
1054 //! calling Destroyer::operator()(pointer), clones all the
\r
1055 //! elements from src calling Cloner::operator()(const value_type &)
\r
1056 //! and inserts them on *this.
\r
1058 //! If cloner throws, all cloned elements are unlinked and destroyed
\r
1059 //! calling Destroyer::operator()(pointer).
\r
1061 //! <b>Complexity</b>: Linear to erased plus inserted elements.
\r
1063 //! <b>Throws</b>: If cloner throws. Basic guarantee.
\r
1064 template <class Cloner, class Destroyer>
\r
1065 void clone_from(const imultiset &src, Cloner cloner, Destroyer destroyer)
\r
1066 { tree_.clone_from(src.tree_, cloner, destroyer); }
\r
1068 //! <b>Requires</b>: value must be an lvalue
\r
1070 //! <b>Effects</b>: Inserts value into the multiset.
\r
1072 //! <b>Returns</b>: An iterator that points to the position where the new
\r
1073 //! element was inserted.
\r
1075 //! <b>Complexity</b>: Average complexity for insert element is at
\r
1076 //! most logarithmic.
\r
1078 //! <b>Throws</b>: If the internal Compare ordering function throws. Strong guarantee.
\r
1080 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
1081 //! No copy-constructors are called.
\r
1082 iterator insert(value_type &value)
\r
1083 { return tree_.insert_equal_upper_bound(value); }
\r
1085 //! <b>Requires</b>: value must be an lvalue
\r
1087 //! <b>Effects</b>: Inserts x into the multiset, using pos as a hint to
\r
1088 //! where it will be inserted.
\r
1090 //! <b>Returns</b>: An iterator that points to the position where the new
\r
1091 //! element was inserted.
\r
1093 //! <b>Complexity</b>: Logarithmic in general, but it is amortized
\r
1094 //! constant time if t is inserted immediately before hint.
\r
1096 //! <b>Throws</b>: If the internal Compare ordering function throws. Strong guarantee.
\r
1098 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
1099 //! No copy-constructors are called.
\r
1100 iterator insert(const_iterator hint, value_type &value)
\r
1101 { return tree_.insert_equal(hint, value); }
\r
1103 //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
\r
1104 //! of type value_type.
\r
1106 //! <b>Effects</b>: Inserts a range into the multiset.
\r
1108 //! <b>Returns</b>: An iterator that points to the position where the new
\r
1109 //! element was inserted.
\r
1111 //! <b>Complexity</b>: Insert range is in general O(N * log(N)), where N is the
\r
1112 //! size of the range. However, it is linear in N if the range is already sorted
\r
1113 //! by value_comp().
\r
1115 //! <b>Throws</b>: If the internal Compare ordering function throws. Basic guarantee.
\r
1117 //! <b>Note</b>: Does not affect the validity of iterators and references.
\r
1118 //! No copy-constructors are called.
\r
1119 template<class Iterator>
\r
1120 void insert(Iterator b, Iterator e)
\r
1121 { tree_.insert_equal(b, e); }
\r
1123 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
1125 //! <b>Complexity</b>: Average complexity is constant time.
\r
1127 //! <b>Returns</b>: An iterator to the element after the erased element.
\r
1129 //! <b>Throws</b>: Nothing.
\r
1131 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1132 //! to the erased elements. No destructors are called.
\r
1133 iterator erase(iterator i)
\r
1134 { return tree_.erase(i); }
\r
1136 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
1138 //! <b>Returns</b>: An iterator to the element after the erased elements.
\r
1140 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
1141 //! O(log(size() + N)), where N is the number of elements in the range.
\r
1143 //! <b>Throws</b>: Nothing.
\r
1145 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1146 //! to the erased elements. No destructors are called.
\r
1147 iterator erase(iterator b, iterator e)
\r
1148 { return tree_.erase(b, e); }
\r
1150 //! <b>Effects</b>: Erases all the elements with the given value.
\r
1152 //! <b>Returns</b>: The number of erased elements.
\r
1154 //! <b>Complexity</b>: O(log(size() + this->count(value)).
\r
1156 //! <b>Throws</b>: If the internal Compare ordering function throws. Basic guarantee.
\r
1158 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1159 //! to the erased elements. No destructors are called.
\r
1160 size_type erase(const value_type &value)
\r
1161 { return tree_.erase(value); }
\r
1163 //! <b>Effects</b>: Erases all the elements that compare equal with
\r
1164 //! the given key and the given comparison functor.
\r
1166 //! <b>Returns</b>: The number of erased elements.
\r
1168 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
\r
1170 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
\r
1172 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1173 //! to the erased elements. No destructors are called.
\r
1174 template<class KeyType, class KeyValueCompare>
\r
1175 size_type erase(const KeyType& key, KeyValueCompare comp)
\r
1176 { return tree_.erase(key, comp); }
\r
1178 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1180 //! <b>Returns</b>: An iterator to the element after the erased element.
\r
1182 //! <b>Effects</b>: Erases the element pointed to by pos.
\r
1183 //! Destroyer::operator()(pointer) is called for the removed element.
\r
1185 //! <b>Complexity</b>: Average complexity for erase element is constant time.
\r
1187 //! <b>Throws</b>: Nothing.
\r
1189 //! <b>Note</b>: Invalidates the iterators
\r
1190 //! to the erased elements.
\r
1191 template<class Destroyer>
\r
1192 iterator erase_and_destroy(iterator i, Destroyer destroyer)
\r
1193 { return tree_.erase_and_destroy(i, destroyer); }
\r
1195 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1197 //! <b>Returns</b>: An iterator to the element after the erased elements.
\r
1199 //! <b>Effects</b>: Erases the range pointed to by b end e.
\r
1200 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1202 //! <b>Complexity</b>: Average complexity for erase range is at most
\r
1203 //! O(log(size() + N)), where N is the number of elements in the range.
\r
1205 //! <b>Throws</b>: Nothing.
\r
1207 //! <b>Note</b>: Invalidates the iterators
\r
1208 //! to the erased elements.
\r
1209 template<class Destroyer>
\r
1210 iterator erase_and_destroy(iterator b, iterator e, Destroyer destroyer)
\r
1211 { return tree_.erase_and_destroy(b, e, destroyer); }
\r
1213 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1215 //! <b>Effects</b>: Erases all the elements with the given value.
\r
1216 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1218 //! <b>Returns</b>: The number of erased elements.
\r
1220 //! <b>Complexity</b>: O(log(size() + this->count(value)).
\r
1222 //! <b>Throws</b>: If the internal Compare ordering function throws. Basic guarantee.
\r
1224 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1225 //! to the erased elements. No destructors are called.
\r
1226 template<class Destroyer>
\r
1227 size_type erase_and_destroy(const value_type &value, Destroyer destroyer)
\r
1228 { return tree_.erase_and_destroy(value, destroyer); }
\r
1230 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1232 //! <b>Effects</b>: Erases all the elements with the given key.
\r
1233 //! according to the comparison functor "comp".
\r
1234 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1236 //! <b>Returns</b>: The number of erased elements.
\r
1238 //! <b>Complexity</b>: O(log(size() + this->count(key, comp)).
\r
1240 //! <b>Throws</b>: If comp ordering function throws. Basic guarantee.
\r
1242 //! <b>Note</b>: Invalidates the iterators
\r
1243 //! to the erased elements.
\r
1244 template<class KeyType, class KeyValueCompare, class Destroyer>
\r
1245 size_type erase_and_destroy(const KeyType& key, KeyValueCompare comp, Destroyer destroyer)
\r
1246 { return tree_.erase_and_destroy(key, comp, destroyer); }
\r
1248 //! <b>Effects</b>: Erases all the elements of the container.
\r
1250 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
1251 //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
\r
1253 //! <b>Throws</b>: Nothing.
\r
1255 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1256 //! to the erased elements. No destructors are called.
\r
1258 { return tree_.clear(); }
\r
1260 //! <b>Requires</b>: Destroyer::operator()(pointer) shouldn't throw.
\r
1262 //! <b>Effects</b>: Erases all the elements of the container.
\r
1264 //! <b>Complexity</b>: Linear to the number of elements on the container.
\r
1265 //! Destroyer::operator()(pointer) is called for the removed elements.
\r
1267 //! <b>Throws</b>: Nothing.
\r
1269 //! <b>Note</b>: Invalidates the iterators (but not the references)
\r
1270 //! to the erased elements. No destructors are called.
\r
1271 template<class Destroyer>
\r
1272 void clear_and_destroy(Destroyer destroyer)
\r
1273 { return tree_.clear_and_destroy(destroyer); }
\r
1275 //! <b>Effects</b>: Returns the number of contained elements with the same key
\r
1276 //! compared with the given comparison functor.
\r
1278 //! <b>Complexity</b>: Logarithmic to the number of elements contained plus lineal
\r
1279 //! to number of objects with the given key.
\r
1281 //! <b>Throws</b>: If comp ordering function throws.
\r
1282 template<class KeyType, class KeyValueCompare>
\r
1283 size_type count(const KeyType& key, KeyValueCompare comp) const
\r
1284 { return tree_.find(key, comp) != end(); }
\r
1286 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
1287 //! key is not less than k or end() if that element does not exist.
\r
1289 //! <b>Complexity</b>: Logarithmic.
\r
1291 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1292 iterator lower_bound(const value_type &value)
\r
1293 { return tree_.lower_bound(value); }
\r
1295 //! <b>Requires</b>: comp must imply the same element order as
\r
1296 //! value_compare. Usually key is the part of the value_type
\r
1297 //! that is used in the ordering functor.
\r
1299 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
1300 //! key according to the comparison functor is not less than k or
\r
1301 //! end() if that element does not exist.
\r
1303 //! <b>Complexity</b>: Logarithmic.
\r
1305 //! <b>Throws</b>: If comp ordering function throws.
\r
1307 //! <b>Note</b>: This function is used when constructing a value_type
\r
1308 //! is expensive and the value_type can be compared with a cheaper
\r
1309 //! key type. Usually this key is part of the value_type.
\r
1310 template<class KeyType, class KeyValueCompare>
\r
1311 iterator lower_bound(const KeyType& key, KeyValueCompare comp)
\r
1312 { return tree_.lower_bound(key, comp); }
\r
1314 //! <b>Effects</b>: Returns a const iterator to the first element whose
\r
1315 //! key is not less than k or end() if that element does not exist.
\r
1317 //! <b>Complexity</b>: Logarithmic.
\r
1319 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1320 const_iterator lower_bound(const value_type &value) const
\r
1321 { return tree_.lower_bound(value); }
\r
1323 //! <b>Requires</b>: comp must imply the same element order as
\r
1324 //! value_compare. Usually key is the part of the value_type
\r
1325 //! that is used in the ordering functor.
\r
1327 //! <b>Effects</b>: Returns a const_iterator to the first element whose
\r
1328 //! key according to the comparison functor is not less than k or
\r
1329 //! end() if that element does not exist.
\r
1331 //! <b>Complexity</b>: Logarithmic.
\r
1333 //! <b>Throws</b>: If comp ordering function throws.
\r
1335 //! <b>Note</b>: This function is used when constructing a value_type
\r
1336 //! is expensive and the value_type can be compared with a cheaper
\r
1337 //! key type. Usually this key is part of the value_type.
\r
1338 template<class KeyType, class KeyValueCompare>
\r
1339 const_iterator lower_bound(const KeyType& key, KeyValueCompare comp) const
\r
1340 { return tree_.lower_bound(key, comp); }
\r
1342 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
1343 //! key is greater than k or end() if that element does not exist.
\r
1345 //! <b>Complexity</b>: Logarithmic.
\r
1347 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1348 iterator upper_bound(const value_type &value)
\r
1349 { return tree_.upper_bound(value); }
\r
1351 //! <b>Requires</b>: comp must imply the same element order as
\r
1352 //! value_compare. Usually key is the part of the value_type
\r
1353 //! that is used in the ordering functor.
\r
1355 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
1356 //! key according to the comparison functor is greater than key or
\r
1357 //! end() if that element does not exist.
\r
1359 //! <b>Complexity</b>: Logarithmic.
\r
1361 //! <b>Throws</b>: If comp ordering function throws.
\r
1363 //! <b>Note</b>: This function is used when constructing a value_type
\r
1364 //! is expensive and the value_type can be compared with a cheaper
\r
1365 //! key type. Usually this key is part of the value_type.
\r
1366 template<class KeyType, class KeyValueCompare>
\r
1367 iterator upper_bound(const KeyType& key, KeyValueCompare comp)
\r
1368 { return tree_.upper_bound(key, comp); }
\r
1370 //! <b>Effects</b>: Returns an iterator to the first element whose
\r
1371 //! key is greater than k or end() if that element does not exist.
\r
1373 //! <b>Complexity</b>: Logarithmic.
\r
1375 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1376 const_iterator upper_bound(const value_type &value) const
\r
1377 { return tree_.upper_bound(value); }
\r
1379 //! <b>Requires</b>: comp must imply the same element order as
\r
1380 //! value_compare. Usually key is the part of the value_type
\r
1381 //! that is used in the ordering functor.
\r
1383 //! <b>Effects</b>: Returns a const_iterator to the first element whose
\r
1384 //! key according to the comparison functor is greater than key or
\r
1385 //! end() if that element does not exist.
\r
1387 //! <b>Complexity</b>: Logarithmic.
\r
1389 //! <b>Throws</b>: If comp ordering function throws.
\r
1391 //! <b>Note</b>: This function is used when constructing a value_type
\r
1392 //! is expensive and the value_type can be compared with a cheaper
\r
1393 //! key type. Usually this key is part of the value_type.
\r
1394 template<class KeyType, class KeyValueCompare>
\r
1395 const_iterator upper_bound(const KeyType& key, KeyValueCompare comp) const
\r
1396 { return tree_.upper_bound(key, comp); }
\r
1398 //! <b>Effects</b>: Finds an iterator to the first element whose value is
\r
1399 //! "value" or end() if that element does not exist.
\r
1401 //! <b>Complexity</b>: Logarithmic.
\r
1403 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1404 iterator find(const value_type &value)
\r
1405 { return tree_.find(value); }
\r
1407 //! <b>Requires</b>: comp must imply the same element order as
\r
1408 //! value_compare. Usually key is the part of the value_type
\r
1409 //! that is used in the ordering functor.
\r
1411 //! <b>Effects</b>: Finds an iterator to the first element whose key is
\r
1412 //! "key" according to the comparison functor or end() if that element
\r
1413 //! does not exist.
\r
1415 //! <b>Complexity</b>: Logarithmic.
\r
1417 //! <b>Throws</b>: If comp ordering function throws.
\r
1419 //! <b>Note</b>: This function is used when constructing a value_type
\r
1420 //! is expensive and the value_type can be compared with a cheaper
\r
1421 //! key type. Usually this key is part of the value_type.
\r
1422 template<class KeyType, class KeyValueCompare>
\r
1423 iterator find(const KeyType& key, KeyValueCompare comp)
\r
1424 { return tree_.find(key, comp); }
\r
1426 //! <b>Effects</b>: Finds a const_iterator to the first element whose value is
\r
1427 //! "value" or end() if that element does not exist.
\r
1429 //! <b>Complexity</b>: Logarithmic.
\r
1431 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1432 const_iterator find(const value_type &value) const
\r
1433 { return tree_.find(value); }
\r
1435 //! <b>Requires</b>: comp must imply the same element order as
\r
1436 //! value_compare. Usually key is the part of the value_type
\r
1437 //! that is used in the ordering functor.
\r
1439 //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
\r
1440 //! "key" according to the comparison functor or end() if that element
\r
1441 //! does not exist.
\r
1443 //! <b>Complexity</b>: Logarithmic.
\r
1445 //! <b>Throws</b>: If comp ordering function throws.
\r
1447 //! <b>Note</b>: This function is used when constructing a value_type
\r
1448 //! is expensive and the value_type can be compared with a cheaper
\r
1449 //! key type. Usually this key is part of the value_type.
\r
1450 template<class KeyType, class KeyValueCompare>
\r
1451 const_iterator find(const KeyType& key, KeyValueCompare comp) const
\r
1452 { return tree_.find(key, comp); }
\r
1454 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
1455 //! an empty range that indicates the position where those elements would be
\r
1456 //! if they there is no elements with key k.
\r
1458 //! <b>Complexity</b>: Logarithmic.
\r
1460 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1461 std::pair<iterator,iterator> equal_range(const value_type &value)
\r
1462 { return tree_.equal_range(value); }
\r
1464 //! <b>Requires</b>: comp must imply the same element order as
\r
1465 //! value_compare. Usually key is the part of the value_type
\r
1466 //! that is used in the ordering functor.
\r
1468 //! <b>Effects</b>: Finds a range containing all elements whose key is k
\r
1469 //! according to the comparison functor or an empty range
\r
1470 //! that indicates the position where those elements would be
\r
1471 //! if they there is no elements with key k.
\r
1473 //! <b>Complexity</b>: Logarithmic.
\r
1475 //! <b>Throws</b>: If comp ordering function throws.
\r
1477 //! <b>Note</b>: This function is used when constructing a value_type
\r
1478 //! is expensive and the value_type can be compared with a cheaper
\r
1479 //! key type. Usually this key is part of the value_type.
\r
1480 template<class KeyType, class KeyValueCompare>
\r
1481 std::pair<iterator,iterator> equal_range(const KeyType& key, KeyValueCompare comp)
\r
1482 { return tree_.equal_range(key, comp); }
\r
1484 //! <b>Effects</b>: Finds a range containing all elements whose key is k or
\r
1485 //! an empty range that indicates the position where those elements would be
\r
1486 //! if they there is no elements with key k.
\r
1488 //! <b>Complexity</b>: Logarithmic.
\r
1490 //! <b>Throws</b>: If the internal Compare ordering function throws.
\r
1491 std::pair<const_iterator, const_iterator>
\r
1492 equal_range(const value_type &value) const
\r
1493 { return tree_.equal_range(value); }
\r
1495 //! <b>Requires</b>: comp must imply the same element order as
\r
1496 //! value_compare. Usually key is the part of the value_type
\r
1497 //! that is used in the ordering functor.
\r
1499 //! <b>Effects</b>: Finds a range containing all elements whose key is k
\r
1500 //! according to the comparison functor or an empty range
\r
1501 //! that indicates the position where those elements would be
\r
1502 //! if they there is no elements with key k.
\r
1504 //! <b>Complexity</b>: Logarithmic.
\r
1506 //! <b>Throws</b>: If comp ordering function throws.
\r
1508 //! <b>Note</b>: This function is used when constructing a value_type
\r
1509 //! is expensive and the value_type can be compared with a cheaper
\r
1510 //! key type. Usually this key is part of the value_type.
\r
1511 template<class KeyType, class KeyValueCompare>
\r
1512 std::pair<const_iterator, const_iterator>
\r
1513 equal_range(const KeyType& key, KeyValueCompare comp) const
\r
1514 { return tree_.equal_range(key, comp); }
\r
1516 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
1517 //! appropriate type. Otherwise the behavior is undefined.
\r
1519 //! <b>Effects</b>: Returns: a valid iterator i belonging to the set
\r
1520 //! that points to the value
\r
1522 //! <b>Complexity</b>: Constant.
\r
1524 //! <b>Throws</b>: Nothing.
\r
1525 static iterator current(value_type &value)
\r
1526 { return tree_type::current(value); }
\r
1528 //! <b>Requires</b>: value must be an lvalue and shall be in a set of
\r
1529 //! appropriate type. Otherwise the behavior is undefined.
\r
1531 //! <b>Effects</b>: Returns: a valid const_iterator i belonging to the
\r
1532 //! set that points to the value
\r
1534 //! <b>Complexity</b>: Constant.
\r
1536 //! <b>Throws</b>: Nothing.
\r
1537 static const_iterator current(const value_type &value)
\r
1538 { return tree_type::current(value); }
\r
1540 friend bool operator==(const imultiset &x, const imultiset &y)
\r
1541 { return x.tree_ == y.tree_; }
\r
1543 friend bool operator<(const imultiset &x, const imultiset &y)
\r
1544 { return x.tree_ < y.tree_; }
\r
1547 template <class V, class P, bool C, class S>
\r
1548 inline bool operator!=(const imultiset<V, P, C, S>& x, const imultiset<V, P, C, S>& y)
\r
1549 { return !(x==y); }
\r
1551 template <class V, class P, bool C, class S>
\r
1552 inline bool operator>(const imultiset<V, P, C, S>& x, const imultiset<V, P, C, S>& y)
\r
1555 template <class V, class P, bool C, class S>
\r
1556 inline bool operator<=(const imultiset<V, P, C, S>& x, const imultiset<V, P, C, S>& y)
\r
1557 { return !(y > x); }
\r
1559 template <class V, class P, bool C, class S>
\r
1560 inline bool operator>=(const imultiset<V, P, C, S>& x, const imultiset<V, P, C, S>& y)
\r
1561 { return !(x < y); }
\r
1563 template <class V, class P, bool C, class S>
\r
1564 inline void swap(imultiset<V, P, C, S>& x, imultiset<V, P, C, S>& y)
\r
1567 } //namespace intrusive
\r
1568 } //namespace boost
\r
1570 #include <boost/intrusive/detail/config_end.hpp>
\r
1572 #endif //BOOST_INTRUSIVE_ISET_HPP
\r