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_MAP_HPP
11 #define BOOST_CONTAINER_FLAT_MAP_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>
24 #include <boost/container/allocator_traits.hpp>
25 #include <boost/container/container_fwd.hpp>
26 #include <boost/container/new_allocator.hpp> //new_allocator
27 #include <boost/container/throw_exception.hpp>
29 #include <boost/container/detail/flat_tree.hpp>
30 #include <boost/container/detail/type_traits.hpp>
31 #include <boost/container/detail/mpl.hpp>
32 #include <boost/container/detail/algorithm.hpp> //equal()
34 #include <boost/move/utility_core.hpp>
35 #include <boost/move/traits.hpp>
37 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
38 #include <boost/move/detail/fwd_macros.hpp>
40 #include <boost/move/detail/move_helpers.hpp>
42 #include <boost/intrusive/detail/minimal_pair_header.hpp> //pair
43 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
45 #include <boost/core/no_exceptions_support.hpp>
47 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
48 #include <initializer_list>
54 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
56 template <class Key, class T, class Compare, class Allocator>
59 namespace container_detail{
61 template<class D, class S>
62 BOOST_CONTAINER_FORCEINLINE static D &force(const S &s)
63 { return *const_cast<D*>((reinterpret_cast<const D*>(&s))); }
65 template<class D, class S>
66 BOOST_CONTAINER_FORCEINLINE static D force_copy(S s)
68 D *vp = reinterpret_cast<D *>(&s);
72 } //namespace container_detail{
74 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
76 //! A flat_map is a kind of associative container that supports unique keys (contains at
77 //! most one of each key value) and provides for fast retrieval of values of another
78 //! type T based on the keys. The flat_map class supports random-access iterators.
80 //! A flat_map satisfies all of the requirements of a container and of a reversible
81 //! container and of an associative container. A flat_map also provides
82 //! most operations described for unique keys. For a
83 //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
84 //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
86 //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
88 //! Allocator is the allocator to allocate the value_types
89 //! (e.g. <i>allocator< std::pair<Key, T> ></i>).
91 //! flat_map is similar to std::map but it's implemented like an ordered vector.
92 //! This means that inserting a new element into a flat_map invalidates
93 //! previous iterators and references
95 //! Erasing an element invalidates iterators and references
96 //! pointing to elements that come after (their keys are bigger) the erased element.
98 //! This container provides random-access iterators.
100 //! \tparam Key is the key_type of the map
101 //! \tparam Value is the <code>mapped_type</code>
102 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
103 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
104 //! (e.g. <i>allocator< std::pair<Key, T> > </i>).
105 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
106 template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > >
108 template <class Key, class T, class Compare, class Allocator>
112 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
114 BOOST_COPYABLE_AND_MOVABLE(flat_map)
115 //This is the tree that we should store if pair was movable
116 typedef container_detail::flat_tree<
118 container_detail::select1st<Key>,
122 //This is the real tree stored here. It's based on a movable pair
123 typedef container_detail::flat_tree<
124 container_detail::pair<Key, T>,
125 container_detail::select1st<Key>,
127 typename allocator_traits<Allocator>::template portable_rebind_alloc
128 <container_detail::pair<Key, T> >::type> impl_tree_t;
129 impl_tree_t m_flat_tree; // flat tree representing flat_map
131 typedef typename impl_tree_t::value_type impl_value_type;
132 typedef typename impl_tree_t::const_iterator impl_const_iterator;
133 typedef typename impl_tree_t::iterator impl_iterator;
134 typedef typename impl_tree_t::allocator_type impl_allocator_type;
135 typedef container_detail::flat_tree_value_compare
137 , container_detail::select1st<Key>
138 , std::pair<Key, T> > value_compare_impl;
139 typedef typename container_detail::get_flat_tree_iterators
140 <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl;
141 typedef typename container_detail::get_flat_tree_iterators
142 <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl;
143 typedef typename container_detail::get_flat_tree_iterators
144 <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl;
145 typedef typename container_detail::get_flat_tree_iterators
146 <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl;
148 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
151 { return m_flat_tree; }
153 const impl_tree_t &tree() const
154 { return m_flat_tree; }
157 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
161 //////////////////////////////////////////////
165 //////////////////////////////////////////////
166 typedef Key key_type;
167 typedef T mapped_type;
168 typedef std::pair<Key, T> value_type;
169 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
170 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
171 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
172 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
173 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
174 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
175 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
176 typedef Allocator allocator_type;
177 typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type;
178 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
179 typedef Compare key_compare;
180 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
181 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
182 typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator;
183 typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator;
184 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
187 //////////////////////////////////////////////
189 // construct/copy/destroy
191 //////////////////////////////////////////////
193 //! <b>Effects</b>: Default constructs an empty flat_map.
195 //! <b>Complexity</b>: Constant.
196 flat_map() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
197 container_detail::is_nothrow_default_constructible<Compare>::value)
200 //value_type must be std::pair<Key, T>
201 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
204 //! <b>Effects</b>: Constructs an empty flat_map using the specified
205 //! comparison object and allocator.
207 //! <b>Complexity</b>: Constant.
208 explicit flat_map(const Compare& comp, const allocator_type& a = allocator_type())
209 : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a))
211 //value_type must be std::pair<Key, T>
212 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
215 //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator.
217 //! <b>Complexity</b>: Constant.
218 explicit flat_map(const allocator_type& a)
219 : m_flat_tree(container_detail::force<impl_allocator_type>(a))
221 //value_type must be std::pair<Key, T>
222 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
225 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
226 //! allocator, and inserts elements from the range [first ,last ).
228 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
229 //! comp and otherwise N logN, where N is last - first.
230 template <class InputIterator>
231 flat_map(InputIterator first, InputIterator last, const Compare& comp = Compare(),
232 const allocator_type& a = allocator_type())
233 : m_flat_tree(true, first, last, comp, container_detail::force<impl_allocator_type>(a))
235 //value_type must be std::pair<Key, T>
236 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
239 //! <b>Effects</b>: Constructs an empty flat_map using the specified
240 //! allocator, and inserts elements from the range [first ,last ).
242 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
243 //! comp and otherwise N logN, where N is last - first.
244 template <class InputIterator>
245 flat_map(InputIterator first, InputIterator last, const allocator_type& a)
246 : m_flat_tree(true, first, last, Compare(), container_detail::force<impl_allocator_type>(a))
248 //value_type must be std::pair<Key, T>
249 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
252 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
253 //! allocator, and inserts elements from the ordered unique range [first ,last). This function
254 //! is more efficient than the normal range creation for ordered ranges.
256 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
259 //! <b>Complexity</b>: Linear in N.
261 //! <b>Note</b>: Non-standard extension.
262 template <class InputIterator>
263 flat_map( ordered_unique_range_t, InputIterator first, InputIterator last
264 , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
265 : m_flat_tree(ordered_unique_range, first, last, comp, a)
267 //value_type must be std::pair<Key, T>
268 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
271 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
272 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
273 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
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 last - first.
277 flat_map(std::initializer_list<value_type> il, const Compare& comp = Compare(),
278 const allocator_type& a = allocator_type())
279 : m_flat_tree(true, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a))
281 //value_type must be std::pair<Key, T>
282 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
285 //! <b>Effects</b>: Constructs an empty flat_map using the specified
286 //! allocator, and inserts elements from the range [il.begin() ,il.end()).
288 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
289 //! comp and otherwise N logN, where N is last - first.
290 flat_map(std::initializer_list<value_type> il, const allocator_type& a)
291 : m_flat_tree(true, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a))
293 //value_type must be std::pair<Key, T>
294 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
297 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
298 //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
299 //! is more efficient than the normal range creation for ordered ranges.
301 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
304 //! <b>Complexity</b>: Linear in N.
306 //! <b>Note</b>: Non-standard extension.
307 flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
308 const allocator_type& a = allocator_type())
309 : m_flat_tree(ordered_unique_range, il.begin(), il.end(), comp, a)
311 //value_type must be std::pair<Key, T>
312 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
316 //! <b>Effects</b>: Copy constructs a flat_map.
318 //! <b>Complexity</b>: Linear in x.size().
319 flat_map(const flat_map& x)
320 : m_flat_tree(x.m_flat_tree)
322 //value_type must be std::pair<Key, T>
323 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
326 //! <b>Effects</b>: Move constructs a flat_map.
327 //! Constructs *this using x's resources.
329 //! <b>Complexity</b>: Constant.
331 //! <b>Postcondition</b>: x is emptied.
332 flat_map(BOOST_RV_REF(flat_map) x)
333 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
334 : m_flat_tree(boost::move(x.m_flat_tree))
336 //value_type must be std::pair<Key, T>
337 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
340 //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator.
342 //! <b>Complexity</b>: Linear in x.size().
343 flat_map(const flat_map& x, const allocator_type &a)
344 : m_flat_tree(x.m_flat_tree, a)
346 //value_type must be std::pair<Key, T>
347 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
350 //! <b>Effects</b>: Move constructs a flat_map using the specified allocator.
351 //! Constructs *this using x's resources.
353 //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise.
354 flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a)
355 : m_flat_tree(boost::move(x.m_flat_tree), a)
357 //value_type must be std::pair<Key, T>
358 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
361 //! <b>Effects</b>: Makes *this a copy of x.
363 //! <b>Complexity</b>: Linear in x.size().
364 flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x)
365 { m_flat_tree = x.m_flat_tree; return *this; }
367 //! <b>Effects</b>: Move constructs a flat_map.
368 //! Constructs *this using x's resources.
370 //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
371 //! is false and (allocation throws or value_type's move constructor throws)
373 //! <b>Complexity</b>: Constant if allocator_traits_type::
374 //! propagate_on_container_move_assignment is true or
375 //! this->get>allocator() == x.get_allocator(). Linear otherwise.
376 flat_map& operator=(BOOST_RV_REF(flat_map) x)
377 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
378 allocator_traits_type::is_always_equal::value) &&
379 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
380 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
382 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
383 //! <b>Effects</b>: Assign elements from il to *this
384 flat_map& operator=(std::initializer_list<value_type> il)
387 this->insert(il.begin(), il.end());
392 //! <b>Effects</b>: Returns a copy of the allocator that
393 //! was passed to the object's constructor.
395 //! <b>Complexity</b>: Constant.
396 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
397 { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
399 //! <b>Effects</b>: Returns a reference to the internal allocator.
401 //! <b>Throws</b>: Nothing
403 //! <b>Complexity</b>: Constant.
405 //! <b>Note</b>: Non-standard extension.
406 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
407 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
409 //! <b>Effects</b>: Returns a reference to the internal allocator.
411 //! <b>Throws</b>: Nothing
413 //! <b>Complexity</b>: Constant.
415 //! <b>Note</b>: Non-standard extension.
416 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
417 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
419 //////////////////////////////////////////////
423 //////////////////////////////////////////////
425 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
427 //! <b>Throws</b>: Nothing.
429 //! <b>Complexity</b>: Constant.
430 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
431 { return container_detail::force_copy<iterator>(m_flat_tree.begin()); }
433 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
435 //! <b>Throws</b>: Nothing.
437 //! <b>Complexity</b>: Constant.
438 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
439 { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); }
441 //! <b>Effects</b>: Returns an iterator to the end of the container.
443 //! <b>Throws</b>: Nothing.
445 //! <b>Complexity</b>: Constant.
446 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
447 { return container_detail::force_copy<iterator>(m_flat_tree.end()); }
449 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
451 //! <b>Throws</b>: Nothing.
453 //! <b>Complexity</b>: Constant.
454 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
455 { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); }
457 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
458 //! of the reversed container.
460 //! <b>Throws</b>: Nothing.
462 //! <b>Complexity</b>: Constant.
463 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
464 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
466 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
467 //! of the reversed container.
469 //! <b>Throws</b>: Nothing.
471 //! <b>Complexity</b>: Constant.
472 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
473 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
475 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
476 //! of the reversed container.
478 //! <b>Throws</b>: Nothing.
480 //! <b>Complexity</b>: Constant.
481 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
482 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); }
484 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
485 //! of the reversed container.
487 //! <b>Throws</b>: Nothing.
489 //! <b>Complexity</b>: Constant.
490 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
491 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
493 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
495 //! <b>Throws</b>: Nothing.
497 //! <b>Complexity</b>: Constant.
498 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
499 { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); }
501 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
503 //! <b>Throws</b>: Nothing.
505 //! <b>Complexity</b>: Constant.
506 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
507 { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); }
509 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
510 //! of the reversed container.
512 //! <b>Throws</b>: Nothing.
514 //! <b>Complexity</b>: Constant.
515 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
516 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
518 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
519 //! of the reversed container.
521 //! <b>Throws</b>: Nothing.
523 //! <b>Complexity</b>: Constant.
524 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
525 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
527 //////////////////////////////////////////////
531 //////////////////////////////////////////////
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
539 { return m_flat_tree.empty(); }
541 //! <b>Effects</b>: Returns the number of the elements contained in the container.
543 //! <b>Throws</b>: Nothing.
545 //! <b>Complexity</b>: Constant.
546 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
547 { return m_flat_tree.size(); }
549 //! <b>Effects</b>: Returns the largest possible size of the container.
551 //! <b>Throws</b>: Nothing.
553 //! <b>Complexity</b>: Constant.
554 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
555 { return m_flat_tree.max_size(); }
557 //! <b>Effects</b>: Number of elements for which memory has been allocated.
558 //! capacity() is always greater than or equal to size().
560 //! <b>Throws</b>: Nothing.
562 //! <b>Complexity</b>: Constant.
563 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
564 { return m_flat_tree.capacity(); }
566 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
567 //! effect. Otherwise, it is a request for allocation of additional memory.
568 //! If the request is successful, then capacity() is greater than or equal to
569 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
571 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
573 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
574 //! to values might be invalidated.
575 void reserve(size_type cnt)
576 { m_flat_tree.reserve(cnt); }
578 //! <b>Effects</b>: Tries to deallocate the excess of memory created
579 // with previous allocations. The size of the vector is unchanged
581 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
583 //! <b>Complexity</b>: Linear to size().
585 { m_flat_tree.shrink_to_fit(); }
587 //////////////////////////////////////////////
591 //////////////////////////////////////////////
593 #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
594 //! Effects: If there is no key equivalent to x in the flat_map, inserts
595 //! value_type(x, T()) into the flat_map.
597 //! Returns: A reference to the mapped_type corresponding to x in *this.
599 //! Complexity: Logarithmic.
600 mapped_type &operator[](const key_type& k);
602 //! Effects: If there is no key equivalent to x in the flat_map, inserts
603 //! value_type(move(x), T()) into the flat_map (the key is move-constructed)
605 //! Returns: A reference to the mapped_type corresponding to x in *this.
607 //! Complexity: Logarithmic.
608 mapped_type &operator[](key_type &&k) ;
609 #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
610 //in compilers like GCC 3.4, we can't catch temporaries
611 mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); }
612 mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); }
614 BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
617 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
618 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
619 //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
621 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
622 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
623 //! references obtained to that element before it was extracted become valid.
625 //! Returns: The bool component is true if the insertion took place and false if the assignment
626 //! took place. The iterator component is pointing at the element that was inserted or updated.
628 //! Complexity: Logarithmic in the size of the container.
630 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
632 return container_detail::force_copy< std::pair<iterator, bool> >
633 (this->m_flat_tree.insert_or_assign
634 ( impl_const_iterator(), k, ::boost::forward<M>(obj))
638 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
639 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
640 //! as if by insert, constructing it from value_type(k, move(obj)).
642 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
643 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
644 //! references obtained to that element before it was extracted become valid.
646 //! Returns: The bool component is true if the insertion took place and false if the assignment
647 //! took place. The iterator component is pointing at the element that was inserted or updated.
649 //! Complexity: Logarithmic in the size of the container.
651 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
653 return container_detail::force_copy< std::pair<iterator, bool> >
654 (this->m_flat_tree.insert_or_assign
655 ( impl_const_iterator(), ::boost::move(k), ::boost::forward<M>(obj))
659 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
660 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
661 //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
662 //! to the container as close as possible to the position just before hint.
664 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
665 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
666 //! references obtained to that element before it was extracted become valid.
668 //! Returns: The bool component is true if the insertion took place and false if the assignment
669 //! took place. The iterator component is pointing at the element that was inserted or updated.
671 //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
672 //! the new element is inserted just before hint.
674 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
676 return container_detail::force_copy< std::pair<iterator, bool> >
677 (this->m_flat_tree.insert_or_assign
678 ( container_detail::force_copy<impl_const_iterator>(hint)
679 , k, ::boost::forward<M>(obj))
683 //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
684 //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
685 //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
686 //! to the container as close as possible to the position just before hint.
688 //! No iterators or references are invalidated. If the insertion is successful, pointers and references
689 //! to the element obtained while it is held in the node handle are invalidated, and pointers and
690 //! references obtained to that element before it was extracted become valid.
692 //! Returns: The bool component is true if the insertion took place and false if the assignment
693 //! took place. The iterator component is pointing at the element that was inserted or updated.
695 //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
696 //! the new element is inserted just before hint.
698 BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
700 return container_detail::force_copy< std::pair<iterator, bool> >
701 (this->m_flat_tree.insert_or_assign
702 ( container_detail::force_copy<impl_const_iterator>(hint)
703 , ::boost::move(k), ::boost::forward<M>(obj))
707 //! @copydoc ::boost::container::flat_set::nth(size_type)
708 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
709 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
711 //! @copydoc ::boost::container::flat_set::nth(size_type) const
712 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
713 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
715 //! @copydoc ::boost::container::flat_set::index_of(iterator)
716 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
717 { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); }
719 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
720 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
721 { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); }
723 //! Returns: A reference to the element whose key is equivalent to x.
725 //! Throws: An exception object of type out_of_range if no such element is present.
727 //! Complexity: logarithmic.
728 T& at(const key_type& k)
730 iterator i = this->find(k);
731 if(i == this->end()){
732 throw_out_of_range("flat_map::at key not found");
737 //! Returns: A reference to the element whose key is equivalent to x.
739 //! Throws: An exception object of type out_of_range if no such element is present.
741 //! Complexity: logarithmic.
742 const T& at(const key_type& k) const
744 const_iterator i = this->find(k);
745 if(i == this->end()){
746 throw_out_of_range("flat_map::at key not found");
751 //////////////////////////////////////////////
755 //////////////////////////////////////////////
757 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
759 //! <b>Effects</b>: Inserts an object x of type T constructed with
760 //! std::forward<Args>(args)... if and only if there is no element in the container
761 //! with key equivalent to the key of x.
763 //! <b>Returns</b>: The bool component of the returned pair is true if and only
764 //! if the insertion takes place, and the iterator component of the pair
765 //! points to the element with key equivalent to the key of x.
767 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
768 //! to the elements with bigger keys than x.
770 //! <b>Note</b>: If an element is inserted it might invalidate elements.
771 template <class... Args>
772 std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
773 { return container_detail::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); }
775 //! <b>Effects</b>: Inserts an object of type T constructed with
776 //! std::forward<Args>(args)... in the container if and only if there is
777 //! no element in the container with key equivalent to the key of x.
778 //! p is a hint pointing to where the insert should start to search.
780 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
783 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
784 //! right before p) plus insertion linear to the elements with bigger keys than x.
786 //! <b>Note</b>: If an element is inserted it might invalidate elements.
787 template <class... Args>
788 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
790 return container_detail::force_copy<iterator>
791 (m_flat_tree.emplace_hint_unique( container_detail::force_copy<impl_const_iterator>(hint)
792 , boost::forward<Args>(args)...));
795 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
796 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
798 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
799 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
800 //! forward_as_tuple(forward<Args>(args)...).
802 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
803 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
805 //! <b>Complexity</b>: Logarithmic.
806 template <class... Args>
807 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
809 return container_detail::force_copy< std::pair<iterator, bool> >(
810 m_flat_tree.try_emplace(impl_const_iterator(), k, boost::forward<Args>(args)...));
813 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
814 //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
816 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
817 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
818 //! forward_as_tuple(forward<Args>(args)...).
820 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
822 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
823 //! is inserted right before p.
824 template <class... Args>
825 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
827 return container_detail::force_copy<iterator>(m_flat_tree.try_emplace
828 (container_detail::force_copy<impl_const_iterator>(hint), k, boost::forward<Args>(args)...).first);
831 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
832 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
834 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
835 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
836 //! forward_as_tuple(forward<Args>(args)...).
838 //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
839 //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
841 //! <b>Complexity</b>: Logarithmic.
842 template <class... Args>
843 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
845 return container_detail::force_copy< std::pair<iterator, bool> >
846 (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k), boost::forward<Args>(args)...));
849 //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
850 //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
852 //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
853 //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
854 //! forward_as_tuple(forward<Args>(args)...).
856 //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
858 //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
859 //! is inserted right before p.
860 template <class... Args>
861 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
863 return container_detail::force_copy<iterator>
864 (m_flat_tree.try_emplace(container_detail::force_copy
865 <impl_const_iterator>(hint), boost::move(k), boost::forward<Args>(args)...).first);
868 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
870 #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \
871 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
872 std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
874 return container_detail::force_copy< std::pair<iterator, bool> >\
875 (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\
878 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
879 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
881 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_unique\
882 (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
884 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
885 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
887 return container_detail::force_copy< std::pair<iterator, bool> >\
888 (m_flat_tree.try_emplace(impl_const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
891 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
892 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
893 { return container_detail::force_copy<iterator>(m_flat_tree.try_emplace\
894 (container_detail::force_copy<impl_const_iterator>(hint), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
896 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
897 BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
899 return container_detail::force_copy< std::pair<iterator, bool> >\
900 (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
903 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
904 BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
905 { return container_detail::force_copy<iterator>(m_flat_tree.try_emplace\
906 (container_detail::force_copy<impl_const_iterator>(hint), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
908 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)
909 #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE
911 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
913 //! <b>Effects</b>: Inserts x if and only if there is no element in the container
914 //! with key equivalent to the key of x.
916 //! <b>Returns</b>: The bool component of the returned pair is true if and only
917 //! if the insertion takes place, and the iterator component of the pair
918 //! points to the element with key equivalent to the key of x.
920 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
921 //! to the elements with bigger keys than x.
923 //! <b>Note</b>: If an element is inserted it might invalidate elements.
924 std::pair<iterator,bool> insert(const value_type& x)
925 { return container_detail::force_copy<std::pair<iterator,bool> >(
926 m_flat_tree.insert_unique(container_detail::force<impl_value_type>(x))); }
928 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
929 //! only if there is no element in the container with key equivalent to the key of x.
931 //! <b>Returns</b>: The bool component of the returned pair is true if and only
932 //! if the insertion takes place, and the iterator component of the pair
933 //! points to the element with key equivalent to the key of x.
935 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
936 //! to the elements with bigger keys than x.
938 //! <b>Note</b>: If an element is inserted it might invalidate elements.
939 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
940 { return container_detail::force_copy<std::pair<iterator,bool> >(
941 m_flat_tree.insert_unique(boost::move(container_detail::force<impl_value_type>(x)))); }
943 //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
944 //! only if there is no element in the container with key equivalent to the key of x.
946 //! <b>Returns</b>: The bool component of the returned pair is true if and only
947 //! if the insertion takes place, and the iterator component of the pair
948 //! points to the element with key equivalent to the key of x.
950 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
951 //! to the elements with bigger keys than x.
953 //! <b>Note</b>: If an element is inserted it might invalidate elements.
954 std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
956 return container_detail::force_copy<std::pair<iterator,bool> >
957 (m_flat_tree.insert_unique(boost::move(x)));
960 //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
961 //! no element in the container with key equivalent to the key of x.
962 //! p is a hint pointing to where the insert should start to search.
964 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
967 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
968 //! right before p) plus insertion linear to the elements with bigger keys than x.
970 //! <b>Note</b>: If an element is inserted it might invalidate elements.
971 iterator insert(const_iterator p, const value_type& x)
973 return container_detail::force_copy<iterator>(
974 m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p)
975 , container_detail::force<impl_value_type>(x)));
978 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
979 //! p is a hint pointing to where the insert should start to search.
981 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
983 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
984 //! right before p) plus insertion linear to the elements with bigger keys than x.
986 //! <b>Note</b>: If an element is inserted it might invalidate elements.
987 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
989 return container_detail::force_copy<iterator>
990 (m_flat_tree.insert_unique( container_detail::force_copy<impl_const_iterator>(p)
991 , boost::move(container_detail::force<impl_value_type>(x))));
994 //! <b>Effects</b>: Inserts an element move constructed from x in the container.
995 //! p is a hint pointing to where the insert should start to search.
997 //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
999 //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1000 //! right before p) plus insertion linear to the elements with bigger keys than x.
1002 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1003 iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1005 return container_detail::force_copy<iterator>(
1006 m_flat_tree.insert_unique(container_detail::force_copy<impl_const_iterator>(p), boost::move(x)));
1009 //! <b>Requires</b>: first, last are not iterators into *this.
1011 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1012 //! if there is no element with key equivalent to the key of that element.
1014 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1015 //! search time plus N*size() insertion time.
1017 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1018 template <class InputIterator>
1019 void insert(InputIterator first, InputIterator last)
1020 { m_flat_tree.insert_unique(first, last); }
1022 //! <b>Requires</b>: first, last are not iterators into *this.
1024 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
1027 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1028 //! if there is no element with key equivalent to the key of that element. This
1029 //! function is more efficient than the normal range creation for ordered ranges.
1031 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1032 //! search time plus N*size() insertion time.
1034 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1036 //! <b>Note</b>: Non-standard extension.
1037 template <class InputIterator>
1038 void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
1039 { m_flat_tree.insert_unique(ordered_unique_range, first, last); }
1041 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1042 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1043 //! if there is no element with key equivalent to the key of that element.
1045 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.first() to il.end())
1046 //! search time plus N*size() insertion time.
1048 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1049 void insert(std::initializer_list<value_type> il)
1050 { m_flat_tree.insert_unique(il.begin(), il.end()); }
1052 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
1055 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1056 //! if there is no element with key equivalent to the key of that element. This
1057 //! function is more efficient than the normal range creation for ordered ranges.
1059 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1060 //! search time plus N*size() insertion time.
1062 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1064 //! <b>Note</b>: Non-standard extension.
1065 void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
1066 { m_flat_tree.insert_unique(ordered_unique_range, il.begin(), il.end()); }
1069 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1071 //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
1072 //! the comparison object of *this. If there is an element in a with key equivalent to the
1073 //! key of an element from source, then that element is not extracted from source.
1075 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1076 //! to those same elements but as members of *this. Iterators referring to the transferred
1077 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
1078 //! not into source.
1080 //! <b>Throws</b>: Nothing unless the comparison object throws.
1082 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
1084 BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, Allocator>& source)
1085 { m_flat_tree.merge_unique(source.tree()); }
1087 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&)
1089 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, Allocator> BOOST_RV_REF_END source)
1090 { return this->merge(static_cast<flat_map<Key, T, C2, Allocator>&>(source)); }
1092 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&)
1094 BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, Allocator>& source)
1095 { m_flat_tree.merge_unique(source.tree()); }
1097 //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, Allocator>&)
1099 BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, Allocator> BOOST_RV_REF_END source)
1100 { return this->merge(static_cast<flat_multimap<Key, T, C2, Allocator>&>(source)); }
1102 //! <b>Effects</b>: Erases the element pointed to by p.
1104 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1105 //! following q prior to the element being erased. If no such element exists,
1108 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
1110 //! <b>Note</b>: Invalidates elements with keys
1111 //! not less than the erased element.
1112 iterator erase(const_iterator p)
1114 return container_detail::force_copy<iterator>
1115 (m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p)));
1118 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1120 //! <b>Returns</b>: Returns the number of erased elements.
1122 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1123 //! linear to the elements with bigger keys.
1124 size_type erase(const key_type& x)
1125 { return m_flat_tree.erase(x); }
1127 //! <b>Effects</b>: Erases all the elements in the range [first, last).
1129 //! <b>Returns</b>: Returns last.
1131 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
1133 //! <b>Complexity</b>: Logarithmic search time plus erasure time
1134 //! linear to the elements with bigger keys.
1135 iterator erase(const_iterator first, const_iterator last)
1137 return container_detail::force_copy<iterator>(
1138 m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first)
1139 , container_detail::force_copy<impl_const_iterator>(last)));
1142 //! <b>Effects</b>: Swaps the contents of *this and x.
1144 //! <b>Throws</b>: Nothing.
1146 //! <b>Complexity</b>: Constant.
1147 void swap(flat_map& x)
1148 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
1149 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
1150 { m_flat_tree.swap(x.m_flat_tree); }
1152 //! <b>Effects</b>: erase(a.begin(),a.end()).
1154 //! <b>Postcondition</b>: size() == 0.
1156 //! <b>Complexity</b>: linear in size().
1157 void clear() BOOST_NOEXCEPT_OR_NOTHROW
1158 { m_flat_tree.clear(); }
1160 //////////////////////////////////////////////
1164 //////////////////////////////////////////////
1166 //! <b>Effects</b>: Returns the comparison object out
1167 //! of which a was constructed.
1169 //! <b>Complexity</b>: Constant.
1170 key_compare key_comp() const
1171 { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); }
1173 //! <b>Effects</b>: Returns an object of value_compare constructed out
1174 //! of the comparison object.
1176 //! <b>Complexity</b>: Constant.
1177 value_compare value_comp() const
1178 { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); }
1180 //////////////////////////////////////////////
1184 //////////////////////////////////////////////
1186 //! <b>Returns</b>: An iterator pointing to an element with the key
1187 //! equivalent to x, or end() if such an element is not found.
1189 //! <b>Complexity</b>: Logarithmic.
1190 iterator find(const key_type& x)
1191 { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); }
1193 //! <b>Returns</b>: A const_iterator pointing to an element with the key
1194 //! equivalent to x, or end() if such an element is not found.
1196 //! <b>Complexity</b>: Logarithmic.
1197 const_iterator find(const key_type& x) const
1198 { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); }
1200 //! <b>Returns</b>: The number of elements with key equivalent to x.
1202 //! <b>Complexity</b>: log(size())+count(k)
1203 size_type count(const key_type& x) const
1204 { return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }
1206 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1207 //! than k, or a.end() if such an element is not found.
1209 //! <b>Complexity</b>: Logarithmic.
1210 iterator lower_bound(const key_type& x)
1211 { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1213 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1214 //! less than k, or a.end() if such an element is not found.
1216 //! <b>Complexity</b>: Logarithmic.
1217 const_iterator lower_bound(const key_type& x) const
1218 { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1220 //! <b>Returns</b>: An iterator pointing to the first element with key not less
1221 //! than x, or end() if such an element is not found.
1223 //! <b>Complexity</b>: Logarithmic.
1224 iterator upper_bound(const key_type& x)
1225 { return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1227 //! <b>Returns</b>: A const iterator pointing to the first element with key not
1228 //! less than x, or end() if such an element is not found.
1230 //! <b>Complexity</b>: Logarithmic.
1231 const_iterator upper_bound(const key_type& x) const
1232 { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1234 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1236 //! <b>Complexity</b>: Logarithmic.
1237 std::pair<iterator,iterator> equal_range(const key_type& x)
1238 { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1240 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1242 //! <b>Complexity</b>: Logarithmic.
1243 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
1244 { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1246 //! <b>Effects</b>: Returns true if x and y are equal
1248 //! <b>Complexity</b>: Linear to the number of elements in the container.
1249 friend bool operator==(const flat_map& x, const flat_map& y)
1250 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
1252 //! <b>Effects</b>: Returns true if x and y are unequal
1254 //! <b>Complexity</b>: Linear to the number of elements in the container.
1255 friend bool operator!=(const flat_map& x, const flat_map& y)
1256 { return !(x == y); }
1258 //! <b>Effects</b>: Returns true if x is less than y
1260 //! <b>Complexity</b>: Linear to the number of elements in the container.
1261 friend bool operator<(const flat_map& x, const flat_map& y)
1262 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
1264 //! <b>Effects</b>: Returns true if x is greater than y
1266 //! <b>Complexity</b>: Linear to the number of elements in the container.
1267 friend bool operator>(const flat_map& x, const flat_map& y)
1270 //! <b>Effects</b>: Returns true if x is equal or less than y
1272 //! <b>Complexity</b>: Linear to the number of elements in the container.
1273 friend bool operator<=(const flat_map& x, const flat_map& y)
1274 { return !(y < x); }
1276 //! <b>Effects</b>: Returns true if x is equal or greater than y
1278 //! <b>Complexity</b>: Linear to the number of elements in the container.
1279 friend bool operator>=(const flat_map& x, const flat_map& y)
1280 { return !(x < y); }
1282 //! <b>Effects</b>: x.swap(y)
1284 //! <b>Complexity</b>: Constant.
1285 friend void swap(flat_map& x, flat_map& y)
1288 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1290 mapped_type &priv_subscript(const key_type& k)
1292 iterator i = lower_bound(k);
1293 // i->first is greater than or equivalent to k.
1294 if (i == end() || key_comp()(k, (*i).first)){
1295 container_detail::value_init<mapped_type> m;
1296 i = insert(i, impl_value_type(k, ::boost::move(m.m_t)));
1300 mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk)
1303 iterator i = lower_bound(k);
1304 // i->first is greater than or equivalent to k.
1305 if (i == end() || key_comp()(k, (*i).first)){
1306 container_detail::value_init<mapped_type> m;
1307 i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t)));
1311 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1314 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1316 } //namespace container {
1318 //!has_trivial_destructor_after_move<> == true_type
1319 //!specialization for optimizations
1320 template <class Key, class T, class Compare, class Allocator>
1321 struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, Allocator> >
1323 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
1324 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
1325 ::boost::has_trivial_destructor_after_move<pointer>::value &&
1326 ::boost::has_trivial_destructor_after_move<Compare>::value;
1329 namespace container {
1331 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1333 //! A flat_multimap is a kind of associative container that supports equivalent keys
1334 //! (possibly containing multiple copies of the same key value) and provides for
1335 //! fast retrieval of values of another type T based on the keys. The flat_multimap
1336 //! class supports random-access iterators.
1338 //! A flat_multimap satisfies all of the requirements of a container and of a reversible
1339 //! container and of an associative container. For a
1340 //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
1341 //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
1343 //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1345 //! Allocator is the allocator to allocate the value_types
1346 //! (e.g. <i>allocator< std::pair<Key, T> ></i>).
1348 //! flat_multimap is similar to std::multimap but it's implemented like an ordered vector.
1349 //! This means that inserting a new element into a flat_map invalidates
1350 //! previous iterators and references
1352 //! Erasing an element invalidates iterators and references
1353 //! pointing to elements that come after (their keys are bigger) the erased element.
1355 //! This container provides random-access iterators.
1357 //! \tparam Key is the key_type of the map
1358 //! \tparam Value is the <code>mapped_type</code>
1359 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1360 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
1361 //! (e.g. <i>allocator< std::pair<Key, T> > </i>).
1362 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1363 template <class Key, class T, class Compare = std::less<Key>, class Allocator = new_allocator< std::pair< Key, T> > >
1365 template <class Key, class T, class Compare, class Allocator>
1369 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1371 BOOST_COPYABLE_AND_MOVABLE(flat_multimap)
1372 typedef container_detail::flat_tree<
1374 container_detail::select1st<Key>,
1377 //This is the real tree stored here. It's based on a movable pair
1378 typedef container_detail::flat_tree<
1379 container_detail::pair<Key, T>,
1380 container_detail::select1st<Key>,
1382 typename allocator_traits<Allocator>::template portable_rebind_alloc
1383 <container_detail::pair<Key, T> >::type> impl_tree_t;
1384 impl_tree_t m_flat_tree; // flat tree representing flat_map
1386 typedef typename impl_tree_t::value_type impl_value_type;
1387 typedef typename impl_tree_t::const_iterator impl_const_iterator;
1388 typedef typename impl_tree_t::iterator impl_iterator;
1389 typedef typename impl_tree_t::allocator_type impl_allocator_type;
1390 typedef container_detail::flat_tree_value_compare
1392 , container_detail::select1st<Key>
1393 , std::pair<Key, T> > value_compare_impl;
1394 typedef typename container_detail::get_flat_tree_iterators
1395 <typename allocator_traits<Allocator>::pointer>::iterator iterator_impl;
1396 typedef typename container_detail::get_flat_tree_iterators
1397 <typename allocator_traits<Allocator>::pointer>::const_iterator const_iterator_impl;
1398 typedef typename container_detail::get_flat_tree_iterators
1399 <typename allocator_traits<Allocator>::pointer>::reverse_iterator reverse_iterator_impl;
1400 typedef typename container_detail::get_flat_tree_iterators
1401 <typename allocator_traits<Allocator>::pointer>::const_reverse_iterator const_reverse_iterator_impl;
1403 typedef typename impl_tree_t::stored_allocator_type impl_stored_allocator_type;
1406 { return m_flat_tree; }
1408 const impl_tree_t &tree() const
1409 { return m_flat_tree; }
1412 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1416 //////////////////////////////////////////////
1420 //////////////////////////////////////////////
1421 typedef Key key_type;
1422 typedef T mapped_type;
1423 typedef std::pair<Key, T> value_type;
1424 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
1425 typedef typename boost::container::allocator_traits<Allocator>::pointer pointer;
1426 typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
1427 typedef typename boost::container::allocator_traits<Allocator>::reference reference;
1428 typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
1429 typedef typename boost::container::allocator_traits<Allocator>::size_type size_type;
1430 typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type;
1431 typedef Allocator allocator_type;
1432 typedef BOOST_CONTAINER_IMPDEF(Allocator) stored_allocator_type;
1433 typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare;
1434 typedef Compare key_compare;
1435 typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
1436 typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
1437 typedef BOOST_CONTAINER_IMPDEF(reverse_iterator_impl) reverse_iterator;
1438 typedef BOOST_CONTAINER_IMPDEF(const_reverse_iterator_impl) const_reverse_iterator;
1439 typedef BOOST_CONTAINER_IMPDEF(impl_value_type) movable_value_type;
1441 //////////////////////////////////////////////
1443 // construct/copy/destroy
1445 //////////////////////////////////////////////
1447 //! <b>Effects</b>: Default constructs an empty flat_map.
1449 //! <b>Complexity</b>: Constant.
1450 flat_multimap() BOOST_NOEXCEPT_IF(container_detail::is_nothrow_default_constructible<Allocator>::value &&
1451 container_detail::is_nothrow_default_constructible<Compare>::value)
1454 //value_type must be std::pair<Key, T>
1455 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1458 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1459 //! object and allocator.
1461 //! <b>Complexity</b>: Constant.
1462 explicit flat_multimap(const Compare& comp,
1463 const allocator_type& a = allocator_type())
1464 : m_flat_tree(comp, container_detail::force<impl_allocator_type>(a))
1466 //value_type must be std::pair<Key, T>
1467 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1470 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator.
1472 //! <b>Complexity</b>: Constant.
1473 explicit flat_multimap(const allocator_type& a)
1474 : m_flat_tree(container_detail::force<impl_allocator_type>(a))
1476 //value_type must be std::pair<Key, T>
1477 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1480 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1481 //! and allocator, and inserts elements from the range [first ,last ).
1483 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1484 //! comp and otherwise N logN, where N is last - first.
1485 template <class InputIterator>
1486 flat_multimap(InputIterator first, InputIterator last,
1487 const Compare& comp = Compare(),
1488 const allocator_type& a = allocator_type())
1489 : m_flat_tree(false, first, last, comp, container_detail::force<impl_allocator_type>(a))
1491 //value_type must be std::pair<Key, T>
1492 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1495 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified
1496 //! allocator, and inserts elements from the range [first ,last ).
1498 //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1499 //! comp and otherwise N logN, where N is last - first.
1500 template <class InputIterator>
1501 flat_multimap(InputIterator first, InputIterator last, const allocator_type& a)
1502 : m_flat_tree(false, first, last, Compare(), container_detail::force<impl_allocator_type>(a))
1504 //value_type must be std::pair<Key, T>
1505 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1508 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1509 //! allocator, and inserts elements from the ordered range [first ,last). This function
1510 //! is more efficient than the normal range creation for ordered ranges.
1512 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1514 //! <b>Complexity</b>: Linear in N.
1516 //! <b>Note</b>: Non-standard extension.
1517 template <class InputIterator>
1518 flat_multimap(ordered_range_t, InputIterator first, InputIterator last,
1519 const Compare& comp = Compare(),
1520 const allocator_type& a = allocator_type())
1521 : m_flat_tree(ordered_range, first, last, comp, a)
1523 //value_type must be std::pair<Key, T>
1524 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1527 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1528 //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1529 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1531 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1532 //! comp and otherwise N logN, where N is last - first.
1533 flat_multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type())
1534 : m_flat_tree(false, il.begin(), il.end(), comp, container_detail::force<impl_allocator_type>(a))
1536 //value_type must be std::pair<Key, T>
1537 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1540 //! <b>Effects</b>: Constructs an empty flat_map using the specified
1541 //! allocator, and inserts elements from the range [il.begin(), il.end()).
1543 //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1544 //! comp and otherwise N logN, where N is last - first.
1545 flat_multimap(std::initializer_list<value_type> il, const allocator_type& a)
1546 : m_flat_tree(false, il.begin(), il.end(), Compare(), container_detail::force<impl_allocator_type>(a))
1548 //value_type must be std::pair<Key, T>
1549 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1552 //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1553 //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function
1554 //! is more efficient than the normal range creation for ordered ranges.
1556 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1558 //! <b>Complexity</b>: Linear in N.
1560 //! <b>Note</b>: Non-standard extension.
1561 flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(),
1562 const allocator_type& a = allocator_type())
1563 : m_flat_tree(ordered_range, il.begin(), il.end(), comp, a)
1565 //value_type must be std::pair<Key, T>
1566 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1570 //! <b>Effects</b>: Copy constructs a flat_multimap.
1572 //! <b>Complexity</b>: Linear in x.size().
1573 flat_multimap(const flat_multimap& x)
1574 : m_flat_tree(x.m_flat_tree)
1576 //value_type must be std::pair<Key, T>
1577 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1580 //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources.
1582 //! <b>Complexity</b>: Constant.
1584 //! <b>Postcondition</b>: x is emptied.
1585 flat_multimap(BOOST_RV_REF(flat_multimap) x)
1586 BOOST_NOEXCEPT_IF(boost::container::container_detail::is_nothrow_move_constructible<Compare>::value)
1587 : m_flat_tree(boost::move(x.m_flat_tree))
1589 //value_type must be std::pair<Key, T>
1590 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1593 //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator.
1595 //! <b>Complexity</b>: Linear in x.size().
1596 flat_multimap(const flat_multimap& x, const allocator_type &a)
1597 : m_flat_tree(x.m_flat_tree, a)
1599 //value_type must be std::pair<Key, T>
1600 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1603 //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator.
1604 //! Constructs *this using x's resources.
1606 //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
1607 flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a)
1608 : m_flat_tree(boost::move(x.m_flat_tree), a)
1610 //value_type must be std::pair<Key, T>
1611 BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<Key, T>, typename Allocator::value_type>::value));
1614 //! <b>Effects</b>: Makes *this a copy of x.
1616 //! <b>Complexity</b>: Linear in x.size().
1617 flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x)
1618 { m_flat_tree = x.m_flat_tree; return *this; }
1620 //! <b>Effects</b>: this->swap(x.get()).
1622 //! <b>Complexity</b>: Constant.
1623 flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x)
1624 BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1625 allocator_traits_type::is_always_equal::value) &&
1626 boost::container::container_detail::is_nothrow_move_assignable<Compare>::value)
1627 { m_flat_tree = boost::move(x.m_flat_tree); return *this; }
1629 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1630 //! <b>Effects</b>: Assign content of il to *this
1632 //! <b>Complexity</b>: Linear in il.size().
1633 flat_multimap& operator=(std::initializer_list<value_type> il)
1636 this->insert(il.begin(), il.end());
1641 //! <b>Effects</b>: Returns a copy of the allocator that
1642 //! was passed to the object's constructor.
1644 //! <b>Complexity</b>: Constant.
1645 allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1646 { return container_detail::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
1648 //! <b>Effects</b>: Returns a reference to the internal allocator.
1650 //! <b>Throws</b>: Nothing
1652 //! <b>Complexity</b>: Constant.
1654 //! <b>Note</b>: Non-standard extension.
1655 stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
1656 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
1658 //! <b>Effects</b>: Returns a reference to the internal allocator.
1660 //! <b>Throws</b>: Nothing
1662 //! <b>Complexity</b>: Constant.
1664 //! <b>Note</b>: Non-standard extension.
1665 const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
1666 { return container_detail::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
1668 //////////////////////////////////////////////
1672 //////////////////////////////////////////////
1674 //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
1676 //! <b>Throws</b>: Nothing.
1678 //! <b>Complexity</b>: Constant.
1679 iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
1680 { return container_detail::force_copy<iterator>(m_flat_tree.begin()); }
1682 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1684 //! <b>Throws</b>: Nothing.
1686 //! <b>Complexity</b>: Constant.
1687 const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
1688 { return container_detail::force_copy<const_iterator>(m_flat_tree.begin()); }
1690 //! <b>Effects</b>: Returns an iterator to the end of the container.
1692 //! <b>Throws</b>: Nothing.
1694 //! <b>Complexity</b>: Constant.
1695 iterator end() BOOST_NOEXCEPT_OR_NOTHROW
1696 { return container_detail::force_copy<iterator>(m_flat_tree.end()); }
1698 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1700 //! <b>Throws</b>: Nothing.
1702 //! <b>Complexity</b>: Constant.
1703 const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
1704 { return container_detail::force_copy<const_iterator>(m_flat_tree.end()); }
1706 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
1707 //! of the reversed container.
1709 //! <b>Throws</b>: Nothing.
1711 //! <b>Complexity</b>: Constant.
1712 reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
1713 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
1715 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1716 //! of the reversed container.
1718 //! <b>Throws</b>: Nothing.
1720 //! <b>Complexity</b>: Constant.
1721 const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1722 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
1724 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
1725 //! of the reversed container.
1727 //! <b>Throws</b>: Nothing.
1729 //! <b>Complexity</b>: Constant.
1730 reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
1731 { return container_detail::force_copy<reverse_iterator>(m_flat_tree.rend()); }
1733 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1734 //! of the reversed container.
1736 //! <b>Throws</b>: Nothing.
1738 //! <b>Complexity</b>: Constant.
1739 const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
1740 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
1742 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
1744 //! <b>Throws</b>: Nothing.
1746 //! <b>Complexity</b>: Constant.
1747 const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1748 { return container_detail::force_copy<const_iterator>(m_flat_tree.cbegin()); }
1750 //! <b>Effects</b>: Returns a const_iterator to the end of the container.
1752 //! <b>Throws</b>: Nothing.
1754 //! <b>Complexity</b>: Constant.
1755 const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
1756 { return container_detail::force_copy<const_iterator>(m_flat_tree.cend()); }
1758 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
1759 //! of the reversed container.
1761 //! <b>Throws</b>: Nothing.
1763 //! <b>Complexity</b>: Constant.
1764 const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
1765 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
1767 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
1768 //! of the reversed container.
1770 //! <b>Throws</b>: Nothing.
1772 //! <b>Complexity</b>: Constant.
1773 const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
1774 { return container_detail::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
1776 //////////////////////////////////////////////
1780 //////////////////////////////////////////////
1782 //! <b>Effects</b>: Returns true if the container contains no elements.
1784 //! <b>Throws</b>: Nothing.
1786 //! <b>Complexity</b>: Constant.
1787 bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
1788 { return m_flat_tree.empty(); }
1790 //! <b>Effects</b>: Returns the number of the elements contained in the container.
1792 //! <b>Throws</b>: Nothing.
1794 //! <b>Complexity</b>: Constant.
1795 size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
1796 { return m_flat_tree.size(); }
1798 //! <b>Effects</b>: Returns the largest possible size of the container.
1800 //! <b>Throws</b>: Nothing.
1802 //! <b>Complexity</b>: Constant.
1803 size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
1804 { return m_flat_tree.max_size(); }
1806 //! <b>Effects</b>: Number of elements for which memory has been allocated.
1807 //! capacity() is always greater than or equal to size().
1809 //! <b>Throws</b>: Nothing.
1811 //! <b>Complexity</b>: Constant.
1812 size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
1813 { return m_flat_tree.capacity(); }
1815 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
1816 //! effect. Otherwise, it is a request for allocation of additional memory.
1817 //! If the request is successful, then capacity() is greater than or equal to
1818 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
1820 //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
1822 //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
1823 //! to values might be invalidated.
1824 void reserve(size_type cnt)
1825 { m_flat_tree.reserve(cnt); }
1827 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1828 // with previous allocations. The size of the vector is unchanged
1830 //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
1832 //! <b>Complexity</b>: Linear to size().
1833 void shrink_to_fit()
1834 { m_flat_tree.shrink_to_fit(); }
1836 //! @copydoc ::boost::container::flat_set::nth(size_type)
1837 iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
1838 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
1840 //! @copydoc ::boost::container::flat_set::nth(size_type) const
1841 const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
1842 { return container_detail::force_copy<iterator>(m_flat_tree.nth(n)); }
1844 //! @copydoc ::boost::container::flat_set::index_of(iterator)
1845 size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
1846 { return m_flat_tree.index_of(container_detail::force_copy<impl_iterator>(p)); }
1848 //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
1849 size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
1850 { return m_flat_tree.index_of(container_detail::force_copy<impl_const_iterator>(p)); }
1852 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1854 //! <b>Effects</b>: Inserts an object of type T constructed with
1855 //! std::forward<Args>(args)... and returns the iterator pointing to the
1856 //! newly inserted element.
1858 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1859 //! to the elements with bigger keys than x.
1861 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1862 template <class... Args>
1863 iterator emplace(BOOST_FWD_REF(Args)... args)
1864 { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); }
1866 //! <b>Effects</b>: Inserts an object of type T constructed with
1867 //! std::forward<Args>(args)... in the container.
1868 //! p is a hint pointing to where the insert should start to search.
1870 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1871 //! to the key of x.
1873 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1874 //! is to be inserted before p) plus linear insertion
1875 //! to the elements with bigger keys than x.
1877 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1878 template <class... Args>
1879 iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
1881 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal
1882 (container_detail::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...));
1885 #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1887 #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \
1888 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1889 iterator emplace(BOOST_MOVE_UREF##N)\
1890 { return container_detail::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N)); }\
1892 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1893 iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1895 return container_detail::force_copy<iterator>(m_flat_tree.emplace_hint_equal\
1896 (container_detail::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1899 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)
1900 #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE
1902 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1904 //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1905 //! newly inserted element.
1907 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1908 //! to the elements with bigger keys than x.
1910 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1911 iterator insert(const value_type& x)
1913 return container_detail::force_copy<iterator>(
1914 m_flat_tree.insert_equal(container_detail::force<impl_value_type>(x)));
1917 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1918 //! the iterator pointing to the newly inserted element.
1920 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1921 //! to the elements with bigger keys than x.
1923 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1924 iterator insert(BOOST_RV_REF(value_type) x)
1925 { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
1927 //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1928 //! the iterator pointing to the newly inserted element.
1930 //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1931 //! to the elements with bigger keys than x.
1933 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1934 iterator insert(BOOST_RV_REF(impl_value_type) x)
1935 { return container_detail::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
1937 //! <b>Effects</b>: Inserts a copy of x in the container.
1938 //! p is a hint pointing to where the insert should start to search.
1940 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1941 //! to the key of x.
1943 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1944 //! is to be inserted before p) plus linear insertion
1945 //! to the elements with bigger keys than x.
1947 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1948 iterator insert(const_iterator p, const value_type& x)
1950 return container_detail::force_copy<iterator>
1951 (m_flat_tree.insert_equal( container_detail::force_copy<impl_const_iterator>(p)
1952 , container_detail::force<impl_value_type>(x)));
1955 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1956 //! p is a hint pointing to where the insert should start to search.
1958 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1959 //! to the key of x.
1961 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1962 //! is to be inserted before p) plus linear insertion
1963 //! to the elements with bigger keys than x.
1965 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1966 iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
1968 return container_detail::force_copy<iterator>
1969 (m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p)
1973 //! <b>Effects</b>: Inserts a value move constructed from x in the container.
1974 //! p is a hint pointing to where the insert should start to search.
1976 //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1977 //! to the key of x.
1979 //! <b>Complexity</b>: Logarithmic search time (constant time if the value
1980 //! is to be inserted before p) plus linear insertion
1981 //! to the elements with bigger keys than x.
1983 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1984 iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x)
1986 return container_detail::force_copy<iterator>(
1987 m_flat_tree.insert_equal(container_detail::force_copy<impl_const_iterator>(p), boost::move(x)));
1990 //! <b>Requires</b>: first, last are not iterators into *this.
1992 //! <b>Effects</b>: inserts each element from the range [first,last) .
1994 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1995 //! search time plus N*size() insertion time.
1997 //! <b>Note</b>: If an element is inserted it might invalidate elements.
1998 template <class InputIterator>
1999 void insert(InputIterator first, InputIterator last)
2000 { m_flat_tree.insert_equal(first, last); }
2002 //! <b>Requires</b>: first, last are not iterators into *this.
2004 //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
2006 //! <b>Effects</b>: inserts each element from the range [first,last) if and only
2007 //! if there is no element with key equivalent to the key of that element. This
2008 //! function is more efficient than the normal range creation for ordered ranges.
2010 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
2011 //! search time plus N*size() insertion time.
2013 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2015 //! <b>Note</b>: Non-standard extension.
2016 template <class InputIterator>
2017 void insert(ordered_range_t, InputIterator first, InputIterator last)
2018 { m_flat_tree.insert_equal(ordered_range, first, last); }
2020 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2021 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .
2023 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
2024 //! search time plus N*size() insertion time.
2026 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2027 void insert(std::initializer_list<value_type> il)
2028 { m_flat_tree.insert_equal(il.begin(), il.end()); }
2030 //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
2032 //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
2033 //! if there is no element with key equivalent to the key of that element. This
2034 //! function is more efficient than the normal range creation for ordered ranges.
2036 //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
2037 //! search time plus N*size() insertion time.
2039 //! <b>Note</b>: If an element is inserted it might invalidate elements.
2041 //! <b>Note</b>: Non-standard extension.
2042 void insert(ordered_range_t, std::initializer_list<value_type> il)
2043 { m_flat_tree.insert_equal(ordered_range, il.begin(), il.end()); }
2046 //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
2048 //! <b>Effects</b>: Extracts each element in source and insert it into a using
2049 //! the comparison object of *this.
2051 //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
2052 //! to those same elements but as members of *this. Iterators referring to the transferred
2053 //! elements will continue to refer to their elements, but they now behave as iterators into *this,
2054 //! not into source.
2056 //! <b>Throws</b>: Nothing unless the comparison object throws.
2058 //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
2060 void merge(flat_multimap<Key, T, C2, Allocator>& source)
2061 { m_flat_tree.merge_equal(source.tree()); }
2063 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&)
2065 void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, Allocator> BOOST_RV_REF_END source)
2066 { return this->merge(static_cast<flat_multimap<Key, T, C2, Allocator>&>(source)); }
2068 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&)
2070 void merge(flat_map<Key, T, C2, Allocator>& source)
2071 { m_flat_tree.merge_equal(source.tree()); }
2073 //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, Allocator>&)
2075 void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, Allocator> BOOST_RV_REF_END source)
2076 { return this->merge(static_cast<flat_map<Key, T, C2, Allocator>&>(source)); }
2078 //! <b>Effects</b>: Erases the element pointed to by p.
2080 //! <b>Returns</b>: Returns an iterator pointing to the element immediately
2081 //! following q prior to the element being erased. If no such element exists,
2084 //! <b>Complexity</b>: Linear to the elements with keys bigger than p
2086 //! <b>Note</b>: Invalidates elements with keys
2087 //! not less than the erased element.
2088 iterator erase(const_iterator p)
2090 return container_detail::force_copy<iterator>(
2091 m_flat_tree.erase(container_detail::force_copy<impl_const_iterator>(p)));
2094 //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
2096 //! <b>Returns</b>: Returns the number of erased elements.
2098 //! <b>Complexity</b>: Logarithmic search time plus erasure time
2099 //! linear to the elements with bigger keys.
2100 size_type erase(const key_type& x)
2101 { return m_flat_tree.erase(x); }
2103 //! <b>Effects</b>: Erases all the elements in the range [first, last).
2105 //! <b>Returns</b>: Returns last.
2107 //! <b>Complexity</b>: size()*N where N is the distance from first to last.
2109 //! <b>Complexity</b>: Logarithmic search time plus erasure time
2110 //! linear to the elements with bigger keys.
2111 iterator erase(const_iterator first, const_iterator last)
2113 return container_detail::force_copy<iterator>
2114 (m_flat_tree.erase( container_detail::force_copy<impl_const_iterator>(first)
2115 , container_detail::force_copy<impl_const_iterator>(last)));
2118 //! <b>Effects</b>: Swaps the contents of *this and x.
2120 //! <b>Throws</b>: Nothing.
2122 //! <b>Complexity</b>: Constant.
2123 void swap(flat_multimap& x)
2124 BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
2125 && boost::container::container_detail::is_nothrow_swappable<Compare>::value )
2126 { m_flat_tree.swap(x.m_flat_tree); }
2128 //! <b>Effects</b>: erase(a.begin(),a.end()).
2130 //! <b>Postcondition</b>: size() == 0.
2132 //! <b>Complexity</b>: linear in size().
2133 void clear() BOOST_NOEXCEPT_OR_NOTHROW
2134 { m_flat_tree.clear(); }
2136 //////////////////////////////////////////////
2140 //////////////////////////////////////////////
2142 //! <b>Effects</b>: Returns the comparison object out
2143 //! of which a was constructed.
2145 //! <b>Complexity</b>: Constant.
2146 key_compare key_comp() const
2147 { return container_detail::force_copy<key_compare>(m_flat_tree.key_comp()); }
2149 //! <b>Effects</b>: Returns an object of value_compare constructed out
2150 //! of the comparison object.
2152 //! <b>Complexity</b>: Constant.
2153 value_compare value_comp() const
2154 { return value_compare(container_detail::force_copy<key_compare>(m_flat_tree.key_comp())); }
2156 //////////////////////////////////////////////
2160 //////////////////////////////////////////////
2162 //! <b>Returns</b>: An iterator pointing to an element with the key
2163 //! equivalent to x, or end() if such an element is not found.
2165 //! <b>Complexity</b>: Logarithmic.
2166 iterator find(const key_type& x)
2167 { return container_detail::force_copy<iterator>(m_flat_tree.find(x)); }
2169 //! <b>Returns</b>: An const_iterator pointing to an element with the key
2170 //! equivalent to x, or end() if such an element is not found.
2172 //! <b>Complexity</b>: Logarithmic.
2173 const_iterator find(const key_type& x) const
2174 { return container_detail::force_copy<const_iterator>(m_flat_tree.find(x)); }
2176 //! <b>Returns</b>: The number of elements with key equivalent to x.
2178 //! <b>Complexity</b>: log(size())+count(k)
2179 size_type count(const key_type& x) const
2180 { return m_flat_tree.count(x); }
2182 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2183 //! than k, or a.end() if such an element is not found.
2185 //! <b>Complexity</b>: Logarithmic
2186 iterator lower_bound(const key_type& x)
2187 { return container_detail::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
2189 //! <b>Returns</b>: A const iterator pointing to the first element with key
2190 //! not less than k, or a.end() if such an element is not found.
2192 //! <b>Complexity</b>: Logarithmic
2193 const_iterator lower_bound(const key_type& x) const
2194 { return container_detail::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
2196 //! <b>Returns</b>: An iterator pointing to the first element with key not less
2197 //! than x, or end() if such an element is not found.
2199 //! <b>Complexity</b>: Logarithmic
2200 iterator upper_bound(const key_type& x)
2201 {return container_detail::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
2203 //! <b>Returns</b>: A const iterator pointing to the first element with key
2204 //! not less than x, or end() if such an element is not found.
2206 //! <b>Complexity</b>: Logarithmic
2207 const_iterator upper_bound(const key_type& x) const
2208 { return container_detail::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
2210 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2212 //! <b>Complexity</b>: Logarithmic
2213 std::pair<iterator,iterator> equal_range(const key_type& x)
2214 { return container_detail::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x)); }
2216 //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2218 //! <b>Complexity</b>: Logarithmic
2219 std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
2220 { return container_detail::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }
2222 //! <b>Effects</b>: Returns true if x and y are equal
2224 //! <b>Complexity</b>: Linear to the number of elements in the container.
2225 friend bool operator==(const flat_multimap& x, const flat_multimap& y)
2226 { return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin()); }
2228 //! <b>Effects</b>: Returns true if x and y are unequal
2230 //! <b>Complexity</b>: Linear to the number of elements in the container.
2231 friend bool operator!=(const flat_multimap& x, const flat_multimap& y)
2232 { return !(x == y); }
2234 //! <b>Effects</b>: Returns true if x is less than y
2236 //! <b>Complexity</b>: Linear to the number of elements in the container.
2237 friend bool operator<(const flat_multimap& x, const flat_multimap& y)
2238 { return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
2240 //! <b>Effects</b>: Returns true if x is greater than y
2242 //! <b>Complexity</b>: Linear to the number of elements in the container.
2243 friend bool operator>(const flat_multimap& x, const flat_multimap& y)
2246 //! <b>Effects</b>: Returns true if x is equal or less than y
2248 //! <b>Complexity</b>: Linear to the number of elements in the container.
2249 friend bool operator<=(const flat_multimap& x, const flat_multimap& y)
2250 { return !(y < x); }
2252 //! <b>Effects</b>: Returns true if x is equal or greater than y
2254 //! <b>Complexity</b>: Linear to the number of elements in the container.
2255 friend bool operator>=(const flat_multimap& x, const flat_multimap& y)
2256 { return !(x < y); }
2258 //! <b>Effects</b>: x.swap(y)
2260 //! <b>Complexity</b>: Constant.
2261 friend void swap(flat_multimap& x, flat_multimap& y)
2267 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2271 //!has_trivial_destructor_after_move<> == true_type
2272 //!specialization for optimizations
2273 template <class Key, class T, class Compare, class Allocator>
2274 struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, Allocator> >
2276 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
2277 static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value &&
2278 ::boost::has_trivial_destructor_after_move<pointer>::value &&
2279 ::boost::has_trivial_destructor_after_move<Compare>::value;
2282 } //namespace boost {
2284 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2286 #include <boost/container/detail/config_end.hpp>
2288 #endif // BOOST_CONTAINER_FLAT_MAP_HPP