1//////////////////////////////////////////////////////////////////////////////
2//
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)
6//
7// See http://www.boost.org/libs/container for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10#ifndef BOOST_CONTAINER_FLAT_SET_HPP
11#define BOOST_CONTAINER_FLAT_SET_HPP
12
13#ifndef BOOST_CONFIG_HPP
14# include <boost/config.hpp>
15#endif
16
17#if defined(BOOST_HAS_PRAGMA_ONCE)
18# pragma once
19#endif
20
21#include <boost/container/detail/config_begin.hpp>
22#include <boost/container/detail/workaround.hpp>
23
24// container
25#include <boost/container/allocator_traits.hpp>
26#include <boost/container/container_fwd.hpp>
27#include <boost/container/new_allocator.hpp> //new_allocator
28// container/detail
29#include <boost/container/detail/flat_tree.hpp>
30#include <boost/container/detail/mpl.hpp>
31// move
32#include <boost/move/traits.hpp>
33#include <boost/move/utility_core.hpp>
34// move/detail
35#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
36#include <boost/move/detail/fwd_macros.hpp>
37#endif
38#include <boost/move/detail/move_helpers.hpp>
39// intrusive/detail
40#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
41#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
42// std
43#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
44#include <initializer_list>
45#endif
46
47namespace boost {
48namespace container {
49
50#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
51template <class Key, class T, class Compare, class Allocator>
52class flat_multimap;
53#endif
54
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.
57//!
58//! flat_set is similar to std::set but it's implemented like an ordered vector.
59//! This means that inserting a new element into a flat_set invalidates
60//! previous iterators and references
61//!
62//! Erasing an element of a flat_set invalidates iterators and references
63//! pointing to elements that come after (their keys are bigger) the erased element.
64//!
65//! This container provides random-access iterators.
66//!
67//! \tparam Key is the type to be inserted in the set, which is also the key_type
68//! \tparam Compare is the comparison functor used to order keys
69//! \tparam Allocator is the allocator to be used to allocate memory for this container
70#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
71template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key> >
72#else
73template <class Key, class Compare, class Allocator>
74#endif
75class flat_set
76 ///@cond
77 : public container_detail::flat_tree<Key, container_detail::identity<Key>, Compare, Allocator>
78 ///@endcond
79{
80 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
81 private:
82 BOOST_COPYABLE_AND_MOVABLE(flat_set)
83 typedef container_detail::flat_tree<Key, container_detail::identity<Key>, Compare, Allocator> base_t;
84
85 public:
86 base_t &tree()
87 { return *this; }
88
89 const base_t &tree() const
90 { return *this; }
91
92 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
93
94 public:
95 //////////////////////////////////////////////
96 //
97 // types
98 //
99 //////////////////////////////////////////////
100 typedef Key key_type;
101 typedef Key value_type;
102 typedef Compare key_compare;
103 typedef Compare value_compare;
104 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
105 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
106 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
107 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
108 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
109 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
110 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
111 typedef Allocator allocator_type;
112 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
113 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
114 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
115 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
116 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
117 typedef typename BOOST_CONTAINER_IMPDEF(base_t::sequence_type) sequence_type;
118
119 public:
120 //////////////////////////////////////////////
121 //
122 // construct/copy/destroy
123 //
124 //////////////////////////////////////////////
125
126 //! <b>Effects</b>: Default constructs an empty container.
127 //!
128 //! <b>Complexity</b>: Constant.
129 BOOST_CONTAINER_FORCEINLINE
130 explicit flat_set() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
131 container_detail::is_nothrow_default_constructible<Compare>::value)
132 : base_t()
133 {}
134
135 //! <b>Effects</b>: Constructs an empty container using the specified
136 //! comparison object.
137 //!
138 //! <b>Complexity</b>: Constant.
139 BOOST_CONTAINER_FORCEINLINE
140 explicit flat_set(const Compare& comp)
141 : base_t(comp)
142 {}
143
144 //! <b>Effects</b>: Constructs an empty container using the specified allocator.
145 //!
146 //! <b>Complexity</b>: Constant.
147 BOOST_CONTAINER_FORCEINLINE
148 explicit flat_set(const allocator_type& a)
149 : base_t(a)
150 {}
151
152 //! <b>Effects</b>: Constructs an empty container using the specified
153 //! comparison object and allocator.
154 //!
155 //! <b>Complexity</b>: Constant.
156 BOOST_CONTAINER_FORCEINLINE
157 flat_set(const Compare& comp, const allocator_type& a)
158 : base_t(comp, a)
159 {}
160
161 //! <b>Effects</b>: Constructs an empty container and
162 //! inserts elements from the range [first ,last ).
163 //!
164 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
165 //! comp and otherwise N logN, where N is last - first.
166 template <class InputIterator>
167 BOOST_CONTAINER_FORCEINLINE
168 flat_set(InputIterator first, InputIterator last)
169 : base_t(true, first, last)
170 {}
171
172 //! <b>Effects</b>: Constructs an empty container using the specified
173 //! allocator, and inserts elements from the range [first ,last ).
174 //!
175 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
176 //! comp and otherwise N logN, where N is last - first.
177 template <class InputIterator>
178 BOOST_CONTAINER_FORCEINLINE
179 flat_set(InputIterator first, InputIterator last, const allocator_type& a)
180 : base_t(true, first, last, a)
181 {}
182
183 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
184 //! inserts elements from the range [first ,last ).
185 //!
186 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
187 //! comp and otherwise N logN, where N is last - first.
188 template <class InputIterator>
189 BOOST_CONTAINER_FORCEINLINE
190 flat_set(InputIterator first, InputIterator last, const Compare& comp)
191 : base_t(true, first, last, comp)
192 {}
193
194 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
195 //! allocator, and inserts elements from the range [first ,last ).
196 //!
197 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
198 //! comp and otherwise N logN, where N is last - first.
199 template <class InputIterator>
200 BOOST_CONTAINER_FORCEINLINE
201 flat_set(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
202 : base_t(true, first, last, comp, a)
203 {}
204
205 //! <b>Effects</b>: Constructs an empty container and
206 //! inserts elements from the ordered unique range [first ,last). This function
207 //! is more efficient than the normal range creation for ordered ranges.
208 //!
209 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
210 //! unique values.
211 //!
212 //! <b>Complexity</b>: Linear in N.
213 //!
214 //! <b>Note</b>: Non-standard extension.
215 template <class InputIterator>
216 BOOST_CONTAINER_FORCEINLINE
217 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last)
218 : base_t(ordered_unique_range, first, last)
219 {}
220
221 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
222 //! inserts elements from the ordered unique range [first ,last). This function
223 //! is more efficient than the normal range creation for ordered ranges.
224 //!
225 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
226 //! unique values.
227 //!
228 //! <b>Complexity</b>: Linear in N.
229 //!
230 //! <b>Note</b>: Non-standard extension.
231 template <class InputIterator>
232 BOOST_CONTAINER_FORCEINLINE
233 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
234 : base_t(ordered_unique_range, first, last, comp)
235 {}
236
237 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
238 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
239 //! is more efficient than the normal range creation for ordered ranges.
240 //!
241 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
242 //! unique values.
243 //!
244 //! <b>Complexity</b>: Linear in N.
245 //!
246 //! <b>Note</b>: Non-standard extension.
247 template <class InputIterator>
248 BOOST_CONTAINER_FORCEINLINE
249 flat_set(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
250 : base_t(ordered_unique_range, first, last, comp, a)
251 {}
252
253#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
254 //! <b>Effects</b>: Constructs an empty container and
255 //! inserts elements from the range [il.begin(), il.end()).
256 //!
257 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
258 //! comp and otherwise N logN, where N is il.begin() - il.end().
259 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il)
260 : base_t(true, il.begin(), il.end())
261 {}
262
263 //! <b>Effects</b>: Constructs an empty container using the specified
264 //! allocator, and inserts elements from the range [il.begin(), il.end()).
265 //!
266 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
267 //! comp and otherwise N logN, where N is il.begin() - il.end().
268 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const allocator_type& a)
269 : base_t(true, il.begin(), il.end(), a)
270 {}
271
272 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
273 //! inserts elements from the range [il.begin(), il.end()).
274 //!
275 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
276 //! comp and otherwise N logN, where N is il.begin() - il.end().
277 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const Compare& comp)
278 : base_t(true, il.begin(), il.end(), comp)
279 {}
280
281 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
282 //! allocator, and inserts elements from the range [il.begin(), il.end()).
283 //!
284 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
285 //! comp and otherwise N logN, where N is il.begin() - il.end().
286 BOOST_CONTAINER_FORCEINLINE flat_set(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
287 : base_t(true, il.begin(), il.end(), comp, a)
288 {}
289
290 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
291 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
292 //! is more efficient than the normal range creation for ordered ranges.
293 //!
294 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
295 //! unique values.
296 //!
297 //! <b>Complexity</b>: Linear in N.
298 //!
299 //! <b>Note</b>: Non-standard extension.
300 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il)
301 : base_t(ordered_unique_range, il.begin(), il.end())
302 {}
303
304 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
305 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
306 //! is more efficient than the normal range creation for ordered ranges.
307 //!
308 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
309 //! unique values.
310 //!
311 //! <b>Complexity</b>: Linear in N.
312 //!
313 //! <b>Note</b>: Non-standard extension.
314 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
315 : base_t(ordered_unique_range, il.begin(), il.end(), comp)
316 {}
317
318 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
319 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
320 //! is more efficient than the normal range creation for ordered ranges.
321 //!
322 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
323 //! unique values.
324 //!
325 //! <b>Complexity</b>: Linear in N.
326 //!
327 //! <b>Note</b>: Non-standard extension.
328 BOOST_CONTAINER_FORCEINLINE flat_set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
329 : base_t(ordered_unique_range, il.begin(), il.end(), comp, a)
330 {}
331#endif
332
333 //! <b>Effects</b>: Copy constructs the container.
334 //!
335 //! <b>Complexity</b>: Linear in x.size().
336 BOOST_CONTAINER_FORCEINLINE flat_set(const flat_set& x)
337 : base_t(static_cast<const base_t&>(x))
338 {}
339
340 //! <b>Effects</b>: Move constructs thecontainer. Constructs *this using x's resources.
341 //!
342 //! <b>Complexity</b>: Constant.
343 //!
344 //! <b>Postcondition</b>: x is emptied.
345 BOOST_CONTAINER_FORCEINLINE flat_set(BOOST_RV_REF(flat_set) x)
346 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
347 : base_t(BOOST_MOVE_BASE(base_t, x))
348 {}
349
350 //! <b>Effects</b>: Copy constructs a container using the specified allocator.
351 //!
352 //! <b>Complexity</b>: Linear in x.size().
353 BOOST_CONTAINER_FORCEINLINE flat_set(const flat_set& x, const allocator_type &a)
354 : base_t(static_cast<const base_t&>(x), a)
355 {}
356
357 //! <b>Effects</b>: Move constructs a container using the specified allocator.
358 //! Constructs *this using x's resources.
359 //!
360 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise
361 BOOST_CONTAINER_FORCEINLINE flat_set(BOOST_RV_REF(flat_set) x, const allocator_type &a)
362 : base_t(BOOST_MOVE_BASE(base_t, x), a)
363 {}
364
365 //! <b>Effects</b>: Makes *this a copy of x.
366 //!
367 //! <b>Complexity</b>: Linear in x.size().
368 BOOST_CONTAINER_FORCEINLINE flat_set& operator=(BOOST_COPY_ASSIGN_REF(flat_set) x)
369 { return static_cast<flat_set&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
370
371 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
372 //! is false and (allocation throws or value_type's move constructor throws)
373 //!
374 //! <b>Complexity</b>: Constant if allocator_traits_type::
375 //! propagate_on_container_move_assignment is true or
376 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
377 BOOST_CONTAINER_FORCEINLINE flat_set& operator=(BOOST_RV_REF(flat_set) x)
378 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
379 allocator_traits_type::is_always_equal::value) &&
380 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
381 { return static_cast<flat_set&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
382
383#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
384 //! <b>Effects</b>: Copy all elements from il to *this.
385 //!
386 //! <b>Complexity</b>: Linear in il.size().
387 flat_set& operator=(std::initializer_list<value_type> il)
388 {
389 this->clear();
390 this->insert(il.begin(), il.end());
391 return *this;
392 }
393#endif
394
395 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
396 //! <b>Effects</b>: Returns a copy of the allocator that
397 //! was passed to the object's constructor.
398 //!
399 //! <b>Complexity</b>: Constant.
400 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
401
402 //! <b>Effects</b>: Returns a reference to the internal allocator.
403 //!
404 //! <b>Throws</b>: Nothing
405 //!
406 //! <b>Complexity</b>: Constant.
407 //!
408 //! <b>Note</b>: Non-standard extension.
409 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
410
411 //! <b>Effects</b>: Returns a reference to the internal allocator.
412 //!
413 //! <b>Throws</b>: Nothing
414 //!
415 //! <b>Complexity</b>: Constant.
416 //!
417 //! <b>Note</b>: Non-standard extension.
418 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
419
420 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
421 //!
422 //! <b>Throws</b>: Nothing.
423 //!
424 //! <b>Complexity</b>: Constant.
425 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
426
427 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
428 //!
429 //! <b>Throws</b>: Nothing.
430 //!
431 //! <b>Complexity</b>: Constant.
432 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
433
434 //! <b>Effects</b>: Returns an iterator to the end of the container.
435 //!
436 //! <b>Throws</b>: Nothing.
437 //!
438 //! <b>Complexity</b>: Constant.
439 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
440
441 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
442 //!
443 //! <b>Throws</b>: Nothing.
444 //!
445 //! <b>Complexity</b>: Constant.
446 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
447
448 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
449 //! of the reversed container.
450 //!
451 //! <b>Throws</b>: Nothing.
452 //!
453 //! <b>Complexity</b>: Constant.
454 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
455
456 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
457 //! of the reversed container.
458 //!
459 //! <b>Throws</b>: Nothing.
460 //!
461 //! <b>Complexity</b>: Constant.
462 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
463
464 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
465 //! of the reversed container.
466 //!
467 //! <b>Throws</b>: Nothing.
468 //!
469 //! <b>Complexity</b>: Constant.
470 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
471
472 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
473 //! of the reversed container.
474 //!
475 //! <b>Throws</b>: Nothing.
476 //!
477 //! <b>Complexity</b>: Constant.
478 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
479
480 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
481 //!
482 //! <b>Throws</b>: Nothing.
483 //!
484 //! <b>Complexity</b>: Constant.
485 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
486
487 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
488 //!
489 //! <b>Throws</b>: Nothing.
490 //!
491 //! <b>Complexity</b>: Constant.
492 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
493
494 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
495 //! of the reversed container.
496 //!
497 //! <b>Throws</b>: Nothing.
498 //!
499 //! <b>Complexity</b>: Constant.
500 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
501
502 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
503 //! of the reversed container.
504 //!
505 //! <b>Throws</b>: Nothing.
506 //!
507 //! <b>Complexity</b>: Constant.
508 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
509
510 //! <b>Effects</b>: Returns true if the container contains no elements.
511 //!
512 //! <b>Throws</b>: Nothing.
513 //!
514 //! <b>Complexity</b>: Constant.
515 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
516
517 //! <b>Effects</b>: Returns the number of the elements contained in the container.
518 //!
519 //! <b>Throws</b>: Nothing.
520 //!
521 //! <b>Complexity</b>: Constant.
522 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
523
524 //! <b>Effects</b>: Returns the largest possible size of the container.
525 //!
526 //! <b>Throws</b>: Nothing.
527 //!
528 //! <b>Complexity</b>: Constant.
529 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
530
531 //! <b>Effects</b>: Number of elements for which memory has been allocated.
532 //! capacity() is always greater than or equal to size().
533 //!
534 //! <b>Throws</b>: Nothing.
535 //!
536 //! <b>Complexity</b>: Constant.
537 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
538
539 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
540 //! effect. Otherwise, it is a request for allocation of additional memory.
541 //! If the request is successful, then capacity() is greater than or equal to
542 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
543 //!
544 //! <b>Throws</b>: If memory allocation allocation throws or Key's copy constructor throws.
545 //!
546 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
547 //! to values might be invalidated.
548 void reserve(size_type cnt);
549
550 //! <b>Effects</b>: Tries to deallocate the excess of memory created
551 // with previous allocations. The size of the vector is unchanged
552 //!
553 //! <b>Throws</b>: If memory allocation throws, or Key's copy constructor throws.
554 //!
555 //! <b>Complexity</b>: Linear to size().
556 void shrink_to_fit();
557
558 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
559
560 //////////////////////////////////////////////
561 //
562 // modifiers
563 //
564 //////////////////////////////////////////////
565
566 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
567
568 //! <b>Effects</b>: Inserts an object x of type Key constructed with
569 //! std::forward<Args>(args)... if and only if there is no element in the container
570 //! with key equivalent to the key of x.
571 //!
572 //! <b>Returns</b>: The bool component of the returned pair is true if and only
573 //! if the insertion takes place, and the iterator component of the pair
574 //! points to the element with key equivalent to the key of x.
575 //!
576 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
577 //! to the elements with bigger keys than x.
578 //!
579 //! <b>Note</b>: If an element is inserted it might invalidate elements.
580 template <class... Args>
581 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
582 { return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
583
584 //! <b>Effects</b>: Inserts an object of type Key constructed with
585 //! std::forward<Args>(args)... in the container if and only if there is
586 //! no element in the container with key equivalent to the key of x.
587 //! p is a hint pointing to where the insert should start to search.
588 //!
589 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
590 //! to the key of x.
591 //!
592 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
593 //! right before p) plus insertion linear to the elements with bigger keys than x.
594 //!
595 //! <b>Note</b>: If an element is inserted it might invalidate elements.
596 template <class... Args>
597 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
598 { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
599
600 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
601
602 #define BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE(N) \
603 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
604 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
605 { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\
606 \
607 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
608 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
609 { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
610 //
611 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE)
612 #undef BOOST_CONTAINER_FLAT_SET_EMPLACE_CODE
613
614 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
615
616 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
617 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
618 //! with key equivalent to the key of x.
619 //!
620 //! <b>Returns</b>: The bool component of the returned pair is true if and only
621 //! if the insertion takes place, and the iterator component of the pair
622 //! points to the element with key equivalent to the key of x.
623 //!
624 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
625 //! to the elements with bigger keys than x.
626 //!
627 //! <b>Note</b>: If an element is inserted it might invalidate elements.
628 std::pair<iterator, bool> insert(const value_type &x);
629
630 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
631 //! only if there is no element in the container with key equivalent to the key of x.
632 //!
633 //! <b>Returns</b>: The bool component of the returned pair is true if and only
634 //! if the insertion takes place, and the iterator component of the pair
635 //! points to the element with key equivalent to the key of x.
636 //!
637 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
638 //! to the elements with bigger keys than x.
639 //!
640 //! <b>Note</b>: If an element is inserted it might invalidate elements.
641 std::pair<iterator, bool> insert(value_type &&x);
642 #else
643 private:
644 typedef std::pair<iterator, bool> insert_return_pair;
645 public:
646 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, insert_return_pair, this->priv_insert)
647 #endif
648
649 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
650 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
651 //! no element in the container with key equivalent to the key of x.
652 //! p is a hint pointing to where the insert should start to search.
653 //!
654 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
655 //! to the key of x.
656 //!
657 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
658 //! right before p) plus insertion linear to the elements with bigger keys than x.
659 //!
660 //! <b>Note</b>: If an element is inserted it might invalidate elements.
661 iterator insert(const_iterator p, const value_type &x);
662
663 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
664 //! p is a hint pointing to where the insert should start to search.
665 //!
666 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
667 //!
668 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
669 //! right before p) plus insertion linear to the elements with bigger keys than x.
670 //!
671 //! <b>Note</b>: If an element is inserted it might invalidate elements.
672 iterator insert(const_iterator p, value_type &&x);
673 #else
674 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
675 #endif
676
677 //! <b>Requires</b>: first, last are not iterators into *this.
678 //!
679 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
680 //! if there is no element with key equivalent to the key of that element.
681 //!
682 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
683 //! search time plus N*size() insertion time.
684 //!
685 //! <b>Note</b>: If an element is inserted it might invalidate elements.
686 template <class InputIterator>
687 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
688 { this->base_t::insert_unique(first, last); }
689
690 //! <b>Requires</b>: first, last are not iterators into *this and
691 //! must be ordered according to the predicate and must be
692 //! unique values.
693 //!
694 //! <b>Effects</b>: inserts each element from the range [first,last) .This function
695 //! is more efficient than the normal range creation for ordered ranges.
696 //!
697 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
698 //! search time plus N*size() insertion time.
699 //!
700 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
701 template <class InputIterator>
702 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
703 { this->base_t::insert_unique(ordered_unique_range, first, last); }
704
705#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
706 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
707 //! if there is no element with key equivalent to the key of that element.
708 //!
709 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
710 //! search time plus N*size() insertion time.
711 //!
712 //! <b>Note</b>: If an element is inserted it might invalidate elements.
713 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
714 { this->base_t::insert_unique(il.begin(), il.end()); }
715
716 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate
717 //! and must be unique values.
718 //!
719 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .This function
720 //! is more efficient than the normal range creation for ordered ranges.
721 //!
722 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
723 //! search time plus N*size() insertion time.
724 //!
725 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
726 BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
727 { this->base_t::insert_unique(ordered_unique_range, il.begin(), il.end()); }
728#endif
729
730 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&)
731 template<class C2>
732 BOOST_CONTAINER_FORCEINLINE void merge(flat_set<Key, C2, Allocator>& source)
733 { this->base_t::merge_unique(source.tree()); }
734
735 //! @copydoc ::boost::container::flat_set::merge(flat_set<Key, C2, Allocator>&)
736 template<class C2>
737 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_set<Key, C2, Allocator> BOOST_RV_REF_END source)
738 { return this->merge(static_cast<flat_set<Key, C2, Allocator>&>(source)); }
739
740 //! @copydoc ::boost::container::flat_map::merge(flat_multimap<Key, T, C2, Allocator>&)
741 template<class C2>
742 BOOST_CONTAINER_FORCEINLINE void merge(flat_multiset<Key, C2, Allocator>& source)
743 { this->base_t::merge_unique(source.tree()); }
744
745 //! @copydoc ::boost::container::flat_set::merge(flat_multiset<Key, C2, Allocator>&)
746 template<class C2>
747 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multiset<Key, C2, Allocator> BOOST_RV_REF_END source)
748 { return this->merge(static_cast<flat_multiset<Key, C2, Allocator>&>(source)); }
749
750 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
751
752 //! <b>Effects</b>: Erases the element pointed to by p.
753 //!
754 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
755 //! following q prior to the element being erased. If no such element exists,
756 //! returns end().
757 //!
758 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
759 //!
760 //! <b>Note</b>: Invalidates elements with keys
761 //! not less than the erased element.
762 iterator erase(const_iterator p);
763
764 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
765 //!
766 //! <b>Returns</b>: Returns the number of erased elements.
767 //!
768 //! <b>Complexity</b>: Logarithmic search time plus erasure time
769 //! linear to the elements with bigger keys.
770 size_type erase(const key_type& x);
771
772 //! <b>Effects</b>: Erases all the elements in the range [first, last).
773 //!
774 //! <b>Returns</b>: Returns last.
775 //!
776 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
777 //!
778 //! <b>Complexity</b>: Logarithmic search time plus erasure time
779 //! linear to the elements with bigger keys.
780 iterator erase(const_iterator first, const_iterator last);
781
782 //! <b>Effects</b>: Swaps the contents of *this and x.
783 //!
784 //! <b>Throws</b>: Nothing.
785 //!
786 //! <b>Complexity</b>: Constant.
787 void swap(flat_set& x)
788 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
789 && boost::container::container_detail::is_nothrow_swappable<Compare>::value );
790
791 //! <b>Effects</b>: erase(a.begin(),a.end()).
792 //!
793 //! <b>Postcondition</b>: size() == 0.
794 //!
795 //! <b>Complexity</b>: linear in size().
796 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
797
798 //! <b>Effects</b>: Returns the comparison object out
799 //! of which a was constructed.
800 //!
801 //! <b>Complexity</b>: Constant.
802 key_compare key_comp() const;
803
804 //! <b>Effects</b>: Returns an object of value_compare constructed out
805 //! of the comparison object.
806 //!
807 //! <b>Complexity</b>: Constant.
808 value_compare value_comp() const;
809
810 //! <b>Returns</b>: An iterator pointing to an element with the key
811 //! equivalent to x, or end() if such an element is not found.
812 //!
813 //! <b>Complexity</b>: Logarithmic.
814 iterator find(const key_type& x);
815
816 //! <b>Returns</b>: A const_iterator pointing to an element with the key
817 //! equivalent to x, or end() if such an element is not found.
818 //!
819 //! <b>Complexity</b>: Logarithmic.
820 const_iterator find(const key_type& x) const;
821
822 //! <b>Requires</b>: size() >= n.
823 //!
824 //! <b>Effects</b>: Returns an iterator to the nth element
825 //! from the beginning of the container. Returns end()
826 //! if n == size().
827 //!
828 //! <b>Throws</b>: Nothing.
829 //!
830 //! <b>Complexity</b>: Constant.
831 //!
832 //! <b>Note</b>: Non-standard extension
833 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
834
835 //! <b>Requires</b>: size() >= n.
836 //!
837 //! <b>Effects</b>: Returns a const_iterator to the nth element
838 //! from the beginning of the container. Returns end()
839 //! if n == size().
840 //!
841 //! <b>Throws</b>: Nothing.
842 //!
843 //! <b>Complexity</b>: Constant.
844 //!
845 //! <b>Note</b>: Non-standard extension
846 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
847
848 //! <b>Requires</b>: begin() <= p <= end().
849 //!
850 //! <b>Effects</b>: Returns the index of the element pointed by p
851 //! and size() if p == end().
852 //!
853 //! <b>Throws</b>: Nothing.
854 //!
855 //! <b>Complexity</b>: Constant.
856 //!
857 //! <b>Note</b>: Non-standard extension
858 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
859
860 //! <b>Requires</b>: begin() <= p <= end().
861 //!
862 //! <b>Effects</b>: Returns the index of the element pointed by p
863 //! and size() if p == end().
864 //!
865 //! <b>Throws</b>: Nothing.
866 //!
867 //! <b>Complexity</b>: Constant.
868 //!
869 //! <b>Note</b>: Non-standard extension
870 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
871
872 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
873
874 //! <b>Returns</b>: The number of elements with key equivalent to x.
875 //!
876 //! <b>Complexity</b>: log(size())+count(k)
877 BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
878 { return static_cast<size_type>(this->base_t::find(x) != this->base_t::cend()); }
879
880 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
881 //! <b>Returns</b>: An iterator pointing to the first element with key not less
882 //! than k, or a.end() if such an element is not found.
883 //!
884 //! <b>Complexity</b>: Logarithmic
885 iterator lower_bound(const key_type& x);
886
887 //! <b>Returns</b>: A const iterator pointing to the first element with key not
888 //! less than k, or a.end() if such an element is not found.
889 //!
890 //! <b>Complexity</b>: Logarithmic
891 const_iterator lower_bound(const key_type& x) const;
892
893 //! <b>Returns</b>: An iterator pointing to the first element with key not less
894 //! than x, or end() if such an element is not found.
895 //!
896 //! <b>Complexity</b>: Logarithmic
897 iterator upper_bound(const key_type& x);
898
899 //! <b>Returns</b>: A const iterator pointing to the first element with key not
900 //! less than x, or end() if such an element is not found.
901 //!
902 //! <b>Complexity</b>: Logarithmic
903 const_iterator upper_bound(const key_type& x) const;
904
905 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
906
907 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
908 //!
909 //! <b>Complexity</b>: Logarithmic
910 BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
911 { return this->base_t::lower_bound_range(x); }
912
913 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
914 //!
915 //! <b>Complexity</b>: Logarithmic
916 BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
917 { return this->base_t::lower_bound_range(x); }
918
919 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
920
921 //! <b>Effects</b>: Returns true if x and y are equal
922 //!
923 //! <b>Complexity</b>: Linear to the number of elements in the container.
924 friend bool operator==(const flat_set& x, const flat_set& y);
925
926 //! <b>Effects</b>: Returns true if x and y are unequal
927 //!
928 //! <b>Complexity</b>: Linear to the number of elements in the container.
929 friend bool operator!=(const flat_set& x, const flat_set& y);
930
931 //! <b>Effects</b>: Returns true if x is less than y
932 //!
933 //! <b>Complexity</b>: Linear to the number of elements in the container.
934 friend bool operator<(const flat_set& x, const flat_set& y);
935
936 //! <b>Effects</b>: Returns true if x is greater than y
937 //!
938 //! <b>Complexity</b>: Linear to the number of elements in the container.
939 friend bool operator>(const flat_set& x, const flat_set& y);
940
941 //! <b>Effects</b>: Returns true if x is equal or less than y
942 //!
943 //! <b>Complexity</b>: Linear to the number of elements in the container.
944 friend bool operator<=(const flat_set& x, const flat_set& y);
945
946 //! <b>Effects</b>: Returns true if x is equal or greater than y
947 //!
948 //! <b>Complexity</b>: Linear to the number of elements in the container.
949 friend bool operator>=(const flat_set& x, const flat_set& y);
950
951 //! <b>Effects</b>: x.swap(y)
952 //!
953 //! <b>Complexity</b>: Constant.
954 friend void swap(flat_set& x, flat_set& y);
955
956 //! <b>Effects</b>: Extracts the internal sequence container.
957 //!
958 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
959 //!
960 //! <b>Postcondition</b>: this->empty()
961 //!
962 //! <b>Throws</b>: If secuence_type's move constructor throws
963 sequence_type extract_sequence();
964
965 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
966
967 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
968 //! one passed externally using the move assignment. Erases non-unique elements.
969 //!
970 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
971 //!
972 //! <b>Throws</b>: If the comparison or the move constructor throws
973 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
974 { this->base_t::adopt_sequence_unique(boost::move(seq)); }
975
976 //! <b>Requires</b>: seq shall be ordered according to this->compare()
977 //! and shall contain unique elements.
978 //!
979 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
980 //! one passed externally using the move assignment.
981 //!
982 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
983 //!
984 //! <b>Throws</b>: If the move assignment throws
985 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
986 { this->base_t::adopt_sequence_unique(ordered_unique_range_t(), boost::move(seq)); }
987
988 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
989 private:
990 template<class KeyType>
991 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> priv_insert(BOOST_FWD_REF(KeyType) x)
992 { return this->base_t::insert_unique(::boost::forward<KeyType>(x)); }
993
994 template<class KeyType>
995 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
996 { return this->base_t::insert_unique(p, ::boost::forward<KeyType>(x)); }
997 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
998};
999
1000#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1001
1002} //namespace container {
1003
1004//!has_trivial_destructor_after_move<> == true_type
1005//!specialization for optimizations
1006template <class Key, class Compare, class Allocator>
1007struct has_trivial_destructor_after_move<boost::container::flat_set<Key, Compare, Allocator> >
1008{
1009 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1010 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1011 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1012 ::boost::has_trivial_destructor_after_move<Compare>::value;
1013};
1014
1015namespace container {
1016
1017#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1018
1019//! flat_multiset is a Sorted Associative Container that stores objects of type Key.
1020//!
1021//! flat_multiset can store multiple copies of the same key value.
1022//!
1023//! flat_multiset is similar to std::multiset but it's implemented like an ordered vector.
1024//! This means that inserting a new element into a flat_multiset invalidates
1025//! previous iterators and references
1026//!
1027//! Erasing an element invalidates iterators and references
1028//! pointing to elements that come after (their keys are bigger) the erased element.
1029//!
1030//! This container provides random-access iterators.
1031//!
1032//! \tparam Key is the type to be inserted in the multiset, which is also the key_type
1033//! \tparam Compare is the comparison functor used to order keys
1034//! \tparam Allocator is the allocator to be used to allocate memory for this container
1035#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1036template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key> >
1037#else
1038template <class Key, class Compare, class Allocator>
1039#endif
1040class flat_multiset
1041 ///@cond
1042 : public container_detail::flat_tree<Key, container_detail::identity<Key>, Compare, Allocator>
1043 ///@endcond
1044{
1045 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1046 private:
1047 BOOST_COPYABLE_AND_MOVABLE(flat_multiset)
1048 typedef container_detail::flat_tree<Key, container_detail::identity<Key>, Compare, Allocator> base_t;
1049
1050 public:
1051 base_t &tree()
1052 { return *this; }
1053
1054 const base_t &tree() const
1055 { return *this; }
1056 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1057
1058 public:
1059 //////////////////////////////////////////////
1060 //
1061 // types
1062 //
1063 //////////////////////////////////////////////
1064 typedef Key key_type;
1065 typedef Key value_type;
1066 typedef Compare key_compare;
1067 typedef Compare value_compare;
1068 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
1069 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1070 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
1071 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
1072 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
1073 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
1074 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
1075 typedef Allocator allocator_type;
1076 typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type;
1077 typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator;
1078 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator;
1079 typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator;
1080 typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator;
1081 typedef typename BOOST_CONTAINER_IMPDEF(base_t::sequence_type) sequence_type;
1082
1083 //! @copydoc ::boost::container::flat_set::flat_set()
1084 BOOST_CONTAINER_FORCEINLINE explicit flat_multiset() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
1085 container_detail::is_nothrow_default_constructible<Compare>::value)
1086 : base_t()
1087 {}
1088
1089 //! @copydoc ::boost::container::flat_set::flat_set(const Compare&)
1090 BOOST_CONTAINER_FORCEINLINE explicit flat_multiset(const Compare& comp)
1091 : base_t(comp)
1092 {}
1093
1094 //! @copydoc ::boost::container::flat_set::flat_set(const allocator_type&)
1095 BOOST_CONTAINER_FORCEINLINE explicit flat_multiset(const allocator_type& a)
1096 : base_t(a)
1097 {}
1098
1099 //! @copydoc ::boost::container::flat_set::flat_set(const Compare&, const allocator_type&)
1100 BOOST_CONTAINER_FORCEINLINE flat_multiset(const Compare& comp, const allocator_type& a)
1101 : base_t(comp, a)
1102 {}
1103
1104 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator)
1105 template <class InputIterator>
1106 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last)
1107 : base_t(false, first, last)
1108 {}
1109
1110 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const allocator_type&)
1111 template <class InputIterator>
1112 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const allocator_type& a)
1113 : base_t(false, first, last, a)
1114 {}
1115
1116 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const Compare& comp)
1117 template <class InputIterator>
1118 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const Compare& comp)
1119 : base_t(false, first, last, comp)
1120 {}
1121
1122 //! @copydoc ::boost::container::flat_set::flat_set(InputIterator, InputIterator, const Compare& comp, const allocator_type&)
1123 template <class InputIterator>
1124 BOOST_CONTAINER_FORCEINLINE flat_multiset(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1125 : base_t(false, first, last, comp, a)
1126 {}
1127
1128 //! <b>Effects</b>: Constructs an empty flat_multiset and
1129 //! inserts elements from the ordered range [first ,last ). This function
1130 //! is more efficient than the normal range creation for ordered ranges.
1131 //!
1132 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1133 //!
1134 //! <b>Complexity</b>: Linear in N.
1135 //!
1136 //! <b>Note</b>: Non-standard extension.
1137 template <class InputIterator>
1138 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last)
1139 : base_t(ordered_range, first, last)
1140 {}
1141
1142 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and
1143 //! inserts elements from the ordered range [first ,last ). This function
1144 //! is more efficient than the normal range creation for ordered ranges.
1145 //!
1146 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1147 //!
1148 //! <b>Complexity</b>: Linear in N.
1149 //!
1150 //! <b>Note</b>: Non-standard extension.
1151 template <class InputIterator>
1152 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1153 : base_t(ordered_range, first, last, comp)
1154 {}
1155
1156 //! <b>Effects</b>: Constructs an empty flat_multiset using the specified comparison object and
1157 //! allocator, and inserts elements from the ordered range [first, last ). This function
1158 //! is more efficient than the normal range creation for ordered ranges.
1159 //!
1160 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1161 //!
1162 //! <b>Complexity</b>: Linear in N.
1163 //!
1164 //! <b>Note</b>: Non-standard extension.
1165 template <class InputIterator>
1166 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1167 : base_t(ordered_range, first, last, comp, a)
1168 {}
1169
1170#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1171 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type)
1172 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il)
1173 : base_t(false, il.begin(), il.end())
1174 {}
1175
1176 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const allocator_type&)
1177 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const allocator_type& a)
1178 : base_t(false, il.begin(), il.end(), a)
1179 {}
1180
1181 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const Compare& comp)
1182 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const Compare& comp)
1183 : base_t(false, il.begin(), il.end(), comp)
1184 {}
1185
1186 //! @copydoc ::boost::container::flat_set::flat_set(std::initializer_list<value_type>, const Compare& comp, const allocator_type&)
1187 BOOST_CONTAINER_FORCEINLINE flat_multiset(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1188 : base_t(false, il.begin(), il.end(), comp, a)
1189 {}
1190
1191 //! <b>Effects</b>: Constructs an empty containerand
1192 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
1193 //! is more efficient than the normal range creation for ordered ranges.
1194 //!
1195 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1196 //!
1197 //! <b>Complexity</b>: Linear in N.
1198 //!
1199 //! <b>Note</b>: Non-standard extension.
1200 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il)
1201 : base_t(ordered_range, il.begin(), il.end())
1202 {}
1203
1204 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
1205 //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
1206 //! is more efficient than the normal range creation for ordered ranges.
1207 //!
1208 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1209 //!
1210 //! <b>Complexity</b>: Linear in N.
1211 //!
1212 //! <b>Note</b>: Non-standard extension.
1213 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1214 : base_t(ordered_range, il.begin(), il.end(), comp)
1215 {}
1216
1217 //! <b>Effects</b>: Constructs an empty container using the specified comparison object and
1218 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
1219 //! is more efficient than the normal range creation for ordered ranges.
1220 //!
1221 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1222 //!
1223 //! <b>Complexity</b>: Linear in N.
1224 //!
1225 //! <b>Note</b>: Non-standard extension.
1226 BOOST_CONTAINER_FORCEINLINE flat_multiset(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1227 : base_t(ordered_range, il.begin(), il.end(), comp, a)
1228 {}
1229#endif
1230
1231 //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &)
1232 BOOST_CONTAINER_FORCEINLINE flat_multiset(const flat_multiset& x)
1233 : base_t(static_cast<const base_t&>(x))
1234 {}
1235
1236 //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&)
1237 BOOST_CONTAINER_FORCEINLINE flat_multiset(BOOST_RV_REF(flat_multiset) x)
1238 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
1239 : base_t(boost::move(static_cast<base_t&>(x)))
1240 {}
1241
1242 //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &, const allocator_type &)
1243 BOOST_CONTAINER_FORCEINLINE flat_multiset(const flat_multiset& x, const allocator_type &a)
1244 : base_t(static_cast<const base_t&>(x), a)
1245 {}
1246
1247 //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&, const allocator_type &)
1248 BOOST_CONTAINER_FORCEINLINE flat_multiset(BOOST_RV_REF(flat_multiset) x, const allocator_type &a)
1249 : base_t(BOOST_MOVE_BASE(base_t, x), a)
1250 {}
1251
1252 //! @copydoc ::boost::container::flat_set::operator=(const flat_set &)
1253 BOOST_CONTAINER_FORCEINLINE flat_multiset& operator=(BOOST_COPY_ASSIGN_REF(flat_multiset) x)
1254 { return static_cast<flat_multiset&>(this->base_t::operator=(static_cast<const base_t&>(x))); }
1255
1256 //! @copydoc ::boost::container::flat_set::operator=(flat_set &&)
1257 BOOST_CONTAINER_FORCEINLINE flat_multiset& operator=(BOOST_RV_REF(flat_multiset) x)
1258 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1259 allocator_traits_type::is_always_equal::value) &&
1260 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
1261 { return static_cast<flat_multiset&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); }
1262
1263#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1264 //! @copydoc ::boost::container::flat_set::operator=(std::initializer_list<value_type>)
1265 flat_multiset& operator=(std::initializer_list<value_type> il)
1266 {
1267 this->clear();
1268 this->insert(il.begin(), il.end());
1269 return *this;
1270 }
1271#endif
1272
1273 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1274
1275 //! @copydoc ::boost::container::flat_set::get_allocator()
1276 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
1277
1278 //! @copydoc ::boost::container::flat_set::get_stored_allocator()
1279 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
1280
1281 //! @copydoc ::boost::container::flat_set::get_stored_allocator() const
1282 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
1283
1284 //! @copydoc ::boost::container::flat_set::begin()
1285 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
1286
1287 //! @copydoc ::boost::container::flat_set::begin() const
1288 const_iterator begin() const;
1289
1290 //! @copydoc ::boost::container::flat_set::cbegin() const
1291 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1292
1293 //! @copydoc ::boost::container::flat_set::end()
1294 iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1295
1296 //! @copydoc ::boost::container::flat_set::end() const
1297 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1298
1299 //! @copydoc ::boost::container::flat_set::cend() const
1300 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1301
1302 //! @copydoc ::boost::container::flat_set::rbegin()
1303 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1304
1305 //! @copydoc ::boost::container::flat_set::rbegin() const
1306 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1307
1308 //! @copydoc ::boost::container::flat_set::crbegin() const
1309 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1310
1311 //! @copydoc ::boost::container::flat_set::rend()
1312 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1313
1314 //! @copydoc ::boost::container::flat_set::rend() const
1315 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1316
1317 //! @copydoc ::boost::container::flat_set::crend() const
1318 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1319
1320 //! @copydoc ::boost::container::flat_set::empty() const
1321 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
1322
1323 //! @copydoc ::boost::container::flat_set::size() const
1324 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
1325
1326 //! @copydoc ::boost::container::flat_set::max_size() const
1327 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
1328
1329 //! @copydoc ::boost::container::flat_set::capacity() const
1330 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW;
1331
1332 //! @copydoc ::boost::container::flat_set::reserve(size_type)
1333 void reserve(size_type cnt);
1334
1335 //! @copydoc ::boost::container::flat_set::shrink_to_fit()
1336 void shrink_to_fit();
1337
1338 #endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1339
1340 //////////////////////////////////////////////
1341 //
1342 // modifiers
1343 //
1344 //////////////////////////////////////////////
1345
1346 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1347
1348 //! <b>Effects</b>: Inserts an object of type Key constructed with
1349 //! std::forward<Args>(args)... and returns the iterator pointing to the
1350 //! newly inserted element.
1351 //!
1352 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1353 //! to the elements with bigger keys than x.
1354 //!
1355 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1356 template <class... Args>
1357 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1358 { return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1359
1360 //! <b>Effects</b>: Inserts an object of type Key constructed with
1361 //! std::forward<Args>(args)... in the container.
1362 //! p is a hint pointing to where the insert should start to search.
1363 //!
1364 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1365 //! to the key of x.
1366 //!
1367 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1368 //! right before p) plus insertion linear to the elements with bigger keys than x.
1369 //!
1370 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1371 template <class... Args>
1372 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1373 { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1374
1375 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1376
1377 #define BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE(N) \
1378 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1379 BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1380 { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\
1381 \
1382 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1383 BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1384 { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
1385 //
1386 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE)
1387 #undef BOOST_CONTAINER_FLAT_MULTISET_EMPLACE_CODE
1388
1389 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1390
1391 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1392 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1393 //! newly inserted element.
1394 //!
1395 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1396 //! to the elements with bigger keys than x.
1397 //!
1398 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1399 iterator insert(const value_type &x);
1400
1401 //! <b>Effects</b>: Inserts a new value_type move constructed from x
1402 //! and returns the iterator pointing to the newly inserted element.
1403 //!
1404 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1405 //! to the elements with bigger keys than x.
1406 //!
1407 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1408 iterator insert(value_type &&x);
1409 #else
1410 BOOST_MOVE_CONVERSION_AWARE_CATCH(insert, value_type, iterator, this->priv_insert)
1411 #endif
1412
1413 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1414 //! <b>Effects</b>: Inserts a copy of x in the container.
1415 //! p is a hint pointing to where the insert should start to search.
1416 //!
1417 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1418 //! to the key of x.
1419 //!
1420 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1421 //! right before p) plus insertion linear to the elements with bigger keys than x.
1422 //!
1423 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1424 iterator insert(const_iterator p, const value_type &x);
1425
1426 //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1427 //! p is a hint pointing to where the insert should start to search.
1428 //!
1429 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1430 //! to the key of x.
1431 //!
1432 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1433 //! right before p) plus insertion linear to the elements with bigger keys than x.
1434 //!
1435 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1436 iterator insert(const_iterator p, value_type &&x);
1437 #else
1438 BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(insert, value_type, iterator, this->priv_insert, const_iterator, const_iterator)
1439 #endif
1440
1441 //! <b>Requires</b>: first, last are not iterators into *this.
1442 //!
1443 //! <b>Effects</b>: inserts each element from the range [first,last) .
1444 //!
1445 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1446 //! search time plus N*size() insertion time.
1447 //!
1448 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1449 template <class InputIterator>
1450 BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1451 { this->base_t::insert_equal(first, last); }
1452
1453 //! <b>Requires</b>: first, last are not iterators into *this and
1454 //! must be ordered according to the predicate.
1455 //!
1456 //! <b>Effects</b>: inserts each element from the range [first,last) .This function
1457 //! is more efficient than the normal range creation for ordered ranges.
1458 //!
1459 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1460 //! search time plus N*size() insertion time.
1461 //!
1462 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1463 template <class InputIterator>
1464 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, InputIterator first, InputIterator last)
1465 { this->base_t::insert_equal(ordered_range, first, last); }
1466
1467#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1468 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()).
1469 //!
1470 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1471 //! search time plus N*size() insertion time.
1472 //!
1473 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1474 BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1475 { this->base_t::insert_equal(il.begin(), il.end()); }
1476
1477 //! <b>Requires</b>: Range [il.begin(), il.end()) must be ordered according to the predicate.
1478 //!
1479 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()). This function
1480 //! is more efficient than the normal range creation for ordered ranges.
1481 //!
1482 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
1483 //! search time plus N*size() insertion time.
1484 //!
1485 //! <b>Note</b>: Non-standard extension. If an element is inserted it might invalidate elements.
1486 BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, std::initializer_list<value_type> il)
1487 { this->base_t::insert_equal(ordered_range, il.begin(), il.end()); }
1488#endif
1489
1490 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&)
1491 template<class C2>
1492 BOOST_CONTAINER_FORCEINLINE void merge(flat_multiset<Key, C2, Allocator>& source)
1493 { this->base_t::merge_equal(source.tree()); }
1494
1495 //! @copydoc ::boost::container::flat_multiset::merge(flat_multiset<Key, C2, Allocator>&)
1496 template<class C2>
1497 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multiset<Key, C2, Allocator> BOOST_RV_REF_END source)
1498 { return this->merge(static_cast<flat_multiset<Key, C2, Allocator>&>(source)); }
1499
1500 //! @copydoc ::boost::container::flat_multimap::merge(flat_map<Key, T, C2, Allocator>&)
1501 template<class C2>
1502 BOOST_CONTAINER_FORCEINLINE void merge(flat_set<Key, C2, Allocator>& source)
1503 { this->base_t::merge_equal(source.tree()); }
1504
1505 //! @copydoc ::boost::container::flat_multiset::merge(flat_set<Key, C2, Allocator>&)
1506 template<class C2>
1507 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_set<Key, C2, Allocator> BOOST_RV_REF_END source)
1508 { return this->merge(static_cast<flat_set<Key, C2, Allocator>&>(source)); }
1509
1510 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1511
1512 //! @copydoc ::boost::container::flat_set::erase(const_iterator)
1513 iterator erase(const_iterator p);
1514
1515 //! @copydoc ::boost::container::flat_set::erase(const key_type&)
1516 size_type erase(const key_type& x);
1517
1518 //! @copydoc ::boost::container::flat_set::erase(const_iterator,const_iterator)
1519 iterator erase(const_iterator first, const_iterator last);
1520
1521 //! @copydoc ::boost::container::flat_set::swap
1522 void swap(flat_multiset& x)
1523 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1524 && boost::container::container_detail::is_nothrow_swappable<Compare>::value );
1525
1526 //! @copydoc ::boost::container::flat_set::clear
1527 void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1528
1529 //! @copydoc ::boost::container::flat_set::key_comp
1530 key_compare key_comp() const;
1531
1532 //! @copydoc ::boost::container::flat_set::value_comp
1533 value_compare value_comp() const;
1534
1535 //! @copydoc ::boost::container::flat_set::find(const key_type& )
1536 iterator find(const key_type& x);
1537
1538 //! @copydoc ::boost::container::flat_set::find(const key_type& ) const
1539 const_iterator find(const key_type& x) const;
1540
1541 //! @copydoc ::boost::container::flat_set::nth(size_type)
1542 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW;
1543
1544 //! @copydoc ::boost::container::flat_set::nth(size_type) const
1545 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW;
1546
1547 //! @copydoc ::boost::container::flat_set::index_of(iterator)
1548 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
1549
1550 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
1551 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW;
1552
1553 //! @copydoc ::boost::container::flat_set::count(const key_type& ) const
1554 size_type count(const key_type& x) const;
1555
1556 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& )
1557 iterator lower_bound(const key_type& x);
1558
1559 //! @copydoc ::boost::container::flat_set::lower_bound(const key_type& ) const
1560 const_iterator lower_bound(const key_type& x) const;
1561
1562 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& )
1563 iterator upper_bound(const key_type& x);
1564
1565 //! @copydoc ::boost::container::flat_set::upper_bound(const key_type& ) const
1566 const_iterator upper_bound(const key_type& x) const;
1567
1568 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& ) const
1569 std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
1570
1571 //! @copydoc ::boost::container::flat_set::equal_range(const key_type& )
1572 std::pair<iterator,iterator> equal_range(const key_type& x);
1573
1574 //! <b>Effects</b>: Returns true if x and y are equal
1575 //!
1576 //! <b>Complexity</b>: Linear to the number of elements in the container.
1577 friend bool operator==(const flat_multiset& x, const flat_multiset& y);
1578
1579 //! <b>Effects</b>: Returns true if x and y are unequal
1580 //!
1581 //! <b>Complexity</b>: Linear to the number of elements in the container.
1582 friend bool operator!=(const flat_multiset& x, const flat_multiset& y);
1583
1584 //! <b>Effects</b>: Returns true if x is less than y
1585 //!
1586 //! <b>Complexity</b>: Linear to the number of elements in the container.
1587 friend bool operator<(const flat_multiset& x, const flat_multiset& y);
1588
1589 //! <b>Effects</b>: Returns true if x is greater than y
1590 //!
1591 //! <b>Complexity</b>: Linear to the number of elements in the container.
1592 friend bool operator>(const flat_multiset& x, const flat_multiset& y);
1593
1594 //! <b>Effects</b>: Returns true if x is equal or less than y
1595 //!
1596 //! <b>Complexity</b>: Linear to the number of elements in the container.
1597 friend bool operator<=(const flat_multiset& x, const flat_multiset& y);
1598
1599 //! <b>Effects</b>: Returns true if x is equal or greater than y
1600 //!
1601 //! <b>Complexity</b>: Linear to the number of elements in the container.
1602 friend bool operator>=(const flat_multiset& x, const flat_multiset& y);
1603
1604 //! <b>Effects</b>: x.swap(y)
1605 //!
1606 //! <b>Complexity</b>: Constant.
1607 friend void swap(flat_multiset& x, flat_multiset& y);
1608
1609 //! <b>Effects</b>: Extracts the internal sequence container.
1610 //!
1611 //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
1612 //!
1613 //! <b>Postcondition</b>: this->empty()
1614 //!
1615 //! <b>Throws</b>: If secuence_type's move constructor throws
1616 sequence_type extract_sequence();
1617
1618 #endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1619
1620 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1621 //! one passed externally using the move assignment.
1622 //!
1623 //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
1624 //!
1625 //! <b>Throws</b>: If the comparison or the move constructor throws
1626 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
1627 { this->base_t::adopt_sequence_equal(boost::move(seq)); }
1628
1629 //! <b>Requires</b>: seq shall be ordered according to this->compare()
1630 //!
1631 //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1632 //! one passed externally using the move assignment.
1633 //!
1634 //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
1635 //!
1636 //! <b>Throws</b>: If the move assignment throws
1637 BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
1638 { this->base_t::adopt_sequence_equal(ordered_range_t(), boost::move(seq)); }
1639
1640 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1641 private:
1642 template <class KeyType>
1643 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(BOOST_FWD_REF(KeyType) x)
1644 { return this->base_t::insert_equal(::boost::forward<KeyType>(x)); }
1645
1646 template <class KeyType>
1647 BOOST_CONTAINER_FORCEINLINE iterator priv_insert(const_iterator p, BOOST_FWD_REF(KeyType) x)
1648 { return this->base_t::insert_equal(p, ::boost::forward<KeyType>(x)); }
1649 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1650};
1651
1652#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1653
1654} //namespace container {
1655
1656//!has_trivial_destructor_after_move<> == true_type
1657//!specialization for optimizations
1658template <class Key, class Compare, class Allocator>
1659struct has_trivial_destructor_after_move<boost::container::flat_multiset<Key, Compare, Allocator> >
1660{
1661 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1662 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1663 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1664 ::boost::has_trivial_destructor_after_move<Compare>::value;
1665};
1666
1667namespace container {
1668
1669#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1670
1671}}
1672
1673#include <boost/container/detail/config_end.hpp>
1674
1675#endif // BOOST_CONTAINER_FLAT_SET_HPP
1676