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

source code of boost/boost/intrusive/set.hpp