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 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_FLAT_SET_HPP
11 #define BOOST_CONTAINER_FLAT_SET_HPP
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
25 #include <boost/container/allocator_traits.hpp>
26 #include <boost/container/container_fwd.hpp>
27 #include <boost/container/new_allocator.hpp> //new_allocator
29 #include <boost/container/detail/flat_tree.hpp>
30 #include <boost/container/detail/mpl.hpp>
32 #include <boost/move/traits.hpp>
33 #include <boost/move/utility_core.hpp>
35 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
36 #include <boost/move/detail/fwd_macros.hpp>
38 #include <boost/move/detail/move_helpers.hpp>
40 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
41 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
43 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
44 #include <initializer_list>
50 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
51 template <class Key, class Compare, class AllocatorOrContainer>
55 //! flat_set is a Sorted Associative Container that stores objects of type Key.
56 //! It is also a Unique Associative Container, meaning that no two elements are the same.
58 //! flat_set is similar to std::set but it's implemented by as an ordered sequence container.
59 //! The underlying sequence container is by default <i>vector</i> but it can also work
60 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
62 //! Using vector-like sequence containers means that inserting a new element into a flat_set might invalidate
63 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
64 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
65 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
67 //! This container provides random-access iterators.
69 //! \tparam Key is the type to be inserted in the set, which is also the key_type
70 //! \tparam Compare is the comparison functor used to order keys
71 //! \tparam AllocatorOrContainer is either:
72 //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
73 //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
74 //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
75 //! sequence container with random-access iterators.
76 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
77 template <class Key, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator<Key> >
79 template <class Key, class Compare, class AllocatorOrContainer>
83 : public dtl::flat_tree<Key, dtl::identity<Key>, Compare, AllocatorOrContainer>
86 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
88 BOOST_COPYABLE_AND_MOVABLE(flat_set)
89 typedef dtl::flat_tree<Key, dtl::identity<Key>, Compare, AllocatorOrContainer> tree_t;
95 const tree_t &tree() const
98 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
101 //////////////////////////////////////////////
105 //////////////////////////////////////////////
106 typedef Key key_type;
107 typedef Compare key_compare;
108 typedef Key value_type;
109 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type;
110 typedef typename sequence_type::allocator_type allocator_type;
111 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
112 typedef typename sequence_type::pointer pointer;
113 typedef typename sequence_type::const_pointer const_pointer;
114 typedef typename sequence_type::reference reference;
115 typedef typename sequence_type::const_reference const_reference;
116 typedef typename sequence_type::size_type size_type;
117 typedef typename sequence_type::difference_type difference_type;
118 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
119 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare;
121 typedef typename sequence_type::iterator iterator;
122 typedef typename sequence_type::const_iterator const_iterator;
123 typedef typename sequence_type::reverse_iterator reverse_iterator;
124 typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
127 //////////////////////////////////////////////
129 // construct/copy/destroy
131 //////////////////////////////////////////////
133 //! <b>Effects</b>: Default constructs an empty container.
135 //! <b>Complexity</b>: Constant.
136 BOOST_CONTAINER_FORCEINLINE
137 flat_set() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
138 dtl::is_nothrow_default_constructible<Compare>::value)
142 //! <b>Effects</b>: Constructs an empty container using the specified
143 //! comparison object.
145 //! <b>Complexity</b>: Constant.
146 BOOST_CONTAINER_FORCEINLINE
147 explicit flat_set(const Compare& comp)
151 //! <b>Effects</b>: Constructs an empty container using the specified allocator.
153 //! <b>Complexity</b>: Constant.
154 BOOST_CONTAINER_FORCEINLINE
155 explicit flat_set(const allocator_type& a)
159 //! <b>Effects</b>: Constructs an empty container using the specified
160 //! comparison object and allocator.
162 //! <b>Complexity</b>: Constant.
163 BOOST_CONTAINER_FORCEINLINE
164 flat_set(const Compare& comp, const allocator_type& a)
168 //! <b>Effects</b>: Constructs an empty container and
169 //! inserts elements from the range [first ,last ).
171 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
172 //! comp and otherwise N logN, where N is last - first.
173 template <class InputIterator>
174 BOOST_CONTAINER_FORCEINLINE
175 flat_set(InputIterator first, InputIterator last)
176 : tree_t(true, first, last)
179 //! <b>Effects</b>: Constructs an empty container using the specified
180 //! allocator, and inserts elements from the range [first ,last ).
182 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
183 //! comp and otherwise N logN, where N is last - first.
184 template <class InputIterator>
185 BOOST_CONTAINER_FORCEINLINE
186 flat_set(InputIterator first, InputIterator last, const allocator_type& a)
187 : tree_t(true, first, last, a)
190 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
191 //! inserts elements from the range [first ,last ).
193 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
194 //! comp and otherwise N logN, where N is last - first.
195 template <class InputIterator>
196 BOOST_CONTAINER_FORCEINLINE
197 flat_set(InputIterator first, InputIterator last, const Compare& comp)
198 : tree_t(true, first, last, comp)
201 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
202 //! allocator, and inserts elements from the range [first ,last ).
204 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
205 //! comp and otherwise N logN, where N is last - first.
206 template <class InputIterator>
207 BOOST_CONTAINER_FORCEINLINE
208 flat_set(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
209 : tree_t(true, first, last, comp, a)
212 //! <b>Effects</b>: Constructs an empty container and
213 //! inserts elements from the ordered unique range [first ,last). This function
214 //! is more efficient than the normal range creation for ordered ranges.
216 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
219 //! <b>Complexity</b>: Linear in N.
221 //! <b>Note</b>: Non-standard extension.
222 template <class InputIterator>
223 BOOST_CONTAINER_FORCEINLINE
224 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last)
225 : tree_t(ordered_unique_range, first, last)
228 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
229 //! inserts elements from the ordered unique range [first ,last). This function
230 //! is more efficient than the normal range creation for ordered ranges.
232 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
235 //! <b>Complexity</b>: Linear in N.
237 //! <b>Note</b>: Non-standard extension.
238 template <class InputIterator>
239 BOOST_CONTAINER_FORCEINLINE
240 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
241 : tree_t(ordered_unique_range, first, last, comp)
244 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
245 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
246 //! is more efficient than the normal range creation for ordered ranges.
248 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
251 //! <b>Complexity</b>: Linear in N.
253 //! <b>Note</b>: Non-standard extension.
254 template <class InputIterator>
255 BOOST_CONTAINER_FORCEINLINE
256 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
257 : tree_t(ordered_unique_range, first, last, comp, a)
260 //! <b>Effects</b>: Constructs an empty container using the specified allocator and
261 //! inserts elements from the ordered unique range [first ,last). This function
262 //! is more efficient than the normal range creation for ordered ranges.
264 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
267 //! <b>Complexity</b>: Linear in N.
269 //! <b>Note</b>: Non-standard extension.
270 template <class InputIterator>
271 BOOST_CONTAINER_FORCEINLINE
272 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
273 : tree_t(ordered_unique_range, first, last, Compare(), a)
276 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
277 //! <b>Effects</b>: Constructs an empty container and
278 //! inserts elements from the range [il.begin(), il.end()).
280 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
281 //! comp and otherwise N logN, where N is il.begin() - il.end().
282 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il)
283 : tree_t(true, il.begin(), il.end())
286 //! <b>Effects</b>: Constructs an empty container using the specified
287 //! allocator, and inserts elements from the range [il.begin(), il.end()).
289 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
290 //! comp and otherwise N logN, where N is il.begin() - il.end().
291 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const allocator_type& a)
292 : tree_t(true, il.begin(), il.end(), a)
295 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
296 //! inserts elements from the range [il.begin(), il.end()).
298 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
299 //! comp and otherwise N logN, where N is il.begin() - il.end().
300 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const Compare& comp)
301 : tree_t(true, il.begin(), il.end(), comp)
304 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
305 //! allocator, and inserts elements from the range [il.begin(), il.end()).
307 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
308 //! comp and otherwise N logN, where N is il.begin() - il.end().
309 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
310 : tree_t(true, il.begin(), il.end(), comp, a)
313 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
314 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
315 //! is more efficient than the normal range creation for ordered ranges.
317 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
320 //! <b>Complexity</b>: Linear in N.
322 //! <b>Note</b>: Non-standard extension.
323 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il)
324 : tree_t(ordered_unique_range, il.begin(), il.end())
327 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
328 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
329 //! is more efficient than the normal range creation for ordered ranges.
331 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
334 //! <b>Complexity</b>: Linear in N.
336 //! <b>Note</b>: Non-standard extension.
337 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
338 : tree_t(ordered_unique_range, il.begin(), il.end(), comp)
341 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
342 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
343 //! is more efficient than the normal range creation for ordered ranges.
345 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
348 //! <b>Complexity</b>: Linear in N.
350 //! <b>Note</b>: Non-standard extension.
351 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
352 : tree_t(ordered_unique_range, il.begin(), il.end(), comp, a)
356 //! <b>Effects</b>: Copy constructs the container.
358 //! <b>Complexity</b>: Linear in x.size().
359 BOOST_CONTAINER_FORCEINLINE flat_set(const flat_set& x)
360 : tree_t(static_cast<const tree_t&>(x))
363 //! <b>Effects</b>: Move constructs thecontainer. Constructs *this using x's resources.
365 //! <b>Complexity</b>: Constant.
367 //! <b>Postcondition</b>: x is emptied.
368 BOOST_CONTAINER_FORCEINLINE flat_set(BOOST_RV_REF(flat_set) x)
369 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
370 : tree_t(BOOST_MOVE_BASE(tree_t, x))
373 //! <b>Effects</b>: Copy constructs a container using the specified allocator.
375 //! <b>Complexity</b>: Linear in x.size().
376 BOOST_CONTAINER_FORCEINLINE flat_set(const flat_set& x, const allocator_type &a)
377 : tree_t(static_cast<const tree_t&>(x), a)
380 //! <b>Effects</b>: Move constructs a container using the specified allocator.
381 //! Constructs *this using x's resources.
383 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
384 BOOST_CONTAINER_FORCEINLINE flat_set(BOOST_RV_REF(flat_set) x, const allocator_type &a)
385 : tree_t(BOOST_MOVE_BASE(tree_t, x), a)
388 //! <b>Effects</b>: Makes *this a copy of x.
390 //! <b>Complexity</b>: Linear in x.size().
391 BOOST_CONTAINER_FORCEINLINE flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x)
392 { return static_cast<flat_set&>(this->tree_t::operator=(static_cast<const tree_t&>(x))); }
394 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
395 //! is false and (allocation throws or value_type's move constructor throws)
397 //! <b>Complexity</b>: Constant if allocator_traits_type::
398 //! propagate_on_container_move_assignment is true or
399 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
400 BOOST_CONTAINER_FORCEINLINE flat_set& operator=(BOOST_RV_REF(flat_set) x)
401 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
402 allocator_traits_type::is_always_equal::value) &&
403 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
404 { return static_cast<flat_set&>(this->tree_t::operator=(BOOST_MOVE_BASE(tree_t, x))); }
406 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
407 //! <b>Effects</b>: Copy all elements from il to *this.
409 //! <b>Complexity</b>: Linear in il.size().
410 flat_set& operator=(std::initializer_list<value_type> il)
413 this->insert(il.begin(), il.end());
418 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
419 //! <b>Effects</b>: Returns a copy of the allocator that
420 //! was passed to the object's constructor.
422 //! <b>Complexity</b>: Constant.
423 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
425 //! <b>Effects</b>: Returns a reference to the internal allocator.
427 //! <b>Throws</b>: Nothing
429 //! <b>Complexity</b>: Constant.
431 //! <b>Note</b>: Non-standard extension.
432 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
434 //! <b>Effects</b>: Returns a reference to the internal allocator.
436 //! <b>Throws</b>: Nothing
438 //! <b>Complexity</b>: Constant.
440 //! <b>Note</b>: Non-standard extension.
441 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
443 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
445 //! <b>Throws</b>: Nothing.
447 //! <b>Complexity</b>: Constant.
448 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
450 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
452 //! <b>Throws</b>: Nothing.
454 //! <b>Complexity</b>: Constant.
455 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
457 //! <b>Effects</b>: Returns an iterator to the end of the container.
459 //! <b>Throws</b>: Nothing.
461 //! <b>Complexity</b>: Constant.
462 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
464 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
466 //! <b>Throws</b>: Nothing.
468 //! <b>Complexity</b>: Constant.
469 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
471 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
472 //! of the reversed container.
474 //! <b>Throws</b>: Nothing.
476 //! <b>Complexity</b>: Constant.
477 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
479 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
480 //! of the reversed container.
482 //! <b>Throws</b>: Nothing.
484 //! <b>Complexity</b>: Constant.
485 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
487 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
488 //! of the reversed container.
490 //! <b>Throws</b>: Nothing.
492 //! <b>Complexity</b>: Constant.
493 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
495 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
496 //! of the reversed container.
498 //! <b>Throws</b>: Nothing.
500 //! <b>Complexity</b>: Constant.
501 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
503 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
505 //! <b>Throws</b>: Nothing.
507 //! <b>Complexity</b>: Constant.
508 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
510 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
512 //! <b>Throws</b>: Nothing.
514 //! <b>Complexity</b>: Constant.
515 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
517 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
518 //! of the reversed container.
520 //! <b>Throws</b>: Nothing.
522 //! <b>Complexity</b>: Constant.
523 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
525 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
526 //! of the reversed container.
528 //! <b>Throws</b>: Nothing.
530 //! <b>Complexity</b>: Constant.
531 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
533 //! <b>Effects</b>: Returns true if the container contains no elements.
535 //! <b>Throws</b>: Nothing.
537 //! <b>Complexity</b>: Constant.
538 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
540 //! <b>Effects</b>: Returns the number of the elements contained in the container.
542 //! <b>Throws</b>: Nothing.
544 //! <b>Complexity</b>: Constant.
545 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
547 //! <b>Effects</b>: Returns the largest possible size of the container.
549 //! <b>Throws</b>: Nothing.
551 //! <b>Complexity</b>: Constant.
552 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
554 //! <b>Effects</b>: Number of elements for which memory has been allocated.
555 //! capacity() is always greater than or equal to size().
557 //! <b>Throws</b>: Nothing.
559 //! <b>Complexity</b>: Constant.
560 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
562 //! <b>Effects</b>: If n is less than or equal to capacity(), or the
563 //! underlying container has no `reserve` member, this call has no
564 //! effect. Otherwise, it is a request for allocation of additional memory.
565 //! If the request is successful, then capacity() is greater than or equal to
566 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
568 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
570 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
571 //! to values might be invalidated.
572 void reserve(size_type cnt);
574 //! <b>Effects</b>: Tries to deallocate the excess of memory created
575 // with previous allocations. The size of the vector is unchanged
577 //! <b>Throws</b>: If memory allocation throws, or Key's copy constructor throws.
579 //! <b>Complexity</b>: Linear to size().
580 void shrink_to_fit();
582 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
584 //////////////////////////////////////////////
588 //////////////////////////////////////////////
590 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
592 //! <b>Effects</b>: Inserts an object x of type Key constructed with
593 //! std::forward<Args>(args)... if and only if there is no element in the container
594 //! with key equivalent to the key of x.
596 //! <b>Returns</b>: The bool component of the returned pair is true if and only
597 //! if the insertion takes place, and the iterator component of the pair
598 //! points to the element with key equivalent to the key of x.
600 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
601 //! to the elements with bigger keys than x.
603 //! <b>Note</b>: If an element is inserted it might invalidate elements.
604 template <class... Args>
605 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
606 { return this->tree_t::emplace_unique(boost::forward<Args>(args)...); }
608 //! <b>Effects</b>: Inserts an object of type Key constructed with
609 //! std::forward<Args>(args)... in the container if and only if there is
610 //! no element in the container with key equivalent to the key of x.
611 //! p is a hint pointing to where the insert should start to search.
613 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
616 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
617 //! right before p) plus insertion linear to the elements with bigger keys than x.
619 //! <b>Note</b>: If an element is inserted it might invalidate elements.
620 template <class... Args>
621 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
622 { return this->tree_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
624 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
626 #define BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE(N) \
627 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
628 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
629 { return this->tree_t::emplace_unique(BOOST_MOVE_FWD##N); }\
631 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
632 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
633 { return this->tree_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
635 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE)
636 #undef BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE
638 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
640 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
641 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
642 //! with key equivalent to the key of x.
644 //! <b>Returns</b>: The bool component of the returned pair is true if and only
645 //! if the insertion takes place, and the iterator component of the pair
646 //! points to the element with key equivalent to the key of x.
648 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
649 //! to the elements with bigger keys than x.
651 //! <b>Note</b>: If an element is inserted it might invalidate elements.
652 std::pair<iterator, bool> insert(const value_type &x);
654 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
655 //! only if there is no element in the container with key equivalent to the key of x.
657 //! <b>Returns</b>: The bool component of the returned pair is true if and only
658 //! if the insertion takes place, and the iterator component of the pair
659 //! points to the element with key equivalent to the key of x.
661 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
662 //! to the elements with bigger keys than x.
664 //! <b>Note</b>: If an element is inserted it might invalidate elements.
665 std::pair<iterator, bool> insert(value_type &&x);
668 typedef std::pair<iterator, bool> insert_return_pair;
670 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
673 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
674 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
675 //! no element in the container with key equivalent to the key of x.
676 //! p is a hint pointing to where the insert should start to search.
678 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
681 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
682 //! right before p) plus insertion linear to the elements with bigger keys than x.
684 //! <b>Note</b>: If an element is inserted it might invalidate elements.
685 iterator insert(const_iterator p, const value_type &x);
687 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
688 //! p is a hint pointing to where the insert should start to search.
690 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
692 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
693 //! right before p) plus insertion linear to the elements with bigger keys than x.
695 //! <b>Note</b>: If an element is inserted it might invalidate elements.
696 iterator insert(const_iterator p, value_type &&x);
698 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
701 //! <b>Requires</b>: first, last are not iterators into *this.
703 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
704 //! if there is no element with key equivalent to the key of that element.
706 //! <b>Complexity</b>: N log(N).
708 //! <b>Note</b>: If an element is inserted it might invalidate elements.
709 template <class InputIterator>
710 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
711 { this->tree_t::insert_unique(first, last); }
713 //! <b>Requires</b>: first, last are not iterators into *this and
714 //! must be ordered according to the predicate and must be
717 //! <b>Effects</b>: inserts each element from the range [first,last) .This function
718 //! is more efficient than the normal range creation for ordered ranges.
720 //! <b>Complexity</b>: Linear.
722 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
723 template <class InputIterator>
724 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
725 { this->tree_t::insert_unique(ordered_unique_range, first, last); }
727 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
728 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
729 //! if there is no element with key equivalent to the key of that element.
731 //! <b>Complexity</b>: N log(N).
733 //! <b>Note</b>: If an element is inserted it might invalidate elements.
734 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
735 { this->tree_t::insert_unique(il.begin(), il.end()); }
737 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate
738 //! and must be unique values.
740 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .This function
741 //! is more efficient than the normal range creation for ordered ranges.
743 //! <b>Complexity</b>: Linear.
745 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
746 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
747 { this->tree_t::insert_unique(ordered_unique_range, il.begin(), il.end()); }
750 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
752 BOOST_CONTAINER_FORCEINLINE void merge(flat_set<Key, C2, AllocatorOrContainer>& source)
753 { this->tree_t::merge_unique(source.tree()); }
755 //! @copydoc ::boost::container::flat_set::merge(flat_set<Key, C2, AllocatorOrContainer>&)
757 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_set<Key, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
758 { return this->merge(static_cast<flat_set<Key, C2, AllocatorOrContainer>&>(source)); }
760 //! @copydoc ::boost::container::flat_map::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
762 BOOST_CONTAINER_FORCEINLINE void merge(flat_multiset<Key, C2, AllocatorOrContainer>& source)
763 { this->tree_t::merge_unique(source.tree()); }
765 //! @copydoc ::boost::container::flat_set::merge(flat_multiset<Key, C2, AllocatorOrContainer>&)
767 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multiset<Key, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
768 { return this->merge(static_cast<flat_multiset<Key, C2, AllocatorOrContainer>&>(source)); }
770 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
772 //! <b>Effects</b>: Erases the element pointed to by p.
774 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
775 //! following q prior to the element being erased. If no such element exists,
778 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
780 //! <b>Note</b>: Invalidates elements with keys
781 //! not less than the erased element.
782 iterator erase(const_iterator p);
784 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
786 //! <b>Returns</b>: Returns the number of erased elements.
788 //! <b>Complexity</b>: Logarithmic search time plus erasure time
789 //! linear to the elements with bigger keys.
790 size_type erase(const key_type& x);
792 //! <b>Effects</b>: Erases all the elements in the range [first, last).
794 //! <b>Returns</b>: Returns last.
796 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
798 //! <b>Complexity</b>: Logarithmic search time plus erasure time
799 //! linear to the elements with bigger keys.
800 iterator erase(const_iterator first, const_iterator last);
802 //! <b>Effects</b>: Swaps the contents of *this and x.
804 //! <b>Throws</b>: Nothing.
806 //! <b>Complexity</b>: Constant.
807 void swap(flat_set& x)
808 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
809 && boost::container::dtl::is_nothrow_swappable<Compare>::value );
811 //! <b>Effects</b>: erase(begin(),end()).
813 //! <b>Postcondition</b>: size() == 0.
815 //! <b>Complexity</b>: linear in size().
816 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
818 //! <b>Effects</b>: Returns the comparison object out
819 //! of which a was constructed.
821 //! <b>Complexity</b>: Constant.
822 key_compare key_comp() const;
824 //! <b>Effects</b>: Returns an object of value_compare constructed out
825 //! of the comparison object.
827 //! <b>Complexity</b>: Constant.
828 value_compare value_comp() const;
830 //! <b>Returns</b>: An iterator pointing to an element with the key
831 //! equivalent to x, or end() if such an element is not found.
833 //! <b>Complexity</b>: Logarithmic.
834 iterator find(const key_type& x);
836 //! <b>Returns</b>: A const_iterator pointing to an element with the key
837 //! equivalent to x, or end() if such an element is not found.
839 //! <b>Complexity</b>: Logarithmic.
840 const_iterator find(const key_type& x) const;
842 //! <b>Requires</b>: This overload is available only if
843 //! key_compare::is_transparent exists.
845 //! <b>Returns</b>: An iterator pointing to an element with the key
846 //! equivalent to x, or end() if such an element is not found.
848 //! <b>Complexity</b>: Logarithmic.
850 iterator find(const K& x);
852 //! <b>Requires</b>: This overload is available only if
853 //! key_compare::is_transparent exists.
855 //! <b>Returns</b>: A const_iterator pointing to an element with the key
856 //! equivalent to x, or end() if such an element is not found.
858 //! <b>Complexity</b>: Logarithmic.
860 const_iterator find(const K& x) const;
862 //! <b>Requires</b>: size() >= n.
864 //! <b>Effects</b>: Returns an iterator to the nth element
865 //! from the beginning of the container. Returns end()
868 //! <b>Throws</b>: Nothing.
870 //! <b>Complexity</b>: Constant.
872 //! <b>Note</b>: Non-standard extension
873 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
875 //! <b>Requires</b>: size() >= n.
877 //! <b>Effects</b>: Returns a const_iterator to the nth element
878 //! from the beginning of the container. Returns end()
881 //! <b>Throws</b>: Nothing.
883 //! <b>Complexity</b>: Constant.
885 //! <b>Note</b>: Non-standard extension
886 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
888 //! <b>Requires</b>: begin() <= p <= end().
890 //! <b>Effects</b>: Returns the index of the element pointed by p
891 //! and size() if p == end().
893 //! <b>Throws</b>: Nothing.
895 //! <b>Complexity</b>: Constant.
897 //! <b>Note</b>: Non-standard extension
898 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
900 //! <b>Requires</b>: begin() <= p <= end().
902 //! <b>Effects</b>: Returns the index of the element pointed by p
903 //! and size() if p == end().
905 //! <b>Throws</b>: Nothing.
907 //! <b>Complexity</b>: Constant.
909 //! <b>Note</b>: Non-standard extension
910 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
912 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
914 //! <b>Returns</b>: The number of elements with key equivalent to x.
916 //! <b>Complexity</b>: log(size())+count(k)
917 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
918 { return static_cast<size_type>(this->tree_t::find(x) != this->tree_t::cend()); }
920 //! <b>Requires</b>: This overload is available only if
921 //! key_compare::is_transparent exists.
923 //! <b>Returns</b>: The number of elements with key equivalent to x.
925 //! <b>Complexity</b>: log(size())+count(k)
927 BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
928 //Don't use find() != end optimization here as transparent comparators with key K might
929 //return a different range than key_type (which can only return a single element range)
930 { return this->tree_t::count(x); }
932 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
934 //! <b>Returns</b>: Returns true if there is an element with key
935 //! equivalent to key in the container, otherwise false.
937 //! <b>Complexity</b>: log(size()).
938 bool contains(const key_type& x) const;
940 //! <b>Requires</b>: This overload is available only if
941 //! key_compare::is_transparent exists.
943 //! <b>Returns</b>: Returns true if there is an element with key
944 //! equivalent to key in the container, otherwise false.
946 //! <b>Complexity</b>: log(size()).
948 bool contains(const K& x) const;
950 //! <b>Returns</b>: An iterator pointing to the first element with key not less
951 //! than x, or end() if such an element is not found.
953 //! <b>Complexity</b>: Logarithmic
954 iterator lower_bound(const key_type& x);
956 //! <b>Returns</b>: A const iterator pointing to the first element with key not
957 //! less than x, or end() if such an element is not found.
959 //! <b>Complexity</b>: Logarithmic
960 const_iterator lower_bound(const key_type& x) const;
962 //! <b>Requires</b>: This overload is available only if
963 //! key_compare::is_transparent exists.
965 //! <b>Returns</b>: An iterator pointing to the first element with key not less
966 //! than x, or end() if such an element is not found.
968 //! <b>Complexity</b>: Logarithmic
970 iterator lower_bound(const K& x);
972 //! <b>Requires</b>: This overload is available only if
973 //! key_compare::is_transparent exists.
975 //! <b>Returns</b>: A const iterator pointing to the first element with key not
976 //! less than x, or end() if such an element is not found.
978 //! <b>Complexity</b>: Logarithmic
980 const_iterator lower_bound(const K& x) const;
982 //! <b>Returns</b>: An iterator pointing to the first element with key greater
983 //! than x, or end() if such an element is not found.
985 //! <b>Complexity</b>: Logarithmic
986 iterator upper_bound(const key_type& x);
988 //! <b>Returns</b>: A const iterator pointing to the first element with key
989 //! greater than x, or end() if such an element is not found.
991 //! <b>Complexity</b>: Logarithmic
992 const_iterator upper_bound(const key_type& x) const;
994 //! <b>Requires</b>: This overload is available only if
995 //! key_compare::is_transparent exists.
997 //! <b>Returns</b>: An iterator pointing to the first element with key greater
998 //! than x, or end() if such an element is not found.
1000 //! <b>Complexity</b>: Logarithmic
1001 template<typename K>
1002 iterator upper_bound(const K& x);
1004 //! <b>Requires</b>: This overload is available only if
1005 //! key_compare::is_transparent exists.
1007 //! <b>Returns</b>: A const iterator pointing to the first element with key
1008 //! greater than x, or end() if such an element is not found.
1010 //! <b>Complexity</b>: Logarithmic
1011 template<typename K>
1012 const_iterator upper_bound(const K& x) const;
1014 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1016 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1018 //! <b>Complexity</b>: Logarithmic
1019 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
1020 { return this->tree_t::lower_bound_range(x); }
1022 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1024 //! <b>Complexity</b>: Logarithmic
1025 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
1026 { return this->tree_t::lower_bound_range(x); }
1028 //! <b>Requires</b>: This overload is available only if
1029 //! key_compare::is_transparent exists.
1031 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1033 //! <b>Complexity</b>: Logarithmic
1034 template<typename K>
1035 std::pair<iterator,iterator> equal_range(const K& x)
1036 //Don't use lower_bound_range optimization here as transparent comparators with key K might
1037 //return a different range than key_type (which can only return a single element range)
1038 { return this->tree_t::equal_range(x); }
1040 //! <b>Requires</b>: This overload is available only if
1041 //! key_compare::is_transparent exists.
1043 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1045 //! <b>Complexity</b>: Logarithmic
1046 template<typename K>
1047 std::pair<const_iterator,const_iterator> equal_range(const K& x) const
1048 //Don't use lower_bound_range optimization here as transparent comparators with key K might
1049 //return a different range than key_type (which can only return a single element range)
1050 { return this->tree_t::equal_range(x); }
1052 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1054 //! <b>Effects</b>: Returns true if x and y are equal
1056 //! <b>Complexity</b>: Linear to the number of elements in the container.
1057 friend bool operator==(const flat_set& x, const flat_set& y);
1059 //! <b>Effects</b>: Returns true if x and y are unequal
1061 //! <b>Complexity</b>: Linear to the number of elements in the container.
1062 friend bool operator!=(const flat_set& x, const flat_set& y);
1064 //! <b>Effects</b>: Returns true if x is less than y
1066 //! <b>Complexity</b>: Linear to the number of elements in the container.
1067 friend bool operator<(const flat_set& x, const flat_set& y);
1069 //! <b>Effects</b>: Returns true if x is greater than y
1071 //! <b>Complexity</b>: Linear to the number of elements in the container.
1072 friend bool operator>(const flat_set& x, const flat_set& y);
1074 //! <b>Effects</b>: Returns true if x is equal or less than y
1076 //! <b>Complexity</b>: Linear to the number of elements in the container.
1077 friend bool operator<=(const flat_set& x, const flat_set& y);
1079 //! <b>Effects</b>: Returns true if x is equal or greater than y
1081 //! <b>Complexity</b>: Linear to the number of elements in the container.
1082 friend bool operator>=(const flat_set& x, const flat_set& y);
1084 //! <b>Effects</b>: x.swap(y)
1086 //! <b>Complexity</b>: Constant.
1087 friend void swap(flat_set& x, flat_set& y);
1089 //! <b>Effects</b>: Extracts the internal sequence container.
1091 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
1093 //! <b>Postcondition</b>: this->empty()
1095 //! <b>Throws</b>: If secuence_type's move constructor throws
1096 sequence_type extract_sequence();
1098 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1100 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1101 //! one passed externally using the move assignment. Erases non-unique elements.
1103 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
1105 //! <b>Throws</b>: If the comparison or the move constructor throws
1106 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
1107 { this->tree_t::adopt_sequence_unique(boost::move(seq)); }
1109 //! <b>Requires</b>: seq shall be ordered according to this->compare()
1110 //! and shall contain unique elements.
1112 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1113 //! one passed externally using the move assignment.
1115 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
1117 //! <b>Throws</b>: If the move assignment throws
1118 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
1119 { this->tree_t::adopt_sequence_unique(ordered_unique_range_t(), boost::move(seq)); }
1121 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1123 template<class KeyType>
1124 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
1125 { return this->tree_t::insert_unique(::boost::forward<KeyType>(x)); }
1127 template<class KeyType>
1128 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1129 { return this->tree_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
1130 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1133 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1135 template <typename InputIterator>
1136 flat_set(InputIterator, InputIterator) ->
1137 flat_set< it_based_value_type_t<InputIterator> >;
1139 template < typename InputIterator, typename AllocatorOrCompare>
1140 flat_set(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1141 flat_set< it_based_value_type_t<InputIterator>
1142 , typename dtl::if_c< // Compare
1143 dtl::is_allocator<AllocatorOrCompare>::value
1144 , std::less<it_based_value_type_t<InputIterator>>
1145 , AllocatorOrCompare
1147 , typename dtl::if_c< // Allocator
1148 dtl::is_allocator<AllocatorOrCompare>::value
1149 , AllocatorOrCompare
1150 , new_allocator<it_based_value_type_t<InputIterator>>
1154 template < typename InputIterator, typename Compare, typename Allocator
1155 , typename = dtl::require_nonallocator_t<Compare>
1156 , typename = dtl::require_allocator_t<Allocator>>
1157 flat_set(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1158 flat_set< it_based_value_type_t<InputIterator>
1162 template <typename InputIterator>
1163 flat_set(ordered_unique_range_t, InputIterator, InputIterator) ->
1164 flat_set< it_based_value_type_t<InputIterator>>;
1167 template < typename InputIterator, typename AllocatorOrCompare>
1168 flat_set(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1169 flat_set< it_based_value_type_t<InputIterator>
1170 , typename dtl::if_c< // Compare
1171 dtl::is_allocator<AllocatorOrCompare>::value
1172 , std::less<it_based_value_type_t<InputIterator>>
1173 , AllocatorOrCompare
1175 , typename dtl::if_c< // Allocator
1176 dtl::is_allocator<AllocatorOrCompare>::value
1177 , AllocatorOrCompare
1178 , new_allocator<it_based_value_type_t<InputIterator>>
1182 template < typename InputIterator, typename Compare, typename Allocator
1183 , typename = dtl::require_nonallocator_t<Compare>
1184 , typename = dtl::require_allocator_t<Allocator>>
1185 flat_set(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1186 flat_set< it_based_value_type_t<InputIterator>
1192 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1194 } //namespace container {
1196 //!has_trivial_destructor_after_move<> == true_type
1197 //!specialization for optimizations
1198 template <class Key, class Compare, class AllocatorOrContainer>
1199 struct has_trivial_destructor_after_move<boost::container::flat_set<Key, Compare, AllocatorOrContainer> >
1201 typedef ::boost::container::dtl::flat_tree<Key, ::boost::container::dtl::identity<Key>, Compare, AllocatorOrContainer> tree;
1202 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1205 namespace container {
1207 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1209 //! flat_multiset is a Sorted Associative Container that stores objects of type Key and
1210 //! can store multiple copies of the same key value.
1212 //! flat_multiset is similar to std::multiset but it's implemented by as an ordered sequence container.
1213 //! The underlying sequence container is by default <i>vector</i> but it can also work
1214 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
1216 //! Using vector-like sequence containers means that inserting a new element into a flat_multiset might invalidate
1217 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
1218 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
1219 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
1221 //! This container provides random-access iterators.
1223 //! \tparam Key is the type to be inserted in the multiset, which is also the key_type
1224 //! \tparam Compare is the comparison functor used to order keys
1225 //! \tparam AllocatorOrContainer is either:
1226 //! - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
1227 //! (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
1228 //! - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
1229 //! sequence container with random-access iterators.
1230 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1231 template <class Key, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator<Key> >
1233 template <class Key, class Compare, class AllocatorOrContainer>
1237 : public dtl::flat_tree<Key, dtl::identity<Key>, Compare, AllocatorOrContainer>
1240 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1242 BOOST_COPYABLE_AND_MOVABLE(flat_multiset)
1243 typedef dtl::flat_tree<Key, dtl::identity<Key>, Compare, AllocatorOrContainer> tree_t;
1249 const tree_t &tree() const
1251 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1254 //////////////////////////////////////////////
1258 //////////////////////////////////////////////
1259 typedef Key key_type;
1260 typedef Compare key_compare;
1261 typedef Key value_type;
1262 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type) sequence_type;
1263 typedef typename sequence_type::allocator_type allocator_type;
1264 typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
1265 typedef typename sequence_type::pointer pointer;
1266 typedef typename sequence_type::const_pointer const_pointer;
1267 typedef typename sequence_type::reference reference;
1268 typedef typename sequence_type::const_reference const_reference;
1269 typedef typename sequence_type::size_type size_type;
1270 typedef typename sequence_type::difference_type difference_type;
1271 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type;
1272 typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare) value_compare;
1274 typedef typename sequence_type::iterator iterator;
1275 typedef typename sequence_type::const_iterator const_iterator;
1276 typedef typename sequence_type::reverse_iterator reverse_iterator;
1277 typedef typename sequence_type::const_reverse_iterator const_reverse_iterator;
1279 //! @copydoc ::boost::container::flat_set::flat_set()
1280 BOOST_CONTAINER_FORCEINLINE flat_multiset() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
1281 dtl::is_nothrow_default_constructible<Compare>::value)
1285 //! @copydoc ::boost::container::flat_set::flat_set(const Compare&)
1286 BOOST_CONTAINER_FORCEINLINE explicit flat_multiset(const Compare& comp)
1290 //! @copydoc ::boost::container::flat_set::flat_set(const allocator_type&)
1291 BOOST_CONTAINER_FORCEINLINE explicit flat_multiset(const allocator_type& a)
1295 //! @copydoc ::boost::container::flat_set::flat_set(const Compare&, const allocator_type&)
1296 BOOST_CONTAINER_FORCEINLINE flat_multiset(const Compare& comp, const allocator_type& a)
1300 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator)
1301 template <class InputIterator>
1302 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last)
1303 : tree_t(false, first, last)
1306 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const allocator_type&)
1307 template <class InputIterator>
1308 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const allocator_type& a)
1309 : tree_t(false, first, last, a)
1312 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const Compare& comp)
1313 template <class InputIterator>
1314 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const Compare& comp)
1315 : tree_t(false, first, last, comp)
1318 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const Compare& comp, const allocator_type&)
1319 template <class InputIterator>
1320 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1321 : tree_t(false, first, last, comp, a)
1324 //! <b>Effects</b>: Constructs an empty flat_multiset and
1325 //! inserts elements from the ordered range [first ,last ). This function
1326 //! is more efficient than the normal range creation for ordered ranges.
1328 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1330 //! <b>Complexity</b>: Linear in N.
1332 //! <b>Note</b>: Non-standard extension.
1333 template <class InputIterator>
1334 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last)
1335 : tree_t(ordered_range, first, last)
1338 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and
1339 //! inserts elements from the ordered range [first ,last ). This function
1340 //! is more efficient than the normal range creation for ordered ranges.
1342 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1344 //! <b>Complexity</b>: Linear in N.
1346 //! <b>Note</b>: Non-standard extension.
1347 template <class InputIterator>
1348 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1349 : tree_t(ordered_range, first, last, comp)
1352 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and
1353 //! allocator, and inserts elements from the ordered range [first, last ). This function
1354 //! is more efficient than the normal range creation for ordered ranges.
1356 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1358 //! <b>Complexity</b>: Linear in N.
1360 //! <b>Note</b>: Non-standard extension.
1361 template <class InputIterator>
1362 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1363 : tree_t(ordered_range, first, last, comp, a)
1366 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified allocator and
1367 //! inserts elements from the ordered range [first ,last ). This function
1368 //! is more efficient than the normal range creation for ordered ranges.
1370 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1372 //! <b>Complexity</b>: Linear in N.
1374 //! <b>Note</b>: Non-standard extension.
1375 template <class InputIterator>
1376 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const allocator_type &a)
1377 : tree_t(ordered_range, first, last, Compare(), a)
1380 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1381 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type)
1382 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il)
1383 : tree_t(false, il.begin(), il.end())
1386 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const allocator_type&)
1387 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const allocator_type& a)
1388 : tree_t(false, il.begin(), il.end(), a)
1391 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const Compare& comp)
1392 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const Compare& comp)
1393 : tree_t(false, il.begin(), il.end(), comp)
1396 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
1397 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1398 : tree_t(false, il.begin(), il.end(), comp, a)
1401 //! <b>Effects</b>: Constructs an empty containerand
1402 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
1403 //! is more efficient than the normal range creation for ordered ranges.
1405 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1407 //! <b>Complexity</b>: Linear in N.
1409 //! <b>Note</b>: Non-standard extension.
1410 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il)
1411 : tree_t(ordered_range, il.begin(), il.end())
1414 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
1415 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
1416 //! is more efficient than the normal range creation for ordered ranges.
1418 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1420 //! <b>Complexity</b>: Linear in N.
1422 //! <b>Note</b>: Non-standard extension.
1423 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1424 : tree_t(ordered_range, il.begin(), il.end(), comp)
1427 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
1428 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
1429 //! is more efficient than the normal range creation for ordered ranges.
1431 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1433 //! <b>Complexity</b>: Linear in N.
1435 //! <b>Note</b>: Non-standard extension.
1436 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1437 : tree_t(ordered_range, il.begin(), il.end(), comp, a)
1441 //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &)
1442 BOOST_CONTAINER_FORCEINLINE flat_multiset(const flat_multiset& x)
1443 : tree_t(static_cast<const tree_t&>(x))
1446 //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&)
1447 BOOST_CONTAINER_FORCEINLINE flat_multiset(BOOST_RV_REF(flat_multiset) x)
1448 BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
1449 : tree_t(boost::move(static_cast<tree_t&>(x)))
1452 //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &, const allocator_type &)
1453 BOOST_CONTAINER_FORCEINLINE flat_multiset(const flat_multiset& x, const allocator_type &a)
1454 : tree_t(static_cast<const tree_t&>(x), a)
1457 //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&, const allocator_type &)
1458 BOOST_CONTAINER_FORCEINLINE flat_multiset(BOOST_RV_REF(flat_multiset) x, const allocator_type &a)
1459 : tree_t(BOOST_MOVE_BASE(tree_t, x), a)
1462 //! @copydoc ::boost::container::flat_set::operator=(const flat_set &)
1463 BOOST_CONTAINER_FORCEINLINE flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x)
1464 { return static_cast<flat_multiset&>(this->tree_t::operator=(static_cast<const tree_t&>(x))); }
1466 //! @copydoc ::boost::container::flat_set::operator=(flat_set &&)
1467 BOOST_CONTAINER_FORCEINLINE flat_multiset& operator=(BOOST_RV_REF(flat_multiset) x)
1468 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1469 allocator_traits_type::is_always_equal::value) &&
1470 boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
1471 { return static_cast<flat_multiset&>(this->tree_t::operator=(BOOST_MOVE_BASE(tree_t, x))); }
1473 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1474 //! @copydoc ::boost::container::flat_set::operator=(std::initializer_list<value_type>)
1475 flat_multiset& operator=(std::initializer_list<value_type> il)
1478 this->insert(il.begin(), il.end());
1483 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1485 //! @copydoc ::boost::container::flat_set::get_allocator()
1486 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
1488 //! @copydoc ::boost::container::flat_set::get_stored_allocator()
1489 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
1491 //! @copydoc ::boost::container::flat_set::get_stored_allocator() const
1492 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
1494 //! @copydoc ::boost::container::flat_set::begin()
1495 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
1497 //! @copydoc ::boost::container::flat_set::begin() const
1498 const_iterator begin() const;
1500 //! @copydoc ::boost::container::flat_set::cbegin() const
1501 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1503 //! @copydoc ::boost::container::flat_set::end()
1504 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1506 //! @copydoc ::boost::container::flat_set::end() const
1507 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1509 //! @copydoc ::boost::container::flat_set::cend() const
1510 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1512 //! @copydoc ::boost::container::flat_set::rbegin()
1513 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1515 //! @copydoc ::boost::container::flat_set::rbegin() const
1516 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1518 //! @copydoc ::boost::container::flat_set::crbegin() const
1519 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1521 //! @copydoc ::boost::container::flat_set::rend()
1522 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1524 //! @copydoc ::boost::container::flat_set::rend() const
1525 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1527 //! @copydoc ::boost::container::flat_set::crend() const
1528 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1530 //! @copydoc ::boost::container::flat_set::empty() const
1531 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
1533 //! @copydoc ::boost::container::flat_set::size() const
1534 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
1536 //! @copydoc ::boost::container::flat_set::max_size() const
1537 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
1539 //! @copydoc ::boost::container::flat_set::capacity() const
1540 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
1542 //! @copydoc ::boost::container::flat_set::reserve(size_type)
1543 void reserve(size_type cnt);
1545 //! @copydoc ::boost::container::flat_set::shrink_to_fit()
1546 void shrink_to_fit();
1548 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1550 //////////////////////////////////////////////
1554 //////////////////////////////////////////////
1556 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1558 //! <b>Effects</b>: Inserts an object of type Key constructed with
1559 //! std::forward<Args>(args)... and returns the iterator pointing to the
1560 //! newly inserted element.
1562 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1563 //! to the elements with bigger keys than x.
1565 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1566 template <class... Args>
1567 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1568 { return this->tree_t::emplace_equal(boost::forward<Args>(args)...); }
1570 //! <b>Effects</b>: Inserts an object of type Key constructed with
1571 //! std::forward<Args>(args)... in the container.
1572 //! p is a hint pointing to where the insert should start to search.
1574 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1575 //! to the key of x.
1577 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1578 //! right before p) plus insertion linear to the elements with bigger keys than x.
1580 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1581 template <class... Args>
1582 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1583 { return this->tree_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1585 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1587 #define BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE(N) \
1588 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1589 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1590 { return this->tree_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1592 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1593 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1594 { return this->tree_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1596 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE)
1597 #undef BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE
1599 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1601 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1602 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1603 //! newly inserted element.
1605 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1606 //! to the elements with bigger keys than x.
1608 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1609 iterator insert(const value_type &x);
1611 //! <b>Effects</b>: Inserts a new value_type move constructed from x
1612 //! and returns the iterator pointing to the newly inserted element.
1614 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1615 //! to the elements with bigger keys than x.
1617 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1618 iterator insert(value_type &&x);
1620 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
1623 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1624 //! <b>Effects</b>: Inserts a copy of x in the container.
1625 //! p is a hint pointing to where the insert should start to search.
1627 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1628 //! to the key of x.
1630 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1631 //! right before p) plus insertion linear to the elements with bigger keys than x.
1633 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1634 iterator insert(const_iterator p, const value_type &x);
1636 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1637 //! p is a hint pointing to where the insert should start to search.
1639 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1640 //! to the key of x.
1642 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1643 //! right before p) plus insertion linear to the elements with bigger keys than x.
1645 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1646 iterator insert(const_iterator p, value_type &&x);
1648 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
1651 //! <b>Requires</b>: first, last are not iterators into *this.
1653 //! <b>Effects</b>: inserts each element from the range [first,last) .
1655 //! <b>Complexity</b>: N log(N).
1657 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1658 template <class InputIterator>
1659 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1660 { this->tree_t::insert_equal(first, last); }
1662 //! <b>Requires</b>: first, last are not iterators into *this and
1663 //! must be ordered according to the predicate.
1665 //! <b>Effects</b>: inserts each element from the range [first,last) .This function
1666 //! is more efficient than the normal range creation for ordered ranges.
1668 //! <b>Complexity</b>: Linear.
1670 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1671 template <class InputIterator>
1672 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, InputIterator first, InputIterator last)
1673 { this->tree_t::insert_equal(ordered_range, first, last); }
1675 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1676 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()).
1678 //! <b>Complexity</b>: N log(N).
1680 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1681 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1682 { this->tree_t::insert_equal(il.begin(), il.end()); }
1684 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate.
1686 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()). This function
1687 //! is more efficient than the normal range creation for ordered ranges.
1689 //! <b>Complexity</b>: Linear.
1691 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1692 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, std::initializer_list<value_type> il)
1693 { this->tree_t::insert_equal(ordered_range, il.begin(), il.end()); }
1696 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
1698 BOOST_CONTAINER_FORCEINLINE void merge(flat_multiset<Key, C2, AllocatorOrContainer>& source)
1699 { this->tree_t::merge_equal(source.tree()); }
1701 //! @copydoc ::boost::container::flat_multiset::merge(flat_multiset<Key, C2, AllocatorOrContainer>&)
1703 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multiset<Key, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1704 { return this->merge(static_cast<flat_multiset<Key, C2, AllocatorOrContainer>&>(source)); }
1706 //! @copydoc ::boost::container::flat_multimap::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1708 BOOST_CONTAINER_FORCEINLINE void merge(flat_set<Key, C2, AllocatorOrContainer>& source)
1709 { this->tree_t::merge_equal(source.tree()); }
1711 //! @copydoc ::boost::container::flat_multiset::merge(flat_set<Key, C2, AllocatorOrContainer>&)
1713 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_set<Key, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1714 { return this->merge(static_cast<flat_set<Key, C2, AllocatorOrContainer>&>(source)); }
1716 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1718 //! @copydoc ::boost::container::flat_set::erase(const_iterator)
1719 iterator erase(const_iterator p);
1721 //! @copydoc ::boost::container::flat_set::erase(const key_type&)
1722 size_type erase(const key_type& x);
1724 //! @copydoc ::boost::container::flat_set::erase(const_iterator,const_iterator)
1725 iterator erase(const_iterator first, const_iterator last);
1727 //! @copydoc ::boost::container::flat_set::swap
1728 void swap(flat_multiset& x)
1729 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1730 && boost::container::dtl::is_nothrow_swappable<Compare>::value );
1732 //! @copydoc ::boost::container::flat_set::clear
1733 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1735 //! @copydoc ::boost::container::flat_set::key_comp
1736 key_compare key_comp() const;
1738 //! @copydoc ::boost::container::flat_set::value_comp
1739 value_compare value_comp() const;
1741 //! @copydoc ::boost::container::flat_set::find(const key_type& )
1742 iterator find(const key_type& x);
1744 //! @copydoc ::boost::container::flat_set::find(const key_type& ) const
1745 const_iterator find(const key_type& x) const;
1747 //! @copydoc ::boost::container::flat_set::nth(size_type)
1748 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
1750 //! @copydoc ::boost::container::flat_set::nth(size_type) const
1751 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
1753 //! @copydoc ::boost::container::flat_set::index_of(iterator)
1754 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
1756 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
1757 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
1759 //! @copydoc ::boost::container::flat_set::count(const key_type& ) const
1760 size_type count(const key_type& x) const;
1762 //! @copydoc ::boost::container::flat_set::contains(const key_type& ) const
1763 bool contains(const key_type& x) const;
1765 //! @copydoc ::boost::container::flat_set::contains(const K& ) const
1766 template<typename K>
1767 bool contains(const K& x) const;
1769 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& )
1770 iterator lower_bound(const key_type& x);
1772 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& ) const
1773 const_iterator lower_bound(const key_type& x) const;
1775 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& )
1776 iterator upper_bound(const key_type& x);
1778 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& ) const
1779 const_iterator upper_bound(const key_type& x) const;
1781 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& ) const
1782 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1784 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& )
1785 std::pair<iterator,iterator> equal_range(const key_type& x);
1787 //! <b>Effects</b>: Returns true if x and y are equal
1789 //! <b>Complexity</b>: Linear to the number of elements in the container.
1790 friend bool operator==(const flat_multiset& x, const flat_multiset& y);
1792 //! <b>Effects</b>: Returns true if x and y are unequal
1794 //! <b>Complexity</b>: Linear to the number of elements in the container.
1795 friend bool operator!=(const flat_multiset& x, const flat_multiset& y);
1797 //! <b>Effects</b>: Returns true if x is less than y
1799 //! <b>Complexity</b>: Linear to the number of elements in the container.
1800 friend bool operator<(const flat_multiset& x, const flat_multiset& y);
1802 //! <b>Effects</b>: Returns true if x is greater than y
1804 //! <b>Complexity</b>: Linear to the number of elements in the container.
1805 friend bool operator>(const flat_multiset& x, const flat_multiset& y);
1807 //! <b>Effects</b>: Returns true if x is equal or less than y
1809 //! <b>Complexity</b>: Linear to the number of elements in the container.
1810 friend bool operator<=(const flat_multiset& x, const flat_multiset& y);
1812 //! <b>Effects</b>: Returns true if x is equal or greater than y
1814 //! <b>Complexity</b>: Linear to the number of elements in the container.
1815 friend bool operator>=(const flat_multiset& x, const flat_multiset& y);
1817 //! <b>Effects</b>: x.swap(y)
1819 //! <b>Complexity</b>: Constant.
1820 friend void swap(flat_multiset& x, flat_multiset& y);
1822 //! <b>Effects</b>: Extracts the internal sequence container.
1824 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
1826 //! <b>Postcondition</b>: this->empty()
1828 //! <b>Throws</b>: If secuence_type's move constructor throws
1829 sequence_type extract_sequence();
1831 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1833 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1834 //! one passed externally using the move assignment.
1836 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
1838 //! <b>Throws</b>: If the comparison or the move constructor throws
1839 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
1840 { this->tree_t::adopt_sequence_equal(boost::move(seq)); }
1842 //! <b>Requires</b>: seq shall be ordered according to this->compare()
1844 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1845 //! one passed externally using the move assignment.
1847 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
1849 //! <b>Throws</b>: If the move assignment throws
1850 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
1851 { this->tree_t::adopt_sequence_equal(ordered_range_t(), boost::move(seq)); }
1853 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1855 template <class KeyType>
1856 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1857 { return this->tree_t::insert_equal(::boost::forward<KeyType>(x)); }
1859 template <class KeyType>
1860 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1861 { return this->tree_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
1862 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1865 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1867 template <typename InputIterator>
1868 flat_multiset(InputIterator, InputIterator) ->
1869 flat_multiset< it_based_value_type_t<InputIterator> >;
1872 template < typename InputIterator, typename AllocatorOrCompare>
1873 flat_multiset(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1874 flat_multiset < it_based_value_type_t<InputIterator>
1875 , typename dtl::if_c< // Compare
1876 dtl::is_allocator<AllocatorOrCompare>::value
1877 , std::less<it_based_value_type_t<InputIterator>>
1878 , AllocatorOrCompare
1880 , typename dtl::if_c< // Allocator
1881 dtl::is_allocator<AllocatorOrCompare>::value
1882 , AllocatorOrCompare
1883 , new_allocator<it_based_value_type_t<InputIterator>>
1887 template < typename InputIterator, typename Compare, typename Allocator
1888 , typename = dtl::require_nonallocator_t<Compare>
1889 , typename = dtl::require_allocator_t<Allocator>>
1890 flat_multiset(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1891 flat_multiset< it_based_value_type_t<InputIterator>
1895 template <typename InputIterator>
1896 flat_multiset(ordered_range_t, InputIterator, InputIterator) ->
1897 flat_multiset< it_based_value_type_t<InputIterator>>;
1899 template < typename InputIterator, typename AllocatorOrCompare>
1900 flat_multiset(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1901 flat_multiset < it_based_value_type_t<InputIterator>
1902 , typename dtl::if_c< // Compare
1903 dtl::is_allocator<AllocatorOrCompare>::value
1904 , std::less<it_based_value_type_t<InputIterator>>
1905 , AllocatorOrCompare
1907 , typename dtl::if_c< // Allocator
1908 dtl::is_allocator<AllocatorOrCompare>::value
1909 , AllocatorOrCompare
1910 , new_allocator<it_based_value_type_t<InputIterator>>
1914 template < typename InputIterator, typename Compare, typename Allocator
1915 , typename = dtl::require_nonallocator_t<Compare>
1916 , typename = dtl::require_allocator_t<Allocator>>
1917 flat_multiset(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1918 flat_multiset< it_based_value_type_t<InputIterator>
1924 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1926 } //namespace container {
1928 //!has_trivial_destructor_after_move<> == true_type
1929 //!specialization for optimizations
1930 template <class Key, class Compare, class AllocatorOrContainer>
1931 struct has_trivial_destructor_after_move<boost::container::flat_multiset<Key, Compare, AllocatorOrContainer> >
1933 typedef ::boost::container::dtl::flat_tree<Key, ::boost::container::dtl::identity<Key>, Compare, AllocatorOrContainer> tree;
1934 static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1937 namespace container {
1939 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1943 #include <boost/container/detail/config_end.hpp>
1945 #endif // BOOST_CONTAINER_FLAT_SET_HPP