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