1 //////////////////////////////////////////////////////////////////////////////
3 // (C) Copyright Ion Gaztanaga 2005-2013. 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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_CONTAINER_SET_HPP
12 #define BOOST_CONTAINER_SET_HPP
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 #include <boost/container/detail/config_begin.hpp>
23 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/container_fwd.hpp>
27 #include <boost/container/detail/mpl.hpp>
28 #include <boost/container/detail/tree.hpp>
29 #include <boost/container/new_allocator.hpp> //new_allocator
31 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
32 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
34 #include <boost/move/traits.hpp>
35 #include <boost/move/utility_core.hpp>
37 #include <boost/move/detail/move_helpers.hpp>
38 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
39 #include <boost/move/detail/fwd_macros.hpp>
42 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
43 #include <initializer_list>
49 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
51 //! A set is a kind of associative container that supports unique keys (contains at
52 //! most one of each key value) and provides for fast retrieval of the keys themselves.
53 //! Class set supports bidirectional iterators.
55 //! A set satisfies all of the requirements of a container and of a reversible container
56 //! , and of an associative container. A set also provides most operations described in
59 //! \tparam Key is the type to be inserted in the set, which is also the key_type
60 //! \tparam Compare is the comparison functor used to order keys
61 //! \tparam Allocator is the allocator to be used to allocate memory for this container
62 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
63 template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key>, class Options = void>
65 template <class Key, class Compare, class Allocator, class Options>
70 < Key, void, Compare, Allocator, Options>
73 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
75 BOOST_COPYABLE_AND_MOVABLE(set)
77 < Key, void, Compare, Allocator, Options> base_t;
78 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
81 //////////////////////////////////////////////
85 //////////////////////////////////////////////
87 typedef Key value_type;
88 typedef Compare key_compare;
89 typedef key_compare value_compare;
90 typedef typename base_t::allocator_type allocator_type;
91 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
92 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
93 typedef typename ::boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
94 typedef typename ::boost::container::allocator_traits<allocator_type>::reference reference;
95 typedef typename ::boost::container::allocator_traits<allocator_type>::const_reference const_reference;
96 typedef typename ::boost::container::allocator_traits<allocator_type>::size_type size_type;
97 typedef typename ::boost::container::allocator_traits<allocator_type>::difference_type difference_type;
98 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
99 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
100 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
101 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
102 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
103 typedef typename BOOST_CONTAINER_IMPDEF(base_t::node_type) node_type;
104 typedef typename BOOST_CONTAINER_IMPDEF(base_t::insert_return_type) insert_return_type;
106 //////////////////////////////////////////////
108 // construct/copy/destroy
110 //////////////////////////////////////////////
112 //! <b>Effects</b>: Default constructs an empty set.
114 //! <b>Complexity</b>: Constant.
116 BOOST_CONTAINER_FORCEINLINE set()
117 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
118 dtl::is_nothrow_default_constructible<Compare>::value)
122 //! <b>Effects</b>: Constructs an empty set using the specified allocator object.
124 //! <b>Complexity</b>: Constant.
125 BOOST_CONTAINER_FORCEINLINE explicit set(const allocator_type& a)
129 //! <b>Effects</b>: Constructs an empty set using the specified comparison object.
131 //! <b>Complexity</b>: Constant.
132 BOOST_CONTAINER_FORCEINLINE explicit set(const Compare& comp)
136 //! <b>Effects</b>: Constructs an empty set using the specified comparison object
139 //! <b>Complexity</b>: Constant.
140 BOOST_CONTAINER_FORCEINLINE set(const Compare& comp, const allocator_type& a)
144 //! <b>Effects</b>: Constructs an empty set using and
145 //! inserts elements from the range [first ,last ).
147 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
148 //! the predicate and otherwise N logN, where N is last - first.
149 template <class InputIterator>
150 BOOST_CONTAINER_FORCEINLINE set(InputIterator first, InputIterator last)
151 : base_t(true, first, last)
154 //! <b>Effects</b>: Constructs an empty set using the specified
155 //! allocator, and inserts elements from the range [first ,last ).
157 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
158 //! the predicate and otherwise N logN, where N is last - first.
159 template <class InputIterator>
160 BOOST_CONTAINER_FORCEINLINE set(InputIterator first, InputIterator last, const allocator_type& a)
161 : base_t(true, first, last, key_compare(), a)
164 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
165 //! inserts elements from the range [first ,last ).
167 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
168 //! the predicate and otherwise N logN, where N is last - first.
169 template <class InputIterator>
170 BOOST_CONTAINER_FORCEINLINE set(InputIterator first, InputIterator last, const Compare& comp)
171 : base_t(true, first, last, comp)
174 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
175 //! allocator, and inserts elements from the range [first ,last ).
177 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
178 //! the predicate and otherwise N logN, where N is last - first.
179 template <class InputIterator>
180 BOOST_CONTAINER_FORCEINLINE set(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
181 : base_t(true, first, last, comp, a)
184 //! <b>Effects</b>: Constructs an empty set and
185 //! inserts elements from the ordered unique range [first ,last). This function
186 //! is more efficient than the normal range creation for ordered ranges.
188 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
191 //! <b>Complexity</b>: Linear in N.
193 //! <b>Note</b>: Non-standard extension.
194 template <class InputIterator>
195 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, InputIterator first, InputIterator last)
196 : base_t(ordered_range, first, last)
199 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
200 //! inserts elements from the ordered unique range [first ,last). This function
201 //! is more efficient than the normal range creation for ordered ranges.
203 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
206 //! <b>Complexity</b>: Linear in N.
208 //! <b>Note</b>: Non-standard extension.
209 template <class InputIterator>
210 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp )
211 : base_t(ordered_range, first, last, comp)
214 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
215 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
216 //! is more efficient than the normal range creation for ordered ranges.
218 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
221 //! <b>Complexity</b>: Linear in N.
223 //! <b>Note</b>: Non-standard extension.
224 template <class InputIterator>
225 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, InputIterator first, InputIterator last
226 , const Compare& comp, const allocator_type& a)
227 : base_t(ordered_range, first, last, comp, a)
230 //! <b>Effects</b>: Constructs an empty set using the specified allocator and
231 //! inserts elements from the ordered unique range [first ,last). This function
232 //! is more efficient than the normal range creation for ordered ranges.
234 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
237 //! <b>Complexity</b>: Linear in N.
239 //! <b>Note</b>: Non-standard extension.
240 template <class InputIterator>
241 BOOST_CONTAINER_FORCEINLINE set(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
242 : base_t(ordered_range, first, last, Compare(), a)
245 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
246 //! <b>Effects</b>: Constructs an empty set and
247 //! inserts elements from the range [il.begin(), il.end()).
249 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
250 //! the predicate and otherwise N logN, where N is il.begin() - il.end().
251 BOOST_CONTAINER_FORCEINLINE set(std::initializer_list<value_type> il)
252 : base_t(true, il.begin(), il.end())
255 //! <b>Effects</b>: Constructs an empty set using the specified
256 //! allocator, and inserts elements from the range [il.begin(), il.end()).
258 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
259 //! the predicate and otherwise N logN, where N is il.begin() - il.end().
260 BOOST_CONTAINER_FORCEINLINE set(std::initializer_list<value_type> il, const allocator_type& a)
261 : base_t(true, il.begin(), il.end(), Compare(), a)
264 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
265 //! inserts elements from the range [il.begin(), il.end()).
267 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
268 //! the predicate and otherwise N logN, where N is il.begin() - il.end().
269 BOOST_CONTAINER_FORCEINLINE set(std::initializer_list<value_type> il, const Compare& comp )
270 : base_t(true, il.begin(), il.end(), comp)
273 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
274 //! allocator, and inserts elements from the range [il.begin(), il.end()).
276 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
277 //! the predicate and otherwise N logN, where N is il.begin() - il.end().
278 BOOST_CONTAINER_FORCEINLINE set(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
279 : base_t(true, il.begin(), il.end(), comp, a)
282 //! <b>Effects</b>: Constructs an empty set and
283 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
284 //! is more efficient than the normal range creation for ordered ranges.
286 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
289 //! <b>Complexity</b>: Linear in N.
291 //! <b>Note</b>: Non-standard extension.
292 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, std::initializer_list<value_type> il)
293 : base_t(ordered_range, il.begin(), il.end())
296 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
297 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
298 //! is more efficient than the normal range creation for ordered ranges.
300 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
303 //! <b>Complexity</b>: Linear in N.
305 //! <b>Note</b>: Non-standard extension.
306 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
307 : base_t(ordered_range, il.begin(), il.end(), comp)
310 //! <b>Effects</b>: Constructs an empty set using the specified comparison object and
311 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
312 //! is more efficient than the normal range creation for ordered ranges.
314 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
317 //! <b>Complexity</b>: Linear in N.
319 //! <b>Note</b>: Non-standard extension.
320 BOOST_CONTAINER_FORCEINLINE set( ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
321 : base_t(ordered_range, il.begin(), il.end(), comp, a)
325 //! <b>Effects</b>: Copy constructs a set.
327 //! <b>Complexity</b>: Linear in x.size().
328 BOOST_CONTAINER_FORCEINLINE set(const set& x)
329 : base_t(static_cast<const base_t&>(x))
332 //! <b>Effects</b>: Move constructs a set. Constructs *this using x's resources.
334 //! <b>Complexity</b>: Constant.
336 //! <b>Postcondition</b>: x is emptied.
337 BOOST_CONTAINER_FORCEINLINE set(BOOST_RV_REF(set) x)
338 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
339 : base_t(BOOST_MOVE_BASE(base_t, x))
342 //! <b>Effects</b>: Copy constructs a set using the specified allocator.
344 //! <b>Complexity</b>: Linear in x.size().
345 BOOST_CONTAINER_FORCEINLINE set(const set& x, const allocator_type &a)
346 : base_t(static_cast<const base_t&>(x), a)
349 //! <b>Effects</b>: Move constructs a set using the specified allocator.
350 //! Constructs *this using x's resources.
352 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
353 BOOST_CONTAINER_FORCEINLINE set(BOOST_RV_REF(set) x, const allocator_type &a)
354 : base_t(BOOST_MOVE_BASE(base_t, x), a)
357 //! <b>Effects</b>: Makes *this a copy of x.
359 //! <b>Complexity</b>: Linear in x.size().
360 BOOST_CONTAINER_FORCEINLINE set& operator=(BOOST_COPY_ASSIGN_REF(set) x)
361 { return static_cast<set&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
363 //! <b>Effects</b>: this->swap(x.get()).
365 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
366 //! is false and (allocation throws or value_type's move constructor throws)
368 //! <b>Complexity</b>: Constant if allocator_traits_type::
369 //! propagate_on_container_move_assignment is true or
370 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
371 BOOST_CONTAINER_FORCEINLINE set& operator=(BOOST_RV_REF(set) x)
372 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
373 allocator_traits_type::is_always_equal::value) &&
374 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
375 { return static_cast<set&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
377 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
378 //! <b>Effects</b>: Copy all elements from il to *this.
380 //! <b>Complexity</b>: Linear in il.size().
381 set& operator=(std::initializer_list<value_type> il)
384 insert(il.begin(), il.end());
389 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
391 //! <b>Effects</b>: Returns a copy of the allocator that
392 //! was passed to the object's constructor.
394 //! <b>Complexity</b>: Constant.
395 allocator_type get_allocator() const;
397 //! <b>Effects</b>: Returns a reference to the internal allocator.
399 //! <b>Throws</b>: Nothing
401 //! <b>Complexity</b>: Constant.
403 //! <b>Note</b>: Non-standard extension.
404 stored_allocator_type &get_stored_allocator();
406 //! <b>Effects</b>: Returns a reference to the internal allocator.
408 //! <b>Throws</b>: Nothing
410 //! <b>Complexity</b>: Constant.
412 //! <b>Note</b>: Non-standard extension.
413 const stored_allocator_type &get_stored_allocator() const;
415 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
417 //! <b>Throws</b>: Nothing.
419 //! <b>Complexity</b>: Constant
422 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
424 //! <b>Throws</b>: Nothing.
426 //! <b>Complexity</b>: Constant.
427 const_iterator begin() const;
429 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
431 //! <b>Throws</b>: Nothing.
433 //! <b>Complexity</b>: Constant.
434 const_iterator cbegin() const;
436 //! <b>Effects</b>: Returns an iterator to the end of the container.
438 //! <b>Throws</b>: Nothing.
440 //! <b>Complexity</b>: Constant.
443 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
445 //! <b>Throws</b>: Nothing.
447 //! <b>Complexity</b>: Constant.
448 const_iterator end() const;
450 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
452 //! <b>Throws</b>: Nothing.
454 //! <b>Complexity</b>: Constant.
455 const_iterator cend() const;
457 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
458 //! of the reversed container.
460 //! <b>Throws</b>: Nothing.
462 //! <b>Complexity</b>: Constant.
463 reverse_iterator rbegin();
465 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
466 //! of the reversed container.
468 //! <b>Throws</b>: Nothing.
470 //! <b>Complexity</b>: Constant.
471 const_reverse_iterator rbegin() const;
473 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
474 //! of the reversed container.
476 //! <b>Throws</b>: Nothing.
478 //! <b>Complexity</b>: Constant.
479 const_reverse_iterator crbegin() const;
481 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
482 //! of the reversed container.
484 //! <b>Throws</b>: Nothing.
486 //! <b>Complexity</b>: Constant.
487 reverse_iterator rend();
489 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
490 //! of the reversed container.
492 //! <b>Throws</b>: Nothing.
494 //! <b>Complexity</b>: Constant.
495 const_reverse_iterator rend() const;
497 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
498 //! of the reversed container.
500 //! <b>Throws</b>: Nothing.
502 //! <b>Complexity</b>: Constant.
503 const_reverse_iterator crend() const;
505 //! <b>Effects</b>: Returns true if the container contains no elements.
507 //! <b>Throws</b>: Nothing.
509 //! <b>Complexity</b>: Constant.
512 //! <b>Effects</b>: Returns the number of the elements contained in the container.
514 //! <b>Throws</b>: Nothing.
516 //! <b>Complexity</b>: Constant.
517 size_type size() const;
519 //! <b>Effects</b>: Returns the largest possible size of the container.
521 //! <b>Throws</b>: Nothing.
523 //! <b>Complexity</b>: Constant.
524 size_type max_size() const;
525 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
527 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
529 //! <b>Effects</b>: Inserts an object x of type Key constructed with
530 //! std::forward<Args>(args)... if and only if there is
531 //! no element in the container with equivalent value.
532 //! and returns the iterator pointing to the
533 //! newly inserted element.
535 //! <b>Returns</b>: The bool component of the returned pair is true if and only
536 //! if the insertion takes place, and the iterator component of the pair
537 //! points to the element with key equivalent to the key of x.
539 //! <b>Throws</b>: If memory allocation throws or
540 //! Key's in-place constructor throws.
542 //! <b>Complexity</b>: Logarithmic.
543 template <class... Args>
544 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
545 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
547 //! <b>Effects</b>: Inserts an object of type Key constructed with
548 //! std::forward<Args>(args)... if and only if there is
549 //! no element in the container with equivalent value.
550 //! p is a hint pointing to where the insert
551 //! should start to search.
553 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
555 //! <b>Complexity</b>: Logarithmic.
556 template <class... Args>
557 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
558 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
560 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
562 #define BOOST_CONTAINER_SET_EMPLACE_CODE(N) \
563 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
564 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
565 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\
567 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
568 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
569 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
571 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SET_EMPLACE_CODE)
572 #undef BOOST_CONTAINER_SET_EMPLACE_CODE
574 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
576 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
577 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
578 //! with key equivalent to the key of x.
580 //! <b>Returns</b>: The bool component of the returned pair is true if and only
581 //! if the insertion takes place, and the iterator component of the pair
582 //! points to the element with key equivalent to the key of x.
584 //! <b>Complexity</b>: Logarithmic.
585 std::pair<iterator, bool> insert(const value_type &x);
587 //! <b>Effects</b>: Move constructs a new value from x if and only if there is
588 //! no element in the container with key equivalent to the key of x.
590 //! <b>Returns</b>: The bool component of the returned pair is true if and only
591 //! if the insertion takes place, and the iterator component of the pair
592 //! points to the element with key equivalent to the key of x.
594 //! <b>Complexity</b>: Logarithmic.
595 std::pair<iterator, bool> insert(value_type &&x);
598 typedef std::pair<iterator, bool> insert_return_pair;
600 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
603 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
604 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
605 //! no element in the container with key equivalent to the key of x.
606 //! p is a hint pointing to where the insert should start to search.
608 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
611 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
612 //! is inserted right before p.
613 iterator insert(const_iterator p, const value_type &x);
615 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
616 //! p is a hint pointing to where the insert should start to search.
618 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
620 //! <b>Complexity</b>: Logarithmic.
621 iterator insert(const_iterator p, value_type &&x);
623 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
626 //! <b>Requires</b>: first, last are not iterators into *this.
628 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
629 //! if there is no element with key equivalent to the key of that element.
631 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
632 template <class InputIterator>
633 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
634 { this->base_t::insert_unique(first, last); }
636 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
637 //! <b>Effects</b>: inserts each element from the range [il.begin(),il.end()) if and only
638 //! if there is no element with key equivalent to the key of that element.
640 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
641 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
642 { this->base_t::insert_unique(il.begin(), il.end()); }
645 //! @copydoc ::boost::container::map::insert(node_type&&)
646 BOOST_CONTAINER_FORCEINLINE insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
647 { return this->base_t::insert_unique_node(boost::move(nh)); }
649 //! @copydoc ::boost::container::map::insert(const_iterator, node_type&&)
650 BOOST_CONTAINER_FORCEINLINE insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
651 { return this->base_t::insert_unique_node(hint, boost::move(nh)); }
653 //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
655 BOOST_CONTAINER_FORCEINLINE void merge(set<Key, C2, Allocator, Options>& source)
658 <Key, void, C2, Allocator, Options> base2_t;
659 this->base_t::merge_unique(static_cast<base2_t&>(source));
662 //! @copydoc ::boost::container::set::merge(set<Key, C2, Allocator, Options>&)
664 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG set<Key, C2, Allocator, Options> BOOST_RV_REF_END source)
665 { return this->merge(static_cast<set<Key, C2, Allocator, Options>&>(source)); }
667 //! @copydoc ::boost::container::map::merge(multimap<Key, T, C2, Allocator, Options>&)
669 BOOST_CONTAINER_FORCEINLINE void merge(multiset<Key, C2, Allocator, Options>& source)
672 <Key, void, C2, Allocator, Options> base2_t;
673 this->base_t::merge_unique(static_cast<base2_t&>(source));
676 //! @copydoc ::boost::container::set::merge(multiset<Key, C2, Allocator, Options>&)
678 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multiset<Key, C2, Allocator, Options> BOOST_RV_REF_END source)
679 { return this->merge(static_cast<multiset<Key, C2, Allocator, Options>&>(source)); }
681 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
683 //! <b>Effects</b>: Erases the element pointed to by p.
685 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
686 //! following q prior to the element being erased. If no such element exists,
689 //! <b>Complexity</b>: Amortized constant time
690 iterator erase(const_iterator p);
692 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
694 //! <b>Returns</b>: Returns the number of erased elements.
696 //! <b>Complexity</b>: log(size()) + count(k)
697 size_type erase(const key_type& x);
699 //! <b>Effects</b>: Erases all the elements in the range [first, last).
701 //! <b>Returns</b>: Returns last.
703 //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
704 iterator erase(const_iterator first, const_iterator last);
706 //! @copydoc ::boost::container::map::extract(const_iterator)
707 node_type extract(const_iterator p);
709 //! @copydoc ::boost::container::map::extract(const key_type&)
710 node_type extract(const key_type& x);
712 //! <b>Effects</b>: Swaps the contents of *this and x.
714 //! <b>Throws</b>: Nothing.
716 //! <b>Complexity</b>: Constant.
718 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
719 && boost::container::dtl::is_nothrow_swappable<Compare>::value );
721 //! <b>Effects</b>: erase(begin(),end()).
723 //! <b>Postcondition</b>: size() == 0.
725 //! <b>Complexity</b>: linear in size().
728 //! <b>Effects</b>: Returns the comparison object out
729 //! of which a was constructed.
731 //! <b>Complexity</b>: Constant.
732 key_compare key_comp() const;
734 //! <b>Effects</b>: Returns an object of value_compare constructed out
735 //! of the comparison object.
737 //! <b>Complexity</b>: Constant.
738 value_compare value_comp() const;
740 //! <b>Returns</b>: An iterator pointing to an element with the key
741 //! equivalent to x, or end() if such an element is not found.
743 //! <b>Complexity</b>: Logarithmic.
744 iterator find(const key_type& x);
746 //! <b>Returns</b>: A const_iterator pointing to an element with the key
747 //! equivalent to x, or end() if such an element is not found.
749 //! <b>Complexity</b>: Logarithmic.
750 const_iterator find(const key_type& x) const;
752 //! <b>Requires</b>: This overload is available only if
753 //! key_compare::is_transparent exists.
755 //! <b>Returns</b>: An iterator pointing to an element with the key
756 //! equivalent to x, or end() if such an element is not found.
758 //! <b>Complexity</b>: Logarithmic.
760 iterator find(const K& x);
762 //! <b>Requires</b>: This overload is available only if
763 //! key_compare::is_transparent exists.
765 //! <b>Returns</b>: A const_iterator pointing to an element with the key
766 //! equivalent to x, or end() if such an element is not found.
768 //! <b>Complexity</b>: Logarithmic.
770 const_iterator find(const K& x) const;
772 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
774 //! <b>Returns</b>: The number of elements with key equivalent to x.
776 //! <b>Complexity</b>: log(size())+count(k)
777 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
778 { return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend()); }
780 //! <b>Requires</b>: This overload is available only if
781 //! key_compare::is_transparent exists.
783 //! <b>Returns</b>: The number of elements with key equivalent to x.
785 //! <b>Complexity</b>: log(size())+count(k)
787 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
788 { return static_cast<size_type>(this->find(x) != this->cend()); }
790 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
792 //! <b>Returns</b>: Returns true if there is an element with key
793 //! equivalent to key in the container, otherwise false.
795 //! <b>Complexity</b>: log(size()).
796 bool contains(const key_type& x) const;
798 //! <b>Requires</b>: This overload is available only if
799 //! key_compare::is_transparent exists.
801 //! <b>Returns</b>: Returns true if there is an element with key
802 //! equivalent to key in the container, otherwise false.
804 //! <b>Complexity</b>: log(size()).
806 bool contains(const K& x) const;
808 //! <b>Returns</b>: An iterator pointing to the first element with key not less
809 //! than x, or end() if such an element is not found.
811 //! <b>Complexity</b>: Logarithmic
812 iterator lower_bound(const key_type& x);
814 //! <b>Returns</b>: A const iterator pointing to the first element with key not
815 //! less than x, or end() if such an element is not found.
817 //! <b>Complexity</b>: Logarithmic
818 const_iterator lower_bound(const key_type& x) const;
820 //! <b>Requires</b>: This overload is available only if
821 //! key_compare::is_transparent exists.
823 //! <b>Returns</b>: An iterator pointing to the first element with key not less
824 //! than x, or end() if such an element is not found.
826 //! <b>Complexity</b>: Logarithmic
828 iterator lower_bound(const K& x);
830 //! <b>Requires</b>: This overload is available only if
831 //! key_compare::is_transparent exists.
833 //! <b>Returns</b>: A const iterator pointing to the first element with key not
834 //! less than x, or end() if such an element is not found.
836 //! <b>Complexity</b>: Logarithmic
838 const_iterator lower_bound(const K& x) const;
840 //! <b>Returns</b>: An iterator pointing to the first element with key greater
841 //! than x, or end() if such an element is not found.
843 //! <b>Complexity</b>: Logarithmic
844 iterator upper_bound(const key_type& x);
846 //! <b>Returns</b>: A const iterator pointing to the first element with key
847 //! greater than x, or end() if such an element is not found.
849 //! <b>Complexity</b>: Logarithmic
850 const_iterator upper_bound(const key_type& x) const;
852 //! <b>Requires</b>: This overload is available only if
853 //! key_compare::is_transparent exists.
855 //! <b>Returns</b>: An iterator pointing to the first element with key greater
856 //! than x, or end() if such an element is not found.
858 //! <b>Complexity</b>: Logarithmic
860 iterator upper_bound(const K& x);
862 //! <b>Requires</b>: This overload is available only if
863 //! key_compare::is_transparent exists.
865 //! <b>Returns</b>: A const iterator pointing to the first element with key
866 //! greater than x, or end() if such an element is not found.
868 //! <b>Complexity</b>: Logarithmic
870 const_iterator upper_bound(const K& x) const;
872 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
874 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
876 //! <b>Complexity</b>: Logarithmic
877 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
878 { return this->base_t::lower_bound_range(x); }
880 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
882 //! <b>Complexity</b>: Logarithmic
883 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
884 { return this->base_t::lower_bound_range(x); }
886 //! <b>Requires</b>: This overload is available only if
887 //! key_compare::is_transparent exists.
889 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
891 //! <b>Complexity</b>: Logarithmic
893 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
894 { return this->base_t::lower_bound_range(x); }
896 //! <b>Requires</b>: This overload is available only if
897 //! key_compare::is_transparent exists.
899 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
901 //! <b>Complexity</b>: Logarithmic
903 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator,const_iterator> equal_range(const K& x) const
904 { return this->base_t::lower_bound_range(x); }
906 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
908 //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
910 //! <b>Complexity</b>: Linear
913 //! <b>Effects</b>: Returns true if x and y are equal
915 //! <b>Complexity</b>: Linear to the number of elements in the container.
916 friend bool operator==(const set& x, const set& y);
918 //! <b>Effects</b>: Returns true if x and y are unequal
920 //! <b>Complexity</b>: Linear to the number of elements in the container.
921 friend bool operator!=(const set& x, const set& y);
923 //! <b>Effects</b>: Returns true if x is less than y
925 //! <b>Complexity</b>: Linear to the number of elements in the container.
926 friend bool operator<(const set& x, const set& y);
928 //! <b>Effects</b>: Returns true if x is greater than y
930 //! <b>Complexity</b>: Linear to the number of elements in the container.
931 friend bool operator>(const set& x, const set& y);
933 //! <b>Effects</b>: Returns true if x is equal or less than y
935 //! <b>Complexity</b>: Linear to the number of elements in the container.
936 friend bool operator<=(const set& x, const set& y);
938 //! <b>Effects</b>: Returns true if x is equal or greater than y
940 //! <b>Complexity</b>: Linear to the number of elements in the container.
941 friend bool operator>=(const set& x, const set& y);
943 //! <b>Effects</b>: x.swap(y)
945 //! <b>Complexity</b>: Constant.
946 friend void swap(set& x, set& y);
948 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
950 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
952 template <class KeyType>
953 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
954 { return this->base_t::insert_unique(::boost::forward<KeyType>(x)); }
956 template <class KeyType>
957 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
958 { return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
959 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
962 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
964 template <typename InputIterator>
965 set(InputIterator, InputIterator) ->
966 set< it_based_value_type_t<InputIterator> >;
968 template < typename InputIterator, typename AllocatorOrCompare>
969 set(InputIterator, InputIterator, AllocatorOrCompare const&) ->
970 set< it_based_value_type_t<InputIterator>
971 , typename dtl::if_c< // Compare
972 dtl::is_allocator<AllocatorOrCompare>::value
973 , std::less<it_based_value_type_t<InputIterator>>
976 , typename dtl::if_c< // Allocator
977 dtl::is_allocator<AllocatorOrCompare>::value
979 , new_allocator<it_based_value_type_t<InputIterator>>
983 template < typename InputIterator, typename Compare, typename Allocator
984 , typename = dtl::require_nonallocator_t<Compare>
985 , typename = dtl::require_allocator_t<Allocator>>
986 set(InputIterator, InputIterator, Compare const&, Allocator const&) ->
987 set< it_based_value_type_t<InputIterator>
991 template <typename InputIterator>
992 set(ordered_unique_range_t, InputIterator, InputIterator) ->
993 set< it_based_value_type_t<InputIterator>>;
996 template < typename InputIterator, typename AllocatorOrCompare>
997 set(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
998 set< it_based_value_type_t<InputIterator>
999 , typename dtl::if_c< // Compare
1000 dtl::is_allocator<AllocatorOrCompare>::value
1001 , std::less<it_based_value_type_t<InputIterator>>
1002 , AllocatorOrCompare
1004 , typename dtl::if_c< // Allocator
1005 dtl::is_allocator<AllocatorOrCompare>::value
1006 , AllocatorOrCompare
1007 , new_allocator<it_based_value_type_t<InputIterator>>
1011 template < typename InputIterator, typename Compare, typename Allocator
1012 , typename = dtl::require_nonallocator_t<Compare>
1013 , typename = dtl::require_allocator_t<Allocator>>
1014 set(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1015 set< it_based_value_type_t<InputIterator>
1021 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1023 } //namespace container {
1025 //!has_trivial_destructor_after_move<> == true_type
1026 //!specialization for optimizations
1027 template <class Key, class Compare, class Allocator, class Options>
1028 struct has_trivial_destructor_after_move<boost::container::set<Key, Compare, Allocator, Options> >
1030 typedef ::boost::container::dtl::tree<Key, void, Compare, Allocator, Options> tree;
1031 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1034 namespace container {
1036 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1038 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1040 //! A multiset is a kind of associative container that supports equivalent keys
1041 //! (possibly contains multiple copies of the same key value) and provides for
1042 //! fast retrieval of the keys themselves. Class multiset supports bidirectional iterators.
1044 //! A multiset satisfies all of the requirements of a container and of a reversible
1045 //! container, and of an associative container). multiset also provides most operations
1046 //! described for duplicate keys.
1048 //! \tparam Key is the type to be inserted in the set, which is also the key_type
1049 //! \tparam Compare is the comparison functor used to order keys
1050 //! \tparam Allocator is the allocator to be used to allocate memory for this container
1051 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
1052 template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key>, class Options = tree_assoc_defaults >
1054 template <class Key, class Compare, class Allocator, class Options>
1059 <Key, void, Compare, Allocator, Options>
1062 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1064 BOOST_COPYABLE_AND_MOVABLE(multiset)
1066 <Key, void, Compare, Allocator, Options> base_t;
1067 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1071 //////////////////////////////////////////////
1075 //////////////////////////////////////////////
1076 typedef Key key_type;
1077 typedef Key value_type;
1078 typedef Compare key_compare;
1079 typedef key_compare value_compare;
1080 typedef typename base_t::allocator_type allocator_type;
1081 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
1082 typedef typename ::boost::container::allocator_traits<allocator_type>::pointer pointer;
1083 typedef typename ::boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
1084 typedef typename ::boost::container::allocator_traits<allocator_type>::reference reference;
1085 typedef typename ::boost::container::allocator_traits<allocator_type>::const_reference const_reference;
1086 typedef typename ::boost::container::allocator_traits<allocator_type>::size_type size_type;
1087 typedef typename ::boost::container::allocator_traits<allocator_type>::difference_type difference_type;
1088 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
1089 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
1090 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
1091 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
1092 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
1093 typedef typename BOOST_CONTAINER_IMPDEF(base_t::node_type) node_type;
1095 //////////////////////////////////////////////
1097 // construct/copy/destroy
1099 //////////////////////////////////////////////
1101 //! @copydoc ::boost::container::set::set()
1102 BOOST_CONTAINER_FORCEINLINE multiset()
1103 BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
1104 dtl::is_nothrow_default_constructible<Compare>::value)
1108 //! @copydoc ::boost::container::set::set(const allocator_type&)
1109 BOOST_CONTAINER_FORCEINLINE explicit multiset(const allocator_type& a)
1113 //! @copydoc ::boost::container::set::set(const Compare&)
1114 BOOST_CONTAINER_FORCEINLINE explicit multiset(const Compare& comp)
1118 //! @copydoc ::boost::container::set::set(const Compare&, const allocator_type&)
1119 BOOST_CONTAINER_FORCEINLINE multiset(const Compare& comp, const allocator_type& a)
1123 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator)
1124 template <class InputIterator>
1125 BOOST_CONTAINER_FORCEINLINE multiset(InputIterator first, InputIterator last)
1126 : base_t(false, first, last)
1129 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const allocator_type&)
1130 template <class InputIterator>
1131 BOOST_CONTAINER_FORCEINLINE multiset(InputIterator first, InputIterator last, const allocator_type& a)
1132 : base_t(false, first, last, key_compare(), a)
1135 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const Compare&)
1136 template <class InputIterator>
1137 BOOST_CONTAINER_FORCEINLINE multiset(InputIterator first, InputIterator last, const Compare& comp)
1138 : base_t(false, first, last, comp)
1141 //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const Compare&, const allocator_type&)
1142 template <class InputIterator>
1143 BOOST_CONTAINER_FORCEINLINE multiset(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1144 : base_t(false, first, last, comp, a)
1147 //! <b>Effects</b>: Constructs an empty multiset and
1148 //! and inserts elements from the ordered range [first ,last ). This function
1149 //! is more efficient than the normal range creation for ordered ranges.
1151 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1153 //! <b>Complexity</b>: Linear in N.
1155 //! <b>Note</b>: Non-standard extension.
1156 template <class InputIterator>
1157 BOOST_CONTAINER_FORCEINLINE multiset( ordered_range_t, InputIterator first, InputIterator last )
1158 : base_t(ordered_range, first, last)
1161 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and
1162 //! inserts elements from the ordered range [first ,last ). This function
1163 //! is more efficient than the normal range creation for ordered ranges.
1165 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1167 //! <b>Complexity</b>: Linear in N.
1169 //! <b>Note</b>: Non-standard extension.
1170 template <class InputIterator>
1171 BOOST_CONTAINER_FORCEINLINE multiset( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1172 : base_t(ordered_range, first, last, comp)
1175 //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and
1176 //! allocator, and inserts elements from the ordered range [first ,last ). This function
1177 //! is more efficient than the normal range creation for ordered ranges.
1179 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1181 //! <b>Complexity</b>: Linear in N.
1183 //! <b>Note</b>: Non-standard extension.
1184 template <class InputIterator>
1185 BOOST_CONTAINER_FORCEINLINE multiset( ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1186 : base_t(ordered_range, first, last, comp, a)
1189 //! <b>Effects</b>: Constructs an empty multiset using the specified allocator and
1190 //! inserts elements from the ordered range [first ,last ). This function
1191 //! is more efficient than the normal range creation for ordered ranges.
1193 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1195 //! <b>Complexity</b>: Linear in N.
1197 //! <b>Note</b>: Non-standard extension.
1198 template <class InputIterator>
1199 BOOST_CONTAINER_FORCEINLINE multiset(ordered_range_t, InputIterator first, InputIterator last, const allocator_type &a)
1200 : base_t(ordered_range, first, last, Compare(), a)
1203 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1204 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>)
1205 BOOST_CONTAINER_FORCEINLINE multiset(std::initializer_list<value_type> il)
1206 : base_t(false, il.begin(), il.end())
1209 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const allocator_type&)
1210 BOOST_CONTAINER_FORCEINLINE multiset(std::initializer_list<value_type> il, const allocator_type& a)
1211 : base_t(false, il.begin(), il.end(), Compare(), a)
1214 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const Compare&)
1215 BOOST_CONTAINER_FORCEINLINE multiset(std::initializer_list<value_type> il, const Compare& comp)
1216 : base_t(false, il.begin(), il.end(), comp)
1219 //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const Compare&, const allocator_type&)
1220 BOOST_CONTAINER_FORCEINLINE multiset(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1221 : base_t(false, il.begin(), il.end(), comp, a)
1224 //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>)
1225 BOOST_CONTAINER_FORCEINLINE multiset(ordered_range_t, std::initializer_list<value_type> il)
1226 : base_t(ordered_range, il.begin(), il.end())
1229 //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare&)
1230 BOOST_CONTAINER_FORCEINLINE multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1231 : base_t(ordered_range, il.begin(), il.end(), comp)
1234 //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare&, const allocator_type&)
1235 BOOST_CONTAINER_FORCEINLINE multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1236 : base_t(ordered_range, il.begin(), il.end(), comp, a)
1240 //! @copydoc ::boost::container::set::set(const set &)
1241 BOOST_CONTAINER_FORCEINLINE multiset(const multiset& x)
1242 : base_t(static_cast<const base_t&>(x))
1245 //! @copydoc ::boost::container::set::set(set &&)
1246 BOOST_CONTAINER_FORCEINLINE multiset(BOOST_RV_REF(multiset) x)
1247 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
1248 : base_t(BOOST_MOVE_BASE(base_t, x))
1251 //! @copydoc ::boost::container::set::set(const set &, const allocator_type &)
1252 BOOST_CONTAINER_FORCEINLINE multiset(const multiset& x, const allocator_type &a)
1253 : base_t(static_cast<const base_t&>(x), a)
1256 //! @copydoc ::boost::container::set::set(set &&, const allocator_type &)
1257 BOOST_CONTAINER_FORCEINLINE multiset(BOOST_RV_REF(multiset) x, const allocator_type &a)
1258 : base_t(BOOST_MOVE_BASE(base_t, x), a)
1261 //! @copydoc ::boost::container::set::operator=(const set &)
1262 BOOST_CONTAINER_FORCEINLINE multiset& operator=(BOOST_COPY_ASSIGN_REF(multiset) x)
1263 { return static_cast<multiset&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
1265 //! @copydoc ::boost::container::set::operator=(set &&)
1266 BOOST_CONTAINER_FORCEINLINE multiset& operator=(BOOST_RV_REF(multiset) x)
1267 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1268 allocator_traits_type::is_always_equal::value) &&
1269 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
1270 { return static_cast<multiset&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
1272 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1273 //! @copydoc ::boost::container::set::operator=(std::initializer_list<value_type>)
1274 multiset& operator=(std::initializer_list<value_type> il)
1277 insert(il.begin(), il.end());
1281 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1283 //! @copydoc ::boost::container::set::get_allocator()
1284 allocator_type get_allocator() const;
1286 //! @copydoc ::boost::container::set::get_stored_allocator()
1287 stored_allocator_type &get_stored_allocator();
1289 //! @copydoc ::boost::container::set::get_stored_allocator() const
1290 const stored_allocator_type &get_stored_allocator() const;
1292 //! @copydoc ::boost::container::set::begin()
1295 //! @copydoc ::boost::container::set::begin() const
1296 const_iterator begin() const;
1298 //! @copydoc ::boost::container::set::cbegin() const
1299 const_iterator cbegin() const;
1301 //! @copydoc ::boost::container::set::end()
1302 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1304 //! @copydoc ::boost::container::set::end() const
1305 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1307 //! @copydoc ::boost::container::set::cend() const
1308 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1310 //! @copydoc ::boost::container::set::rbegin()
1311 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1313 //! @copydoc ::boost::container::set::rbegin() const
1314 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1316 //! @copydoc ::boost::container::set::crbegin() const
1317 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1319 //! @copydoc ::boost::container::set::rend()
1320 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1322 //! @copydoc ::boost::container::set::rend() const
1323 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1325 //! @copydoc ::boost::container::set::crend() const
1326 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1328 //! @copydoc ::boost::container::set::empty() const
1331 //! @copydoc ::boost::container::set::size() const
1332 size_type size() const;
1334 //! @copydoc ::boost::container::set::max_size() const
1335 size_type max_size() const;
1337 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1339 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1341 //! <b>Effects</b>: Inserts an object of type Key constructed with
1342 //! std::forward<Args>(args)... and returns the iterator pointing to the
1343 //! newly inserted element.
1345 //! <b>Complexity</b>: Logarithmic.
1346 template <class... Args>
1347 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1348 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1350 //! <b>Effects</b>: Inserts an object of type Key constructed with
1351 //! std::forward<Args>(args)...
1353 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1354 //! to the key of x.
1356 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1357 //! is inserted right before p.
1358 template <class... Args>
1359 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1360 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1362 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1364 #define BOOST_CONTAINER_MULTISET_EMPLACE_CODE(N) \
1365 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1366 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1367 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1369 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1370 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1371 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1373 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTISET_EMPLACE_CODE)
1374 #undef BOOST_CONTAINER_MULTISET_EMPLACE_CODE
1376 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1378 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1379 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1380 //! newly inserted element.
1382 //! <b>Complexity</b>: Logarithmic.
1383 iterator insert(const value_type &x);
1385 //! <b>Effects</b>: Inserts a copy of x in the container.
1387 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1388 //! to the key of x.
1390 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1391 //! is inserted right before p.
1392 iterator insert(value_type &&x);
1394 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
1397 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1398 //! <b>Effects</b>: Inserts a copy of x in the container.
1399 //! p is a hint pointing to where the insert should start to search.
1401 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1402 //! to the key of x.
1404 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1405 //! is inserted right before p.
1406 iterator insert(const_iterator p, const value_type &x);
1408 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1409 //! p is a hint pointing to where the insert should start to search.
1411 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1412 //! to the key of x.
1414 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1415 //! is inserted right before p.
1416 iterator insert(const_iterator p, value_type &&x);
1418 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
1421 //! <b>Requires</b>: first, last are not iterators into *this.
1423 //! <b>Effects</b>: inserts each element from the range [first,last) .
1425 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1426 template <class InputIterator>
1427 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1428 { this->base_t::insert_equal(first, last); }
1430 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1431 //! @copydoc ::boost::container::set::insert(std::initializer_list<value_type>)
1432 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1433 { this->base_t::insert_equal(il.begin(), il.end()); }
1436 //! @copydoc ::boost::container::multimap::insert(node_type&&)
1437 BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1438 { return this->base_t::insert_equal_node(boost::move(nh)); }
1440 //! @copydoc ::boost::container::multimap::insert(const_iterator, node_type&&)
1441 BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1442 { return this->base_t::insert_equal_node(hint, boost::move(nh)); }
1444 //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1446 BOOST_CONTAINER_FORCEINLINE void merge(multiset<Key, C2, Allocator, Options>& source)
1449 <Key, void, C2, Allocator, Options> base2_t;
1450 this->base_t::merge_equal(static_cast<base2_t&>(source));
1453 //! @copydoc ::boost::container::multiset::merge(multiset<Key, C2, Allocator, Options>&)
1455 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multiset<Key, C2, Allocator, Options> BOOST_RV_REF_END source)
1456 { return this->merge(static_cast<multiset<Key, C2, Allocator, Options>&>(source)); }
1458 //! @copydoc ::boost::container::multimap::merge(map<Key, T, C2, Allocator, Options>&)
1460 BOOST_CONTAINER_FORCEINLINE void merge(set<Key, C2, Allocator, Options>& source)
1463 <Key, void, C2, Allocator, Options> base2_t;
1464 this->base_t::merge_equal(static_cast<base2_t&>(source));
1467 //! @copydoc ::boost::container::multiset::merge(set<Key, C2, Allocator, Options>&)
1469 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG set<Key, C2, Allocator, Options> BOOST_RV_REF_END source)
1470 { return this->merge(static_cast<set<Key, C2, Allocator, Options>&>(source)); }
1472 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1474 //! @copydoc ::boost::container::set::erase(const_iterator)
1475 iterator erase(const_iterator p);
1477 //! @copydoc ::boost::container::set::erase(const key_type&)
1478 size_type erase(const key_type& x);
1480 //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
1481 iterator erase(const_iterator first, const_iterator last);
1483 //! @copydoc ::boost::container::multimap::extract(const_iterator)
1484 node_type extract(const_iterator p);
1486 //! @copydoc ::boost::container::multimap::extract(const key_type&)
1487 node_type extract(const key_type& x);
1489 //! @copydoc ::boost::container::set::swap
1490 void swap(multiset& x)
1491 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1492 && boost::container::dtl::is_nothrow_swappable<Compare>::value );
1494 //! @copydoc ::boost::container::set::clear
1495 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1497 //! @copydoc ::boost::container::set::key_comp
1498 key_compare key_comp() const;
1500 //! @copydoc ::boost::container::set::value_comp
1501 value_compare value_comp() const;
1503 //! @copydoc ::boost::container::set::find(const key_type& )
1504 iterator find(const key_type& x);
1506 //! @copydoc ::boost::container::set::find(const key_type& ) const
1507 const_iterator find(const key_type& x) const;
1509 //! @copydoc ::boost::container::set::find(const K& )
1510 template<typename K>
1511 iterator find(const K& x);
1513 //! @copydoc ::boost::container::set::find(const K& )
1514 template<typename K>
1515 const_iterator find(const K& x) const;
1517 //! @copydoc ::boost::container::set::count(const key_type& ) const
1518 size_type count(const key_type& x) const;
1520 //! @copydoc ::boost::container::set::count(const K& ) const
1521 template<typename K>
1522 size_type count(const K& x) const;
1524 //! @copydoc ::boost::container::set::contains(const key_type& ) const
1525 bool contains(const key_type& x) const;
1527 //! @copydoc ::boost::container::set::contains(const K& ) const
1528 template<typename K>
1529 bool contains(const K& x) const;
1531 //! @copydoc ::boost::container::set::lower_bound(const key_type& )
1532 iterator lower_bound(const key_type& x);
1534 //! @copydoc ::boost::container::set::lower_bound(const key_type& ) const
1535 const_iterator lower_bound(const key_type& x) const;
1537 //! @copydoc ::boost::container::set::lower_bound(const K& )
1538 template<typename K>
1539 iterator lower_bound(const K& x);
1541 //! @copydoc ::boost::container::set::lower_bound(const K& ) const
1542 template<typename K>
1543 const_iterator lower_bound(const K& x) const;
1545 //! @copydoc ::boost::container::set::upper_bound(const key_type& )
1546 iterator upper_bound(const key_type& x);
1548 //! @copydoc ::boost::container::set::upper_bound(const key_type& ) const
1549 const_iterator upper_bound(const key_type& x) const;
1551 //! @copydoc ::boost::container::set::upper_bound(const K& )
1552 template<typename K>
1553 iterator upper_bound(const K& x);
1555 //! @copydoc ::boost::container::set::upper_bound(const K& ) const
1556 template<typename K>
1557 const_iterator upper_bound(const K& x) const;
1559 //! @copydoc ::boost::container::set::equal_range(const key_type& ) const
1560 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1562 //! @copydoc ::boost::container::set::equal_range(const key_type& )
1563 std::pair<iterator,iterator> equal_range(const key_type& x);
1565 //! @copydoc ::boost::container::set::equal_range(const K& ) const
1566 template<typename K>
1567 std::pair<const_iterator, const_iterator> equal_range(const K& x) const;
1569 //! @copydoc ::boost::container::set::equal_range(const K& )
1570 template<typename K>
1571 std::pair<iterator,iterator> equal_range(const K& x);
1573 //! @copydoc ::boost::container::set::rebalance()
1576 //! <b>Effects</b>: Returns true if x and y are equal
1578 //! <b>Complexity</b>: Linear to the number of elements in the container.
1579 friend bool operator==(const multiset& x, const multiset& y);
1581 //! <b>Effects</b>: Returns true if x and y are unequal
1583 //! <b>Complexity</b>: Linear to the number of elements in the container.
1584 friend bool operator!=(const multiset& x, const multiset& y);
1586 //! <b>Effects</b>: Returns true if x is less than y
1588 //! <b>Complexity</b>: Linear to the number of elements in the container.
1589 friend bool operator<(const multiset& x, const multiset& y);
1591 //! <b>Effects</b>: Returns true if x is greater than y
1593 //! <b>Complexity</b>: Linear to the number of elements in the container.
1594 friend bool operator>(const multiset& x, const multiset& y);
1596 //! <b>Effects</b>: Returns true if x is equal or less than y
1598 //! <b>Complexity</b>: Linear to the number of elements in the container.
1599 friend bool operator<=(const multiset& x, const multiset& y);
1601 //! <b>Effects</b>: Returns true if x is equal or greater than y
1603 //! <b>Complexity</b>: Linear to the number of elements in the container.
1604 friend bool operator>=(const multiset& x, const multiset& y);
1606 //! <b>Effects</b>: x.swap(y)
1608 //! <b>Complexity</b>: Constant.
1609 friend void swap(multiset& x, multiset& y);
1611 #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1613 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1615 template <class KeyType>
1616 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1617 { return this->base_t::insert_equal(::boost::forward<KeyType>(x)); }
1619 template <class KeyType>
1620 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1621 { return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
1623 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1626 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1628 template <typename InputIterator>
1629 multiset(InputIterator, InputIterator) ->
1630 multiset< it_based_value_type_t<InputIterator> >;
1633 template < typename InputIterator, typename AllocatorOrCompare>
1634 multiset(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1635 multiset < it_based_value_type_t<InputIterator>
1636 , typename dtl::if_c< // Compare
1637 dtl::is_allocator<AllocatorOrCompare>::value
1638 , std::less<it_based_value_type_t<InputIterator>>
1639 , AllocatorOrCompare
1641 , typename dtl::if_c< // Allocator
1642 dtl::is_allocator<AllocatorOrCompare>::value
1643 , AllocatorOrCompare
1644 , new_allocator<it_based_value_type_t<InputIterator>>
1648 template < typename InputIterator, typename Compare, typename Allocator
1649 , typename = dtl::require_nonallocator_t<Compare>
1650 , typename = dtl::require_allocator_t<Allocator>>
1651 multiset(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1652 multiset< it_based_value_type_t<InputIterator>
1656 template <typename InputIterator>
1657 multiset(ordered_range_t, InputIterator, InputIterator) ->
1658 multiset< it_based_value_type_t<InputIterator>>;
1660 template < typename InputIterator, typename AllocatorOrCompare>
1661 multiset(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1662 multiset < it_based_value_type_t<InputIterator>
1663 , typename dtl::if_c< // Compare
1664 dtl::is_allocator<AllocatorOrCompare>::value
1665 , std::less<it_based_value_type_t<InputIterator>>
1666 , AllocatorOrCompare
1668 , typename dtl::if_c< // Allocator
1669 dtl::is_allocator<AllocatorOrCompare>::value
1670 , AllocatorOrCompare
1671 , new_allocator<it_based_value_type_t<InputIterator>>
1675 template < typename InputIterator, typename Compare, typename Allocator
1676 , typename = dtl::require_nonallocator_t<Compare>
1677 , typename = dtl::require_allocator_t<Allocator>>
1678 multiset(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1679 multiset< it_based_value_type_t<InputIterator>
1685 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1687 } //namespace container {
1689 //!has_trivial_destructor_after_move<> == true_type
1690 //!specialization for optimizations
1691 template <class Key, class Compare, class Allocator, class Options>
1692 struct has_trivial_destructor_after_move<boost::container::multiset<Key, Compare, Allocator, Options> >
1694 typedef ::boost::container::dtl::tree<Key, void, Compare, Allocator, Options> tree;
1695 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1698 namespace container {
1700 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1704 #include <boost/container/detail/config_end.hpp>
1706 #endif // BOOST_CONTAINER_SET_HPP