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

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