ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
4// Software License, Version 1.0. (See accompanying file
5// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6//
7// See http://www.boost.org/libs/container for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10
11#ifndef BOOST_CONTAINER_SET_HPP
12#define BOOST_CONTAINER_SET_HPP
13
14#if (defined _MSC_VER) && (_MSC_VER >= 1200)
15# pragma once
16#endif
17
18#include <boost/container/detail/config_begin.hpp>
19#include <boost/container/detail/workaround.hpp>
20#include <boost/container/container_fwd.hpp>
21
22#include <utility>
23#include <functional>
24#include <memory>
25
26#include <boost/move/utility.hpp>
27#include <boost/move/detail/move_helpers.hpp>
28#include <boost/container/detail/mpl.hpp>
29#include <boost/container/detail/tree.hpp>
30#include <boost/move/utility.hpp>
31#ifndef BOOST_CONTAINER_PERFECT_FORWARDING
32#include <boost/container/detail/preprocessor.hpp>
33#endif
34
35namespace boost {
36namespace container {
37
38/// @cond
39// Forward declarations of operators < and ==, needed for friend declaration.
40template <class Key, class Compare, class Allocator>
41inline bool operator==(const set<Key,Compare,Allocator>& x,
42 const set<Key,Compare,Allocator>& y);
43
44template <class Key, class Compare, class Allocator>
45inline bool operator<(const set<Key,Compare,Allocator>& x,
46 const set<Key,Compare,Allocator>& y);
47/// @endcond
48
49//! A set is a kind of associative container that supports unique keys (contains at
50//! most one of each key value) and provides for fast retrieval of the keys themselves.
51//! Class set supports bidirectional iterators.
52//!
53//! A set satisfies all of the requirements of a container and of a reversible container
54//! , and of an associative container. A set also provides most operations described in
55//! for unique keys.
56#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
57template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> >
58#else
59template <class Key, class Compare, class Allocator>
60#endif
61class set
62{
63 /// @cond
64 private:
65 BOOST_COPYABLE_AND_MOVABLE(set)
66 typedef container_detail::rbtree<Key, Key,
67 container_detail::identity<Key>, Compare, Allocator> tree_t;
68 tree_t m_tree; // red-black tree representing set
69 /// @endcond
70
71 public:
72 //////////////////////////////////////////////
73 //
74 // types
75 //
76 //////////////////////////////////////////////
77 typedef Key key_type;
78 typedef Key value_type;
79 typedef Compare key_compare;
80 typedef Compare value_compare;
81 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
82 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
83 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
84 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
85 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
86 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
87 typedef Allocator allocator_type;
88 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
89 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator;
90 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator;
91 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator;
92 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator;
93
94 //////////////////////////////////////////////
95 //
96 // construct/copy/destroy
97 //
98 //////////////////////////////////////////////
99
100 //! <b>Effects</b>: Default constructs an empty set.
101 //!
102 //! <b>Complexity</b>: Constant.
103 set()
104 : m_tree()
105 {}
106
107 //! <b>Effects</b>: Constructs an empty set using the specified comparison object
108 //! and allocator.
109 //!
110 //! <b>Complexity</b>: Constant.
111 explicit set(const Compare& comp,
112 const allocator_type& a = allocator_type())
113 : m_tree(comp, a)
114 {}
115
116 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
117 //! allocator, and inserts elements from the range [first ,last ).
118 //!
119 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
120 //! comp and otherwise N logN, where N is last - first.
121 template <class InputIterator>
122 set(InputIterator first, InputIterator last, const Compare& comp = Compare(),
123 const allocator_type& a = allocator_type())
124 : m_tree(true, first, last, comp, a)
125 {}
126
127 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
128 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
129 //! is more efficient than the normal range creation for ordered ranges.
130 //!
131 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
132 //! unique values.
133 //!
134 //! <b>Complexity</b>: Linear in N.
135 template <class InputIterator>
136 set( ordered_unique_range_t, InputIterator first, InputIterator last
137 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
138 : m_tree(ordered_range, first, last, comp, a)
139 {}
140
141 //! <b>Effects</b>: Copy constructs a set.
142 //!
143 //! <b>Complexity</b>: Linear in x.size().
144 set(const set& x)
145 : m_tree(x.m_tree)
146 {}
147
148 //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources.
149 //!
150 //! <b>Complexity</b>: Constant.
151 //!
152 //! <b>Postcondition</b>: x is emptied.
153 set(BOOST_RV_REF(set) x)
154 : m_tree(boost::move(x.m_tree))
155 {}
156
157 //! <b>Effects</b>: Copy constructs a set using the specified allocator.
158 //!
159 //! <b>Complexity</b>: Linear in x.size().
160 set(const set& x, const allocator_type &a)
161 : m_tree(x.m_tree, a)
162 {}
163
164 //! <b>Effects</b>: Move constructs a set using the specified allocator.
165 //! Constructs *this using x's resources.
166 //!
167 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
168 set(BOOST_RV_REF(set) x, const allocator_type &a)
169 : m_tree(boost::move(x.m_tree), a)
170 {}
171
172 //! <b>Effects</b>: Makes *this a copy of x.
173 //!
174 //! <b>Complexity</b>: Linear in x.size().
175 set& operator=(BOOST_COPY_ASSIGN_REF(set) x)
176 { m_tree = x.m_tree; return *this; }
177
178 //! <b>Effects</b>: this->swap(x.get()).
179 //!
180 //! <b>Complexity</b>: Constant.
181 set& operator=(BOOST_RV_REF(set) x)
182 { m_tree = boost::move(x.m_tree); return *this; }
183
184 //! <b>Effects</b>: Returns a copy of the Allocator that
185 //! was passed to the object's constructor.
186 //!
187 //! <b>Complexity</b>: Constant.
188 allocator_type get_allocator() const
189 { return m_tree.get_allocator(); }
190
191 //! <b>Effects</b>: Returns a reference to the internal allocator.
192 //!
193 //! <b>Throws</b>: Nothing
194 //!
195 //! <b>Complexity</b>: Constant.
196 //!
197 //! <b>Note</b>: Non-standard extension.
198 const stored_allocator_type &get_stored_allocator() const
199 { return m_tree.get_stored_allocator(); }
200
201 //! <b>Effects</b>: Returns a reference to the internal allocator.
202 //!
203 //! <b>Throws</b>: Nothing
204 //!
205 //! <b>Complexity</b>: Constant.
206 //!
207 //! <b>Note</b>: Non-standard extension.
208 stored_allocator_type &get_stored_allocator()
209 { return m_tree.get_stored_allocator(); }
210
211 //////////////////////////////////////////////
212 //
213 // capacity
214 //
215 //////////////////////////////////////////////
216
217 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
218 //!
219 //! <b>Throws</b>: Nothing.
220 //!
221 //! <b>Complexity</b>: Constant
222 iterator begin()
223 { return m_tree.begin(); }
224
225 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
226 //!
227 //! <b>Throws</b>: Nothing.
228 //!
229 //! <b>Complexity</b>: Constant.
230 const_iterator begin() const
231 { return m_tree.begin(); }
232
233 //! <b>Effects</b>: Returns an iterator to the end of the container.
234 //!
235 //! <b>Throws</b>: Nothing.
236 //!
237 //! <b>Complexity</b>: Constant.
238 iterator end()
239 { return m_tree.end(); }
240
241 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
242 //!
243 //! <b>Throws</b>: Nothing.
244 //!
245 //! <b>Complexity</b>: Constant.
246 const_iterator end() const
247 { return m_tree.end(); }
248
249 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
250 //! of the reversed container.
251 //!
252 //! <b>Throws</b>: Nothing.
253 //!
254 //! <b>Complexity</b>: Constant.
255 reverse_iterator rbegin()
256 { return m_tree.rbegin(); }
257
258 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
259 //! of the reversed container.
260 //!
261 //! <b>Throws</b>: Nothing.
262 //!
263 //! <b>Complexity</b>: Constant.
264 const_reverse_iterator rbegin() const
265 { return m_tree.rbegin(); }
266
267 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
268 //! of the reversed container.
269 //!
270 //! <b>Throws</b>: Nothing.
271 //!
272 //! <b>Complexity</b>: Constant.
273 reverse_iterator rend()
274 { return m_tree.rend(); }
275
276 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
277 //! of the reversed container.
278 //!
279 //! <b>Throws</b>: Nothing.
280 //!
281 //! <b>Complexity</b>: Constant.
282 const_reverse_iterator rend() const
283 { return m_tree.rend(); }
284
285 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
286 //!
287 //! <b>Throws</b>: Nothing.
288 //!
289 //! <b>Complexity</b>: Constant.
290 const_iterator cbegin() const
291 { return m_tree.cbegin(); }
292
293 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
294 //!
295 //! <b>Throws</b>: Nothing.
296 //!
297 //! <b>Complexity</b>: Constant.
298 const_iterator cend() const
299 { return m_tree.cend(); }
300
301 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
302 //! of the reversed container.
303 //!
304 //! <b>Throws</b>: Nothing.
305 //!
306 //! <b>Complexity</b>: Constant.
307 const_reverse_iterator crbegin() const
308 { return m_tree.crbegin(); }
309
310 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
311 //! of the reversed container.
312 //!
313 //! <b>Throws</b>: Nothing.
314 //!
315 //! <b>Complexity</b>: Constant.
316 const_reverse_iterator crend() const
317 { return m_tree.crend(); }
318
319 //////////////////////////////////////////////
320 //
321 // capacity
322 //
323 //////////////////////////////////////////////
324
325 //! <b>Effects</b>: Returns true if the container contains no elements.
326 //!
327 //! <b>Throws</b>: Nothing.
328 //!
329 //! <b>Complexity</b>: Constant.
330 bool empty() const
331 { return m_tree.empty(); }
332
333 //! <b>Effects</b>: Returns the number of the elements contained in the container.
334 //!
335 //! <b>Throws</b>: Nothing.
336 //!
337 //! <b>Complexity</b>: Constant.
338 size_type size() const
339 { return m_tree.size(); }
340
341 //! <b>Effects</b>: Returns the largest possible size of the container.
342 //!
343 //! <b>Throws</b>: Nothing.
344 //!
345 //! <b>Complexity</b>: Constant.
346 size_type max_size() const
347 { return m_tree.max_size(); }
348
349 //////////////////////////////////////////////
350 //
351 // modifiers
352 //
353 //////////////////////////////////////////////
354
355 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
356
357 //! <b>Effects</b>: Inserts an object x of type Key constructed with
358 //! std::forward<Args>(args)... if and only if there is
359 //! no element in the container with equivalent value.
360 //! and returns the iterator pointing to the
361 //! newly inserted element.
362 //!
363 //! <b>Returns</b>: The bool component of the returned pair is true if and only
364 //! if the insertion takes place, and the iterator component of the pair
365 //! points to the element with key equivalent to the key of x.
366 //!
367 //! <b>Throws</b>: If memory allocation throws or
368 //! Key's in-place constructor throws.
369 //!
370 //! <b>Complexity</b>: Logarithmic.
371 template <class... Args>
372 std::pair<iterator,bool> emplace(Args&&... args)
373 { return m_tree.emplace_unique(boost::forward<Args>(args)...); }
374
375 //! <b>Effects</b>: Inserts an object of type Key constructed with
376 //! std::forward<Args>(args)... if and only if there is
377 //! no element in the container with equivalent value.
378 //! p is a hint pointing to where the insert
379 //! should start to search.
380 //!
381 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
382 //!
383 //! <b>Complexity</b>: Logarithmic.
384 template <class... Args>
385 iterator emplace_hint(const_iterator hint, Args&&... args)
386 { return m_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); }
387
388 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
389
390 #define BOOST_PP_LOCAL_MACRO(n) \
391 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
392 std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
393 { return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
394 \
395 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
396 iterator emplace_hint(const_iterator hint \
397 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
398 { return m_tree.emplace_hint_unique(hint \
399 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
400 //!
401 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
402 #include BOOST_PP_LOCAL_ITERATE()
403
404 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
405
406 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
407 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
408 //! with key equivalent to the key of x.
409 //!
410 //! <b>Returns</b>: The bool component of the returned pair is true if and only
411 //! if the insertion takes place, and the iterator component of the pair
412 //! points to the element with key equivalent to the key of x.
413 //!
414 //! <b>Complexity</b>: Logarithmic.
415 std::pair<iterator, bool> insert(const value_type &x);
416
417 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
418 //! no element in the container with key equivalent to the key of x.
419 //!
420 //! <b>Returns</b>: The bool component of the returned pair is true if and only
421 //! if the insertion takes place, and the iterator component of the pair
422 //! points to the element with key equivalent to the key of x.
423 //!
424 //! <b>Complexity</b>: Logarithmic.
425 std::pair<iterator, bool> insert(value_type &&x);
426 #else
427 private:
428 typedef std::pair<iterator, bool> insert_return_pair;
429 public:
430 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
431 #endif
432
433 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
434 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
435 //! no element in the container with key equivalent to the key of x.
436 //! p is a hint pointing to where the insert should start to search.
437 //!
438 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
439 //! to the key of x.
440 //!
441 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
442 //! is inserted right before p.
443 iterator insert(const_iterator p, const value_type &x);
444
445 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
446 //! p is a hint pointing to where the insert should start to search.
447 //!
448 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
449 //!
450 //! <b>Complexity</b>: Logarithmic.
451 iterator insert(const_iterator position, value_type &&x);
452 #else
453 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator)
454 #endif
455
456 //! <b>Requires</b>: first, last are not iterators into *this.
457 //!
458 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
459 //! if there is no element with key equivalent to the key of that element.
460 //!
461 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
462 template <class InputIterator>
463 void insert(InputIterator first, InputIterator last)
464 { m_tree.insert_unique(first, last); }
465
466 //! <b>Effects</b>: Erases the element pointed to by p.
467 //!
468 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
469 //! following q prior to the element being erased. If no such element exists,
470 //! returns end().
471 //!
472 //! <b>Complexity</b>: Amortized constant time
473 iterator erase(const_iterator p)
474 { return m_tree.erase(p); }
475
476 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
477 //!
478 //! <b>Returns</b>: Returns the number of erased elements.
479 //!
480 //! <b>Complexity</b>: log(size()) + count(k)
481 size_type erase(const key_type& x)
482 { return m_tree.erase(x); }
483
484 //! <b>Effects</b>: Erases all the elements in the range [first, last).
485 //!
486 //! <b>Returns</b>: Returns last.
487 //!
488 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
489 iterator erase(const_iterator first, const_iterator last)
490 { return m_tree.erase(first, last); }
491
492 //! <b>Effects</b>: Swaps the contents of *this and x.
493 //!
494 //! <b>Throws</b>: Nothing.
495 //!
496 //! <b>Complexity</b>: Constant.
497 void swap(set& x)
498 { m_tree.swap(x.m_tree); }
499
500 //! <b>Effects</b>: erase(a.begin(),a.end()).
501 //!
502 //! <b>Postcondition</b>: size() == 0.
503 //!
504 //! <b>Complexity</b>: linear in size().
505 void clear()
506 { m_tree.clear(); }
507
508 //////////////////////////////////////////////
509 //
510 // observers
511 //
512 //////////////////////////////////////////////
513
514 //! <b>Effects</b>: Returns the comparison object out
515 //! of which a was constructed.
516 //!
517 //! <b>Complexity</b>: Constant.
518 key_compare key_comp() const
519 { return m_tree.key_comp(); }
520
521 //! <b>Effects</b>: Returns an object of value_compare constructed out
522 //! of the comparison object.
523 //!
524 //! <b>Complexity</b>: Constant.
525 value_compare value_comp() const
526 { return m_tree.key_comp(); }
527
528 //////////////////////////////////////////////
529 //
530 // set operations
531 //
532 //////////////////////////////////////////////
533
534 //! <b>Returns</b>: An iterator pointing to an element with the key
535 //! equivalent to x, or end() if such an element is not found.
536 //!
537 //! <b>Complexity</b>: Logarithmic.
538 iterator find(const key_type& x)
539 { return m_tree.find(x); }
540
541 //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key
542 //! equivalent to x, or end() if such an element is not found.
543 //!
544 //! <b>Complexity</b>: Logarithmic.
545 const_iterator find(const key_type& x) const
546 { return m_tree.find(x); }
547
548 //! <b>Returns</b>: The number of elements with key equivalent to x.
549 //!
550 //! <b>Complexity</b>: log(size())+count(k)
551 size_type count(const key_type& x) const
552 { return m_tree.find(x) == m_tree.end() ? 0 : 1; }
553
554 //! <b>Returns</b>: An iterator pointing to the first element with key not less
555 //! than k, or a.end() if such an element is not found.
556 //!
557 //! <b>Complexity</b>: Logarithmic
558 iterator lower_bound(const key_type& x)
559 { return m_tree.lower_bound(x); }
560
561 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
562 //! less than k, or a.end() if such an element is not found.
563 //!
564 //! <b>Complexity</b>: Logarithmic
565 const_iterator lower_bound(const key_type& x) const
566 { return m_tree.lower_bound(x); }
567
568 //! <b>Returns</b>: An iterator pointing to the first element with key not less
569 //! than x, or end() if such an element is not found.
570 //!
571 //! <b>Complexity</b>: Logarithmic
572 iterator upper_bound(const key_type& x)
573 { return m_tree.upper_bound(x); }
574
575 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
576 //! less than x, or end() if such an element is not found.
577 //!
578 //! <b>Complexity</b>: Logarithmic
579 const_iterator upper_bound(const key_type& x) const
580 { return m_tree.upper_bound(x); }
581
582 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
583 //!
584 //! <b>Complexity</b>: Logarithmic
585 std::pair<iterator,iterator> equal_range(const key_type& x)
586 { return m_tree.equal_range(x); }
587
588 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
589 //!
590 //! <b>Complexity</b>: Logarithmic
591 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
592 { return m_tree.equal_range(x); }
593
594 /// @cond
595 template <class K1, class C1, class A1>
596 friend bool operator== (const set<K1,C1,A1>&, const set<K1,C1,A1>&);
597
598 template <class K1, class C1, class A1>
599 friend bool operator< (const set<K1,C1,A1>&, const set<K1,C1,A1>&);
600
601 private:
602 template <class KeyType>
603 std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
604 { return m_tree.insert_unique(::boost::forward<KeyType>(x)); }
605
606 template <class KeyType>
607 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
608 { return m_tree.insert_unique(p, ::boost::forward<KeyType>(x)); }
609 /// @endcond
610};
611
612template <class Key, class Compare, class Allocator>
613inline bool operator==(const set<Key,Compare,Allocator>& x,
614 const set<Key,Compare,Allocator>& y)
615{ return x.m_tree == y.m_tree; }
616
617template <class Key, class Compare, class Allocator>
618inline bool operator<(const set<Key,Compare,Allocator>& x,
619 const set<Key,Compare,Allocator>& y)
620{ return x.m_tree < y.m_tree; }
621
622template <class Key, class Compare, class Allocator>
623inline bool operator!=(const set<Key,Compare,Allocator>& x,
624 const set<Key,Compare,Allocator>& y)
625{ return !(x == y); }
626
627template <class Key, class Compare, class Allocator>
628inline bool operator>(const set<Key,Compare,Allocator>& x,
629 const set<Key,Compare,Allocator>& y)
630{ return y < x; }
631
632template <class Key, class Compare, class Allocator>
633inline bool operator<=(const set<Key,Compare,Allocator>& x,
634 const set<Key,Compare,Allocator>& y)
635{ return !(y < x); }
636
637template <class Key, class Compare, class Allocator>
638inline bool operator>=(const set<Key,Compare,Allocator>& x,
639 const set<Key,Compare,Allocator>& y)
640{ return !(x < y); }
641
642template <class Key, class Compare, class Allocator>
643inline void swap(set<Key,Compare,Allocator>& x, set<Key,Compare,Allocator>& y)
644{ x.swap(y); }
645
646/// @cond
647
648} //namespace container {
649
650//!has_trivial_destructor_after_move<> == true_type
651//!specialization for optimizations
652template <class Key, class C, class Allocator>
653struct has_trivial_destructor_after_move<boost::container::set<Key, C, Allocator> >
654{
655 static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
656};
657
658namespace container {
659
660// Forward declaration of operators < and ==, needed for friend declaration.
661
662template <class Key, class Compare, class Allocator>
663inline bool operator==(const multiset<Key,Compare,Allocator>& x,
664 const multiset<Key,Compare,Allocator>& y);
665
666template <class Key, class Compare, class Allocator>
667inline bool operator<(const multiset<Key,Compare,Allocator>& x,
668 const multiset<Key,Compare,Allocator>& y);
669/// @endcond
670
671//! A multiset is a kind of associative container that supports equivalent keys
672//! (possibly contains multiple copies of the same key value) and provides for
673//! fast retrieval of the keys themselves. Class multiset supports bidirectional iterators.
674//!
675//! A multiset satisfies all of the requirements of a container and of a reversible
676//! container, and of an associative container). multiset also provides most operations
677//! described for duplicate keys.
678#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
679template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> >
680#else
681template <class Key, class Compare, class Allocator>
682#endif
683class multiset
684{
685 /// @cond
686 private:
687 BOOST_COPYABLE_AND_MOVABLE(multiset)
688 typedef container_detail::rbtree<Key, Key,
689 container_detail::identity<Key>, Compare, Allocator> tree_t;
690 tree_t m_tree; // red-black tree representing multiset
691 /// @endcond
692
693 public:
694
695 //////////////////////////////////////////////
696 //
697 // types
698 //
699 //////////////////////////////////////////////
700 typedef Key key_type;
701 typedef Key value_type;
702 typedef Compare key_compare;
703 typedef Compare value_compare;
704 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
705 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
706 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
707 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
708 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
709 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
710 typedef Allocator allocator_type;
711 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
712 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator;
713 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator;
714 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator;
715 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator;
716
717 //////////////////////////////////////////////
718 //
719 // construct/copy/destroy
720 //
721 //////////////////////////////////////////////
722
723 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison
724 //! object and allocator.
725 //!
726 //! <b>Complexity</b>: Constant.
727 multiset()
728 : m_tree()
729 {}
730
731 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison
732 //! object and allocator.
733 //!
734 //! <b>Complexity</b>: Constant.
735 explicit multiset(const Compare& comp,
736 const allocator_type& a = allocator_type())
737 : m_tree(comp, a)
738 {}
739
740 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object
741 //! and allocator, and inserts elements from the range [first ,last ).
742 //!
743 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
744 //! comp and otherwise N logN, where N is last - first.
745 template <class InputIterator>
746 multiset(InputIterator first, InputIterator last,
747 const Compare& comp = Compare(),
748 const allocator_type& a = allocator_type())
749 : m_tree(false, first, last, comp, a)
750 {}
751
752 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and
753 //! allocator, and inserts elements from the ordered range [first ,last ). This function
754 //! is more efficient than the normal range creation for ordered ranges.
755 //!
756 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
757 //!
758 //! <b>Complexity</b>: Linear in N.
759 template <class InputIterator>
760 multiset( ordered_range_t, InputIterator first, InputIterator last
761 , const Compare& comp = Compare()
762 , const allocator_type& a = allocator_type())
763 : m_tree(ordered_range, first, last, comp, a)
764 {}
765
766 //! <b>Effects</b>: Copy constructs a multiset.
767 //!
768 //! <b>Complexity</b>: Linear in x.size().
769 multiset(const multiset& x)
770 : m_tree(x.m_tree)
771 {}
772
773 //! <b>Effects</b>: Move constructs a multiset. Constructs *this using x's resources.
774 //!
775 //! <b>Complexity</b>: Constant.
776 //!
777 //! <b>Postcondition</b>: x is emptied.
778 multiset(BOOST_RV_REF(multiset) x)
779 : m_tree(boost::move(x.m_tree))
780 {}
781
782 //! <b>Effects</b>: Copy constructs a multiset using the specified allocator.
783 //!
784 //! <b>Complexity</b>: Linear in x.size().
785 multiset(const multiset& x, const allocator_type &a)
786 : m_tree(x.m_tree, a)
787 {}
788
789 //! <b>Effects</b>: Move constructs a multiset using the specified allocator.
790 //! Constructs *this using x's resources.
791 //!
792 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
793 //!
794 //! <b>Postcondition</b>: x is emptied.
795 multiset(BOOST_RV_REF(multiset) x, const allocator_type &a)
796 : m_tree(boost::move(x.m_tree), a)
797 {}
798
799 //! <b>Effects</b>: Makes *this a copy of x.
800 //!
801 //! <b>Complexity</b>: Linear in x.size().
802 multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x)
803 { m_tree = x.m_tree; return *this; }
804
805 //! <b>Effects</b>: this->swap(x.get()).
806 //!
807 //! <b>Complexity</b>: Constant.
808 multiset& operator=(BOOST_RV_REF(multiset) x)
809 { m_tree = boost::move(x.m_tree); return *this; }
810
811 //! <b>Effects</b>: Returns a copy of the Allocator that
812 //! was passed to the object's constructor.
813 //!
814 //! <b>Complexity</b>: Constant.
815 allocator_type get_allocator() const
816 { return m_tree.get_allocator(); }
817
818 //! <b>Effects</b>: Returns a reference to the internal allocator.
819 //!
820 //! <b>Throws</b>: Nothing
821 //!
822 //! <b>Complexity</b>: Constant.
823 //!
824 //! <b>Note</b>: Non-standard extension.
825 stored_allocator_type &get_stored_allocator()
826 { return m_tree.get_stored_allocator(); }
827
828 //! <b>Effects</b>: Returns a reference to the internal allocator.
829 //!
830 //! <b>Throws</b>: Nothing
831 //!
832 //! <b>Complexity</b>: Constant.
833 //!
834 //! <b>Note</b>: Non-standard extension.
835 const stored_allocator_type &get_stored_allocator() const
836 { return m_tree.get_stored_allocator(); }
837
838 //////////////////////////////////////////////
839 //
840 // iterators
841 //
842 //////////////////////////////////////////////
843
844 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
845 //!
846 //! <b>Throws</b>: Nothing.
847 //!
848 //! <b>Complexity</b>: Constant.
849 iterator begin()
850 { return m_tree.begin(); }
851
852 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
853 //!
854 //! <b>Throws</b>: Nothing.
855 //!
856 //! <b>Complexity</b>: Constant.
857 const_iterator begin() const
858 { return m_tree.begin(); }
859
860 //! <b>Effects</b>: Returns an iterator to the end of the container.
861 //!
862 //! <b>Throws</b>: Nothing.
863 //!
864 //! <b>Complexity</b>: Constant.
865 iterator end()
866 { return m_tree.end(); }
867
868 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
869 //!
870 //! <b>Throws</b>: Nothing.
871 //!
872 //! <b>Complexity</b>: Constant.
873 const_iterator end() const
874 { return m_tree.end(); }
875
876 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
877 //! of the reversed container.
878 //!
879 //! <b>Throws</b>: Nothing.
880 //!
881 //! <b>Complexity</b>: Constant.
882 reverse_iterator rbegin()
883 { return m_tree.rbegin(); }
884
885 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
886 //! of the reversed container.
887 //!
888 //! <b>Throws</b>: Nothing.
889 //!
890 //! <b>Complexity</b>: Constant.
891 const_reverse_iterator rbegin() const
892 { return m_tree.rbegin(); }
893
894 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
895 //! of the reversed container.
896 //!
897 //! <b>Throws</b>: Nothing.
898 //!
899 //! <b>Complexity</b>: Constant.
900 reverse_iterator rend()
901 { return m_tree.rend(); }
902
903 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
904 //! of the reversed container.
905 //!
906 //! <b>Throws</b>: Nothing.
907 //!
908 //! <b>Complexity</b>: Constant.
909 const_reverse_iterator rend() const
910 { return m_tree.rend(); }
911
912 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
913 //!
914 //! <b>Throws</b>: Nothing.
915 //!
916 //! <b>Complexity</b>: Constant.
917 const_iterator cbegin() const
918 { return m_tree.cbegin(); }
919
920 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
921 //!
922 //! <b>Throws</b>: Nothing.
923 //!
924 //! <b>Complexity</b>: Constant.
925 const_iterator cend() const
926 { return m_tree.cend(); }
927
928 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
929 //! of the reversed container.
930 //!
931 //! <b>Throws</b>: Nothing.
932 //!
933 //! <b>Complexity</b>: Constant.
934 const_reverse_iterator crbegin() const
935 { return m_tree.crbegin(); }
936
937 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
938 //! of the reversed container.
939 //!
940 //! <b>Throws</b>: Nothing.
941 //!
942 //! <b>Complexity</b>: Constant.
943 const_reverse_iterator crend() const
944 { return m_tree.crend(); }
945
946 //////////////////////////////////////////////
947 //
948 // capacity
949 //
950 //////////////////////////////////////////////
951
952 //! <b>Effects</b>: Returns true if the container contains no elements.
953 //!
954 //! <b>Throws</b>: Nothing.
955 //!
956 //! <b>Complexity</b>: Constant.
957 bool empty() const
958 { return m_tree.empty(); }
959
960 //! <b>Effects</b>: Returns the number of the elements contained in the container.
961 //!
962 //! <b>Throws</b>: Nothing.
963 //!
964 //! <b>Complexity</b>: Constant.
965 size_type size() const
966 { return m_tree.size(); }
967
968 //! <b>Effects</b>: Returns the largest possible size of the container.
969 //!
970 //! <b>Throws</b>: Nothing.
971 //!
972 //! <b>Complexity</b>: Constant.
973 size_type max_size() const
974 { return m_tree.max_size(); }
975
976 //////////////////////////////////////////////
977 //
978 // modifiers
979 //
980 //////////////////////////////////////////////
981
982 #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
983
984 //! <b>Effects</b>: Inserts an object of type Key constructed with
985 //! std::forward<Args>(args)... and returns the iterator pointing to the
986 //! newly inserted element.
987 //!
988 //! <b>Complexity</b>: Logarithmic.
989 template <class... Args>
990 iterator emplace(Args&&... args)
991 { return m_tree.emplace_equal(boost::forward<Args>(args)...); }
992
993 //! <b>Effects</b>: Inserts an object of type Key constructed with
994 //! std::forward<Args>(args)...
995 //!
996 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
997 //! to the key of x.
998 //!
999 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1000 //! is inserted right before p.
1001 template <class... Args>
1002 iterator emplace_hint(const_iterator hint, Args&&... args)
1003 { return m_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); }
1004
1005 #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1006
1007 #define BOOST_PP_LOCAL_MACRO(n) \
1008 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1009 iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1010 { return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \
1011 \
1012 BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \
1013 iterator emplace_hint(const_iterator hint \
1014 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \
1015 { return m_tree.emplace_hint_equal(hint \
1016 BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \
1017 //!
1018 #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
1019 #include BOOST_PP_LOCAL_ITERATE()
1020
1021 #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
1022
1023
1024
1025
1026 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1027 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1028 //! newly inserted element.
1029 //!
1030 //! <b>Complexity</b>: Logarithmic.
1031 iterator insert(const value_type &x);
1032
1033 //! <b>Effects</b>: Inserts a copy of x in the container.
1034 //!
1035 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1036 //! to the key of x.
1037 //!
1038 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1039 //! is inserted right before p.
1040 iterator insert(value_type &&x);
1041 #else
1042 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
1043 #endif
1044
1045 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1046 //! <b>Effects</b>: Inserts a copy of x in the container.
1047 //! p is a hint pointing to where the insert should start to search.
1048 //!
1049 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1050 //! to the key of x.
1051 //!
1052 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1053 //! is inserted right before p.
1054 iterator insert(const_iterator p, const value_type &x);
1055
1056 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1057 //! p is a hint pointing to where the insert should start to search.
1058 //!
1059 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1060 //! to the key of x.
1061 //!
1062 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1063 //! is inserted right before p.
1064 iterator insert(const_iterator position, value_type &&x);
1065 #else
1066 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator)
1067 #endif
1068
1069 //! <b>Requires</b>: first, last are not iterators into *this.
1070 //!
1071 //! <b>Effects</b>: inserts each element from the range [first,last) .
1072 //!
1073 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1074 template <class InputIterator>
1075 void insert(InputIterator first, InputIterator last)
1076 { m_tree.insert_equal(first, last); }
1077
1078 //! <b>Effects</b>: Erases the element pointed to by p.
1079 //!
1080 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1081 //! following q prior to the element being erased. If no such element exists,
1082 //! returns end().
1083 //!
1084 //! <b>Complexity</b>: Amortized constant time
1085 iterator erase(const_iterator p)
1086 { return m_tree.erase(p); }
1087
1088 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1089 //!
1090 //! <b>Returns</b>: Returns the number of erased elements.
1091 //!
1092 //! <b>Complexity</b>: log(size()) + count(k)
1093 size_type erase(const key_type& x)
1094 { return m_tree.erase(x); }
1095
1096 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1097 //!
1098 //! <b>Returns</b>: Returns last.
1099 //!
1100 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
1101 iterator erase(const_iterator first, const_iterator last)
1102 { return m_tree.erase(first, last); }
1103
1104 //! <b>Effects</b>: Swaps the contents of *this and x.
1105 //!
1106 //! <b>Throws</b>: Nothing.
1107 //!
1108 //! <b>Complexity</b>: Constant.
1109 void swap(multiset& x)
1110 { m_tree.swap(x.m_tree); }
1111
1112 //! <b>Effects</b>: erase(a.begin(),a.end()).
1113 //!
1114 //! <b>Postcondition</b>: size() == 0.
1115 //!
1116 //! <b>Complexity</b>: linear in size().
1117 void clear()
1118 { m_tree.clear(); }
1119
1120 //////////////////////////////////////////////
1121 //
1122 // observers
1123 //
1124 //////////////////////////////////////////////
1125
1126 //! <b>Effects</b>: Returns the comparison object out
1127 //! of which a was constructed.
1128 //!
1129 //! <b>Complexity</b>: Constant.
1130 key_compare key_comp() const
1131 { return m_tree.key_comp(); }
1132
1133 //! <b>Effects</b>: Returns an object of value_compare constructed out
1134 //! of the comparison object.
1135 //!
1136 //! <b>Complexity</b>: Constant.
1137 value_compare value_comp() const
1138 { return m_tree.key_comp(); }
1139
1140 //////////////////////////////////////////////
1141 //
1142 // set operations
1143 //
1144 //////////////////////////////////////////////
1145
1146 //! <b>Returns</b>: An iterator pointing to an element with the key
1147 //! equivalent to x, or end() if such an element is not found.
1148 //!
1149 //! <b>Complexity</b>: Logarithmic.
1150 iterator find(const key_type& x)
1151 { return m_tree.find(x); }
1152
1153 //! <b>Returns</b>: Allocator const iterator pointing to an element with the key
1154 //! equivalent to x, or end() if such an element is not found.
1155 //!
1156 //! <b>Complexity</b>: Logarithmic.
1157 const_iterator find(const key_type& x) const
1158 { return m_tree.find(x); }
1159
1160 //! <b>Returns</b>: The number of elements with key equivalent to x.
1161 //!
1162 //! <b>Complexity</b>: log(size())+count(k)
1163 size_type count(const key_type& x) const
1164 { return m_tree.count(x); }
1165
1166 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1167 //! than k, or a.end() if such an element is not found.
1168 //!
1169 //! <b>Complexity</b>: Logarithmic
1170 iterator lower_bound(const key_type& x)
1171 { return m_tree.lower_bound(x); }
1172
1173 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
1174 //! less than k, or a.end() if such an element is not found.
1175 //!
1176 //! <b>Complexity</b>: Logarithmic
1177 const_iterator lower_bound(const key_type& x) const
1178 { return m_tree.lower_bound(x); }
1179
1180 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1181 //! than x, or end() if such an element is not found.
1182 //!
1183 //! <b>Complexity</b>: Logarithmic
1184 iterator upper_bound(const key_type& x)
1185 { return m_tree.upper_bound(x); }
1186
1187 //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
1188 //! less than x, or end() if such an element is not found.
1189 //!
1190 //! <b>Complexity</b>: Logarithmic
1191 const_iterator upper_bound(const key_type& x) const
1192 { return m_tree.upper_bound(x); }
1193
1194 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1195 //!
1196 //! <b>Complexity</b>: Logarithmic
1197 std::pair<iterator,iterator> equal_range(const key_type& x)
1198 { return m_tree.equal_range(x); }
1199
1200 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1201 //!
1202 //! <b>Complexity</b>: Logarithmic
1203 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
1204 { return m_tree.equal_range(x); }
1205
1206 /// @cond
1207 template <class K1, class C1, class A1>
1208 friend bool operator== (const multiset<K1,C1,A1>&,
1209 const multiset<K1,C1,A1>&);
1210 template <class K1, class C1, class A1>
1211 friend bool operator< (const multiset<K1,C1,A1>&,
1212 const multiset<K1,C1,A1>&);
1213 private:
1214 template <class KeyType>
1215 iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1216 { return m_tree.insert_equal(::boost::forward<KeyType>(x)); }
1217
1218 template <class KeyType>
1219 iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1220 { return m_tree.insert_equal(p, ::boost::forward<KeyType>(x)); }
1221
1222 /// @endcond
1223};
1224
1225template <class Key, class Compare, class Allocator>
1226inline bool operator==(const multiset<Key,Compare,Allocator>& x,
1227 const multiset<Key,Compare,Allocator>& y)
1228{ return x.m_tree == y.m_tree; }
1229
1230template <class Key, class Compare, class Allocator>
1231inline bool operator<(const multiset<Key,Compare,Allocator>& x,
1232 const multiset<Key,Compare,Allocator>& y)
1233{ return x.m_tree < y.m_tree; }
1234
1235template <class Key, class Compare, class Allocator>
1236inline bool operator!=(const multiset<Key,Compare,Allocator>& x,
1237 const multiset<Key,Compare,Allocator>& y)
1238{ return !(x == y); }
1239
1240template <class Key, class Compare, class Allocator>
1241inline bool operator>(const multiset<Key,Compare,Allocator>& x,
1242 const multiset<Key,Compare,Allocator>& y)
1243{ return y < x; }
1244
1245template <class Key, class Compare, class Allocator>
1246inline bool operator<=(const multiset<Key,Compare,Allocator>& x,
1247 const multiset<Key,Compare,Allocator>& y)
1248{ return !(y < x); }
1249
1250template <class Key, class Compare, class Allocator>
1251inline bool operator>=(const multiset<Key,Compare,Allocator>& x,
1252 const multiset<Key,Compare,Allocator>& y)
1253{ return !(x < y); }
1254
1255template <class Key, class Compare, class Allocator>
1256inline void swap(multiset<Key,Compare,Allocator>& x, multiset<Key,Compare,Allocator>& y)
1257{ x.swap(y); }
1258
1259/// @cond
1260
1261} //namespace container {
1262
1263//!has_trivial_destructor_after_move<> == true_type
1264//!specialization for optimizations
1265template <class Key, class C, class Allocator>
1266struct has_trivial_destructor_after_move<boost::container::multiset<Key, C, Allocator> >
1267{
1268 static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
1269};
1270
1271namespace container {
1272
1273/// @endcond
1274
1275}}
1276
1277#include <boost/container/detail/config_end.hpp>
1278
1279#endif /* BOOST_CONTAINER_SET_HPP */
1280