1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_FLAT_MAP_HPP
11 #define BOOST_CONTAINER_FLAT_MAP_HPP
12 
13 #ifndef BOOST_CONFIG_HPP
14 #  include <boost/config.hpp>
15 #endif
16 
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
18 #  pragma once
19 #endif
20 
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
23 // container
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>
28 // container/detail
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()
33 #include <boost/container/detail/container_or_allocator_rebind.hpp>
34 // move
35 #include <boost/move/utility_core.hpp>
36 #include <boost/move/traits.hpp>
37 // move/detail
38 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
39 #include <boost/move/detail/fwd_macros.hpp>
40 #endif
41 #include <boost/move/detail/move_helpers.hpp>
42 // intrusive
43 #include <boost/intrusive/detail/minimal_pair_header.hpp>      //pair
44 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
45 //others
46 #include <boost/core/no_exceptions_support.hpp>
47 
48 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
49 #include <initializer_list>
50 #endif
51 
52 namespace boost {
53 namespace container {
54 
55 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
56 
57 template <class Key, class T, class Compare, class AllocatorOrContainer>
58 class flat_multimap;
59 
60 namespace dtl{
61 
62 template<class D, class S>
force(S & s)63 BOOST_CONTAINER_FORCEINLINE static D &force(S &s)
64 {  return *reinterpret_cast<D*>(&s); }
65 
66 template<class D, class S>
force_copy(const S & s)67 BOOST_CONTAINER_FORCEINLINE static D force_copy(const S &s)
68 {
69    const D *const vp = reinterpret_cast<const D *>(&s);
70    D ret_val(*vp);
71    return ret_val;
72 }
73 
74 }  //namespace dtl{
75 
76 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
77 
78 //! A flat_map is a kind of associative container that supports unique keys (contains at
79 //! most one of each key value) and provides for fast retrieval of values of another
80 //! type T based on the keys.
81 //!
82 //! A flat_map satisfies all of the requirements of a container, a reversible
83 //! container and an associative container. A flat_map also provides
84 //! most operations described for unique keys. For a
85 //! flat_map<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
86 //! (unlike std::map<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
87 //!
88 //! flat_map is similar to std::map but it's implemented by as an ordered sequence container.
89 //! The underlying sequence container is by default <i>vector</i> but it can also work
90 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
91 //!
92 //! Using vector-like sequence containers means that inserting a new element into a flat_map might invalidate
93 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
94 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
95 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
96 //!
97 //! This container provides random-access iterators.
98 //!
99 //! \tparam Key is the key_type of the map
100 //! \tparam Value is the <code>mapped_type</code>
101 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
102 //! \tparam AllocatorOrContainer is either:
103 //!   - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
104 //!     (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
105 //!   - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
106 //!     sequence container with random-access iterators..
107 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
108 template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
109 #else
110 template <class Key, class T, class Compare, class AllocatorOrContainer>
111 #endif
112 class flat_map
113 {
114    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
115    private:
116    BOOST_COPYABLE_AND_MOVABLE(flat_map)
117    //This is the tree that we should store if pair was movable
118    typedef dtl::flat_tree<
119                            std::pair<Key, T>,
120                            dtl::select1st<Key>,
121                            Compare,
122                            AllocatorOrContainer> tree_t;
123 
124    //This is the real tree stored here. It's based on a movable pair
125    typedef dtl::flat_tree<
126                            dtl::pair<Key, T>,
127                            dtl::select1st<Key>,
128                            Compare,
129                            typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
130                            > impl_tree_t;
131    impl_tree_t m_flat_tree;  // flat tree representing flat_map
132 
133    typedef typename impl_tree_t::value_type              impl_value_type;
134    typedef typename impl_tree_t::const_iterator          impl_const_iterator;
135    typedef typename impl_tree_t::iterator                impl_iterator;
136    typedef typename impl_tree_t::allocator_type          impl_allocator_type;
137    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
138    typedef std::initializer_list<impl_value_type>        impl_initializer_list;
139    #endif
140 
141    typedef dtl::flat_tree_value_compare
142       < Compare
143       , dtl::select1st<Key>
144       , std::pair<Key, T> >                              value_compare_t;
145    typedef typename tree_t::iterator                     iterator_t;
146    typedef typename tree_t::const_iterator               const_iterator_t;
147    typedef typename tree_t::reverse_iterator             reverse_iterator_t;
148    typedef typename tree_t::const_reverse_iterator       const_reverse_iterator_t;
149 
150    public:
151    typedef typename impl_tree_t::stored_allocator_type   impl_stored_allocator_type;
152    typedef typename impl_tree_t::sequence_type           impl_sequence_type;
153 
tree()154    BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
155    {  return m_flat_tree;  }
156 
tree() const157    BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
158    {  return m_flat_tree;  }
159 
160    private:
161    typedef typename tree_t::get_stored_allocator_const_return_t         get_stored_allocator_const_return_t;
162    typedef typename tree_t::get_stored_allocator_noconst_return_t       get_stored_allocator_noconst_return_t;
163    typedef typename impl_tree_t::get_stored_allocator_const_return_t    impl_get_stored_allocator_const_return_t;
164    typedef typename impl_tree_t::get_stored_allocator_noconst_return_t  impl_get_stored_allocator_noconst_return_t;
165 
166    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
167 
168    public:
169 
170    //////////////////////////////////////////////
171    //
172    //                    types
173    //
174    //////////////////////////////////////////////
175    typedef Key                                                                      key_type;
176    typedef T                                                                        mapped_type;
177    typedef Compare                                                                  key_compare;
178    typedef std::pair<Key, T>                                                        value_type;
179    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type)                   sequence_type;
180    typedef typename sequence_type::allocator_type                                   allocator_type;
181    typedef ::boost::container::allocator_traits<allocator_type>                     allocator_traits_type;
182    typedef typename sequence_type::pointer                                          pointer;
183    typedef typename sequence_type::const_pointer                                    const_pointer;
184    typedef typename sequence_type::reference                                        reference;
185    typedef typename sequence_type::const_reference                                  const_reference;
186    typedef typename sequence_type::size_type                                        size_type;
187    typedef typename sequence_type::difference_type                                  difference_type;
188    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
189    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare)                   value_compare;
190 
191    typedef typename sequence_type::iterator                                         iterator;
192    typedef typename sequence_type::const_iterator                                   const_iterator;
193    typedef typename sequence_type::reverse_iterator                                 reverse_iterator;
194    typedef typename sequence_type::const_reverse_iterator                           const_reverse_iterator;
195    typedef BOOST_CONTAINER_IMPDEF(impl_value_type)                                  movable_value_type;
196 
197    //AllocatorOrContainer::value_type must be std::pair<Key, T>
198    BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value));
199 
200    //////////////////////////////////////////////
201    //
202    //          construct/copy/destroy
203    //
204    //////////////////////////////////////////////
205 
206    //! <b>Effects</b>: Default constructs an empty flat_map.
207    //!
208    //! <b>Complexity</b>: Constant.
flat_map()209    BOOST_CONTAINER_FORCEINLINE flat_map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
210                                                             dtl::is_nothrow_default_constructible<Compare>::value)
211       : m_flat_tree()
212    {}
213 
214    //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator.
215    //!
216    //! <b>Complexity</b>: Constant.
flat_map(const allocator_type & a)217    BOOST_CONTAINER_FORCEINLINE explicit flat_map(const allocator_type& a)
218       : m_flat_tree(dtl::force<const impl_allocator_type>(a))
219    {}
220 
221    //! <b>Effects</b>: Constructs an empty flat_map using the specified
222    //! comparison object.
223    //!
224    //! <b>Complexity</b>: Constant.
flat_map(const Compare & comp)225    BOOST_CONTAINER_FORCEINLINE explicit flat_map(const Compare& comp)
226       : m_flat_tree(comp)
227    {}
228 
229    //! <b>Effects</b>: Constructs an empty flat_map using the specified
230    //! comparison object and allocator.
231    //!
232    //! <b>Complexity</b>: Constant.
flat_map(const Compare & comp,const allocator_type & a)233    BOOST_CONTAINER_FORCEINLINE flat_map(const Compare& comp, const allocator_type& a)
234       : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a))
235    {}
236 
237    //! <b>Effects</b>: Constructs an empty flat_map and
238    //! and inserts elements from the range [first ,last ).
239    //!
240    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
241    //! the predicate and otherwise N logN, where N is last - first.
242    template <class InputIterator>
flat_map(InputIterator first,InputIterator last)243    BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last)
244       : m_flat_tree(true, first, last)
245    {}
246 
247    //! <b>Effects</b>: Constructs an empty flat_map using the specified
248    //! allocator, and inserts elements from the range [first ,last ).
249    //!
250    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
251    //! the predicate and otherwise N logN, where N is last - first.
252    template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const allocator_type & a)253    BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const allocator_type& a)
254       : m_flat_tree(true, first, last, dtl::force<const impl_allocator_type>(a))
255    {}
256 
257    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
258    //! and inserts elements from the range [first ,last ).
259    //!
260    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
261    //! the predicate and otherwise N logN, where N is last - first.
262    template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const Compare & comp)263    BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp)
264       : m_flat_tree(true, first, last, comp)
265    {}
266 
267    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
268    //! allocator, and inserts elements from the range [first ,last ).
269    //!
270    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
271    //! the predicate and otherwise N logN, where N is last - first.
272    template <class InputIterator>
flat_map(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)273    BOOST_CONTAINER_FORCEINLINE flat_map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
274       : m_flat_tree(true, first, last, comp, dtl::force<const impl_allocator_type>(a))
275    {}
276 
277    //! <b>Effects</b>: Constructs an empty flat_map
278    //! and inserts elements from the ordered range [first ,last). This function
279    //! is more efficient than the normal range creation for ordered ranges.
280    //!
281    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
282    //!
283    //! <b>Complexity</b>: Linear in N.
284    //!
285    //! <b>Note</b>: Non-standard extension.
286    template <class InputIterator>
287    BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last)288    flat_map(ordered_unique_range_t, InputIterator first, InputIterator last)
289       : m_flat_tree(ordered_range, first, last)
290    {}
291 
292    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
293    //! inserts elements from the ordered range [first ,last). This function
294    //! is more efficient than the normal range creation for ordered ranges.
295    //!
296    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
297    //!
298    //! <b>Complexity</b>: Linear in N.
299    //!
300    //! <b>Note</b>: Non-standard extension.
301    template <class InputIterator>
302    BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp)303    flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
304       : m_flat_tree(ordered_range, first, last, comp)
305    {}
306 
307    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
308    //! allocator, and inserts elements from the ordered range [first ,last). This function
309    //! is more efficient than the normal range creation for ordered ranges.
310    //!
311    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
312    //!
313    //! <b>Complexity</b>: Linear in N.
314    //!
315    //! <b>Note</b>: Non-standard extension.
316    template <class InputIterator>
317    BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)318    flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
319       : m_flat_tree(ordered_range, first, last, comp, dtl::force<const impl_allocator_type>(a))
320    {}
321 
322    //! <b>Effects</b>: Constructs an empty flat_map using the specified allocator and
323    //! inserts elements from the ordered range [first ,last). This function
324    //! is more efficient than the normal range creation for ordered ranges.
325    //!
326    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
327    //!
328    //! <b>Complexity</b>: Linear in N.
329    //!
330    //! <b>Note</b>: Non-standard extension.
331    template <class InputIterator>
332    BOOST_CONTAINER_FORCEINLINE
flat_map(ordered_unique_range_t,InputIterator first,InputIterator last,const allocator_type & a)333       flat_map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
334       : m_flat_tree(ordered_range, first, last, Compare(), a)
335    {}
336 
337 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
338    //! <b>Effects</b>: Constructs an empty flat_map and
339    //! inserts elements from the range [il.begin() ,il.end()).
340    //!
341    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
342    //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il)343    BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il)
344      : m_flat_tree( true
345                   , dtl::force<impl_initializer_list>(il).begin()
346                   , dtl::force<impl_initializer_list>(il).end())
347    {}
348 
349    //! <b>Effects</b>: Constructs an empty flat_map using the specified
350    //! allocator, and inserts elements from the range [il.begin() ,il.end()).
351    //!
352    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
353    //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const allocator_type & a)354    BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const allocator_type& a)
355      : m_flat_tree( true
356                   , dtl::force<impl_initializer_list>(il).begin()
357                   , dtl::force<impl_initializer_list>(il).end()
358                   , dtl::force<const impl_allocator_type>(a))
359    {}
360 
361    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
362    //! inserts elements from the range [il.begin() ,il.end()).
363    //!
364    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
365    //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const Compare & comp)366    BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp)
367      : m_flat_tree(true
368                   , dtl::force<impl_initializer_list>(il).begin()
369                   , dtl::force<impl_initializer_list>(il).end()
370                   , comp)
371    {}
372 
373    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
374    //! allocator, and inserts elements from the range [il.begin() ,il.end()).
375    //!
376    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
377    //! the predicate and otherwise N logN, where N is last - first.
flat_map(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)378    BOOST_CONTAINER_FORCEINLINE flat_map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
379      : m_flat_tree(true
380                   , dtl::force<impl_initializer_list>(il).begin()
381                   , dtl::force<impl_initializer_list>(il).end()
382                   , comp
383                   , dtl::force<const impl_allocator_type>(a))
384    {}
385 
386    //! <b>Effects</b>: Constructs an empty flat_map using and
387    //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
388    //! is more efficient than the normal range creation for ordered ranges.
389    //!
390    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
391    //! unique values.
392    //!
393    //! <b>Complexity</b>: Linear in N.
394    //!
395    //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il)396    BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il)
397      : m_flat_tree(ordered_unique_range
398                   , dtl::force<impl_initializer_list>(il).begin()
399                   , dtl::force<impl_initializer_list>(il).end())
400    {}
401 
402    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
403    //! inserts elements from the ordered unique range [il.begin(), il.end()). This function
404    //! is more efficient than the normal range creation for ordered ranges.
405    //!
406    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
407    //! unique values.
408    //!
409    //! <b>Complexity</b>: Linear in N.
410    //!
411    //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp)412    BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
413      : m_flat_tree(ordered_unique_range
414                   , dtl::force<impl_initializer_list>(il).begin()
415                   , dtl::force<impl_initializer_list>(il).end()
416                   , comp)
417    {}
418 
419    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
420    //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
421    //! is more efficient than the normal range creation for ordered ranges.
422    //!
423    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
424    //! unique values.
425    //!
426    //! <b>Complexity</b>: Linear in N.
427    //!
428    //! <b>Note</b>: Non-standard extension.
flat_map(ordered_unique_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)429    BOOST_CONTAINER_FORCEINLINE flat_map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
430      : m_flat_tree( ordered_unique_range
431                   , dtl::force<impl_initializer_list>(il).begin()
432                   , dtl::force<impl_initializer_list>(il).end()
433                   , comp
434                   , dtl::force<const impl_allocator_type>(a))
435    {}
436 #endif
437 
438    //! <b>Effects</b>: Copy constructs a flat_map.
439    //!
440    //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x)441    BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x)
442       : m_flat_tree(x.m_flat_tree)
443    {}
444 
445    //! <b>Effects</b>: Move constructs a flat_map.
446    //!   Constructs *this using x's resources.
447    //!
448    //! <b>Complexity</b>: Constant.
449    //!
450    //! <b>Postcondition</b>: x is emptied.
flat_map(BOOST_RV_REF (flat_map)x)451    BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x)
452       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
453       : m_flat_tree(boost::move(x.m_flat_tree))
454    {}
455 
456    //! <b>Effects</b>: Copy constructs a flat_map using the specified allocator.
457    //!
458    //! <b>Complexity</b>: Linear in x.size().
flat_map(const flat_map & x,const allocator_type & a)459    BOOST_CONTAINER_FORCEINLINE flat_map(const flat_map& x, const allocator_type &a)
460       : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a))
461    {}
462 
463    //! <b>Effects</b>: Move constructs a flat_map using the specified allocator.
464    //!   Constructs *this using x's resources.
465    //!
466    //! <b>Complexity</b>: Constant if x.get_allocator() == a, linear otherwise.
flat_map(BOOST_RV_REF (flat_map)x,const allocator_type & a)467    BOOST_CONTAINER_FORCEINLINE flat_map(BOOST_RV_REF(flat_map) x, const allocator_type &a)
468       : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a))
469    {}
470 
471    //! <b>Effects</b>: Makes *this a copy of x.
472    //!
473    //! <b>Complexity</b>: Linear in x.size().
operator =(BOOST_COPY_ASSIGN_REF (flat_map)x)474    BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_COPY_ASSIGN_REF(flat_map) x)
475    {  m_flat_tree = x.m_flat_tree;   return *this;  }
476 
477    //! <b>Effects</b>: Move constructs a flat_map.
478    //!   Constructs *this using x's resources.
479    //!
480    //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
481    //!   is false and (allocation throws or value_type's move constructor throws)
482    //!
483    //! <b>Complexity</b>: Constant if allocator_traits_type::
484    //!   propagate_on_container_move_assignment is true or
485    //!   this->get>allocator() == x.get_allocator(). Linear otherwise.
operator =(BOOST_RV_REF (flat_map)x)486    BOOST_CONTAINER_FORCEINLINE flat_map& operator=(BOOST_RV_REF(flat_map) x)
487       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
488                           allocator_traits_type::is_always_equal::value) &&
489                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
490    {  m_flat_tree = boost::move(x.m_flat_tree);   return *this;  }
491 
492 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
493    //! <b>Effects</b>: Assign elements from il to *this
operator =(std::initializer_list<value_type> il)494    flat_map& operator=(std::initializer_list<value_type> il)
495    {
496       this->clear();
497       this->insert(il.begin(), il.end());
498       return *this;
499    }
500 #endif
501 
502    //! <b>Effects</b>: Returns a copy of the allocator that
503    //!   was passed to the object's constructor.
504    //!
505    //! <b>Complexity</b>: Constant.
get_allocator() const506    BOOST_CONTAINER_FORCEINLINE allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
507       { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
508 
509    //! <b>Effects</b>: Returns a reference to the internal allocator.
510    //!
511    //! <b>Throws</b>: Nothing
512    //!
513    //! <b>Complexity</b>: Constant.
514    //!
515    //! <b>Note</b>: Non-standard extension.
get_stored_allocator()516    BOOST_CONTAINER_FORCEINLINE get_stored_allocator_noconst_return_t get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
517    {
518       impl_get_stored_allocator_noconst_return_t r = m_flat_tree.get_stored_allocator();
519       return dtl::force<stored_allocator_type>(r);
520    }
521 
522    //! <b>Effects</b>: Returns a reference to the internal allocator.
523    //!
524    //! <b>Throws</b>: Nothing
525    //!
526    //! <b>Complexity</b>: Constant.
527    //!
528    //! <b>Note</b>: Non-standard extension.
get_stored_allocator() const529    BOOST_CONTAINER_FORCEINLINE get_stored_allocator_const_return_t get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
530    {
531       impl_get_stored_allocator_const_return_t r = m_flat_tree.get_stored_allocator();
532       return dtl::force<const stored_allocator_type>(r);
533    }
534 
535    //////////////////////////////////////////////
536    //
537    //                iterators
538    //
539    //////////////////////////////////////////////
540 
541    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
542    //!
543    //! <b>Throws</b>: Nothing.
544    //!
545    //! <b>Complexity</b>: Constant.
begin()546    BOOST_CONTAINER_FORCEINLINE iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
547       { return dtl::force_copy<iterator>(m_flat_tree.begin()); }
548 
549    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
550    //!
551    //! <b>Throws</b>: Nothing.
552    //!
553    //! <b>Complexity</b>: Constant.
begin() const554    BOOST_CONTAINER_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
555       { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); }
556 
557    //! <b>Effects</b>: Returns an iterator to the end of the container.
558    //!
559    //! <b>Throws</b>: Nothing.
560    //!
561    //! <b>Complexity</b>: Constant.
end()562    BOOST_CONTAINER_FORCEINLINE iterator end() BOOST_NOEXCEPT_OR_NOTHROW
563       { return dtl::force_copy<iterator>(m_flat_tree.end()); }
564 
565    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
566    //!
567    //! <b>Throws</b>: Nothing.
568    //!
569    //! <b>Complexity</b>: Constant.
end() const570    BOOST_CONTAINER_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
571       { return dtl::force_copy<const_iterator>(m_flat_tree.end()); }
572 
573    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
574    //! of the reversed container.
575    //!
576    //! <b>Throws</b>: Nothing.
577    //!
578    //! <b>Complexity</b>: Constant.
rbegin()579    BOOST_CONTAINER_FORCEINLINE reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
580       { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
581 
582    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
583    //! of the reversed container.
584    //!
585    //! <b>Throws</b>: Nothing.
586    //!
587    //! <b>Complexity</b>: Constant.
rbegin() const588    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
589       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
590 
591    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
592    //! of the reversed container.
593    //!
594    //! <b>Throws</b>: Nothing.
595    //!
596    //! <b>Complexity</b>: Constant.
rend()597    BOOST_CONTAINER_FORCEINLINE reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
598       { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); }
599 
600    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
601    //! of the reversed container.
602    //!
603    //! <b>Throws</b>: Nothing.
604    //!
605    //! <b>Complexity</b>: Constant.
rend() const606    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
607       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
608 
609    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
610    //!
611    //! <b>Throws</b>: Nothing.
612    //!
613    //! <b>Complexity</b>: Constant.
cbegin() const614    BOOST_CONTAINER_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
615       { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); }
616 
617    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
618    //!
619    //! <b>Throws</b>: Nothing.
620    //!
621    //! <b>Complexity</b>: Constant.
cend() const622    BOOST_CONTAINER_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
623       { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); }
624 
625    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
626    //! of the reversed container.
627    //!
628    //! <b>Throws</b>: Nothing.
629    //!
630    //! <b>Complexity</b>: Constant.
crbegin() const631    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
632       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
633 
634    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
635    //! of the reversed container.
636    //!
637    //! <b>Throws</b>: Nothing.
638    //!
639    //! <b>Complexity</b>: Constant.
crend() const640    BOOST_CONTAINER_FORCEINLINE const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
641       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
642 
643    //////////////////////////////////////////////
644    //
645    //                capacity
646    //
647    //////////////////////////////////////////////
648 
649    //! <b>Effects</b>: Returns true if the container contains no elements.
650    //!
651    //! <b>Throws</b>: Nothing.
652    //!
653    //! <b>Complexity</b>: Constant.
empty() const654    BOOST_CONTAINER_FORCEINLINE bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
655       { return m_flat_tree.empty(); }
656 
657    //! <b>Effects</b>: Returns the number of the elements contained in the container.
658    //!
659    //! <b>Throws</b>: Nothing.
660    //!
661    //! <b>Complexity</b>: Constant.
size() const662    BOOST_CONTAINER_FORCEINLINE size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
663       { return m_flat_tree.size(); }
664 
665    //! <b>Effects</b>: Returns the largest possible size of the container.
666    //!
667    //! <b>Throws</b>: Nothing.
668    //!
669    //! <b>Complexity</b>: Constant.
max_size() const670    BOOST_CONTAINER_FORCEINLINE size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
671       { return m_flat_tree.max_size(); }
672 
673    //! <b>Effects</b>: Number of elements for which memory has been allocated.
674    //!   capacity() is always greater than or equal to size().
675    //!
676    //! <b>Throws</b>: Nothing.
677    //!
678    //! <b>Complexity</b>: Constant.
capacity() const679    BOOST_CONTAINER_FORCEINLINE size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
680       { return m_flat_tree.capacity(); }
681 
682    //! <b>Effects</b>: If n is less than or equal to capacity(), or the
683    //!   underlying container has no `reserve` member, this call has no
684    //!   effect. Otherwise, it is a request for allocation of additional memory.
685    //!   If the request is successful, then capacity() is greater than or equal to
686    //!   n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
687    //!
688    //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
689    //!
690    //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
691    //!   to values might be invalidated.
reserve(size_type cnt)692    BOOST_CONTAINER_FORCEINLINE void reserve(size_type cnt)
693       { m_flat_tree.reserve(cnt);   }
694 
695    //! <b>Effects</b>: Tries to deallocate the excess of memory created
696    //    with previous allocations. The size of the vector is unchanged
697    //!
698    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
699    //!
700    //! <b>Complexity</b>: Linear to size().
shrink_to_fit()701    BOOST_CONTAINER_FORCEINLINE void shrink_to_fit()
702       { m_flat_tree.shrink_to_fit(); }
703 
704    //////////////////////////////////////////////
705    //
706    //               element access
707    //
708    //////////////////////////////////////////////
709 
710    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
711    //! Effects: If there is no key equivalent to x in the flat_map, inserts
712    //!   value_type(x, T()) into the flat_map.
713    //!
714    //! Returns: A reference to the mapped_type corresponding to x in *this.
715    //!
716    //! Complexity: Logarithmic.
717    mapped_type &operator[](const key_type& k);
718 
719    //! Effects: If there is no key equivalent to x in the flat_map, inserts
720    //! value_type(move(x), T()) into the flat_map (the key is move-constructed)
721    //!
722    //! Returns: A reference to the mapped_type corresponding to x in *this.
723    //!
724    //! Complexity: Logarithmic.
725    mapped_type &operator[](key_type &&k) ;
726    #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
727       //in compilers like GCC 3.4, we can't catch temporaries
operator [](const key_type & k)728       BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k)         {  return this->priv_subscript(k);  }
operator [](BOOST_RV_REF (key_type)k)729       BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k)  {  return this->priv_subscript(::boost::move(k));  }
730    #else
731       BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
732    #endif
733 
734    //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
735    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
736    //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
737    //!
738    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
739    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
740    //! references obtained to that element before it was extracted become valid.
741    //!
742    //! Returns: The bool component is true if the insertion took place and false if the assignment
743    //!   took place. The iterator component is pointing at the element that was inserted or updated.
744    //!
745    //! Complexity: Logarithmic in the size of the container.
746    template <class M>
insert_or_assign(const key_type & k,BOOST_FWD_REF (M)obj)747    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
748    {
749       return dtl::force_copy< std::pair<iterator, bool> >
750          (this->m_flat_tree.insert_or_assign
751             ( impl_const_iterator(), k, ::boost::forward<M>(obj))
752          );
753    }
754 
755    //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
756    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
757    //! as if by insert, constructing it from value_type(k, move(obj)).
758    //!
759    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
760    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
761    //! references obtained to that element before it was extracted become valid.
762    //!
763    //! Returns: The bool component is true if the insertion took place and false if the assignment
764    //!   took place. The iterator component is pointing at the element that was inserted or updated.
765    //!
766    //! Complexity: Logarithmic in the size of the container.
767    template <class M>
insert_or_assign(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)768    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
769    {
770       return dtl::force_copy< std::pair<iterator, bool> >
771          (this->m_flat_tree.insert_or_assign
772             ( impl_const_iterator(), ::boost::move(k), ::boost::forward<M>(obj))
773          );
774    }
775 
776    //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
777    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
778    //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
779    //! to the container as close as possible to the position just before hint.
780    //!
781    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
782    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
783    //! references obtained to that element before it was extracted become valid.
784    //!
785    //! Returns: The bool component is true if the insertion took place and false if the assignment
786    //!   took place. The iterator component is pointing at the element that was inserted or updated.
787    //!
788    //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
789    //! the new element is inserted just before hint.
790    template <class M>
insert_or_assign(const_iterator hint,const key_type & k,BOOST_FWD_REF (M)obj)791    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
792    {
793       return dtl::force_copy< std::pair<iterator, bool> >
794          (this->m_flat_tree.insert_or_assign
795             ( dtl::force_copy<impl_const_iterator>(hint)
796             , k, ::boost::forward<M>(obj))
797          );
798    }
799 
800    //! Effects: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
801    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
802    //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
803    //! to the container as close as possible to the position just before hint.
804    //!
805    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
806    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
807    //! references obtained to that element before it was extracted become valid.
808    //!
809    //! Returns: The bool component is true if the insertion took place and false if the assignment
810    //!   took place. The iterator component is pointing at the element that was inserted or updated.
811    //!
812    //! Complexity: Logarithmic in the size of the container in general, but amortized constant if
813    //! the new element is inserted just before hint.
814    template <class M>
insert_or_assign(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (M)obj)815    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
816    {
817       return dtl::force_copy< std::pair<iterator, bool> >
818          (this->m_flat_tree.insert_or_assign
819             ( dtl::force_copy<impl_const_iterator>(hint)
820             , ::boost::move(k), ::boost::forward<M>(obj))
821          );
822    }
823 
824    //! @copydoc ::boost::container::flat_set::nth(size_type)
nth(size_type n)825    BOOST_CONTAINER_FORCEINLINE iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
826    {  return dtl::force_copy<iterator>(m_flat_tree.nth(n));  }
827 
828    //! @copydoc ::boost::container::flat_set::nth(size_type) const
nth(size_type n) const829    BOOST_CONTAINER_FORCEINLINE const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
830    {  return dtl::force_copy<iterator>(m_flat_tree.nth(n));  }
831 
832    //! @copydoc ::boost::container::flat_set::index_of(iterator)
index_of(iterator p)833    BOOST_CONTAINER_FORCEINLINE size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
834    {  return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p));  }
835 
836    //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
index_of(const_iterator p) const837    BOOST_CONTAINER_FORCEINLINE size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
838    {  return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p));  }
839 
840    //! Returns: A reference to the element whose key is equivalent to x.
841    //!
842    //! Throws: An exception object of type out_of_range if no such element is present.
843    //!
844    //! Complexity: logarithmic.
at(const key_type & k)845    T& at(const key_type& k)
846    {
847       iterator i = this->find(k);
848       if(i == this->end()){
849          throw_out_of_range("flat_map::at key not found");
850       }
851       return i->second;
852    }
853 
854    //! Returns: A reference to the element whose key is equivalent to x.
855    //!
856    //! Throws: An exception object of type out_of_range if no such element is present.
857    //!
858    //! Complexity: logarithmic.
at(const key_type & k) const859    const T& at(const key_type& k) const
860    {
861       const_iterator i = this->find(k);
862       if(i == this->end()){
863          throw_out_of_range("flat_map::at key not found");
864       }
865       return i->second;
866    }
867 
868    //////////////////////////////////////////////
869    //
870    //                modifiers
871    //
872    //////////////////////////////////////////////
873 
874    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
875 
876    //! <b>Effects</b>: Inserts an object x of type T constructed with
877    //!   std::forward<Args>(args)... if and only if there is no element in the container
878    //!   with key equivalent to the key of x.
879    //!
880    //! <b>Returns</b>: The bool component of the returned pair is true if and only
881    //!   if the insertion takes place, and the iterator component of the pair
882    //!   points to the element with key equivalent to the key of x.
883    //!
884    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
885    //!   to the elements with bigger keys than x.
886    //!
887    //! <b>Note</b>: If an element is inserted it might invalidate elements.
888    template <class... Args>
emplace(BOOST_FWD_REF (Args)...args)889    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
890    {  return dtl::force_copy< std::pair<iterator, bool> >(m_flat_tree.emplace_unique(boost::forward<Args>(args)...)); }
891 
892    //! <b>Effects</b>: Inserts an object of type T constructed with
893    //!   std::forward<Args>(args)... in the container if and only if there is
894    //!   no element in the container with key equivalent to the key of x.
895    //!   p is a hint pointing to where the insert should start to search.
896    //!
897    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
898    //!   to the key of x.
899    //!
900    //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
901    //!   right before p) plus insertion linear to the elements with bigger keys than x.
902    //!
903    //! <b>Note</b>: If an element is inserted it might invalidate elements.
904    template <class... Args>
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)905    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
906    {
907       return dtl::force_copy<iterator>
908          (m_flat_tree.emplace_hint_unique( dtl::force_copy<impl_const_iterator>(hint)
909                                          , boost::forward<Args>(args)...));
910    }
911 
912    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
913    //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
914    //!
915    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
916    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
917    //! forward_as_tuple(forward<Args>(args)...).
918    //!
919    //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
920    //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
921    //!
922    //! <b>Complexity</b>: Logarithmic.
923    template <class... Args>
try_emplace(const key_type & k,BOOST_FWD_REF (Args)...args)924    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
925    {
926       return dtl::force_copy< std::pair<iterator, bool> >(
927          m_flat_tree.try_emplace(impl_const_iterator(), k, boost::forward<Args>(args)...));
928    }
929 
930    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
931    //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
932    //!
933    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
934    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
935    //! forward_as_tuple(forward<Args>(args)...).
936    //!
937    //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
938    //!
939    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
940    //!   is inserted right before p.
941    template <class... Args>
try_emplace(const_iterator hint,const key_type & k,BOOST_FWD_REF (Args)...args)942    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
943    {
944       return dtl::force_copy<iterator>(m_flat_tree.try_emplace
945          (dtl::force_copy<impl_const_iterator>(hint), k, boost::forward<Args>(args)...).first);
946    }
947 
948    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
949    //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
950    //!
951    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
952    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
953    //! forward_as_tuple(forward<Args>(args)...).
954    //!
955    //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
956    //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
957    //!
958    //! <b>Complexity</b>: Logarithmic.
959    template <class... Args>
try_emplace(BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)960    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
961    {
962       return dtl::force_copy< std::pair<iterator, bool> >
963          (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k), boost::forward<Args>(args)...));
964    }
965 
966    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct,
967    //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
968    //!
969    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
970    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
971    //! forward_as_tuple(forward<Args>(args)...).
972    //!
973    //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
974    //!
975    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
976    //!   is inserted right before p.
977    template <class... Args>
try_emplace(const_iterator hint,BOOST_RV_REF (key_type)k,BOOST_FWD_REF (Args)...args)978    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
979    {
980       return dtl::force_copy<iterator>
981          (m_flat_tree.try_emplace(dtl::force_copy
982             <impl_const_iterator>(hint), boost::move(k), boost::forward<Args>(args)...).first);
983    }
984 
985    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
986 
987    #define BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE(N) \
988    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
989    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
990    {\
991       return dtl::force_copy< std::pair<iterator, bool> >\
992          (m_flat_tree.emplace_unique(BOOST_MOVE_FWD##N));\
993    }\
994    \
995    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
996    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
997    {\
998       return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_unique\
999          (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1000    }\
1001    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1002    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1003    {\
1004       return dtl::force_copy< std::pair<iterator, bool> >\
1005          (m_flat_tree.try_emplace(impl_const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1006    }\
1007    \
1008    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1009    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1010    {  return dtl::force_copy<iterator>(m_flat_tree.try_emplace\
1011          (dtl::force_copy<impl_const_iterator>(hint), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
1012    \
1013    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1014    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1015    {\
1016       return dtl::force_copy< std::pair<iterator, bool> >\
1017          (m_flat_tree.try_emplace(impl_const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
1018    }\
1019    \
1020    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1021    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1022    {  return dtl::force_copy<iterator>(m_flat_tree.try_emplace\
1023       (dtl::force_copy<impl_const_iterator>(hint), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first); }\
1024    //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)1025    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE)
1026    #undef BOOST_CONTAINER_FLAT_MAP_EMPLACE_CODE
1027 
1028    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1029 
1030    //! <b>Effects</b>: Inserts x if and only if there is no element in the container
1031    //!   with key equivalent to the key of x.
1032    //!
1033    //! <b>Returns</b>: The bool component of the returned pair is true if and only
1034    //!   if the insertion takes place, and the iterator component of the pair
1035    //!   points to the element with key equivalent to the key of x.
1036    //!
1037    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1038    //!   to the elements with bigger keys than x.
1039    //!
1040    //! <b>Note</b>: If an element is inserted it might invalidate elements.
1041    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x)
1042    {  return dtl::force_copy<std::pair<iterator,bool> >(
1043          m_flat_tree.insert_unique(dtl::force<const impl_value_type>(x))); }
1044 
1045    //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
1046    //! only if there is no element in the container with key equivalent to the key of x.
1047    //!
1048    //! <b>Returns</b>: The bool component of the returned pair is true if and only
1049    //!   if the insertion takes place, and the iterator component of the pair
1050    //!   points to the element with key equivalent to the key of x.
1051    //!
1052    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1053    //!   to the elements with bigger keys than x.
1054    //!
1055    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)1056    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
1057    {  return dtl::force_copy<std::pair<iterator,bool> >(
1058       m_flat_tree.insert_unique(boost::move(dtl::force<impl_value_type>(x)))); }
1059 
1060    //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
1061    //! only if there is no element in the container with key equivalent to the key of x.
1062    //!
1063    //! <b>Returns</b>: The bool component of the returned pair is true if and only
1064    //!   if the insertion takes place, and the iterator component of the pair
1065    //!   points to the element with key equivalent to the key of x.
1066    //!
1067    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
1068    //!   to the elements with bigger keys than x.
1069    //!
1070    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (movable_value_type)x)1071    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
1072    {
1073       return dtl::force_copy<std::pair<iterator,bool> >
1074       (m_flat_tree.insert_unique(boost::move(x)));
1075    }
1076 
1077    //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
1078    //!   no element in the container with key equivalent to the key of x.
1079    //!   p is a hint pointing to where the insert should start to search.
1080    //!
1081    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1082    //!   to the key of x.
1083    //!
1084    //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1085    //!   right before p) plus insertion linear to the elements with bigger keys than x.
1086    //!
1087    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)1088    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
1089    {
1090       return dtl::force_copy<iterator>(
1091          m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p)
1092                                   , dtl::force<const impl_value_type>(x)));
1093    }
1094 
1095    //! <b>Effects</b>: Inserts an element move constructed from x in the container.
1096    //!   p is a hint pointing to where the insert should start to search.
1097    //!
1098    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
1099    //!
1100    //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1101    //!   right before p) plus insertion linear to the elements with bigger keys than x.
1102    //!
1103    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)1104    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
1105    {
1106       return dtl::force_copy<iterator>
1107          (m_flat_tree.insert_unique( dtl::force_copy<impl_const_iterator>(p)
1108                                    , boost::move(dtl::force<impl_value_type>(x))));
1109    }
1110 
1111    //! <b>Effects</b>: Inserts an element move constructed from x in the container.
1112    //!   p is a hint pointing to where the insert should start to search.
1113    //!
1114    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
1115    //!
1116    //! <b>Complexity</b>: Logarithmic search time (constant if x is inserted
1117    //!   right before p) plus insertion linear to the elements with bigger keys than x.
1118    //!
1119    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (movable_value_type)x)1120    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1121    {
1122       return dtl::force_copy<iterator>(
1123          m_flat_tree.insert_unique(dtl::force_copy<impl_const_iterator>(p), boost::move(x)));
1124    }
1125 
1126    //! <b>Requires</b>: first, last are not iterators into *this.
1127    //!
1128    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1129    //!   if there is no element with key equivalent to the key of that element.
1130    //!
1131    //! <b>Complexity</b>: N log(size()+N).
1132    //!
1133    //! <b>Note</b>: If an element is inserted it might invalidate elements.
1134    template <class InputIterator>
insert(InputIterator first,InputIterator last)1135    BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1136    {  m_flat_tree.insert_unique(first, last);  }
1137 
1138    //! <b>Requires</b>: first, last are not iterators into *this.
1139    //!
1140    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
1141    //! unique values.
1142    //!
1143    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
1144    //!   if there is no element with key equivalent to the key of that element. This
1145    //!   function is more efficient than the normal range creation for ordered ranges.
1146    //!
1147    //! <b>Complexity</b>: Linear.
1148    //!
1149    //! <b>Note</b>: If an element is inserted it might invalidate elements.
1150    //!
1151    //! <b>Note</b>: Non-standard extension.
1152    template <class InputIterator>
insert(ordered_unique_range_t,InputIterator first,InputIterator last)1153    BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, InputIterator first, InputIterator last)
1154       {  m_flat_tree.insert_unique(ordered_unique_range, first, last); }
1155 
1156 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1157    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1158    //!   if there is no element with key equivalent to the key of that element.
1159    //!
1160    //! <b>Complexity</b>: N log(N).
1161    //!
1162    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)1163    BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1164    {
1165       m_flat_tree.insert_unique( dtl::force<impl_initializer_list>(il).begin()
1166                                , dtl::force<impl_initializer_list>(il).end());
1167    }
1168 
1169    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
1170    //! unique values.
1171    //!
1172    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
1173    //!   if there is no element with key equivalent to the key of that element. This
1174    //!   function is more efficient than the normal range creation for ordered ranges.
1175    //!
1176    //! <b>Complexity</b>: Linear.
1177    //!
1178    //! <b>Note</b>: If an element is inserted it might invalidate elements.
1179    //!
1180    //! <b>Note</b>: Non-standard extension.
insert(ordered_unique_range_t,std::initializer_list<value_type> il)1181    BOOST_CONTAINER_FORCEINLINE void insert(ordered_unique_range_t, std::initializer_list<value_type> il)
1182    {
1183       m_flat_tree.insert_unique(ordered_unique_range
1184                                , dtl::force<impl_initializer_list>(il).begin()
1185                                , dtl::force<impl_initializer_list>(il).end());
1186    }
1187 #endif
1188 
1189    //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1190    //!
1191    //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
1192    //!   the comparison object of *this. If there is an element in a with key equivalent to the
1193    //!   key of an element from source, then that element is not extracted from source.
1194    //!
1195    //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1196    //!   to those same elements but as members of *this. Iterators referring to the transferred
1197    //!   elements will continue to refer to their elements, but they now behave as iterators into *this,
1198    //!   not into source.
1199    //!
1200    //! <b>Throws</b>: Nothing unless the comparison object throws.
1201    //!
1202    //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
1203    template<class C2>
merge(flat_map<Key,T,C2,AllocatorOrContainer> & source)1204    BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source)
1205    {  m_flat_tree.merge_unique(source.tree());   }
1206 
1207    //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1208    template<class C2>
merge(BOOST_RV_REF_BEG flat_map<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)1209    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1210    {  return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); }
1211 
1212    //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1213    template<class C2>
merge(flat_multimap<Key,T,C2,AllocatorOrContainer> & source)1214    BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source)
1215    {  m_flat_tree.merge_unique(source.tree());   }
1216 
1217    //! @copydoc ::boost::container::flat_map::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
1218    template<class C2>
merge(BOOST_RV_REF_BEG flat_multimap<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)1219    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
1220    {  return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source));  }
1221 
1222    //! <b>Effects</b>: Erases the element pointed to by p.
1223    //!
1224    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
1225    //!   following q prior to the element being erased. If no such element exists,
1226    //!   returns end().
1227    //!
1228    //! <b>Complexity</b>: Linear to the elements with keys bigger than p
1229    //!
1230    //! <b>Note</b>: Invalidates elements with keys
1231    //!   not less than the erased element.
erase(const_iterator p)1232    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p)
1233    {
1234       return dtl::force_copy<iterator>
1235          (m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p)));
1236    }
1237 
1238    //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
1239    //!
1240    //! <b>Returns</b>: Returns the number of erased elements.
1241    //!
1242    //! <b>Complexity</b>: Logarithmic search time plus erasure time
1243    //!   linear to the elements with bigger keys.
erase(const key_type & x)1244    BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x)
1245       { return m_flat_tree.erase(x); }
1246 
1247    //! <b>Effects</b>: Erases all the elements in the range [first, last).
1248    //!
1249    //! <b>Returns</b>: Returns last.
1250    //!
1251    //! <b>Complexity</b>: size()*N where N is the distance from first to last.
1252    //!
1253    //! <b>Complexity</b>: Logarithmic search time plus erasure time
1254    //!   linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)1255    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
1256    {
1257       return dtl::force_copy<iterator>(
1258          m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first)
1259                           , dtl::force_copy<impl_const_iterator>(last)));
1260    }
1261 
1262    //! <b>Effects</b>: Swaps the contents of *this and x.
1263    //!
1264    //! <b>Throws</b>: Nothing.
1265    //!
1266    //! <b>Complexity</b>: Constant.
swap(flat_map & x)1267    BOOST_CONTAINER_FORCEINLINE void swap(flat_map& x)
1268       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
1269                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
1270    { m_flat_tree.swap(x.m_flat_tree); }
1271 
1272    //! <b>Effects</b>: erase(a.begin(),a.end()).
1273    //!
1274    //! <b>Postcondition</b>: size() == 0.
1275    //!
1276    //! <b>Complexity</b>: linear in size().
clear()1277    BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW
1278       { m_flat_tree.clear(); }
1279 
1280    //////////////////////////////////////////////
1281    //
1282    //                observers
1283    //
1284    //////////////////////////////////////////////
1285 
1286    //! <b>Effects</b>: Returns the comparison object out
1287    //!   of which a was constructed.
1288    //!
1289    //! <b>Complexity</b>: Constant.
key_comp() const1290    BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
1291       { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); }
1292 
1293    //! <b>Effects</b>: Returns an object of value_compare constructed out
1294    //!   of the comparison object.
1295    //!
1296    //! <b>Complexity</b>: Constant.
value_comp() const1297    BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
1298       { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); }
1299 
1300    //////////////////////////////////////////////
1301    //
1302    //              map operations
1303    //
1304    //////////////////////////////////////////////
1305 
1306    //! <b>Returns</b>: An iterator pointing to an element with the key
1307    //!   equivalent to x, or end() if such an element is not found.
1308    //!
1309    //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)1310    BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x)
1311       { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
1312 
1313    //! <b>Returns</b>: A const_iterator pointing to an element with the key
1314    //!   equivalent to x, or end() if such an element is not found.
1315    //!
1316    //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const1317    BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
1318       { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
1319 
1320    //! <b>Requires</b>: This overload is available only if
1321    //! key_compare::is_transparent exists.
1322    //!
1323    //! <b>Returns</b>: An iterator pointing to an element with the key
1324    //!   equivalent to x, or end() if such an element is not found.
1325    //!
1326    //! <b>Complexity</b>: Logarithmic.
1327    template<class K>
find(const K & x)1328    BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
1329       { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
1330 
1331    //! <b>Requires</b>: This overload is available only if
1332    //! key_compare::is_transparent exists.
1333    //!
1334    //! <b>Returns</b>: A const_iterator pointing to an element with the key
1335    //!   equivalent to x, or end() if such an element is not found.
1336    //!
1337    //! <b>Complexity</b>: Logarithmic.
1338    template<class K>
find(const K & x) const1339    BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
1340       { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
1341 
1342    //! <b>Returns</b>: The number of elements with key equivalent to x.
1343    //!
1344    //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const1345    BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
1346       {  return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end());  }
1347 
1348    //! <b>Requires</b>: This overload is available only if
1349    //! key_compare::is_transparent exists.
1350    //!
1351    //! <b>Returns</b>: The number of elements with key equivalent to x.
1352    //!
1353    //! <b>Complexity</b>: log(size())+count(k)
1354    template<class K>
count(const K & x) const1355    BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
1356       {  return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end());  }
1357 
1358    //! <b>Returns</b>: Returns true if there is an element with key
1359    //!   equivalent to key in the container, otherwise false.
1360    //!
1361    //! <b>Complexity</b>: log(size()).
contains(const key_type & x) const1362    bool contains(const key_type& x) const
1363       {  return m_flat_tree.find(x) != m_flat_tree.end();  }
1364 
1365    //! <b>Requires</b>: This overload is available only if
1366    //! key_compare::is_transparent exists.
1367    //!
1368    //! <b>Returns</b>: Returns true if there is an element with key
1369    //!   equivalent to key in the container, otherwise false.
1370    //!
1371    //! <b>Complexity</b>: log(size()).
1372    template<typename K>
contains(const K & x) const1373    bool contains(const K& x) const
1374       {  return m_flat_tree.find(x) != m_flat_tree.end();  }
1375 
1376    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1377    //!   than k, or a.end() if such an element is not found.
1378    //!
1379    //! <b>Complexity</b>: Logarithmic.
lower_bound(const key_type & x)1380    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x)
1381       {  return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1382 
1383    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1384    //!   less than k, or a.end() if such an element is not found.
1385    //!
1386    //! <b>Complexity</b>: Logarithmic.
lower_bound(const key_type & x) const1387    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
1388       {  return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1389 
1390    //! <b>Requires</b>: This overload is available only if
1391    //! key_compare::is_transparent exists.
1392    //!
1393    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1394    //!   than k, or a.end() if such an element is not found.
1395    //!
1396    //! <b>Complexity</b>: Logarithmic.
1397    template<class K>
lower_bound(const K & x)1398    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
1399       {  return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
1400 
1401    //! <b>Requires</b>: This overload is available only if
1402    //! key_compare::is_transparent exists.
1403    //!
1404    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1405    //!   less than k, or a.end() if such an element is not found.
1406    //!
1407    //! <b>Complexity</b>: Logarithmic.
1408    template<class K>
lower_bound(const K & x) const1409    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
1410       {  return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
1411 
1412    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1413    //!   than x, or end() if such an element is not found.
1414    //!
1415    //! <b>Complexity</b>: Logarithmic.
upper_bound(const key_type & x)1416    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x)
1417       {  return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1418 
1419    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1420    //!   less than x, or end() if such an element is not found.
1421    //!
1422    //! <b>Complexity</b>: Logarithmic.
upper_bound(const key_type & x) const1423    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
1424       {  return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1425 
1426    //! <b>Requires</b>: This overload is available only if
1427    //! key_compare::is_transparent exists.
1428    //!
1429    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1430    //!   than x, or end() if such an element is not found.
1431    //!
1432    //! <b>Complexity</b>: Logarithmic.
1433    template<class K>
upper_bound(const K & x)1434    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
1435       {  return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
1436 
1437    //! <b>Requires</b>: This overload is available only if
1438    //! key_compare::is_transparent exists.
1439    //!
1440    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1441    //!   less than x, or end() if such an element is not found.
1442    //!
1443    //! <b>Complexity</b>: Logarithmic.
1444    template<class K>
upper_bound(const K & x) const1445    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
1446       {  return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
1447 
1448    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1449    //!
1450    //! <b>Complexity</b>: Logarithmic.
equal_range(const key_type & x)1451    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
1452       {  return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1453 
1454    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1455    //!
1456    //! <b>Complexity</b>: Logarithmic.
equal_range(const key_type & x) const1457    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
1458       {  return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1459 
1460    //! <b>Requires</b>: This overload is available only if
1461    //! key_compare::is_transparent exists.
1462    //!
1463    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1464    //!
1465    //! <b>Complexity</b>: Logarithmic.
1466    template<class K>
equal_range(const K & x)1467    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
1468       {  return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(x)); }
1469 
1470    //! <b>Requires</b>: This overload is available only if
1471    //! key_compare::is_transparent exists.
1472    //!
1473    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1474    //!
1475    //! <b>Complexity</b>: Logarithmic.
1476    template<class K>
equal_range(const K & x) const1477    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
1478       {  return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }
1479 
1480    //! <b>Effects</b>: Extracts the internal sequence container.
1481    //!
1482    //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
1483    //!
1484    //! <b>Postcondition</b>: this->empty()
1485    //!
1486    //! <b>Throws</b>: If secuence_type's move constructor throws
extract_sequence()1487    BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
1488    {
1489       return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref()));
1490    }
1491 
1492    //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1493    //!   one passed externally using the move assignment. Erases non-unique elements.
1494    //!
1495    //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
1496    //!
1497    //! <b>Throws</b>: If the comparison or the move constructor throws
adopt_sequence(BOOST_RV_REF (sequence_type)seq)1498    BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
1499    {  this->m_flat_tree.adopt_sequence_unique(boost::move(dtl::force<impl_sequence_type>(seq)));  }
1500 
1501    //! <b>Requires</b>: seq shall be ordered according to this->compare()
1502    //!   and shall contain unique elements.
1503    //!
1504    //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
1505    //!   one passed externally using the move assignment.
1506    //!
1507    //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
1508    //!
1509    //! <b>Throws</b>: If the move assignment throws
adopt_sequence(ordered_unique_range_t,BOOST_RV_REF (sequence_type)seq)1510    BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_unique_range_t, BOOST_RV_REF(sequence_type) seq)
1511    {  this->m_flat_tree.adopt_sequence_unique(ordered_unique_range_t(), boost::move(dtl::force<impl_sequence_type>(seq)));  }
1512 
1513    //! <b>Effects</b>: Returns true if x and y are equal
1514    //!
1515    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_map & x,const flat_map & y)1516    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_map& x, const flat_map& y)
1517    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
1518 
1519    //! <b>Effects</b>: Returns true if x and y are unequal
1520    //!
1521    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_map & x,const flat_map & y)1522    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_map& x, const flat_map& y)
1523    {  return !(x == y); }
1524 
1525    //! <b>Effects</b>: Returns true if x is less than y
1526    //!
1527    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_map & x,const flat_map & y)1528    BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_map& x, const flat_map& y)
1529    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
1530 
1531    //! <b>Effects</b>: Returns true if x is greater than y
1532    //!
1533    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_map & x,const flat_map & y)1534    BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_map& x, const flat_map& y)
1535    {  return y < x;  }
1536 
1537    //! <b>Effects</b>: Returns true if x is equal or less than y
1538    //!
1539    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_map & x,const flat_map & y)1540    BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_map& x, const flat_map& y)
1541    {  return !(y < x);  }
1542 
1543    //! <b>Effects</b>: Returns true if x is equal or greater than y
1544    //!
1545    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_map & x,const flat_map & y)1546    BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_map& x, const flat_map& y)
1547    {  return !(x < y);  }
1548 
1549    //! <b>Effects</b>: x.swap(y)
1550    //!
1551    //! <b>Complexity</b>: Constant.
swap(flat_map & x,flat_map & y)1552    BOOST_CONTAINER_FORCEINLINE friend void swap(flat_map& x, flat_map& y)
1553    {  x.swap(y);  }
1554 
1555    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1556    private:
priv_subscript(const key_type & k)1557    mapped_type &priv_subscript(const key_type& k)
1558    {
1559       iterator i = lower_bound(k);
1560       // i->first is greater than or equivalent to k.
1561       if (i == end() || key_comp()(k, (*i).first)){
1562          dtl::value_init<mapped_type> m;
1563          i = insert(i, impl_value_type(k, ::boost::move(m.m_t)));
1564       }
1565       return (*i).second;
1566    }
priv_subscript(BOOST_RV_REF (key_type)mk)1567    mapped_type &priv_subscript(BOOST_RV_REF(key_type) mk)
1568    {
1569       key_type &k = mk;
1570       iterator i = lower_bound(k);
1571       // i->first is greater than or equivalent to k.
1572       if (i == end() || key_comp()(k, (*i).first)){
1573          dtl::value_init<mapped_type> m;
1574          i = insert(i, impl_value_type(boost::move(k), ::boost::move(m.m_t)));
1575       }
1576       return (*i).second;
1577    }
1578    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1579 };
1580 
1581 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1582 
1583 template <typename InputIterator>
1584 flat_map(InputIterator, InputIterator) ->
1585    flat_map< it_based_non_const_first_type_t<InputIterator>
1586            , it_based_second_type_t<InputIterator>>;
1587 
1588 template < typename InputIterator, typename AllocatorOrCompare>
1589     flat_map(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1590     flat_map< it_based_non_const_first_type_t<InputIterator>
1591             , it_based_second_type_t<InputIterator>
1592             , typename dtl::if_c< // Compare
1593                 dtl::is_allocator<AllocatorOrCompare>::value
1594                 , std::less<it_based_non_const_first_type_t<InputIterator>>
1595                 , AllocatorOrCompare
1596             >::type
1597             , typename dtl::if_c< // Allocator
1598                 dtl::is_allocator<AllocatorOrCompare>::value
1599                 , AllocatorOrCompare
1600                 , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1601                 >::type
1602             >;
1603 
1604 template < typename InputIterator, typename Compare, typename Allocator
1605          , typename = dtl::require_nonallocator_t<Compare>
1606          , typename = dtl::require_allocator_t<Allocator>>
1607 flat_map(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1608    flat_map< it_based_non_const_first_type_t<InputIterator>
1609            , it_based_second_type_t<InputIterator>
1610            , Compare
1611            , Allocator>;
1612 
1613 template <typename InputIterator>
1614 flat_map(ordered_unique_range_t, InputIterator, InputIterator) ->
1615    flat_map< it_based_non_const_first_type_t<InputIterator>
1616            , it_based_second_type_t<InputIterator>>;
1617 
1618 template < typename InputIterator, typename AllocatorOrCompare>
1619 flat_map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1620    flat_map< it_based_non_const_first_type_t<InputIterator>
1621            , it_based_second_type_t<InputIterator>
1622            , typename dtl::if_c<   // Compare
1623                dtl::is_allocator<AllocatorOrCompare>::value
1624                , std::less<it_based_non_const_first_type_t<InputIterator>>
1625                , AllocatorOrCompare
1626                >::type
1627            , typename dtl::if_c<   // Allocator
1628                dtl::is_allocator<AllocatorOrCompare>::value
1629                , AllocatorOrCompare
1630                , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1631                >::type
1632            >;
1633 
1634 template < typename InputIterator, typename Compare, typename Allocator
1635          , typename = dtl::require_nonallocator_t<Compare>
1636          , typename = dtl::require_allocator_t<Allocator>>
1637 flat_map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1638    flat_map< it_based_non_const_first_type_t<InputIterator>
1639            , it_based_second_type_t<InputIterator>
1640            , Compare
1641            , Allocator>;
1642 
1643 #endif
1644 
1645 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1646 
1647 }  //namespace container {
1648 
1649 //!has_trivial_destructor_after_move<> == true_type
1650 //!specialization for optimizations
1651 template <class Key, class T, class Compare, class AllocatorOrContainer>
1652 struct has_trivial_destructor_after_move<boost::container::flat_map<Key, T, Compare, AllocatorOrContainer> >
1653 {
1654    typedef typename ::boost::container::allocator_traits<AllocatorOrContainer>::pointer pointer;
1655    static const bool value = ::boost::has_trivial_destructor_after_move<AllocatorOrContainer>::value &&
1656                              ::boost::has_trivial_destructor_after_move<pointer>::value &&
1657                              ::boost::has_trivial_destructor_after_move<Compare>::value;
1658 };
1659 
1660 namespace container {
1661 
1662 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1663 
1664 //! A flat_multimap is a kind of associative container that supports equivalent keys
1665 //! (possibly containing multiple copies of the same key value) and provides for
1666 //! fast retrieval of values of another type T based on the keys.
1667 //!
1668 //! A flat_multimap satisfies all of the requirements of a container and of a reversible
1669 //! container and of an associative container. For a
1670 //! flat_multimap<Key,T> the key_type is Key and the value_type is std::pair<Key,T>
1671 //! (unlike std::multimap<Key, T> which value_type is std::pair<<b>const</b> Key, T>).
1672 //!
1673 //! flat_multimap is similar to std::multimap but it's implemented by as an ordered sequence container.
1674 //! The underlying sequence container is by default <i>vector</i> but it can also work
1675 //! user-provided vector-like SequenceContainers (like <i>static_vector</i> or <i>small_vector</i>).
1676 //!
1677 //! Using vector-like sequence containers means that inserting a new element into a flat_multimap might invalidate
1678 //! previous iterators and references (unless that sequence container is <i>stable_vector</i> or a similar
1679 //! container that offers stable pointers and references). Similarly, erasing an element might invalidate
1680 //! iterators and references pointing to elements that come after (their keys are bigger) the erased element.
1681 //!
1682 //! This container provides random-access iterators.
1683 //!
1684 //! \tparam Key is the key_type of the map
1685 //! \tparam Value is the <code>mapped_type</code>
1686 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1687 //! \tparam AllocatorOrContainer is either:
1688 //!   - The allocator to allocate <code>value_type</code>s (e.g. <i>allocator< std::pair<Key, T> > </i>).
1689 //!     (in this case <i>sequence_type</i> will be vector<value_type, AllocatorOrContainer>)
1690 //!   - The SequenceContainer to be used as the underlying <i>sequence_type</i>. It must be a vector-like
1691 //!     sequence container with random-access iterators.
1692 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1693 template <class Key, class T, class Compare = std::less<Key>, class AllocatorOrContainer = new_allocator< std::pair< Key, T> > >
1694 #else
1695 template <class Key, class T, class Compare, class AllocatorOrContainer>
1696 #endif
1697 class flat_multimap
1698 {
1699    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1700    private:
1701    BOOST_COPYABLE_AND_MOVABLE(flat_multimap)
1702    typedef dtl::flat_tree<
1703                            std::pair<Key, T>,
1704                            dtl::select1st<Key>,
1705                            Compare,
1706                            AllocatorOrContainer> tree_t;
1707    //This is the real tree stored here. It's based on a movable pair
1708    typedef dtl::flat_tree<
1709                            dtl::pair<Key, T>,
1710                            dtl::select1st<Key>,
1711                            Compare,
1712                            typename dtl::container_or_allocator_rebind<AllocatorOrContainer, dtl::pair<Key, T> >::type
1713                            > impl_tree_t;
1714    impl_tree_t m_flat_tree;  // flat tree representing flat_map
1715 
1716    typedef typename impl_tree_t::value_type              impl_value_type;
1717    typedef typename impl_tree_t::const_iterator          impl_const_iterator;
1718    typedef typename impl_tree_t::iterator                impl_iterator;
1719    typedef typename impl_tree_t::allocator_type          impl_allocator_type;
1720    #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1721    typedef std::initializer_list<impl_value_type>        impl_initializer_list;
1722    #endif
1723 
1724    typedef dtl::flat_tree_value_compare
1725       < Compare
1726       , dtl::select1st<Key>
1727       , std::pair<Key, T> >                                 value_compare_t;
1728    typedef typename tree_t::iterator                        iterator_t;
1729    typedef typename tree_t::const_iterator                  const_iterator_t;
1730    typedef typename tree_t::reverse_iterator                reverse_iterator_t;
1731    typedef typename tree_t::const_reverse_iterator          const_reverse_iterator_t;
1732 
1733    public:
1734    typedef typename impl_tree_t::stored_allocator_type      impl_stored_allocator_type;
1735    typedef typename impl_tree_t::sequence_type              impl_sequence_type;
1736 
tree()1737    BOOST_CONTAINER_FORCEINLINE impl_tree_t &tree()
1738    {  return m_flat_tree;  }
1739 
tree() const1740    BOOST_CONTAINER_FORCEINLINE const impl_tree_t &tree() const
1741    {  return m_flat_tree;  }
1742 
1743    private:
1744    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1745 
1746    public:
1747 
1748    //////////////////////////////////////////////
1749    //
1750    //                    types
1751    //
1752    //////////////////////////////////////////////
1753    typedef Key                                                                      key_type;
1754    typedef T                                                                        mapped_type;
1755    typedef Compare                                                                  key_compare;
1756    typedef std::pair<Key, T>                                                        value_type;
1757    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::sequence_type)                   sequence_type;
1758    typedef typename sequence_type::allocator_type                                   allocator_type;
1759    typedef ::boost::container::allocator_traits<allocator_type>                     allocator_traits_type;
1760    typedef typename sequence_type::pointer                                          pointer;
1761    typedef typename sequence_type::const_pointer                                    const_pointer;
1762    typedef typename sequence_type::reference                                        reference;
1763    typedef typename sequence_type::const_reference                                  const_reference;
1764    typedef typename sequence_type::size_type                                        size_type;
1765    typedef typename sequence_type::difference_type                                  difference_type;
1766    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
1767    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::value_compare)                   value_compare;
1768 
1769    typedef typename sequence_type::iterator                                         iterator;
1770    typedef typename sequence_type::const_iterator                                   const_iterator;
1771    typedef typename sequence_type::reverse_iterator                                 reverse_iterator;
1772    typedef typename sequence_type::const_reverse_iterator                           const_reverse_iterator;
1773    typedef BOOST_CONTAINER_IMPDEF(impl_value_type)                                  movable_value_type;
1774 
1775    //AllocatorOrContainer::value_type must be std::pair<Key, T>
1776    BOOST_STATIC_ASSERT((dtl::is_same<std::pair<Key, T>, value_type>::value));
1777 
1778    //////////////////////////////////////////////
1779    //
1780    //          construct/copy/destroy
1781    //
1782    //////////////////////////////////////////////
1783 
1784    //! <b>Effects</b>: Default constructs an empty flat_map.
1785    //!
1786    //! <b>Complexity</b>: Constant.
flat_multimap()1787    BOOST_CONTAINER_FORCEINLINE flat_multimap()
1788       BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<AllocatorOrContainer>::value &&
1789                         dtl::is_nothrow_default_constructible<Compare>::value)
1790       : m_flat_tree()
1791    {}
1792 
1793    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified allocator.
1794    //!
1795    //! <b>Complexity</b>: Constant.
flat_multimap(const allocator_type & a)1796    BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const allocator_type& a)
1797       : m_flat_tree(dtl::force<const impl_allocator_type>(a))
1798    {}
1799 
1800    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1801    //!   object .
1802    //!
1803    //! <b>Complexity</b>: Constant.
flat_multimap(const Compare & comp)1804    BOOST_CONTAINER_FORCEINLINE explicit flat_multimap(const Compare& comp)
1805       : m_flat_tree(comp)
1806    {}
1807 
1808    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison
1809    //!   object and allocator.
1810    //!
1811    //! <b>Complexity</b>: Constant.
1812    BOOST_CONTAINER_FORCEINLINE
flat_multimap(const Compare & comp,const allocator_type & a)1813    flat_multimap(const Compare& comp, const allocator_type& a)
1814       : m_flat_tree(comp, dtl::force<const impl_allocator_type>(a))
1815    {}
1816 
1817    //! <b>Effects</b>: Constructs an empty flat_multimap
1818    //!   and inserts elements from the range [first ,last ).
1819    //!
1820    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1821    //! the predicate and otherwise N logN, where N is last - first.
1822    template <class InputIterator>
1823    BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last)1824    flat_multimap(InputIterator first, InputIterator last)
1825       : m_flat_tree(false, first, last)
1826    {}
1827 
1828    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified
1829    //!   allocator, and inserts elements from the range [first ,last ).
1830    //!
1831    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1832    //! the predicate and otherwise N logN, where N is last - first.
1833    template <class InputIterator>
1834    BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const allocator_type & a)1835    flat_multimap(InputIterator first, InputIterator last, const allocator_type& a)
1836       : m_flat_tree(false, first, last, dtl::force<const impl_allocator_type>(a))
1837    {}
1838 
1839    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1840    //!   and inserts elements from the range [first ,last ).
1841    //!
1842    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1843    //! the predicate and otherwise N logN, where N is last - first.
1844    template <class InputIterator>
1845    BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const Compare & comp)1846    flat_multimap(InputIterator first, InputIterator last, const Compare& comp)
1847       : m_flat_tree(false, first, last, comp)
1848    {}
1849 
1850    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object
1851    //!   and allocator, and inserts elements from the range [first ,last ).
1852    //!
1853    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1854    //! the predicate and otherwise N logN, where N is last - first.
1855    template <class InputIterator>
1856    BOOST_CONTAINER_FORCEINLINE
flat_multimap(InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1857    flat_multimap(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1858       : m_flat_tree(false, first, last, comp, dtl::force<const impl_allocator_type>(a))
1859    {}
1860 
1861    //! <b>Effects</b>: Constructs an empty flat_multimap
1862    //! and inserts elements from the ordered range [first ,last). This function
1863    //! is more efficient than the normal range creation for ordered ranges.
1864    //!
1865    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1866    //!
1867    //! <b>Complexity</b>: Linear in N.
1868    //!
1869    //! <b>Note</b>: Non-standard extension.
1870    template <class InputIterator>
1871    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last)1872    flat_multimap(ordered_range_t, InputIterator first, InputIterator last)
1873       : m_flat_tree(ordered_range, first, last)
1874    {}
1875 
1876    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1877    //! inserts elements from the ordered range [first ,last). This function
1878    //! is more efficient than the normal range creation for ordered ranges.
1879    //!
1880    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1881    //!
1882    //! <b>Complexity</b>: Linear in N.
1883    //!
1884    //! <b>Note</b>: Non-standard extension.
1885    template <class InputIterator>
1886    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp)1887    flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1888       : m_flat_tree(ordered_range, first, last, comp)
1889    {}
1890 
1891    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1892    //! allocator, and inserts elements from the ordered range [first ,last). This function
1893    //! is more efficient than the normal range creation for ordered ranges.
1894    //!
1895    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1896    //!
1897    //! <b>Complexity</b>: Linear in N.
1898    //!
1899    //! <b>Note</b>: Non-standard extension.
1900    template <class InputIterator>
1901    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const Compare & comp,const allocator_type & a)1902    flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
1903       : m_flat_tree(ordered_range, first, last, comp, a)
1904    {}
1905 
1906    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1907    //! inserts elements from the ordered range [first ,last). This function
1908    //! is more efficient than the normal range creation for ordered ranges.
1909    //!
1910    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1911    //!
1912    //! <b>Complexity</b>: Linear in N.
1913    //!
1914    //! <b>Note</b>: Non-standard extension.
1915    template <class InputIterator>
1916    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,InputIterator first,InputIterator last,const allocator_type & a)1917       flat_multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type &a)
1918       : m_flat_tree(ordered_range, first, last, Compare(), a)
1919    {}
1920 
1921 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1922    //! <b>Effects</b>: Constructs an empty flat_map and
1923    //! inserts elements from the range [il.begin(), il.end()).
1924    //!
1925    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1926    //! the predicate and otherwise N logN, where N is last - first.
1927    BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il)1928    flat_multimap(std::initializer_list<value_type> il)
1929       : m_flat_tree( false
1930                    , dtl::force<impl_initializer_list>(il).begin()
1931                    , dtl::force<impl_initializer_list>(il).end())
1932    {}
1933 
1934    //! <b>Effects</b>: Constructs an empty flat_map using the specified
1935    //! allocator, and inserts elements from the range [il.begin(), il.end()).
1936    //!
1937    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1938    //! the predicate and otherwise N logN, where N is last - first.
1939    BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const allocator_type & a)1940    flat_multimap(std::initializer_list<value_type> il, const allocator_type& a)
1941       : m_flat_tree(false
1942                    , dtl::force<impl_initializer_list>(il).begin()
1943                    , dtl::force<impl_initializer_list>(il).end()
1944                    , dtl::force<const impl_allocator_type>(a))
1945    {}
1946 
1947    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1948    //! inserts elements from the range [il.begin(), il.end()).
1949    //!
1950    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1951    //! the predicate and otherwise N logN, where N is last - first.
1952    BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const Compare & comp)1953    flat_multimap(std::initializer_list<value_type> il, const Compare& comp)
1954       : m_flat_tree(false
1955                    , dtl::force<impl_initializer_list>(il).begin()
1956                    , dtl::force<impl_initializer_list>(il).end(), comp)
1957    {}
1958 
1959    //! <b>Effects</b>: Constructs an empty flat_map using the specified comparison object and
1960    //! allocator, and inserts elements from the range [il.begin(), il.end()).
1961    //!
1962    //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using
1963    //! the predicate and otherwise N logN, where N is last - first.
1964    BOOST_CONTAINER_FORCEINLINE
flat_multimap(std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)1965    flat_multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1966       : m_flat_tree( false
1967                    , dtl::force<impl_initializer_list>(il).begin()
1968                    , dtl::force<impl_initializer_list>(il).end()
1969                    , comp, dtl::force<const impl_allocator_type>(a))
1970    {}
1971 
1972    //! <b>Effects</b>: Constructs an empty flat_multimap and
1973    //! inserts elements from the ordered range [il.begin(), il.end()). This function
1974    //! is more efficient than the normal range creation for ordered ranges.
1975    //!
1976    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1977    //!
1978    //! <b>Complexity</b>: Linear in N.
1979    //!
1980    //! <b>Note</b>: Non-standard extension.
1981    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il)1982    flat_multimap(ordered_range_t, std::initializer_list<value_type> il)
1983       : m_flat_tree( ordered_range
1984                    , dtl::force<impl_initializer_list>(il).begin()
1985                    , dtl::force<impl_initializer_list>(il).end())
1986    {}
1987 
1988    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
1989    //! inserts elements from the ordered range [il.begin(), il.end()). This function
1990    //! is more efficient than the normal range creation for ordered ranges.
1991    //!
1992    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1993    //!
1994    //! <b>Complexity</b>: Linear in N.
1995    //!
1996    //! <b>Note</b>: Non-standard extension.
1997    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp)1998    flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1999       : m_flat_tree( ordered_range
2000                    , dtl::force<impl_initializer_list>(il).begin()
2001                    , dtl::force<impl_initializer_list>(il).end(), comp)
2002    {}
2003 
2004    //! <b>Effects</b>: Constructs an empty flat_multimap using the specified comparison object and
2005    //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function
2006    //! is more efficient than the normal range creation for ordered ranges.
2007    //!
2008    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
2009    //!
2010    //! <b>Complexity</b>: Linear in N.
2011    //!
2012    //! <b>Note</b>: Non-standard extension.
2013    BOOST_CONTAINER_FORCEINLINE
flat_multimap(ordered_range_t,std::initializer_list<value_type> il,const Compare & comp,const allocator_type & a)2014    flat_multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
2015       : m_flat_tree( ordered_range
2016                    , dtl::force<impl_initializer_list>(il).begin()
2017                    , dtl::force<impl_initializer_list>(il).end()
2018                    , comp, dtl::force<const impl_allocator_type>(a))
2019    {}
2020 #endif
2021 
2022    //! <b>Effects</b>: Copy constructs a flat_multimap.
2023    //!
2024    //! <b>Complexity</b>: Linear in x.size().
2025    BOOST_CONTAINER_FORCEINLINE
flat_multimap(const flat_multimap & x)2026    flat_multimap(const flat_multimap& x)
2027       : m_flat_tree(x.m_flat_tree)
2028    {}
2029 
2030    //! <b>Effects</b>: Move constructs a flat_multimap. Constructs *this using x's resources.
2031    //!
2032    //! <b>Complexity</b>: Constant.
2033    //!
2034    //! <b>Postcondition</b>: x is emptied.
2035    BOOST_CONTAINER_FORCEINLINE
flat_multimap(BOOST_RV_REF (flat_multimap)x)2036    flat_multimap(BOOST_RV_REF(flat_multimap) x)
2037       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
2038       : m_flat_tree(boost::move(x.m_flat_tree))
2039    {}
2040 
2041    //! <b>Effects</b>: Copy constructs a flat_multimap using the specified allocator.
2042    //!
2043    //! <b>Complexity</b>: Linear in x.size().
2044    BOOST_CONTAINER_FORCEINLINE
flat_multimap(const flat_multimap & x,const allocator_type & a)2045    flat_multimap(const flat_multimap& x, const allocator_type &a)
2046       : m_flat_tree(x.m_flat_tree, dtl::force<const impl_allocator_type>(a))
2047    {}
2048 
2049    //! <b>Effects</b>: Move constructs a flat_multimap using the specified allocator.
2050    //!                 Constructs *this using x's resources.
2051    //!
2052    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
2053    BOOST_CONTAINER_FORCEINLINE
flat_multimap(BOOST_RV_REF (flat_multimap)x,const allocator_type & a)2054    flat_multimap(BOOST_RV_REF(flat_multimap) x, const allocator_type &a)
2055       : m_flat_tree(boost::move(x.m_flat_tree), dtl::force<const impl_allocator_type>(a))
2056    {}
2057 
2058    //! <b>Effects</b>: Makes *this a copy of x.
2059    //!
2060    //! <b>Complexity</b>: Linear in x.size().
2061    BOOST_CONTAINER_FORCEINLINE
operator =(BOOST_COPY_ASSIGN_REF (flat_multimap)x)2062    flat_multimap& operator=(BOOST_COPY_ASSIGN_REF(flat_multimap) x)
2063       {  m_flat_tree = x.m_flat_tree;   return *this;  }
2064 
2065    //! <b>Effects</b>: this->swap(x.get()).
2066    //!
2067    //! <b>Complexity</b>: Constant.
2068    BOOST_CONTAINER_FORCEINLINE
operator =(BOOST_RV_REF (flat_multimap)x)2069    flat_multimap& operator=(BOOST_RV_REF(flat_multimap) x)
2070       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
2071                           allocator_traits_type::is_always_equal::value) &&
2072                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
2073       {  m_flat_tree = boost::move(x.m_flat_tree);   return *this;  }
2074 
2075 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2076    //! <b>Effects</b>: Assign content of il to *this
2077    //!
2078    //! <b>Complexity</b>: Linear in il.size().
2079    BOOST_CONTAINER_FORCEINLINE
operator =(std::initializer_list<value_type> il)2080    flat_multimap& operator=(std::initializer_list<value_type> il)
2081    {
2082       this->clear();
2083       this->insert(il.begin(), il.end());
2084       return *this;
2085    }
2086 #endif
2087 
2088    //! <b>Effects</b>: Returns a copy of the allocator that
2089    //!   was passed to the object's constructor.
2090    //!
2091    //! <b>Complexity</b>: Constant.
2092    BOOST_CONTAINER_FORCEINLINE
get_allocator() const2093    allocator_type get_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
2094       { return dtl::force_copy<allocator_type>(m_flat_tree.get_allocator()); }
2095 
2096    //! <b>Effects</b>: Returns a reference to the internal allocator.
2097    //!
2098    //! <b>Throws</b>: Nothing
2099    //!
2100    //! <b>Complexity</b>: Constant.
2101    //!
2102    //! <b>Note</b>: Non-standard extension.
2103    BOOST_CONTAINER_FORCEINLINE
get_stored_allocator()2104    stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW
2105       { return dtl::force<stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
2106 
2107    //! <b>Effects</b>: Returns a reference to the internal allocator.
2108    //!
2109    //! <b>Throws</b>: Nothing
2110    //!
2111    //! <b>Complexity</b>: Constant.
2112    //!
2113    //! <b>Note</b>: Non-standard extension.
2114    BOOST_CONTAINER_FORCEINLINE
get_stored_allocator() const2115    const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW
2116       { return dtl::force<const stored_allocator_type>(m_flat_tree.get_stored_allocator()); }
2117 
2118    //////////////////////////////////////////////
2119    //
2120    //                iterators
2121    //
2122    //////////////////////////////////////////////
2123 
2124    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
2125    //!
2126    //! <b>Throws</b>: Nothing.
2127    //!
2128    //! <b>Complexity</b>: Constant.
2129    BOOST_CONTAINER_FORCEINLINE
begin()2130    iterator begin() BOOST_NOEXCEPT_OR_NOTHROW
2131       { return dtl::force_copy<iterator>(m_flat_tree.begin()); }
2132 
2133    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
2134    //!
2135    //! <b>Throws</b>: Nothing.
2136    //!
2137    //! <b>Complexity</b>: Constant.
2138    BOOST_CONTAINER_FORCEINLINE
begin() const2139    const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW
2140       { return dtl::force_copy<const_iterator>(m_flat_tree.begin()); }
2141 
2142    //! <b>Effects</b>: Returns an iterator to the end of the container.
2143    //!
2144    //! <b>Throws</b>: Nothing.
2145    //!
2146    //! <b>Complexity</b>: Constant.
2147    BOOST_CONTAINER_FORCEINLINE
end()2148    iterator end() BOOST_NOEXCEPT_OR_NOTHROW
2149       { return dtl::force_copy<iterator>(m_flat_tree.end()); }
2150 
2151    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
2152    //!
2153    //! <b>Throws</b>: Nothing.
2154    //!
2155    //! <b>Complexity</b>: Constant.
2156    BOOST_CONTAINER_FORCEINLINE
end() const2157    const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW
2158       { return dtl::force_copy<const_iterator>(m_flat_tree.end()); }
2159 
2160    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
2161    //! of the reversed container.
2162    //!
2163    //! <b>Throws</b>: Nothing.
2164    //!
2165    //! <b>Complexity</b>: Constant.
2166    BOOST_CONTAINER_FORCEINLINE
rbegin()2167    reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW
2168       { return dtl::force_copy<reverse_iterator>(m_flat_tree.rbegin()); }
2169 
2170    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
2171    //! of the reversed container.
2172    //!
2173    //! <b>Throws</b>: Nothing.
2174    //!
2175    //! <b>Complexity</b>: Constant.
2176    BOOST_CONTAINER_FORCEINLINE
rbegin() const2177    const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2178       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rbegin()); }
2179 
2180    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
2181    //! of the reversed container.
2182    //!
2183    //! <b>Throws</b>: Nothing.
2184    //!
2185    //! <b>Complexity</b>: Constant.
2186    BOOST_CONTAINER_FORCEINLINE
rend()2187    reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW
2188       { return dtl::force_copy<reverse_iterator>(m_flat_tree.rend()); }
2189 
2190    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
2191    //! of the reversed container.
2192    //!
2193    //! <b>Throws</b>: Nothing.
2194    //!
2195    //! <b>Complexity</b>: Constant.
2196    BOOST_CONTAINER_FORCEINLINE
rend() const2197    const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW
2198       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.rend()); }
2199 
2200    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
2201    //!
2202    //! <b>Throws</b>: Nothing.
2203    //!
2204    //! <b>Complexity</b>: Constant.
2205    BOOST_CONTAINER_FORCEINLINE
cbegin() const2206    const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2207       { return dtl::force_copy<const_iterator>(m_flat_tree.cbegin()); }
2208 
2209    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
2210    //!
2211    //! <b>Throws</b>: Nothing.
2212    //!
2213    //! <b>Complexity</b>: Constant.
2214    BOOST_CONTAINER_FORCEINLINE
cend() const2215    const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW
2216       { return dtl::force_copy<const_iterator>(m_flat_tree.cend()); }
2217 
2218    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
2219    //! of the reversed container.
2220    //!
2221    //! <b>Throws</b>: Nothing.
2222    //!
2223    //! <b>Complexity</b>: Constant.
2224    BOOST_CONTAINER_FORCEINLINE
crbegin() const2225    const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW
2226       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crbegin()); }
2227 
2228    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
2229    //! of the reversed container.
2230    //!
2231    //! <b>Throws</b>: Nothing.
2232    //!
2233    //! <b>Complexity</b>: Constant.
2234    BOOST_CONTAINER_FORCEINLINE
crend() const2235    const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW
2236       { return dtl::force_copy<const_reverse_iterator>(m_flat_tree.crend()); }
2237 
2238    //////////////////////////////////////////////
2239    //
2240    //                capacity
2241    //
2242    //////////////////////////////////////////////
2243 
2244    //! <b>Effects</b>: Returns true if the container contains no elements.
2245    //!
2246    //! <b>Throws</b>: Nothing.
2247    //!
2248    //! <b>Complexity</b>: Constant.
2249    BOOST_CONTAINER_FORCEINLINE
empty() const2250    bool empty() const BOOST_NOEXCEPT_OR_NOTHROW
2251       { return m_flat_tree.empty(); }
2252 
2253    //! <b>Effects</b>: Returns the number of the elements contained in the container.
2254    //!
2255    //! <b>Throws</b>: Nothing.
2256    //!
2257    //! <b>Complexity</b>: Constant.
2258    BOOST_CONTAINER_FORCEINLINE
size() const2259    size_type size() const BOOST_NOEXCEPT_OR_NOTHROW
2260       { return m_flat_tree.size(); }
2261 
2262    //! <b>Effects</b>: Returns the largest possible size of the container.
2263    //!
2264    //! <b>Throws</b>: Nothing.
2265    //!
2266    //! <b>Complexity</b>: Constant.
2267    BOOST_CONTAINER_FORCEINLINE
max_size() const2268    size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW
2269       { return m_flat_tree.max_size(); }
2270 
2271    //! <b>Effects</b>: Number of elements for which memory has been allocated.
2272    //!   capacity() is always greater than or equal to size().
2273    //!
2274    //! <b>Throws</b>: Nothing.
2275    //!
2276    //! <b>Complexity</b>: Constant.
2277    BOOST_CONTAINER_FORCEINLINE
capacity() const2278    size_type capacity() const BOOST_NOEXCEPT_OR_NOTHROW
2279       { return m_flat_tree.capacity(); }
2280 
2281    //! <b>Effects</b>: If n is less than or equal to capacity(), or the
2282    //!   underlying container has no `reserve` member, this call has no
2283    //!   effect. Otherwise, it is a request for allocation of additional memory.
2284    //!   If the request is successful, then capacity() is greater than or equal to
2285    //!   n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
2286    //!
2287    //! <b>Throws</b>: If memory allocation allocation throws or T's copy constructor throws.
2288    //!
2289    //! <b>Note</b>: If capacity() is less than "cnt", iterators and references to
2290    //!   to values might be invalidated.
2291    BOOST_CONTAINER_FORCEINLINE
reserve(size_type cnt)2292    void reserve(size_type cnt)
2293       { m_flat_tree.reserve(cnt);   }
2294 
2295    //! <b>Effects</b>: Tries to deallocate the excess of memory created
2296    //    with previous allocations. The size of the vector is unchanged
2297    //!
2298    //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws.
2299    //!
2300    //! <b>Complexity</b>: Linear to size().
2301    BOOST_CONTAINER_FORCEINLINE
shrink_to_fit()2302    void shrink_to_fit()
2303       { m_flat_tree.shrink_to_fit(); }
2304 
2305    //! @copydoc ::boost::container::flat_set::nth(size_type)
2306    BOOST_CONTAINER_FORCEINLINE
nth(size_type n)2307    iterator nth(size_type n) BOOST_NOEXCEPT_OR_NOTHROW
2308    {  return dtl::force_copy<iterator>(m_flat_tree.nth(n));  }
2309 
2310    //! @copydoc ::boost::container::flat_set::nth(size_type) const
2311    BOOST_CONTAINER_FORCEINLINE
nth(size_type n) const2312    const_iterator nth(size_type n) const BOOST_NOEXCEPT_OR_NOTHROW
2313    {  return dtl::force_copy<iterator>(m_flat_tree.nth(n));  }
2314 
2315    //! @copydoc ::boost::container::flat_set::index_of(iterator)
2316    BOOST_CONTAINER_FORCEINLINE
index_of(iterator p)2317    size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW
2318    {  return m_flat_tree.index_of(dtl::force_copy<impl_iterator>(p));  }
2319 
2320    //! @copydoc ::boost::container::flat_set::index_of(const_iterator) const
2321    BOOST_CONTAINER_FORCEINLINE
index_of(const_iterator p) const2322    size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW
2323    {  return m_flat_tree.index_of(dtl::force_copy<impl_const_iterator>(p));  }
2324 
2325    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2326 
2327    //! <b>Effects</b>: Inserts an object of type T constructed with
2328    //!   std::forward<Args>(args)... and returns the iterator pointing to the
2329    //!   newly inserted element.
2330    //!
2331    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2332    //!   to the elements with bigger keys than x.
2333    //!
2334    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2335    template <class... Args>
2336    BOOST_CONTAINER_FORCEINLINE
emplace(BOOST_FWD_REF (Args)...args)2337    iterator emplace(BOOST_FWD_REF(Args)... args)
2338    {  return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(boost::forward<Args>(args)...)); }
2339 
2340    //! <b>Effects</b>: Inserts an object of type T constructed with
2341    //!   std::forward<Args>(args)... in the container.
2342    //!   p is a hint pointing to where the insert should start to search.
2343    //!
2344    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2345    //!   to the key of x.
2346    //!
2347    //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2348    //!   is to be inserted before p) plus linear insertion
2349    //!   to the elements with bigger keys than x.
2350    //!
2351    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2352    template <class... Args>
2353    BOOST_CONTAINER_FORCEINLINE
emplace_hint(const_iterator hint,BOOST_FWD_REF (Args)...args)2354    iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
2355    {
2356       return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal
2357          (dtl::force_copy<impl_const_iterator>(hint), boost::forward<Args>(args)...));
2358    }
2359 
2360    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
2361 
2362    #define BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE(N) \
2363    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2364    BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
2365    {  return dtl::force_copy<iterator>(m_flat_tree.emplace_equal(BOOST_MOVE_FWD##N));  }\
2366    \
2367    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
2368    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
2369    {\
2370       return dtl::force_copy<iterator>(m_flat_tree.emplace_hint_equal\
2371          (dtl::force_copy<impl_const_iterator>(hint) BOOST_MOVE_I##N BOOST_MOVE_FWD##N));\
2372    }\
2373    //
BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)2374    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE)
2375    #undef BOOST_CONTAINER_FLAT_MULTIMAP_EMPLACE_CODE
2376 
2377    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
2378 
2379    //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
2380    //!   newly inserted element.
2381    //!
2382    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2383    //!   to the elements with bigger keys than x.
2384    //!
2385    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2386    BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x)
2387    {
2388       return dtl::force_copy<iterator>(
2389          m_flat_tree.insert_equal(dtl::force<const impl_value_type>(x)));
2390    }
2391 
2392    //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
2393    //!   the iterator pointing to the newly inserted element.
2394    //!
2395    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2396    //!   to the elements with bigger keys than x.
2397    //!
2398    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (value_type)x)2399    BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(value_type) x)
2400    { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
2401 
2402    //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
2403    //!   the iterator pointing to the newly inserted element.
2404    //!
2405    //! <b>Complexity</b>: Logarithmic search time plus linear insertion
2406    //!   to the elements with bigger keys than x.
2407    //!
2408    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(BOOST_RV_REF (impl_value_type)x)2409    BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(impl_value_type) x)
2410       { return dtl::force_copy<iterator>(m_flat_tree.insert_equal(boost::move(x))); }
2411 
2412    //! <b>Effects</b>: Inserts a copy of x in the container.
2413    //!   p is a hint pointing to where the insert should start to search.
2414    //!
2415    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2416    //!   to the key of x.
2417    //!
2418    //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2419    //!   is to be inserted before p) plus linear insertion
2420    //!   to the elements with bigger keys than x.
2421    //!
2422    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,const value_type & x)2423    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
2424    {
2425       return dtl::force_copy<iterator>
2426          (m_flat_tree.insert_equal( dtl::force_copy<impl_const_iterator>(p)
2427                                   , dtl::force<const impl_value_type>(x)));
2428    }
2429 
2430    //! <b>Effects</b>: Inserts a value move constructed from x in the container.
2431    //!   p is a hint pointing to where the insert should start to search.
2432    //!
2433    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2434    //!   to the key of x.
2435    //!
2436    //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2437    //!   is to be inserted before p) plus linear insertion
2438    //!   to the elements with bigger keys than x.
2439    //!
2440    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (value_type)x)2441    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
2442    {
2443       return dtl::force_copy<iterator>
2444          (m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p)
2445                                   , boost::move(x)));
2446    }
2447 
2448    //! <b>Effects</b>: Inserts a value move constructed from x in the container.
2449    //!   p is a hint pointing to where the insert should start to search.
2450    //!
2451    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
2452    //!   to the key of x.
2453    //!
2454    //! <b>Complexity</b>: Logarithmic search time (constant time if the value
2455    //!   is to be inserted before p) plus linear insertion
2456    //!   to the elements with bigger keys than x.
2457    //!
2458    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(const_iterator p,BOOST_RV_REF (impl_value_type)x)2459    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(impl_value_type) x)
2460    {
2461       return dtl::force_copy<iterator>(
2462          m_flat_tree.insert_equal(dtl::force_copy<impl_const_iterator>(p), boost::move(x)));
2463    }
2464 
2465    //! <b>Requires</b>: first, last are not iterators into *this.
2466    //!
2467    //! <b>Effects</b>: inserts each element from the range [first,last) .
2468    //!
2469    //! <b>Complexity</b>: N log(N).
2470    //!
2471    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2472    template <class InputIterator>
insert(InputIterator first,InputIterator last)2473    BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
2474       {  m_flat_tree.insert_equal(first, last); }
2475 
2476    //! <b>Requires</b>: first, last are not iterators into *this.
2477    //!
2478    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
2479    //!
2480    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
2481    //!   if there is no element with key equivalent to the key of that element. This
2482    //!   function is more efficient than the normal range creation for ordered ranges.
2483    //!
2484    //! <b>Complexity</b>: Linear.
2485    //!
2486    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2487    //!
2488    //! <b>Note</b>: Non-standard extension.
2489    template <class InputIterator>
insert(ordered_range_t,InputIterator first,InputIterator last)2490    BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, InputIterator first, InputIterator last)
2491       {  m_flat_tree.insert_equal(ordered_range, first, last); }
2492 
2493 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
2494    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) .
2495    //!
2496    //! <b>Complexity</b>: N log(N).
2497    //!
2498    //! <b>Note</b>: If an element is inserted it might invalidate elements.
insert(std::initializer_list<value_type> il)2499    BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
2500    {
2501       m_flat_tree.insert_equal( dtl::force<impl_initializer_list>(il).begin()
2502                               , dtl::force<impl_initializer_list>(il).end());
2503    }
2504 
2505    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
2506    //!
2507    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
2508    //!   if there is no element with key equivalent to the key of that element. This
2509    //!   function is more efficient than the normal range creation for ordered ranges.
2510    //!
2511    //! <b>Complexity</b>: Linear.
2512    //!
2513    //! <b>Note</b>: If an element is inserted it might invalidate elements.
2514    //!
2515    //! <b>Note</b>: Non-standard extension.
insert(ordered_range_t,std::initializer_list<value_type> il)2516    BOOST_CONTAINER_FORCEINLINE void insert(ordered_range_t, std::initializer_list<value_type> il)
2517    {
2518       m_flat_tree.insert_equal( ordered_range
2519                               , dtl::force<impl_initializer_list>(il).begin()
2520                               , dtl::force<impl_initializer_list>(il).end());
2521    }
2522 #endif
2523 
2524    //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
2525    //!
2526    //! <b>Effects</b>: Extracts each element in source and insert it into a using
2527    //!   the comparison object of *this.
2528    //!
2529    //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
2530    //!   to those same elements but as members of *this. Iterators referring to the transferred
2531    //!   elements will continue to refer to their elements, but they now behave as iterators into *this,
2532    //!   not into source.
2533    //!
2534    //! <b>Throws</b>: Nothing unless the comparison object throws.
2535    //!
2536    //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
2537    template<class C2>
merge(flat_multimap<Key,T,C2,AllocatorOrContainer> & source)2538    BOOST_CONTAINER_FORCEINLINE void merge(flat_multimap<Key, T, C2, AllocatorOrContainer>& source)
2539    {  m_flat_tree.merge_equal(source.tree());   }
2540 
2541    //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
2542    template<class C2>
merge(BOOST_RV_REF_BEG flat_multimap<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)2543    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_multimap<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
2544    {  return this->merge(static_cast<flat_multimap<Key, T, C2, AllocatorOrContainer>&>(source)); }
2545 
2546    //! @copydoc ::boost::container::flat_multimap::merge(flat_multimap<Key, T, C2, AllocatorOrContainer>&)
2547    template<class C2>
merge(flat_map<Key,T,C2,AllocatorOrContainer> & source)2548    BOOST_CONTAINER_FORCEINLINE void merge(flat_map<Key, T, C2, AllocatorOrContainer>& source)
2549    {  m_flat_tree.merge_equal(source.tree());   }
2550 
2551    //! @copydoc ::boost::container::flat_multimap::merge(flat_map<Key, T, C2, AllocatorOrContainer>&)
2552    template<class C2>
merge(BOOST_RV_REF_BEG flat_map<Key,T,C2,AllocatorOrContainer> BOOST_RV_REF_END source)2553    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG flat_map<Key, T, C2, AllocatorOrContainer> BOOST_RV_REF_END source)
2554    {  return this->merge(static_cast<flat_map<Key, T, C2, AllocatorOrContainer>&>(source)); }
2555 
2556    //! <b>Effects</b>: Erases the element pointed to by p.
2557    //!
2558    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
2559    //!   following q prior to the element being erased. If no such element exists,
2560    //!   returns end().
2561    //!
2562    //! <b>Complexity</b>: Linear to the elements with keys bigger than p
2563    //!
2564    //! <b>Note</b>: Invalidates elements with keys
2565    //!   not less than the erased element.
erase(const_iterator p)2566    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator p)
2567    {
2568       return dtl::force_copy<iterator>(
2569          m_flat_tree.erase(dtl::force_copy<impl_const_iterator>(p)));
2570    }
2571 
2572    //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
2573    //!
2574    //! <b>Returns</b>: Returns the number of erased elements.
2575    //!
2576    //! <b>Complexity</b>: Logarithmic search time plus erasure time
2577    //!   linear to the elements with bigger keys.
erase(const key_type & x)2578    BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x)
2579       { return m_flat_tree.erase(x); }
2580 
2581    //! <b>Effects</b>: Erases all the elements in the range [first, last).
2582    //!
2583    //! <b>Returns</b>: Returns last.
2584    //!
2585    //! <b>Complexity</b>: size()*N where N is the distance from first to last.
2586    //!
2587    //! <b>Complexity</b>: Logarithmic search time plus erasure time
2588    //!   linear to the elements with bigger keys.
erase(const_iterator first,const_iterator last)2589    BOOST_CONTAINER_FORCEINLINE iterator erase(const_iterator first, const_iterator last)
2590    {
2591       return dtl::force_copy<iterator>
2592          (m_flat_tree.erase( dtl::force_copy<impl_const_iterator>(first)
2593                            , dtl::force_copy<impl_const_iterator>(last)));
2594    }
2595 
2596    //! <b>Effects</b>: Swaps the contents of *this and x.
2597    //!
2598    //! <b>Throws</b>: Nothing.
2599    //!
2600    //! <b>Complexity</b>: Constant.
swap(flat_multimap & x)2601    BOOST_CONTAINER_FORCEINLINE void swap(flat_multimap& x)
2602       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
2603                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value )
2604    { m_flat_tree.swap(x.m_flat_tree); }
2605 
2606    //! <b>Effects</b>: erase(a.begin(),a.end()).
2607    //!
2608    //! <b>Postcondition</b>: size() == 0.
2609    //!
2610    //! <b>Complexity</b>: linear in size().
clear()2611    BOOST_CONTAINER_FORCEINLINE void clear() BOOST_NOEXCEPT_OR_NOTHROW
2612       { m_flat_tree.clear(); }
2613 
2614    //////////////////////////////////////////////
2615    //
2616    //                observers
2617    //
2618    //////////////////////////////////////////////
2619 
2620    //! <b>Effects</b>: Returns the comparison object out
2621    //!   of which a was constructed.
2622    //!
2623    //! <b>Complexity</b>: Constant.
key_comp() const2624    BOOST_CONTAINER_FORCEINLINE key_compare key_comp() const
2625       { return dtl::force_copy<key_compare>(m_flat_tree.key_comp()); }
2626 
2627    //! <b>Effects</b>: Returns an object of value_compare constructed out
2628    //!   of the comparison object.
2629    //!
2630    //! <b>Complexity</b>: Constant.
value_comp() const2631    BOOST_CONTAINER_FORCEINLINE value_compare value_comp() const
2632       { return value_compare(dtl::force_copy<key_compare>(m_flat_tree.key_comp())); }
2633 
2634    //////////////////////////////////////////////
2635    //
2636    //              map operations
2637    //
2638    //////////////////////////////////////////////
2639 
2640    //! <b>Returns</b>: An iterator pointing to an element with the key
2641    //!   equivalent to x, or end() if such an element is not found.
2642    //!
2643    //! <b>Complexity</b>: Logarithmic.
find(const key_type & x)2644    BOOST_CONTAINER_FORCEINLINE iterator find(const key_type& x)
2645       { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
2646 
2647    //! <b>Returns</b>: An const_iterator pointing to an element with the key
2648    //!   equivalent to x, or end() if such an element is not found.
2649    //!
2650    //! <b>Complexity</b>: Logarithmic.
find(const key_type & x) const2651    BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
2652       { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
2653 
2654    //! <b>Requires</b>: This overload is available only if
2655    //! key_compare::is_transparent exists.
2656    //!
2657    //! <b>Returns</b>: An iterator pointing to an element with the key
2658    //!   equivalent to x, or end() if such an element is not found.
2659    //!
2660    //! <b>Complexity</b>: Logarithmic.
2661    template<class K>
find(const K & x)2662    BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
2663       { return dtl::force_copy<iterator>(m_flat_tree.find(x)); }
2664 
2665    //! <b>Requires</b>: This overload is available only if
2666    //! key_compare::is_transparent exists.
2667    //!
2668    //! <b>Returns</b>: An const_iterator pointing to an element with the key
2669    //!   equivalent to x, or end() if such an element is not found.
2670    //!
2671    //! <b>Complexity</b>: Logarithmic.
2672    template<class K>
find(const K & x) const2673    BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
2674       { return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }
2675 
2676    //! <b>Returns</b>: The number of elements with key equivalent to x.
2677    //!
2678    //! <b>Complexity</b>: log(size())+count(k)
count(const key_type & x) const2679    BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
2680       { return m_flat_tree.count(x); }
2681 
2682    //! <b>Requires</b>: This overload is available only if
2683    //! key_compare::is_transparent exists.
2684    //!
2685    //! <b>Returns</b>: The number of elements with key equivalent to x.
2686    //!
2687    //! <b>Complexity</b>: log(size())+count(k)
2688    template<class K>
count(const K & x) const2689    BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
2690       { return m_flat_tree.count(x); }
2691 
2692    //! <b>Returns</b>: Returns true if there is an element with key
2693    //!   equivalent to key in the container, otherwise false.
2694    //!
2695    //! <b>Complexity</b>: log(size()).
contains(const key_type & x) const2696    bool contains(const key_type& x) const
2697       {  return m_flat_tree.find(x) != m_flat_tree.end();  }
2698 
2699    //! <b>Requires</b>: This overload is available only if
2700    //! key_compare::is_transparent exists.
2701    //!
2702    //! <b>Returns</b>: Returns true if there is an element with key
2703    //!   equivalent to key in the container, otherwise false.
2704    //!
2705    //! <b>Complexity</b>: log(size()).
2706    template<typename K>
contains(const K & x) const2707    bool contains(const K& x) const
2708       {  return m_flat_tree.find(x) != m_flat_tree.end();  }
2709 
2710    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2711    //!   than k, or a.end() if such an element is not found.
2712    //!
2713    //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x)2714    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x)
2715       {  return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
2716 
2717    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2718    //!   than k, or a.end() if such an element is not found.
2719    //!
2720    //! <b>Complexity</b>: Logarithmic
lower_bound(const key_type & x) const2721    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
2722       {  return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
2723 
2724    //! <b>Requires</b>: This overload is available only if
2725    //! key_compare::is_transparent exists.
2726    //!
2727    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2728    //!   than k, or a.end() if such an element is not found.
2729    //!
2730    //! <b>Complexity</b>: Logarithmic
2731    template<class K>
lower_bound(const K & x)2732    BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
2733       {  return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }
2734 
2735    //! <b>Requires</b>: This overload is available only if
2736    //! key_compare::is_transparent exists.
2737    //!
2738    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2739    //!   than k, or a.end() if such an element is not found.
2740    //!
2741    //! <b>Complexity</b>: Logarithmic
2742    template<class K>
lower_bound(const K & x) const2743    BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
2744       {  return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
2745 
2746    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2747    //!   than x, or end() if such an element is not found.
2748    //!
2749    //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x)2750    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const key_type& x)
2751       {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
2752 
2753    //! <b>Returns</b>: A const iterator pointing to the first element with key
2754    //!   not less than x, or end() if such an element is not found.
2755    //!
2756    //! <b>Complexity</b>: Logarithmic
upper_bound(const key_type & x) const2757    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
2758       {  return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
2759 
2760    //! <b>Requires</b>: This overload is available only if
2761    //! key_compare::is_transparent exists.
2762    //!
2763    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2764    //!   than x, or end() if such an element is not found.
2765    //!
2766    //! <b>Complexity</b>: Logarithmic
2767    template<class K>
upper_bound(const K & x)2768    BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
2769       {return dtl::force_copy<iterator>(m_flat_tree.upper_bound(x)); }
2770 
2771    //! <b>Requires</b>: This overload is available only if
2772    //! key_compare::is_transparent exists.
2773    //!
2774    //! <b>Returns</b>: A const iterator pointing to the first element with key
2775    //!   not less than x, or end() if such an element is not found.
2776    //!
2777    //! <b>Complexity</b>: Logarithmic
2778    template<class K>
upper_bound(const K & x) const2779    BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
2780       {  return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }
2781 
2782    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2783    //!
2784    //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x)2785    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
2786       {  return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x));   }
2787 
2788    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2789    //!
2790    //! <b>Complexity</b>: Logarithmic
equal_range(const key_type & x) const2791    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
2792       {  return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x));   }
2793 
2794    //! <b>Requires</b>: This overload is available only if
2795    //! key_compare::is_transparent exists.
2796    //!
2797    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2798    //!
2799    //! <b>Complexity</b>: Logarithmic
2800    template<class K>
equal_range(const K & x)2801    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
2802       {  return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(x));   }
2803 
2804    //! <b>Requires</b>: This overload is available only if
2805    //! key_compare::is_transparent exists.
2806    //!
2807    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2808    //!
2809    //! <b>Complexity</b>: Logarithmic
2810    template<class K>
equal_range(const K & x) const2811    BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
2812       {  return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x));   }
2813 
2814    //! <b>Effects</b>: Extracts the internal sequence container.
2815    //!
2816    //! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
2817    //!
2818    //! <b>Postcondition</b>: this->empty()
2819    //!
2820    //! <b>Throws</b>: If secuence_type's move constructor throws
extract_sequence()2821    BOOST_CONTAINER_FORCEINLINE sequence_type extract_sequence()
2822    {
2823       return boost::move(dtl::force<sequence_type>(m_flat_tree.get_sequence_ref()));
2824    }
2825 
2826    //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
2827    //!   one passed externally using the move assignment.
2828    //!
2829    //! <b>Complexity</b>: Assuming O(1) move assignment, O(NlogN) with N = seq.size()
2830    //!
2831    //! <b>Throws</b>: If the comparison or the move constructor throws
adopt_sequence(BOOST_RV_REF (sequence_type)seq)2832    BOOST_CONTAINER_FORCEINLINE void adopt_sequence(BOOST_RV_REF(sequence_type) seq)
2833    {  this->m_flat_tree.adopt_sequence_equal(boost::move(dtl::force<impl_sequence_type>(seq)));  }
2834 
2835    //! <b>Requires</b>: seq shall be ordered according to this->compare().
2836    //!
2837    //! <b>Effects</b>: Discards the internally hold sequence container and adopts the
2838    //!   one passed externally using the move assignment.
2839    //!
2840    //! <b>Complexity</b>: Assuming O(1) move assignment, O(1)
2841    //!
2842    //! <b>Throws</b>: If the move assignment throws
adopt_sequence(ordered_range_t,BOOST_RV_REF (sequence_type)seq)2843    BOOST_CONTAINER_FORCEINLINE void adopt_sequence(ordered_range_t, BOOST_RV_REF(sequence_type) seq)
2844    {  this->m_flat_tree.adopt_sequence_equal(ordered_range_t(), boost::move(dtl::force<impl_sequence_type>(seq)));  }
2845 
2846    //! <b>Effects</b>: Returns true if x and y are equal
2847    //!
2848    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator ==(const flat_multimap & x,const flat_multimap & y)2849    BOOST_CONTAINER_FORCEINLINE friend bool operator==(const flat_multimap& x, const flat_multimap& y)
2850    {  return x.size() == y.size() && ::boost::container::algo_equal(x.begin(), x.end(), y.begin());  }
2851 
2852    //! <b>Effects</b>: Returns true if x and y are unequal
2853    //!
2854    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator !=(const flat_multimap & x,const flat_multimap & y)2855    BOOST_CONTAINER_FORCEINLINE friend bool operator!=(const flat_multimap& x, const flat_multimap& y)
2856    {  return !(x == y); }
2857 
2858    //! <b>Effects</b>: Returns true if x is less than y
2859    //!
2860    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <(const flat_multimap & x,const flat_multimap & y)2861    BOOST_CONTAINER_FORCEINLINE friend bool operator<(const flat_multimap& x, const flat_multimap& y)
2862    {  return ::boost::container::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());  }
2863 
2864    //! <b>Effects</b>: Returns true if x is greater than y
2865    //!
2866    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >(const flat_multimap & x,const flat_multimap & y)2867    BOOST_CONTAINER_FORCEINLINE friend bool operator>(const flat_multimap& x, const flat_multimap& y)
2868    {  return y < x;  }
2869 
2870    //! <b>Effects</b>: Returns true if x is equal or less than y
2871    //!
2872    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator <=(const flat_multimap & x,const flat_multimap & y)2873    BOOST_CONTAINER_FORCEINLINE friend bool operator<=(const flat_multimap& x, const flat_multimap& y)
2874    {  return !(y < x);  }
2875 
2876    //! <b>Effects</b>: Returns true if x is equal or greater than y
2877    //!
2878    //! <b>Complexity</b>: Linear to the number of elements in the container.
operator >=(const flat_multimap & x,const flat_multimap & y)2879    BOOST_CONTAINER_FORCEINLINE friend bool operator>=(const flat_multimap& x, const flat_multimap& y)
2880    {  return !(x < y);  }
2881 
2882    //! <b>Effects</b>: x.swap(y)
2883    //!
2884    //! <b>Complexity</b>: Constant.
swap(flat_multimap & x,flat_multimap & y)2885    BOOST_CONTAINER_FORCEINLINE friend void swap(flat_multimap& x, flat_multimap& y)
2886    {  x.swap(y);  }
2887 };
2888 
2889 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2890 
2891 template <typename InputIterator>
2892 flat_multimap(InputIterator, InputIterator) ->
2893    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2894                 , it_based_second_type_t<InputIterator>>;
2895 
2896 template < typename InputIterator, typename AllocatorOrCompare>
2897 flat_multimap(InputIterator, InputIterator, AllocatorOrCompare const&) ->
2898    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2899                 , it_based_second_type_t<InputIterator>
2900                 , typename dtl::if_c<   // Compare
2901                     dtl::is_allocator<AllocatorOrCompare>::value
2902                     , std::less<it_based_non_const_first_type_t<InputIterator>>
2903                     , AllocatorOrCompare
2904                     >::type
2905                 , typename dtl::if_c<   // Allocator
2906                     dtl::is_allocator<AllocatorOrCompare>::value
2907                     , AllocatorOrCompare
2908                     , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2909                     >::type
2910                 >;
2911 
2912 template < typename InputIterator, typename Compare, typename Allocator
2913          , typename = dtl::require_nonallocator_t<Compare>
2914          , typename = dtl::require_allocator_t<Allocator>>
2915 flat_multimap(InputIterator, InputIterator, Compare const&, Allocator const&) ->
2916    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2917                 , it_based_second_type_t<InputIterator>
2918                 , Compare
2919                 , Allocator>;
2920 
2921 template <typename InputIterator>
2922 flat_multimap(ordered_range_t, InputIterator, InputIterator) ->
2923    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2924                 , it_based_second_type_t<InputIterator>>;
2925 
2926 template < typename InputIterator, typename AllocatorOrCompare>
2927 flat_multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
2928    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2929                 , it_based_second_type_t<InputIterator>
2930                 , typename dtl::if_c<   // Compare
2931                     dtl::is_allocator<AllocatorOrCompare>::value
2932                     , std::less<it_based_non_const_first_type_t<InputIterator>>
2933                     , AllocatorOrCompare
2934                     >::type
2935                 , typename dtl::if_c<   // Allocator
2936                     dtl::is_allocator<AllocatorOrCompare>::value
2937                     , AllocatorOrCompare
2938                     , new_allocator<std::pair<it_based_non_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2939                     >::type
2940                 >;
2941 
2942 template < typename InputIterator, typename Compare, typename Allocator
2943          , typename = dtl::require_nonallocator_t<Compare>
2944          , typename = dtl::require_allocator_t<Allocator>>
2945 flat_multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
2946    flat_multimap< it_based_non_const_first_type_t<InputIterator>
2947                 , it_based_second_type_t<InputIterator>
2948                 , Compare
2949                 , Allocator>;
2950 
2951 #endif
2952 
2953 }}
2954 
2955 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2956 
2957 namespace boost {
2958 
2959 //!has_trivial_destructor_after_move<> == true_type
2960 //!specialization for optimizations
2961 template <class Key, class T, class Compare, class AllocatorOrContainer>
2962 struct has_trivial_destructor_after_move< boost::container::flat_multimap<Key, T, Compare, AllocatorOrContainer> >
2963 {
2964    typedef typename ::boost::container::allocator_traits<AllocatorOrContainer>::pointer pointer;
2965    static const bool value = ::boost::has_trivial_destructor_after_move<AllocatorOrContainer>::value &&
2966                              ::boost::has_trivial_destructor_after_move<pointer>::value &&
2967                              ::boost::has_trivial_destructor_after_move<Compare>::value;
2968 };
2969 
2970 }  //namespace boost {
2971 
2972 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2973 
2974 #include <boost/container/detail/config_end.hpp>
2975 
2976 #endif   // BOOST_CONTAINER_FLAT_MAP_HPP
2977