Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-18 09:30:18

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010 #ifndef BOOST_CONTAINER_MAP_HPP
0011 #define BOOST_CONTAINER_MAP_HPP
0012 
0013 #ifndef BOOST_CONFIG_HPP
0014 #  include <boost/config.hpp>
0015 #endif
0016 
0017 #if defined(BOOST_HAS_PRAGMA_ONCE)
0018 #  pragma once
0019 #endif
0020 
0021 #include <boost/container/detail/config_begin.hpp>
0022 #include <boost/container/detail/workaround.hpp>
0023 
0024 // container
0025 #include <boost/container/container_fwd.hpp>
0026 #include <boost/container/new_allocator.hpp> //new_allocator
0027 #include <boost/container/throw_exception.hpp>
0028 // container/detail
0029 #include <boost/container/detail/mpl.hpp>
0030 #include <boost/container/detail/tree.hpp>
0031 #include <boost/container/detail/type_traits.hpp>
0032 #include <boost/container/detail/value_init.hpp>
0033 #include <boost/container/detail/pair.hpp>
0034 #include <boost/container/detail/pair_key_mapped_of_value.hpp>
0035 
0036 // move
0037 #include <boost/move/traits.hpp>
0038 #include <boost/move/utility_core.hpp>
0039 // move/detail
0040 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0041 #include <boost/move/detail/fwd_macros.hpp>
0042 #endif
0043 #include <boost/move/detail/move_helpers.hpp>
0044 // intrusive/detail
0045 #include <boost/intrusive/detail/minimal_pair_header.hpp>      //pair
0046 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal
0047 // other
0048 #include <boost/static_assert.hpp>
0049 // std
0050 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0051 #include <initializer_list>
0052 #endif
0053 
0054 namespace boost {
0055 namespace container {
0056 
0057 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
0058 
0059 //! A map is a kind of associative container that supports unique keys (contains at
0060 //! most one of each key value) and provides for fast retrieval of values of another
0061 //! type T based on the keys. The map class supports bidirectional iterators.
0062 //!
0063 //! A map satisfies all of the requirements of a container and of a reversible
0064 //! container and of an associative container. The <code>value_type</code> stored
0065 //! by this container is the value_type is std::pair<const Key, T>.
0066 //!
0067 //! \tparam Key is the key_type of the map
0068 //! \tparam T is the <code>mapped_type</code>
0069 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
0070 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
0071 //!   (e.g. <i>allocator< std::pair<const Key, T> > </i>).
0072 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
0073 template < class Key, class T, class Compare = std::less<Key>
0074          , class Allocator = void, class Options = tree_assoc_defaults >
0075 #else
0076 template <class Key, class T, class Compare, class Allocator, class Options>
0077 #endif
0078 class map
0079    ///@cond
0080    : public dtl::tree
0081       < std::pair<const Key, T>
0082       , int
0083       , Compare, Allocator, Options>
0084    ///@endcond
0085 {
0086    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0087    private:
0088    BOOST_COPYABLE_AND_MOVABLE(map)
0089 
0090    typedef int                                                             select_1st_t;
0091    typedef std::pair<const Key, T>                                         value_type_impl;
0092    typedef dtl::tree
0093       <value_type_impl, select_1st_t, Compare, Allocator, Options>         base_t;
0094    typedef dtl::pair <Key, T>                                              movable_value_type_impl;
0095    typedef typename base_t::value_compare                                  value_compare_impl;
0096    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
0097 
0098    public:
0099    //////////////////////////////////////////////
0100    //
0101    //                    types
0102    //
0103    //////////////////////////////////////////////
0104 
0105    typedef Key                                                                            key_type;
0106    typedef T                                                                              mapped_type;
0107    typedef typename base_t::allocator_type                                                allocator_type;
0108    typedef ::boost::container::allocator_traits<allocator_type>                           allocator_traits_type;
0109    typedef typename boost::container::allocator_traits<allocator_type>::value_type        value_type;
0110    typedef typename boost::container::allocator_traits<allocator_type>::pointer           pointer;
0111    typedef typename boost::container::allocator_traits<allocator_type>::const_pointer     const_pointer;
0112    typedef typename boost::container::allocator_traits<allocator_type>::reference         reference;
0113    typedef typename boost::container::allocator_traits<allocator_type>::const_reference   const_reference;
0114    typedef typename boost::container::allocator_traits<allocator_type>::size_type         size_type;
0115    typedef typename boost::container::allocator_traits<allocator_type>::difference_type   difference_type;
0116    typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type)                 stored_allocator_type;
0117    typedef BOOST_CONTAINER_IMPDEF(value_compare_impl)                                     value_compare;
0118    typedef Compare                                                                        key_compare;
0119    typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator)                              iterator;
0120    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator)                        const_iterator;
0121    typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator)                      reverse_iterator;
0122    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator)                const_reverse_iterator;
0123    //typedef std::pair<key_type, mapped_type>                                               nonconst_value_type;
0124    typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl)                                movable_value_type;
0125    typedef BOOST_CONTAINER_IMPDEF(node_handle<
0126       typename base_t::stored_allocator_type
0127       BOOST_MOVE_I pair_key_mapped_of_value
0128          <key_type BOOST_MOVE_I mapped_type> >)                                     node_type;
0129    typedef BOOST_CONTAINER_IMPDEF
0130       (insert_return_type_base<iterator BOOST_MOVE_I node_type>)                    insert_return_type;
0131 
0132    //allocator_type::value_type type must be std::pair<CONST Key, T>
0133    BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value));
0134 
0135    //////////////////////////////////////////////
0136    //
0137    //          construct/copy/destroy
0138    //
0139    //////////////////////////////////////////////
0140 
0141    //! <b>Effects</b>: Default constructs an empty map.
0142    //!
0143    //! <b>Complexity</b>: Constant.
0144    BOOST_CONTAINER_FORCEINLINE 
0145    map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
0146                            dtl::is_nothrow_default_constructible<Compare>::value)
0147       : base_t()
0148    {}
0149 
0150    //! <b>Effects</b>: Constructs an empty map using the specified comparison object
0151    //! and allocator.
0152    //!
0153    //! <b>Complexity</b>: Constant.
0154    BOOST_CONTAINER_FORCEINLINE map(const Compare& comp, const allocator_type& a)
0155       : base_t(comp, a)
0156    {}
0157 
0158    //! <b>Effects</b>: Constructs an empty map using the specified comparison object.
0159    //!
0160    //! <b>Complexity</b>: Constant.
0161    BOOST_CONTAINER_FORCEINLINE explicit map(const Compare& comp)
0162       : base_t(comp)
0163    {}
0164 
0165    //! <b>Effects</b>: Constructs an empty map using the specified allocator.
0166    //!
0167    //! <b>Complexity</b>: Constant.
0168    BOOST_CONTAINER_FORCEINLINE explicit map(const allocator_type& a)
0169       : base_t(a)
0170    {}
0171 
0172    //! <b>Effects</b>: Constructs an empty map and
0173    //! inserts elements from the range [first ,last ).
0174    //!
0175    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0176    //! the predicate and otherwise N logN, where N is last - first.
0177    template <class InputIterator>
0178    BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last)
0179       : base_t(true, first, last)
0180    {}
0181 
0182    //! <b>Effects</b>: Constructs an empty map using the specified 
0183    //! allocator, and inserts elements from the range [first ,last ).
0184    //!
0185    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0186    //! the predicate and otherwise N logN, where N is last - first.
0187    template <class InputIterator>
0188    BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const allocator_type& a)
0189       : base_t(true, first, last, Compare(), a)
0190    {}
0191 
0192    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0193    //! inserts elements from the range [first ,last ).
0194    //!
0195    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0196    //! the predicate and otherwise N logN, where N is last - first.
0197    template <class InputIterator>
0198    BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp)
0199       : base_t(true, first, last, comp)
0200    {}
0201 
0202    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0203    //! allocator, and inserts elements from the range [first ,last ).
0204    //!
0205    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0206    //! the predicate and otherwise N logN, where N is last - first.
0207    template <class InputIterator>
0208    BOOST_CONTAINER_FORCEINLINE map(InputIterator first, InputIterator last, const Compare& comp, const allocator_type& a)
0209       : base_t(true, first, last, comp, a)
0210    {}
0211 
0212    //! <b>Effects</b>: Constructs an empty map and
0213    //! inserts elements from the ordered unique range [first ,last). This function
0214    //! is more efficient than the normal range creation for ordered ranges.
0215    //!
0216    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
0217    //! unique values.
0218    //!
0219    //! <b>Complexity</b>: Linear in N.
0220    //!
0221    //! <b>Note</b>: Non-standard extension.
0222    template <class InputIterator>
0223    BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last)
0224       : base_t(ordered_range, first, last)
0225    {}
0226 
0227    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0228    //! inserts elements from the ordered unique range [first ,last). This function
0229    //! is more efficient than the normal range creation for ordered ranges.
0230    //!
0231    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
0232    //! unique values.
0233    //!
0234    //! <b>Complexity</b>: Linear in N.
0235    //!
0236    //! <b>Note</b>: Non-standard extension.
0237    template <class InputIterator>
0238    BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last, const Compare& comp)
0239       : base_t(ordered_range, first, last, comp)
0240    {}
0241 
0242    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0243    //! allocator, and inserts elements from the ordered unique range [first ,last). This function
0244    //! is more efficient than the normal range creation for ordered ranges.
0245    //!
0246    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
0247    //! unique values.
0248    //!
0249    //! <b>Complexity</b>: Linear in N.
0250    //!
0251    //! <b>Note</b>: Non-standard extension.
0252    template <class InputIterator>
0253    BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, InputIterator first, InputIterator last
0254       , const Compare& comp, const allocator_type& a)
0255       : base_t(ordered_range, first, last, comp, a)
0256    {}
0257 
0258    //! <b>Effects</b>: Constructs an empty map using the specified allocator object and
0259    //! inserts elements from the ordered unique range [first ,last). This function
0260    //! is more efficient than the normal range creation for ordered ranges.
0261    //!
0262    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
0263    //! unique values.
0264    //!
0265    //! <b>Complexity</b>: Linear in N.
0266    //!
0267    //! <b>Note</b>: Non-standard extension.
0268    template <class InputIterator>
0269    BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
0270       : base_t(ordered_range, first, last, Compare(), a)
0271    {}
0272 
0273 
0274 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0275    //! <b>Effects</b>: Constructs an empty map and
0276    //! inserts elements from the range [il.begin(), il.end()).
0277    //!
0278    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted according
0279    //! to the predicate and otherwise N logN, where N is il.first() - il.end().
0280    BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il)
0281       : base_t(true, il.begin(), il.end())
0282    {}
0283 
0284    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0285    //! inserts elements from the range [il.begin(), il.end()).
0286    //!
0287    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0288    //! the predicate and otherwise N logN, where N is il.first() - il.end().
0289    BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp)
0290       : base_t(true, il.begin(), il.end(), comp)
0291    {}
0292 
0293    //! <b>Effects</b>: Constructs an empty map using the specified
0294    //! allocator, and inserts elements from the range [il.begin(), il.end()).
0295    //!
0296    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0297    //! the predicate and otherwise N logN, where N is il.first() - il.end().
0298    BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const allocator_type& a)
0299       : base_t(true, il.begin(), il.end(), Compare(), a)
0300    {}
0301 
0302    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0303    //! allocator, and inserts elements from the range [il.begin(), il.end()).
0304    //!
0305    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
0306    //! the predicate and otherwise N logN, where N is il.first() - il.end().
0307    BOOST_CONTAINER_FORCEINLINE map(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
0308       : base_t(true, il.begin(), il.end(), comp, a)
0309    {}
0310 
0311    //! <b>Effects</b>: Constructs an empty map and inserts elements from the ordered unique range [il.begin(), il.end()).
0312    //! This function is more efficient than the normal range creation for ordered ranges.
0313    //!
0314    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
0315    //! unique values.
0316    //!
0317    //! <b>Complexity</b>: Linear in N.
0318    //!
0319    //! <b>Note</b>: Non-standard extension.
0320    BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il)
0321       : base_t(ordered_range, il.begin(), il.end())
0322    {}
0323 
0324    //! <b>Effects</b>: Constructs an empty map using the specified comparison object,
0325    //!  and inserts elements from the ordered unique range [il.begin(), il.end()). This function
0326    //! is more efficient than the normal range creation for ordered ranges.
0327    //!
0328    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
0329    //! unique values.
0330    //!
0331    //! <b>Complexity</b>: Linear in N.
0332    //!
0333    //! <b>Note</b>: Non-standard extension.
0334    BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp)
0335       : base_t(ordered_range, il.begin(), il.end(), comp)
0336    {}
0337 
0338    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
0339    //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function
0340    //! is more efficient than the normal range creation for ordered ranges.
0341    //!
0342    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be
0343    //! unique values.
0344    //!
0345    //! <b>Complexity</b>: Linear in N.
0346    //!
0347    //! <b>Note</b>: Non-standard extension.
0348    BOOST_CONTAINER_FORCEINLINE map( ordered_unique_range_t, std::initializer_list<value_type> il
0349                                   , const Compare& comp, const allocator_type& a)
0350       : base_t(ordered_range, il.begin(), il.end(), comp, a)
0351    {} 
0352 
0353 #endif
0354 
0355    //! <b>Effects</b>: Copy constructs a map.
0356    //!
0357    //! <b>Complexity</b>: Linear in x.size().
0358    BOOST_CONTAINER_FORCEINLINE map(const map& x)
0359       : base_t(static_cast<const base_t&>(x))
0360    {}
0361 
0362    //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
0363    //!
0364    //! <b>Complexity</b>: Constant.
0365    //!
0366    //! <b>Postcondition</b>: x is emptied.
0367    BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x)
0368       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
0369       : base_t(BOOST_MOVE_BASE(base_t, x))
0370    {}
0371 
0372    //! <b>Effects</b>: Copy constructs a map using the specified allocator.
0373    //!
0374    //! <b>Complexity</b>: Linear in x.size().
0375    BOOST_CONTAINER_FORCEINLINE map(const map& x, const allocator_type &a)
0376       : base_t(static_cast<const base_t&>(x), a)
0377    {}
0378 
0379    //! <b>Effects</b>: Move constructs a map using the specified allocator.
0380    //!                 Constructs *this using x's resources.
0381    //!
0382    //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise.
0383    //!
0384    //! <b>Postcondition</b>: x is emptied.
0385    BOOST_CONTAINER_FORCEINLINE map(BOOST_RV_REF(map) x, const allocator_type &a)
0386       : base_t(BOOST_MOVE_BASE(base_t, x), a)
0387    {}
0388 
0389    //! <b>Effects</b>: Makes *this a copy of x.
0390    //!
0391    //! <b>Complexity</b>: Linear in x.size().
0392    BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_COPY_ASSIGN_REF(map) x)
0393    {  return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x)));  }
0394 
0395    //! <b>Effects</b>: this->swap(x.get()).
0396    //!
0397    //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment
0398    //!   is false and (allocation throws or value_type's move constructor throws)
0399    //!
0400    //! <b>Complexity</b>: Constant if allocator_traits_type::
0401    //!   propagate_on_container_move_assignment is true or
0402    //!   this->get>allocator() == x.get_allocator(). Linear otherwise.
0403    BOOST_CONTAINER_FORCEINLINE map& operator=(BOOST_RV_REF(map) x)
0404       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
0405                           allocator_traits_type::is_always_equal::value) &&
0406                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
0407    {  return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x)));  }
0408 
0409 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0410    //! <b>Effects</b>: Assign content of il to *this.
0411    //!
0412    BOOST_CONTAINER_FORCEINLINE map& operator=(std::initializer_list<value_type> il)
0413    {
0414        this->clear();
0415        insert(il.begin(), il.end());
0416        return *this;
0417    }
0418 #endif
0419 
0420    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0421 
0422    //! <b>Effects</b>: Returns a copy of the allocator that
0423    //!   was passed to the object's constructor.
0424    //!
0425    //! <b>Complexity</b>: Constant.
0426    allocator_type get_allocator() const;
0427 
0428    //! <b>Effects</b>: Returns a reference to the internal allocator.
0429    //!
0430    //! <b>Throws</b>: Nothing
0431    //!
0432    //! <b>Complexity</b>: Constant.
0433    //!
0434    //! <b>Note</b>: Non-standard extension.
0435    stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW;
0436 
0437    //! <b>Effects</b>: Returns a reference to the internal allocator.
0438    //!
0439    //! <b>Throws</b>: Nothing
0440    //!
0441    //! <b>Complexity</b>: Constant.
0442    //!
0443    //! <b>Note</b>: Non-standard extension.
0444    const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW;
0445 
0446    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
0447    //!
0448    //! <b>Throws</b>: Nothing.
0449    //!
0450    //! <b>Complexity</b>: Constant.
0451    iterator begin() BOOST_NOEXCEPT_OR_NOTHROW;
0452 
0453    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
0454    //!
0455    //! <b>Throws</b>: Nothing.
0456    //!
0457    //! <b>Complexity</b>: Constant.
0458    const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW;
0459 
0460    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
0461    //!
0462    //! <b>Throws</b>: Nothing.
0463    //!
0464    //! <b>Complexity</b>: Constant.
0465    const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
0466 
0467    //! <b>Effects</b>: Returns an iterator to the end of the container.
0468    //!
0469    //! <b>Throws</b>: Nothing.
0470    //!
0471    //! <b>Complexity</b>: Constant.
0472    iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
0473 
0474    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
0475    //!
0476    //! <b>Throws</b>: Nothing.
0477    //!
0478    //! <b>Complexity</b>: Constant.
0479    const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
0480 
0481    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
0482    //!
0483    //! <b>Throws</b>: Nothing.
0484    //!
0485    //! <b>Complexity</b>: Constant.
0486    const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
0487 
0488    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
0489    //! of the reversed container.
0490    //!
0491    //! <b>Throws</b>: Nothing.
0492    //!
0493    //! <b>Complexity</b>: Constant.
0494    reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
0495 
0496    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
0497    //! of the reversed container.
0498    //!
0499    //! <b>Throws</b>: Nothing.
0500    //!
0501    //! <b>Complexity</b>: Constant.
0502    const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
0503 
0504    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
0505    //! of the reversed container.
0506    //!
0507    //! <b>Throws</b>: Nothing.
0508    //!
0509    //! <b>Complexity</b>: Constant.
0510    const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
0511 
0512    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
0513    //! of the reversed container.
0514    //!
0515    //! <b>Throws</b>: Nothing.
0516    //!
0517    //! <b>Complexity</b>: Constant.
0518    reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
0519 
0520    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
0521    //! of the reversed container.
0522    //!
0523    //! <b>Throws</b>: Nothing.
0524    //!
0525    //! <b>Complexity</b>: Constant.
0526    const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
0527 
0528    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
0529    //! of the reversed container.
0530    //!
0531    //! <b>Throws</b>: Nothing.
0532    //!
0533    //! <b>Complexity</b>: Constant.
0534    const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
0535 
0536    //! <b>Effects</b>: Returns true if the container contains no elements.
0537    //!
0538    //! <b>Throws</b>: Nothing.
0539    //!
0540    //! <b>Complexity</b>: Constant.
0541    bool empty() const BOOST_NOEXCEPT_OR_NOTHROW;
0542 
0543    //! <b>Effects</b>: Returns the number of the elements contained in the container.
0544    //!
0545    //! <b>Throws</b>: Nothing.
0546    //!
0547    //! <b>Complexity</b>: Constant.
0548    size_type size() const BOOST_NOEXCEPT_OR_NOTHROW;
0549 
0550    //! <b>Effects</b>: Returns the largest possible size of the container.
0551    //!
0552    //! <b>Throws</b>: Nothing.
0553    //!
0554    //! <b>Complexity</b>: Constant.
0555    size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW;
0556 
0557    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0558 
0559    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0560    //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
0561    //! value_type(x, T()) into the map.
0562    //!
0563    //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
0564    //!
0565    //! <b>Complexity</b>: Logarithmic.
0566    mapped_type& operator[](const key_type &k);
0567 
0568    //! <b>Effects</b>: If there is no key equivalent to x in the map, inserts
0569    //! value_type(boost::move(x), T()) into the map (the key is move-constructed)
0570    //!
0571    //! <b>Returns</b>: A reference to the mapped_type corresponding to x in *this.
0572    //!
0573    //! <b>Complexity</b>: Logarithmic.
0574    mapped_type& operator[](key_type &&k);
0575    #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
0576       //in compilers like GCC 3.4, we can't catch temporaries
0577       BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](const key_type &k)         {  return this->priv_subscript(k);  }
0578       BOOST_CONTAINER_FORCEINLINE mapped_type& operator[](BOOST_RV_REF(key_type) k)  {  return this->priv_subscript(::boost::move(k));  }
0579    #else
0580       BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
0581    #endif
0582 
0583    //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
0584    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
0585    //! as if by insert, constructing it from value_type(k, forward<M>(obj)).
0586    //! 
0587    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
0588    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
0589    //! references obtained to that element before it was extracted become valid.
0590    //!
0591    //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
0592    //!   took place. The iterator component is pointing at the element that was inserted or updated.
0593    //!
0594    //! <b>Complexity</b>: Logarithmic in the size of the container.
0595    template <class M>
0596    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(const key_type& k, BOOST_FWD_REF(M) obj)
0597    {  return this->base_t::insert_or_assign(const_iterator(), k, ::boost::forward<M>(obj));  }
0598 
0599    //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
0600    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
0601    //! as if by insert, constructing it from value_type(k, move(obj)).
0602    //! 
0603    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
0604    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
0605    //! references obtained to that element before it was extracted become valid.
0606    //!
0607    //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
0608    //!   took place. The iterator component is pointing at the element that was inserted or updated.
0609    //!
0610    //! <b>Complexity</b>: Logarithmic in the size of the container.
0611    template <class M>
0612    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> insert_or_assign(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
0613    {  return this->base_t::insert_or_assign(const_iterator(), ::boost::move(k), ::boost::forward<M>(obj));  }
0614 
0615    //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
0616    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
0617    //! as if by insert, constructing it from value_type(k, forward<M>(obj)) and the new element
0618    //! to the container as close as possible to the position just before hint.
0619    //! 
0620    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
0621    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
0622    //! references obtained to that element before it was extracted become valid.
0623    //!
0624    //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
0625    //!   took place. The iterator component is pointing at the element that was inserted or updated.
0626    //!
0627    //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
0628    //! the new element is inserted just before hint.
0629    template <class M>
0630    BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
0631    {  return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)).first;  }
0632 
0633    //! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
0634    //! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
0635    //! as if by insert, constructing it from value_type(k, move(obj)) and the new element
0636    //! to the container as close as possible to the position just before hint.
0637    //! 
0638    //! No iterators or references are invalidated. If the insertion is successful, pointers and references
0639    //! to the element obtained while it is held in the node handle are invalidated, and pointers and
0640    //! references obtained to that element before it was extracted become valid.
0641    //!
0642    //! <b>Returns</b>: The bool component is true if the insertion took place and false if the assignment
0643    //!   took place. The iterator component is pointing at the element that was inserted or updated.
0644    //!
0645    //! <b>Complexity</b>: Logarithmic in the size of the container in general, but amortized constant if
0646    //! the new element is inserted just before hint.
0647    template <class M>
0648    BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
0649    {  return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)).first;  }
0650 
0651    //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
0652    //! Throws: An exception object of type out_of_range if no such element is present.
0653    //! <b>Complexity</b>: logarithmic.
0654    T& at(const key_type& k)
0655    {
0656       iterator i = this->find(k);
0657       if(i == this->end()){
0658          throw_out_of_range("map::at key not found");
0659       }
0660       return i->second;
0661    }
0662 
0663    //! <b>Returns</b>: A reference to the element whose key is equivalent to x.
0664    //! Throws: An exception object of type out_of_range if no such element is present.
0665    //! <b>Complexity</b>: logarithmic.
0666    BOOST_CONTAINER_ATTRIBUTE_NODISCARD const T& at(const key_type& k) const
0667    {
0668       const_iterator i = this->find(k);
0669       if(i == this->end()){
0670          throw_out_of_range("map::at key not found");
0671       }
0672       return i->second;
0673    }
0674 
0675    //////////////////////////////////////////////
0676    //
0677    //                modifiers
0678    //
0679    //////////////////////////////////////////////
0680 
0681    //! <b>Effects</b>: Inserts x if and only if there is no element in the container
0682    //!   with key equivalent to the key of x.
0683    //!
0684    //! <b>Returns</b>: The bool component of the returned pair is true if and only
0685    //!   if the insertion takes place, and the iterator component of the pair
0686    //!   points to the element with key equivalent to the key of x.
0687    //!
0688    //! <b>Complexity</b>: Logarithmic.
0689    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(const value_type& x)
0690    { return this->base_t::insert_unique_convertible(x); }
0691 
0692    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
0693    //!   no element in the container with key equivalent to the key of x.
0694    //!
0695    //! <b>Returns</b>: The bool component of the returned pair is true if and only
0696    //!   if the insertion takes place, and the iterator component of the pair
0697    //!   points to the element with key equivalent to the key of x.
0698    //!
0699    //! <b>Complexity</b>: Logarithmic.
0700    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
0701    { return this->base_t::insert_unique_convertible(boost::move(x)); }
0702 
0703    //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
0704    //! there is no element in the container  with key equivalent to the key of x.
0705    //!
0706    //! <b>Returns</b>: The bool component of the returned pair is true if and only
0707    //!   if the insertion takes place, and the iterator component of the pair
0708    //!   points to the element with key equivalent to the key of x.
0709    //!
0710    //! <b>Complexity</b>: Logarithmic.
0711    template <class Pair>
0712    BOOST_CONTAINER_FORCEINLINE BOOST_CONTAINER_DOC1ST
0713          ( std::pair<iterator BOOST_MOVE_I bool>
0714          , typename dtl::enable_if_c<
0715                dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value ||
0716                dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value
0717             BOOST_MOVE_I std::pair<iterator BOOST_MOVE_I bool> >::type)
0718       insert(BOOST_FWD_REF(Pair) x)
0719    {  return this->base_t::emplace_unique(boost::forward<Pair>(x)); }
0720 
0721    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
0722    { return this->base_t::insert_unique_hint_convertible(p, x); }
0723 
0724    //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
0725    //!   no element in the container with key equivalent to the key of x.
0726    //!   p is a hint pointing to where the insert should start to search.
0727    //!
0728    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
0729    //!   to the key of x.
0730    //!
0731    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0732    //!   is inserted right before p.
0733    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(value_type) x)
0734    { return this->base_t::insert_unique_hint_convertible(p, boost::move(x)); }
0735 
0736    //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
0737    //!   no element in the container with key equivalent to the key of x.
0738    //!   p is a hint pointing to where the insert should start to search.
0739    //!
0740    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
0741    //!   to the key of x.
0742    //!
0743    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0744    //!   is inserted right before p.
0745    template <class Pair>
0746    BOOST_CONTAINER_FORCEINLINE BOOST_CONTAINER_DOC1ST
0747          ( iterator
0748          , typename dtl::enable_if_c<
0749             dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value  ||
0750             dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value
0751             BOOST_MOVE_I iterator >::type)
0752       insert(const_iterator p, BOOST_FWD_REF(Pair) x)
0753    {  return this->base_t::emplace_hint_unique(p, boost::forward<Pair>(x));  }
0754 
0755 
0756 /*
0757    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
0758    //!   no element in the container with key equivalent to the key of x.
0759    //!   p is a hint pointing to where the insert should start to search.
0760    //!
0761    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
0762    //!   to the key of x.
0763    //!
0764    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0765    //!   is inserted right before p.
0766    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x)
0767    { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
0768 
0769    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
0770    //!   no element in the container with key equivalent to the key of x.
0771    //!   p is a hint pointing to where the insert should start to search.
0772    //!
0773    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
0774    //!   to the key of x.
0775    //!
0776    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0777    //!   is inserted right before p.
0778    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
0779    { return this->try_emplace(p, boost::move(x.first), boost::move(x.second)); }
0780 
0781    //! <b>Effects</b>: Inserts a copy of x in the container.
0782    //!   p is a hint pointing to where the insert should start to search.
0783    //!
0784    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
0785    //!
0786    //! <b>Complexity</b>: Logarithmic.
0787    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const nonconst_value_type& x)
0788    { return this->try_emplace(p, x.first, x.second); }
0789 
0790 
0791 */
0792    //! <b>Requires</b>: first, last are not iterators into *this.
0793    //!
0794    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
0795    //!   if there is no element with key equivalent to the key of that element.
0796    //!
0797    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
0798    template <class InputIterator>
0799    BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
0800    {  this->base_t::insert_unique_range(first, last);  }
0801 
0802 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
0803    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only
0804    //!   if there is no element with key equivalent to the key of that element.
0805    //!
0806    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
0807    BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
0808    {  this->base_t::insert_unique_range(il.begin(), il.end()); }
0809 #endif
0810 
0811    //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
0812    //!
0813    //! <b>Effects</b>: If nh is empty, has no effect. Otherwise, inserts the element owned
0814    //!   by nh if and only if there is no element in the container with a key equivalent to nh.key().
0815    //!
0816    //! <b>Returns</b>: If nh is empty, insert_return_type.inserted is false, insert_return_type.position
0817    //!   is end(), and insert_return_type.node is empty. Otherwise if the insertion took place,
0818    //!   insert_return_type.inserted is true, insert_return_type.position points to the inserted element,
0819    //!   and insert_return_type.node is empty; if the insertion failed, insert_return_type.inserted is
0820    //!   false, insert_return_type.node has the previous value of nh, and insert_return_type.position
0821    //!   points to an element with a key equivalent to nh.key().
0822    //!
0823    //! <b>Complexity</b>: Logarithmic
0824    insert_return_type insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
0825    {
0826       typename base_t::node_type  n(boost::move(nh));
0827       typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(boost::move(n)));
0828       return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
0829    }
0830 
0831    //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
0832    //!   to the position just prior to "hint".
0833    //!
0834    //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
0835    //!   right before "hint".
0836    insert_return_type insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
0837    {
0838       typename base_t::node_type  n(boost::move(nh));
0839       typename base_t::insert_return_type base_ret(this->base_t::insert_unique_node(hint, boost::move(n)));
0840       return insert_return_type (base_ret.inserted, base_ret.position, boost::move(base_ret.node));
0841    }
0842 
0843    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0844 
0845    //! <b>Effects</b>: Inserts an object x of type T constructed with
0846    //!   std::forward<Args>(args)... in the container if and only if there is
0847    //!   no element in the container with an equivalent key.
0848    //!   p is a hint pointing to where the insert should start to search.
0849    //!
0850    //! <b>Returns</b>: The bool component of the returned pair is true if and only
0851    //!   if the insertion takes place, and the iterator component of the pair
0852    //!   points to the element with key equivalent to the key of x.
0853    //!
0854    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0855    //!   is inserted right before p.
0856    template <class... Args>
0857    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args)
0858    {  return this->base_t::emplace_unique(boost::forward<Args>(args)...); }
0859 
0860    //! <b>Effects</b>: Inserts an object of type T constructed with
0861    //!   std::forward<Args>(args)... in the container if and only if there is
0862    //!   no element in the container with an equivalent key.
0863    //!   p is a hint pointing to where the insert should start to search.
0864    //!
0865    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
0866    //!   to the key of x.
0867    //!
0868    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
0869    //!   is inserted right before p.
0870    template <class... Args>
0871    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
0872    {  return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); }
0873 
0874    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 
0875    //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
0876    //! 
0877    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
0878    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
0879    //! forward_as_tuple(forward<Args>(args)...).
0880    //! 
0881    //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
0882    //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
0883    //! 
0884    //! <b>Complexity</b>: Logarithmic.
0885    template <class... Args>
0886    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k, BOOST_FWD_REF(Args)... args)
0887    {  return this->base_t::try_emplace(const_iterator(), k, boost::forward<Args>(args)...); }
0888 
0889    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 
0890    //! forward_as_tuple(k), forward_as_tuple(forward<Args>(args)...).
0891    //! 
0892    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
0893    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(k),
0894    //! forward_as_tuple(forward<Args>(args)...).
0895    //! 
0896    //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
0897    //! 
0898    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
0899    //!   is inserted right before p.
0900    template <class... Args>
0901    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k, BOOST_FWD_REF(Args)... args)
0902    {  return this->base_t::try_emplace(hint, k, boost::forward<Args>(args)...).first; }
0903 
0904    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 
0905    //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
0906    //! 
0907    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
0908    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
0909    //! forward_as_tuple(forward<Args>(args)...).
0910    //! 
0911    //! <b>Returns</b>: The bool component of the returned pair is true if and only if the
0912    //! insertion took place. The returned iterator points to the map element whose key is equivalent to k.
0913    //! 
0914    //! <b>Complexity</b>: Logarithmic.
0915    template <class... Args>
0916    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
0917    {  return this->base_t::try_emplace(const_iterator(), boost::move(k), boost::forward<Args>(args)...); }
0918 
0919    //! <b>Requires</b>: value_type shall be EmplaceConstructible into map from piecewise_construct, 
0920    //! forward_as_tuple(move(k)), forward_as_tuple(forward<Args>(args)...).
0921    //! 
0922    //! <b>Effects</b>: If the map already contains an element whose key is equivalent to k, there is no effect. Otherwise
0923    //! inserts an object of type value_type constructed with piecewise_construct, forward_as_tuple(move(k)),
0924    //! forward_as_tuple(forward<Args>(args)...).
0925    //! 
0926    //! <b>Returns</b>: The returned iterator points to the map element whose key is equivalent to k.
0927    //! 
0928    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if value
0929    //!   is inserted right before p.
0930    template <class... Args>
0931    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
0932    {  return this->base_t::try_emplace(hint, boost::move(k), boost::forward<Args>(args)...).first; }
0933 
0934    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0935 
0936    #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \
0937    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0938    BOOST_CONTAINER_FORCEINLINE std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\
0939    {  return this->base_t::emplace_unique(BOOST_MOVE_FWD##N);   }\
0940    \
0941    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0942    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0943    {  return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N);  }\
0944    \
0945    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0946    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(const key_type& k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0947    {  return this->base_t::try_emplace(const_iterator(), k BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
0948    \
0949    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0950    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, const key_type &k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0951    {  return this->base_t::try_emplace(hint, k BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
0952    \
0953    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0954    BOOST_CONTAINER_FORCEINLINE std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0955    {  return this->base_t::try_emplace(const_iterator(), boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\
0956    \
0957    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0958    BOOST_CONTAINER_FORCEINLINE iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0959    {  return this->base_t::try_emplace(hint, boost::move(k) BOOST_MOVE_I##N BOOST_MOVE_FWD##N).first; }\
0960    //
0961    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE)
0962    #undef BOOST_CONTAINER_MAP_EMPLACE_CODE
0963 
0964    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0965 
0966    //! <b>Effects</b>: If present, erases the element in the container with key equivalent to x.
0967    //!
0968    //! <b>Returns</b>: Returns the number of erased elements (0/1).
0969    //!
0970    //! <b>Complexity</b>: log(size()) + count(k)
0971    BOOST_CONTAINER_FORCEINLINE size_type erase(const key_type& x)
0972       { return this->base_t::erase_unique(x); }
0973 
0974    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0975 
0976    //! <b>Effects</b>: Erases the element pointed to by p.
0977    //!
0978    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
0979    //!   following q prior to the element being erased. If no such element exists,
0980    //!   returns end().
0981    //!
0982    //! <b>Complexity</b>: Amortized constant time
0983    iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW;
0984 
0985    //! <b>Effects</b>: Erases all the elements in the range [first, last).
0986    //!
0987    //! <b>Returns</b>: Returns last.
0988    //!
0989    //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
0990    iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW;
0991 
0992    #else
0993    using base_t::erase;
0994    #endif   //   #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
0995 
0996    //! <b>Effects</b>: Removes the first element in the container with key equivalent to k.
0997    //!
0998    //! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type.
0999    //!
1000    //! <b>Complexity</b>: log(size()).
1001    node_type extract(const key_type& k)
1002    {
1003       typename base_t::node_type base_nh(this->base_t::extract(k));
1004       node_type nh(boost::move(base_nh));
1005       return BOOST_MOVE_RET(node_type, nh);
1006    }
1007 
1008    //! <b>Effects</b>: Removes the element pointed to by "position".
1009    //!
1010    //! <b>Returns</b>: A node_type owning the element, otherwise an empty node_type.
1011    //!
1012    //! <b>Complexity</b>: Amortized constant.
1013    node_type extract(const_iterator position)
1014    {
1015       typename base_t::node_type base_nh(this->base_t::extract(position));
1016       node_type nh(boost::move(base_nh));
1017       return BOOST_MOVE_RET(node_type, nh);
1018    }
1019 
1020    //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1021    //!
1022    //! <b>Effects</b>: Attempts to extract each element in source and insert it into a using
1023    //!   the comparison object of *this. If there is an element in a with key equivalent to the
1024    //!   key of an element from source, then that element is not extracted from source.
1025    //! 
1026    //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1027    //!   to those same elements but as members of *this. Iterators referring to the transferred
1028    //!   elements will continue to refer to their elements, but they now behave as iterators into *this,
1029    //!   not into source.
1030    //!
1031    //! <b>Throws</b>: Nothing unless the comparison object throws.
1032    //!
1033    //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
1034    template<class C2>
1035    BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
1036    {
1037       typedef dtl::tree
1038          <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1039       this->merge_unique(static_cast<base2_t&>(source));
1040    }
1041 
1042    //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1043    template<class C2>
1044    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1045    {  return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
1046 
1047    //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1048    template<class C2>
1049    BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
1050    {
1051       typedef dtl::tree
1052          <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1053       this->base_t::merge_unique(static_cast<base2_t&>(source));
1054    }
1055 
1056    //! @copydoc ::boost::container::map::merge(map<Key, T, C2, Allocator, Options>&)
1057    template<class C2>
1058    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
1059    {  return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
1060 
1061    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1062    //! <b>Effects</b>: Swaps the contents of *this and x.
1063    //!
1064    //! <b>Throws</b>: Nothing.
1065    //!
1066    //! <b>Complexity</b>: Constant.
1067    void swap(map& x)
1068       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
1069                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value );
1070 
1071    //! <b>Effects</b>: erase(begin(),end()).
1072    //!
1073    //! <b>Postcondition</b>: size() == 0.
1074    //!
1075    //! <b>Complexity</b>: linear in size().
1076    void clear() BOOST_NOEXCEPT_OR_NOTHROW;
1077 
1078    //! <b>Effects</b>: Returns the comparison object out
1079    //!   of which a was constructed.
1080    //!
1081    //! <b>Complexity</b>: Constant.
1082    key_compare key_comp() const;
1083 
1084    //! <b>Effects</b>: Returns an object of value_compare constructed out
1085    //!   of the comparison object.
1086    //!
1087    //! <b>Complexity</b>: Constant.
1088    value_compare value_comp() const;
1089 
1090    //! <b>Returns</b>: An iterator pointing to an element with the key
1091    //!   equivalent to x, or end() if such an element is not found.
1092    //!
1093    //! <b>Complexity</b>: Logarithmic.
1094    iterator find(const key_type& x);
1095 
1096    //! <b>Returns</b>: A const_iterator pointing to an element with the key
1097    //!   equivalent to x, or end() if such an element is not found.
1098    //!
1099    //! <b>Complexity</b>: Logarithmic.
1100    const_iterator find(const key_type& x) const;
1101 
1102    //! <b>Requires</b>: This overload is available only if
1103    //! key_compare::is_transparent exists.
1104    //!
1105    //! <b>Returns</b>: An iterator pointing to an element with the key
1106    //!   equivalent to x, or end() if such an element is not found.
1107    //!
1108    //! <b>Complexity</b>: Logarithmic.
1109    template<typename K>
1110    iterator find(const K& x);
1111 
1112    //! <b>Requires</b>: This overload is available only if
1113    //! key_compare::is_transparent exists.
1114    //!
1115    //! <b>Returns</b>: A const_iterator pointing to an element with the key
1116    //!   equivalent to x, or end() if such an element is not found.
1117    //!
1118    //! <b>Complexity</b>: Logarithmic.
1119    template<typename K>
1120    const_iterator find(const K& x) const;
1121 
1122    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1123 
1124    //! <b>Returns</b>: The number of elements with key equivalent to x.
1125    //!
1126    //! <b>Complexity</b>: log(size())+count(k)
1127    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1128       size_type count(const key_type& x) const
1129    {  return static_cast<size_type>(this->find(x) != this->cend());  }
1130 
1131    //! <b>Requires</b>: This overload is available only if
1132    //! key_compare::is_transparent exists.
1133    //!
1134    //! <b>Returns</b>: The number of elements with key equivalent to x.
1135    //!
1136    //! <b>Complexity</b>: log(size())+count(k)
1137    template<typename K>
1138    BOOST_CONTAINER_ATTRIBUTE_NODISCARD BOOST_CONTAINER_FORCEINLINE
1139       size_type count(const K& x) const
1140    {  return static_cast<size_type>(this->find(x) != this->cend());  }
1141 
1142    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1143 
1144    //! <b>Returns</b>: Returns true if there is an element with key
1145    //!   equivalent to key in the container, otherwise false.
1146    //!
1147    //! <b>Complexity</b>: log(size()).
1148    bool contains(const key_type& x) const;
1149 
1150    //! <b>Requires</b>: This overload is available only if
1151    //! key_compare::is_transparent exists.
1152    //!
1153    //! <b>Returns</b>: Returns true if there is an element with key
1154    //!   equivalent to key in the container, otherwise false.
1155    //!
1156    //! <b>Complexity</b>: log(size()).
1157    template<typename K>
1158    bool contains(const K& x) const;
1159 
1160    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1161    //!   than x, or end() if such an element is not found.
1162    //!
1163    //! <b>Complexity</b>: Logarithmic
1164    iterator lower_bound(const key_type& x);
1165 
1166    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1167    //!   less than x, or end() if such an element is not found.
1168    //!
1169    //! <b>Complexity</b>: Logarithmic
1170    const_iterator lower_bound(const key_type& x) const;
1171 
1172    //! <b>Requires</b>: This overload is available only if
1173    //! key_compare::is_transparent exists.
1174    //!
1175    //! <b>Returns</b>: An iterator pointing to the first element with key not less
1176    //!   than x, or end() if such an element is not found.
1177    //!
1178    //! <b>Complexity</b>: Logarithmic
1179    template<typename K>
1180    iterator lower_bound(const K& x);
1181 
1182    //! <b>Requires</b>: This overload is available only if
1183    //! key_compare::is_transparent exists.
1184    //!
1185    //! <b>Returns</b>: A const iterator pointing to the first element with key not
1186    //!   less than x, or end() if such an element is not found.
1187    //!
1188    //! <b>Complexity</b>: Logarithmic
1189    template<typename K>
1190    const_iterator lower_bound(const K& x) const;
1191 
1192    //! <b>Returns</b>: An iterator pointing to the first element with key greater
1193    //!   than x, or end() if such an element is not found.
1194    //!
1195    //! <b>Complexity</b>: Logarithmic
1196    iterator upper_bound(const key_type& x);
1197 
1198    //! <b>Returns</b>: A const iterator pointing to the first element with key
1199    //!   greater than x, or end() if such an element is not found.
1200    //!
1201    //! <b>Complexity</b>: Logarithmic
1202    const_iterator upper_bound(const key_type& x) const;
1203 
1204    //! <b>Requires</b>: This overload is available only if
1205    //! key_compare::is_transparent exists.
1206    //!
1207    //! <b>Returns</b>: An iterator pointing to the first element with key greater
1208    //!   than x, or end() if such an element is not found.
1209    //!
1210    //! <b>Complexity</b>: Logarithmic
1211    template<typename K>
1212    iterator upper_bound(const K& x);
1213 
1214    //! <b>Requires</b>: This overload is available only if
1215    //! key_compare::is_transparent exists.
1216    //!
1217    //! <b>Returns</b>: A const iterator pointing to the first element with key
1218    //!   greater than x, or end() if such an element is not found.
1219    //!
1220    //! <b>Complexity</b>: Logarithmic
1221    template<typename K>
1222    const_iterator upper_bound(const K& x) const;
1223 
1224    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1225    //!
1226    //! <b>Complexity</b>: Logarithmic
1227    std::pair<iterator,iterator> equal_range(const key_type& x);
1228 
1229    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1230    //!
1231    //! <b>Complexity</b>: Logarithmic
1232    std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
1233 
1234    //! <b>Requires</b>: This overload is available only if
1235    //! key_compare::is_transparent exists.
1236    //!
1237    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1238    //!
1239    //! <b>Complexity</b>: Logarithmic
1240    template<typename K>
1241    std::pair<iterator,iterator> equal_range(const K& x);
1242 
1243    //! <b>Requires</b>: This overload is available only if
1244    //! key_compare::is_transparent exists.
1245    //!
1246    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
1247    //!
1248    //! <b>Complexity</b>: Logarithmic
1249    template<typename K>
1250    std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
1251 
1252    //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
1253    //!
1254    //! <b>Complexity</b>: Linear
1255    void rebalance();
1256 
1257    //! <b>Effects</b>: Returns true if x and y are equal
1258    //!
1259    //! <b>Complexity</b>: Linear to the number of elements in the container.
1260    friend bool operator==(const map& x, const map& y);
1261 
1262    //! <b>Effects</b>: Returns true if x and y are unequal
1263    //!
1264    //! <b>Complexity</b>: Linear to the number of elements in the container.
1265    friend bool operator!=(const map& x, const map& y);
1266 
1267    //! <b>Effects</b>: Returns true if x is less than y
1268    //!
1269    //! <b>Complexity</b>: Linear to the number of elements in the container.
1270    friend bool operator<(const map& x, const map& y);
1271 
1272    //! <b>Effects</b>: Returns true if x is greater than y
1273    //!
1274    //! <b>Complexity</b>: Linear to the number of elements in the container.
1275    friend bool operator>(const map& x, const map& y);
1276 
1277    //! <b>Effects</b>: Returns true if x is equal or less than y
1278    //!
1279    //! <b>Complexity</b>: Linear to the number of elements in the container.
1280    friend bool operator<=(const map& x, const map& y);
1281 
1282    //! <b>Effects</b>: Returns true if x is equal or greater than y
1283    //!
1284    //! <b>Complexity</b>: Linear to the number of elements in the container.
1285    friend bool operator>=(const map& x, const map& y);
1286 
1287    //! <b>Effects</b>: x.swap(y)
1288    //!
1289    //! <b>Complexity</b>: Constant.
1290    friend void swap(map& x, map& y)
1291       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
1292                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value );
1293 
1294    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1295 
1296    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1297    private:
1298    template<class KeyConvertible>
1299    BOOST_CONTAINER_FORCEINLINE mapped_type& priv_subscript(BOOST_FWD_REF(KeyConvertible) k)
1300    {
1301       return this->try_emplace(boost::forward<KeyConvertible>(k)).first->second;
1302    }
1303    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1304 };
1305 
1306 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
1307 
1308 template <typename InputIterator>
1309 map(InputIterator, InputIterator) ->
1310    map< it_based_non_const_first_type_t<InputIterator>
1311            , it_based_second_type_t<InputIterator>>;
1312 
1313 template < typename InputIterator, typename AllocatorOrCompare>
1314     map(InputIterator, InputIterator, AllocatorOrCompare const&) ->
1315     map< it_based_non_const_first_type_t<InputIterator>
1316             , it_based_second_type_t<InputIterator>
1317             , typename dtl::if_c< // Compare
1318                 dtl::is_allocator<AllocatorOrCompare>::value
1319                 , std::less<it_based_non_const_first_type_t<InputIterator>>
1320                 , AllocatorOrCompare
1321             >::type
1322             , typename dtl::if_c< // Allocator
1323                 dtl::is_allocator<AllocatorOrCompare>::value
1324                 , AllocatorOrCompare
1325                 , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1326                 >::type
1327             >;
1328 
1329 template < typename InputIterator, typename Compare, typename Allocator
1330          , typename = dtl::require_nonallocator_t<Compare>
1331          , typename = dtl::require_allocator_t<Allocator>>
1332 map(InputIterator, InputIterator, Compare const&, Allocator const&) ->
1333    map< it_based_non_const_first_type_t<InputIterator>
1334            , it_based_second_type_t<InputIterator>
1335            , Compare
1336            , Allocator>;
1337 
1338 template <typename InputIterator>
1339 map(ordered_unique_range_t, InputIterator, InputIterator) ->
1340    map< it_based_non_const_first_type_t<InputIterator>
1341            , it_based_second_type_t<InputIterator>>;
1342 
1343 template < typename InputIterator, typename AllocatorOrCompare>
1344 map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
1345    map< it_based_non_const_first_type_t<InputIterator>
1346            , it_based_second_type_t<InputIterator>
1347            , typename dtl::if_c<   // Compare
1348                dtl::is_allocator<AllocatorOrCompare>::value
1349                , std::less<it_based_non_const_first_type_t<InputIterator>>
1350                , AllocatorOrCompare
1351                >::type
1352            , typename dtl::if_c<   // Allocator
1353                dtl::is_allocator<AllocatorOrCompare>::value
1354                , AllocatorOrCompare
1355                , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
1356                >::type
1357            >;
1358 
1359 template < typename InputIterator, typename Compare, typename Allocator
1360          , typename = dtl::require_nonallocator_t<Compare>
1361          , typename = dtl::require_allocator_t<Allocator>>
1362 map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
1363    map< it_based_non_const_first_type_t<InputIterator>
1364            , it_based_second_type_t<InputIterator>
1365            , Compare
1366            , Allocator>;
1367 
1368 #endif
1369 
1370 
1371 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1372 
1373 }  //namespace container {
1374 
1375 //!has_trivial_destructor_after_move<> == true_type
1376 //!specialization for optimizations
1377 template <class Key, class T, class Compare, class Allocator, class Options>
1378 struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator, Options> >
1379 {
1380    typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
1381    static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
1382 };
1383 
1384 namespace container {
1385 
1386 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1387 
1388 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
1389 
1390 //! A multimap is a kind of associative container that supports equivalent keys
1391 //! (possibly containing multiple copies of the same key value) and provides for
1392 //! fast retrieval of values of another type T based on the keys. The multimap class
1393 //! supports bidirectional iterators.
1394 //!
1395 //! A multimap satisfies all of the requirements of a container and of a reversible
1396 //! container and of an associative container. The <code>value_type</code> stored
1397 //! by this container is the value_type is std::pair<const Key, T>.
1398 //!
1399 //! \tparam Key is the key_type of the map
1400 //! \tparam Value is the <code>mapped_type</code>
1401 //! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
1402 //! \tparam Allocator is the allocator to allocate the <code>value_type</code>s
1403 //!   (e.g. <i>allocator< std::pair<const Key, T> > </i>).
1404 //! \tparam Options is an packed option type generated using using boost::container::tree_assoc_options.
1405 template < class Key, class T, class Compare = std::less<Key>
1406          , class Allocator = new_allocator< std::pair< const Key, T> >, class Options = tree_assoc_defaults>
1407 #else
1408 template <class Key, class T, class Compare, class Allocator, class Options>
1409 #endif
1410 class multimap
1411    ///@cond
1412    : public dtl::tree
1413       < std::pair<const Key, T>
1414       , int
1415       , Compare, Allocator, Options>
1416    ///@endcond
1417 {
1418    #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1419    private:
1420    BOOST_COPYABLE_AND_MOVABLE(multimap)
1421 
1422    typedef int                                                                   select_1st_t;
1423    typedef std::pair<const Key, T>                                               value_type_impl;
1424    typedef dtl::tree
1425       <value_type_impl, select_1st_t, Compare, Allocator, Options>               base_t;
1426    typedef dtl::pair <Key, T>                                       movable_value_type_impl;
1427    typedef typename base_t::value_compare                                        value_compare_impl;
1428    #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
1429 
1430    public:
1431    //////////////////////////////////////////////
1432    //
1433    //                    types
1434    //
1435    //////////////////////////////////////////////
1436 
1437    typedef Key                                                                            key_type;
1438    typedef T                                                                              mapped_type;
1439    typedef typename base_t::allocator_type                                                allocator_type;
1440    typedef ::boost::container::allocator_traits<allocator_type>                           allocator_traits_type;
1441    typedef typename boost::container::allocator_traits<allocator_type>::value_type        value_type;
1442    typedef typename boost::container::allocator_traits<allocator_type>::pointer           pointer;
1443    typedef typename boost::container::allocator_traits<allocator_type>::const_pointer     const_pointer;
1444    typedef typename boost::container::allocator_traits<allocator_type>::reference         reference;
1445    typedef typename boost::container::allocator_traits<allocator_type>::const_reference   const_reference;
1446    typedef typename boost::container::allocator_traits<allocator_type>::size_type         size_type;
1447    typedef typename boost::container::allocator_traits<allocator_type>::difference_type   difference_type;
1448    typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type)                 stored_allocator_type;
1449    typedef BOOST_CONTAINER_IMPDEF(value_compare_impl)                                     value_compare;
1450    typedef Compare                                                                        key_compare;
1451    typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator)                              iterator;
1452    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator)                        const_iterator;
1453    typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator)                      reverse_iterator;
1454    typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator)                const_reverse_iterator;
1455    //typedef std::pair<key_type, mapped_type>                                               nonconst_value_type;
1456    typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl)                                movable_value_type;
1457    typedef BOOST_CONTAINER_IMPDEF(node_handle<
1458       typename base_t::stored_allocator_type
1459       BOOST_MOVE_I pair_key_mapped_of_value
1460          <key_type BOOST_MOVE_I mapped_type> >)                                     node_type;
1461 
1462    //allocator_type::value_type type must be std::pair<CONST Key, T>
1463    BOOST_STATIC_ASSERT((dtl::is_same<typename allocator_type::value_type, std::pair<const Key, T> >::value));
1464 
1465    //////////////////////////////////////////////
1466    //
1467    //          construct/copy/destroy
1468    //
1469    //////////////////////////////////////////////
1470 
1471    //! <b>Effects</b>: Default constructs an empty multimap.
1472    //!
1473    //! <b>Complexity</b>: Constant.
1474    BOOST_CONTAINER_FORCEINLINE multimap()
1475       BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
1476                         dtl::is_nothrow_default_constructible<Compare>::value)
1477       : base_t()
1478    {}
1479 
1480    //! <b>Effects</b>: Constructs an empty multimap using the specified allocator
1481    //!   object and allocator.
1482    //!
1483    //! <b>Complexity</b>: Constant.
1484    BOOST_CONTAINER_FORCEINLINE explicit multimap(const allocator_type& a)
1485       : base_t(a)
1486    {}
1487 
1488    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison.
1489    //!
1490    //! <b>Complexity</b>: Constant.
1491    BOOST_CONTAINER_FORCEINLINE explicit multimap(const Compare& comp)
1492       : base_t(comp)
1493    {}
1494 
1495    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison and allocator.
1496    //!
1497    //! <b>Complexity</b>: Constant.
1498    BOOST_CONTAINER_FORCEINLINE multimap(const Compare& comp, const allocator_type& a)
1499       : base_t(comp, a)
1500    {}
1501 
1502    //! <b>Effects</b>: Constructs an empty multimap and
1503    //! inserts elements from the range [first ,last ).
1504    //!
1505    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1506    //! the predicate and otherwise N logN, where N is last - first.
1507    template <class InputIterator>
1508    BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last)
1509       : base_t(false, first, last)
1510    {}
1511 
1512    //! <b>Effects</b>: Constructs an empty multimap using the specified 
1513    //! allocator, and inserts elements from the range [first ,last ).
1514    //!
1515    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1516    //! the predicate and otherwise N logN, where N is last - first.
1517    template <class InputIterator>
1518    BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const allocator_type& a)
1519       : base_t(false, first, last, Compare(), a)
1520    {}
1521 
1522    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1523    //! inserts elements from the range [first ,last ).
1524    //!
1525    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1526    //! the predicate and otherwise N logN, where N is last - first.
1527    template <class InputIterator>
1528    BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last, const Compare& comp)
1529       : base_t(false, first, last, comp)
1530    {}
1531 
1532    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
1533    //!   and allocator, and inserts elements from the range [first ,last ).
1534    //!
1535    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1536    //! the predicate and otherwise N logN, where N is last - first.
1537    template <class InputIterator>
1538    BOOST_CONTAINER_FORCEINLINE multimap(InputIterator first, InputIterator last,
1539             const Compare& comp, const allocator_type& a)
1540       : base_t(false, first, last, comp, a)
1541    {}
1542 
1543    //! <b>Effects</b>: Constructs an empty multimap and
1544    //! inserts elements from the ordered range [first ,last). This function
1545    //! is more efficient than the normal range creation for ordered ranges.
1546    //!
1547    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1548    //!
1549    //! <b>Complexity</b>: Linear in N.
1550    //!
1551    //! <b>Note</b>: Non-standard extension.
1552    template <class InputIterator>
1553    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last)
1554       : base_t(ordered_range, first, last)
1555    {}
1556 
1557    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1558    //! inserts elements from the ordered range [first ,last). This function
1559    //! is more efficient than the normal range creation for ordered ranges.
1560    //!
1561    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1562    //!
1563    //! <b>Complexity</b>: Linear in N.
1564    //!
1565    //! <b>Note</b>: Non-standard extension.
1566    template <class InputIterator>
1567    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp)
1568       : base_t(ordered_range, first, last, comp)
1569    {}
1570 
1571    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1572    //! allocator, and inserts elements from the ordered range [first ,last). This function
1573    //! is more efficient than the normal range creation for ordered ranges.
1574    //!
1575    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1576    //!
1577    //! <b>Complexity</b>: Linear in N.
1578    //!
1579    //! <b>Note</b>: Non-standard extension.
1580    template <class InputIterator>
1581    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp,
1582          const allocator_type& a)
1583       : base_t(ordered_range, first, last, comp, a)
1584    {}
1585 
1586    //! <b>Effects</b>: Constructs an empty multimap using the specified allocator and
1587    //! inserts elements from the ordered range [first ,last). This function
1588    //! is more efficient than the normal range creation for ordered ranges.
1589    //!
1590    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
1591    //!
1592    //! <b>Complexity</b>: Linear in N.
1593    //!
1594    //! <b>Note</b>: Non-standard extension.
1595    template <class InputIterator>
1596    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type& a)
1597       : base_t(ordered_range, first, last, Compare(), a)
1598    {}
1599 
1600 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1601    //! <b>Effects</b>: Constructs an empty multimap and
1602    //! and inserts elements from the range [il.begin(), il.end()).
1603    //!
1604    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1605    //! the predicate and otherwise N logN, where N is il.first() - il.end().
1606    BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il)
1607       : base_t(false, il.begin(), il.end())
1608    {}
1609 
1610    //! <b>Effects</b>: Constructs an empty multimap using the specified
1611    //! allocator, and inserts elements from the range [il.begin(), il.end()).
1612    //!
1613    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1614    //! the predicate and otherwise N logN, where N is il.first() - il.end().
1615    BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const allocator_type& a)
1616       : base_t(false, il.begin(), il.end(), Compare(), a)
1617    {}
1618 
1619    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1620    //! inserts elements from the range [il.begin(), il.end()).
1621    //!
1622    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1623    //! the predicate and otherwise N logN, where N is il.first() - il.end().
1624    BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp)
1625       : base_t(false, il.begin(), il.end(), comp)
1626    {}
1627 
1628    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
1629    //! allocator, and inserts elements from the range [il.begin(), il.end()).
1630    //!
1631    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
1632    //! the predicate and otherwise N logN, where N is il.first() - il.end().
1633    BOOST_CONTAINER_FORCEINLINE multimap(std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1634       : base_t(false, il.begin(), il.end(), comp, a)
1635    {}
1636 
1637 
1638    //! <b>Effects</b>: Constructs an empty map and
1639    //! inserts elements from the ordered range [il.begin(), il.end()). This function
1640    //! is more efficient than the normal range creation for ordered ranges.
1641    //!
1642    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1643    //!
1644    //! <b>Complexity</b>: Linear in N.
1645    //!
1646    //! <b>Note</b>: Non-standard extension.
1647    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il)
1648       : base_t(ordered_range, il.begin(), il.end())
1649    {}
1650 
1651    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
1652    //! inserts elements from the ordered range [il.begin(), il.end()). This function
1653    //! is more efficient than the normal range creation for ordered ranges.
1654    //!
1655    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1656    //!
1657    //! <b>Complexity</b>: Linear in N.
1658    //!
1659    //! <b>Note</b>: Non-standard extension.
1660    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp)
1661       : base_t(ordered_range, il.begin(), il.end(), comp)
1662    {}
1663 
1664    //! <b>Effects</b>: Constructs an empty map and
1665    //! inserts elements from the ordered range [il.begin(), il.end()). This function
1666    //! is more efficient than the normal range creation for ordered ranges.
1667    //!
1668    //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate.
1669    //!
1670    //! <b>Complexity</b>: Linear in N.
1671    //!
1672    //! <b>Note</b>: Non-standard extension.
1673    BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp, const allocator_type& a)
1674       : base_t(ordered_range, il.begin(), il.end(), comp, a)
1675    {}
1676 
1677 #endif
1678 
1679    //! <b>Effects</b>: Copy constructs a multimap.
1680    //!
1681    //! <b>Complexity</b>: Linear in x.size().
1682    BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x)
1683       : base_t(static_cast<const base_t&>(x))
1684    {}
1685 
1686    //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
1687    //!
1688    //! <b>Complexity</b>: Constant.
1689    //!
1690    //! <b>Postcondition</b>: x is emptied.
1691    BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x)
1692       BOOST_NOEXCEPT_IF(boost::container::dtl::is_nothrow_move_constructible<Compare>::value)
1693       : base_t(BOOST_MOVE_BASE(base_t, x))
1694    {}
1695 
1696    //! <b>Effects</b>: Copy constructs a multimap.
1697    //!
1698    //! <b>Complexity</b>: Linear in x.size().
1699    BOOST_CONTAINER_FORCEINLINE multimap(const multimap& x, const allocator_type &a)
1700       : base_t(static_cast<const base_t&>(x), a)
1701    {}
1702 
1703    //! <b>Effects</b>: Move constructs a multimap using the specified allocator.
1704    //!                 Constructs *this using x's resources.
1705    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
1706    //!
1707    //! <b>Postcondition</b>: x is emptied.
1708    BOOST_CONTAINER_FORCEINLINE multimap(BOOST_RV_REF(multimap) x, const allocator_type &a)
1709       : base_t(BOOST_MOVE_BASE(base_t, x), a)
1710    {}
1711 
1712    //! <b>Effects</b>: Makes *this a copy of x.
1713    //!
1714    //! <b>Complexity</b>: Linear in x.size().
1715    BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x)
1716    {  return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x)));  }
1717 
1718    //! <b>Effects</b>: this->swap(x.get()).
1719    //!
1720    //! <b>Complexity</b>: Constant.
1721    BOOST_CONTAINER_FORCEINLINE multimap& operator=(BOOST_RV_REF(multimap) x)
1722       BOOST_NOEXCEPT_IF( (allocator_traits_type::propagate_on_container_move_assignment::value ||
1723                           allocator_traits_type::is_always_equal::value) &&
1724                            boost::container::dtl::is_nothrow_move_assignable<Compare>::value)
1725    {  return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x)));  }
1726 
1727 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1728    //! <b>Effects</b>: Assign content of il to *this.
1729    //!
1730    BOOST_CONTAINER_FORCEINLINE multimap& operator=(std::initializer_list<value_type> il)
1731    {
1732        this->clear();
1733        insert(il.begin(), il.end());
1734        return *this;
1735    }
1736 #endif
1737 
1738    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1739 
1740    //! @copydoc ::boost::container::set::get_allocator()
1741    allocator_type get_allocator() const;
1742 
1743    //! @copydoc ::boost::container::set::get_stored_allocator()
1744    stored_allocator_type &get_stored_allocator();
1745 
1746    //! @copydoc ::boost::container::set::get_stored_allocator() const
1747    const stored_allocator_type &get_stored_allocator() const;
1748 
1749    //! @copydoc ::boost::container::set::begin()
1750    iterator begin();
1751 
1752    //! @copydoc ::boost::container::set::begin() const
1753    const_iterator begin() const;
1754 
1755    //! @copydoc ::boost::container::set::cbegin() const
1756    const_iterator cbegin() const;
1757 
1758    //! @copydoc ::boost::container::set::end()
1759    iterator end() BOOST_NOEXCEPT_OR_NOTHROW;
1760 
1761    //! @copydoc ::boost::container::set::end() const
1762    const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW;
1763 
1764    //! @copydoc ::boost::container::set::cend() const
1765    const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW;
1766 
1767    //! @copydoc ::boost::container::set::rbegin()
1768    reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW;
1769 
1770    //! @copydoc ::boost::container::set::rbegin() const
1771    const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1772 
1773    //! @copydoc ::boost::container::set::crbegin() const
1774    const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW;
1775 
1776    //! @copydoc ::boost::container::set::rend()
1777    reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW;
1778 
1779    //! @copydoc ::boost::container::set::rend() const
1780    const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW;
1781 
1782    //! @copydoc ::boost::container::set::crend() const
1783    const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW;
1784 
1785    //! @copydoc ::boost::container::set::empty() const
1786    bool empty() const;
1787 
1788    //! @copydoc ::boost::container::set::size() const
1789    size_type size() const;
1790 
1791    //! @copydoc ::boost::container::set::max_size() const
1792    size_type max_size() const;
1793 
1794    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1795 
1796    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1797 
1798    //! <b>Effects</b>: Inserts an object of type T constructed with
1799    //!   std::forward<Args>(args)... in the container.
1800    //!   p is a hint pointing to where the insert should start to search.
1801    //!
1802    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1803    //!   to the key of x.
1804    //!
1805    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1806    //!   is inserted right before p.
1807    template <class... Args>
1808    BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_FWD_REF(Args)... args)
1809    {  return this->base_t::emplace_equal(boost::forward<Args>(args)...); }
1810 
1811    //! <b>Effects</b>: Inserts an object of type T constructed with
1812    //!   std::forward<Args>(args)... in the container.
1813    //!   p is a hint pointing to where the insert should start to search.
1814    //!
1815    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1816    //!   to the key of x.
1817    //!
1818    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1819    //!   is inserted right before p.
1820    template <class... Args>
1821    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args)
1822    {  return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); }
1823 
1824    #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1825 
1826    #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \
1827    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1828    BOOST_CONTAINER_FORCEINLINE iterator emplace(BOOST_MOVE_UREF##N)\
1829    {  return this->base_t::emplace_equal(BOOST_MOVE_FWD##N);   }\
1830    \
1831    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
1832    BOOST_CONTAINER_FORCEINLINE iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
1833    {  return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N);  }\
1834    //
1835    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE)
1836    #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE
1837 
1838    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1839 
1840    //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
1841    //!   newly inserted element.
1842    //!
1843    //! <b>Complexity</b>: Logarithmic.
1844    BOOST_CONTAINER_FORCEINLINE iterator insert(const value_type& x)
1845    { return this->base_t::insert_equal_convertible(x); }
1846 
1847    //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
1848    //!   the iterator pointing to the newly inserted element.
1849    //!
1850    //! <b>Complexity</b>: Logarithmic.
1851    BOOST_CONTAINER_FORCEINLINE iterator insert(BOOST_RV_REF(value_type) x)
1852    { return this->base_t::insert_equal_convertible(boost::move(x)); }
1853 
1854    //! <b>Effects</b>: Inserts a new value constructed from x and returns
1855    //!   the iterator pointing to the newly inserted element.
1856    //!
1857    //! <b>Complexity</b>: Logarithmic.
1858    template<class Pair>
1859    BOOST_CONTAINER_FORCEINLINE BOOST_CONTAINER_DOC1ST
1860          ( iterator
1861          , typename dtl::enable_if_c<
1862             dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value  ||
1863             dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value
1864             BOOST_MOVE_I iterator >::type)
1865       insert(BOOST_FWD_REF(Pair) x)
1866    { return this->base_t::emplace_equal(boost::forward<Pair>(x)); }
1867 
1868    //! <b>Effects</b>: Inserts a copy of x in the container.
1869    //!   p is a hint pointing to where the insert should start to search.
1870    //!
1871    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1872    //!   to the key of x.
1873    //!
1874    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1875    //!   is inserted right before p.
1876    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, const value_type& x)
1877    { return this->base_t::insert_equal_hint_convertible(p, x); }
1878 
1879    //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
1880    //!   p is a hint pointing to where the insert should start to search.
1881    //!
1882    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1883    //!   to the key of x.
1884    //!
1885    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1886    //!   is inserted right before p.
1887    BOOST_CONTAINER_FORCEINLINE iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x)
1888    { return this->base_t::insert_equal_hint_convertible(p, boost::move(x)); }
1889 
1890    //! <b>Effects</b>: Inserts a new value constructed from x in the container.
1891    //!   p is a hint pointing to where the insert should start to search.
1892    //!
1893    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
1894    //!   to the key of x.
1895    //!
1896    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
1897    //!   is inserted right before p.
1898    template<class Pair>
1899    BOOST_CONTAINER_FORCEINLINE BOOST_CONTAINER_DOC1ST
1900          ( iterator
1901          , typename dtl::enable_if_c<
1902             dtl::is_convertible<Pair BOOST_MOVE_I value_type>::value  ||
1903             dtl::is_convertible<Pair BOOST_MOVE_I movable_value_type>::value
1904             BOOST_MOVE_I iterator>::type)
1905       insert(const_iterator p, BOOST_FWD_REF(Pair) x)
1906    { return this->base_t::emplace_hint_equal(p, boost::forward<Pair>(x)); }
1907 
1908    //! <b>Requires</b>: first, last are not iterators into *this.
1909    //!
1910    //! <b>Effects</b>: inserts each element from the range [first,last) .
1911    //!
1912    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
1913    template <class InputIterator>
1914    BOOST_CONTAINER_FORCEINLINE void insert(InputIterator first, InputIterator last)
1915    {  this->base_t::insert_equal_range(first, last); }
1916 
1917 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
1918    //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end().
1919    //!
1920    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end())
1921    BOOST_CONTAINER_FORCEINLINE void insert(std::initializer_list<value_type> il)
1922    {  this->base_t::insert_equal_range(il.begin(), il.end()); }
1923 #endif
1924 
1925    //! <b>Requires</b>: nh is empty or this->get_allocator() == nh.get_allocator().
1926    //!
1927    //! <b>Effects/Returns</b>: If nh is empty, has no effect and returns end(). Otherwise, inserts 
1928    //!   the element owned by nh and returns an iterator pointing to the newly inserted element.
1929    //!   If a range containing elements with keys equivalent to nh.key() exists, 
1930    //!   the element is inserted at the end of that range. nh is always emptied.
1931    //!
1932    //! <b>Complexity</b>: Logarithmic
1933    iterator insert(BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1934    {
1935       typename base_t::node_type n(boost::move(nh));
1936       return this->base_t::insert_equal_node(boost::move(n));
1937    }
1938 
1939    //! <b>Effects</b>: Same as `insert(node_type && nh)` but the element is inserted as close as possible
1940    //!   to the position just prior to "hint".
1941    //!
1942    //! <b>Complexity</b>: logarithmic in general, but amortized constant if the element is inserted
1943    //!   right before "hint".
1944    iterator insert(const_iterator hint, BOOST_RV_REF_BEG_IF_CXX11 node_type BOOST_RV_REF_END_IF_CXX11 nh)
1945    {
1946       typename base_t::node_type n(boost::move(nh));
1947       return this->base_t::insert_equal_node(hint, boost::move(n));
1948    }
1949 
1950    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1951 
1952    //! @copydoc ::boost::container::set::erase(const_iterator)
1953    iterator erase(const_iterator p);
1954 
1955    //! @copydoc ::boost::container::set::erase(const key_type&)
1956    size_type erase(const key_type& x);
1957 
1958    //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator)
1959    iterator erase(const_iterator first, const_iterator last);
1960    #endif
1961 
1962    //! @copydoc ::boost::container::map::extract(const key_type&)
1963    node_type extract(const key_type& k)
1964    {
1965       typename base_t::node_type base_nh(this->base_t::extract(k));
1966       return node_type(boost::move(base_nh));
1967    }
1968 
1969    //! @copydoc ::boost::container::map::extract(const_iterator)
1970    node_type extract(const_iterator position)
1971    {
1972       typename base_t::node_type base_nh(this->base_t::extract(position));
1973       return node_type (boost::move(base_nh));
1974    }
1975 
1976    //! <b>Requires</b>: this->get_allocator() == source.get_allocator().
1977    //!
1978    //! <b>Effects</b>: Extracts each element in source and insert it into a using
1979    //!   the comparison object of *this.
1980    //! 
1981    //! <b>Postcondition</b>: Pointers and references to the transferred elements of source refer
1982    //!   to those same elements but as members of *this. Iterators referring to the transferred
1983    //!   elements will continue to refer to their elements, but they now behave as iterators into *this,
1984    //!   not into source.
1985    //!
1986    //! <b>Throws</b>: Nothing unless the comparison object throws.
1987    //!
1988    //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
1989    template<class C2>
1990    BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
1991    {
1992       typedef dtl::tree
1993          <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
1994       this->base_t::merge_equal(static_cast<base2_t&>(source));
1995    }
1996 
1997    //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
1998    template<class C2>
1999    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG multimap<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
2000    {  return this->merge(static_cast<multimap<Key, T, C2, Allocator, Options>&>(source)); }
2001 
2002    //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
2003    template<class C2>
2004    BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
2005    {
2006       typedef dtl::tree
2007          <value_type_impl, select_1st_t, C2, Allocator, Options> base2_t;
2008       this->base_t::merge_equal(static_cast<base2_t&>(source));
2009    }
2010 
2011    //! @copydoc ::boost::container::multimap::merge(multimap<Key, T, C2, Allocator, Options>&)
2012    template<class C2>
2013    BOOST_CONTAINER_FORCEINLINE void merge(BOOST_RV_REF_BEG map<Key, T, C2, Allocator, Options> BOOST_RV_REF_END source)
2014    {  return this->merge(static_cast<map<Key, T, C2, Allocator, Options>&>(source)); }
2015 
2016    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2017    //! @copydoc ::boost::container::set::swap
2018    void swap(multiset& x)
2019       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
2020                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value );
2021 
2022    //! @copydoc ::boost::container::set::clear
2023    void clear() BOOST_NOEXCEPT_OR_NOTHROW;
2024 
2025    //! @copydoc ::boost::container::set::key_comp
2026    key_compare key_comp() const;
2027 
2028    //! @copydoc ::boost::container::set::value_comp
2029    value_compare value_comp() const;
2030 
2031    //! <b>Returns</b>: An iterator pointing to an element with the key
2032    //!   equivalent to x, or end() if such an element is not found.
2033    //!
2034    //! <b>Complexity</b>: Logarithmic.
2035    iterator find(const key_type& x);
2036 
2037    //! <b>Returns</b>: A const iterator pointing to an element with the key
2038    //!   equivalent to x, or end() if such an element is not found.
2039    //!
2040    //! <b>Complexity</b>: Logarithmic.
2041    const_iterator find(const key_type& x) const;
2042 
2043    //! <b>Requires</b>: This overload is available only if
2044    //! key_compare::is_transparent exists.
2045    //!
2046    //! <b>Returns</b>: An iterator pointing to an element with the key
2047    //!   equivalent to x, or end() if such an element is not found.
2048    //!
2049    //! <b>Complexity</b>: Logarithmic.
2050    template<typename K>
2051    iterator find(const K& x);
2052 
2053    //! <b>Requires</b>: This overload is available only if
2054    //! key_compare::is_transparent exists.
2055    //!
2056    //! <b>Returns</b>: A const_iterator pointing to an element with the key
2057    //!   equivalent to x, or end() if such an element is not found.
2058    //!
2059    //! <b>Complexity</b>: Logarithmic.
2060    template<typename K>
2061    const_iterator find(const K& x) const;
2062 
2063    //! <b>Returns</b>: The number of elements with key equivalent to x.
2064    //!
2065    //! <b>Complexity</b>: log(size())+count(k)
2066    size_type count(const key_type& x) const;
2067 
2068    //! <b>Requires</b>: This overload is available only if
2069    //! key_compare::is_transparent exists.
2070    //!
2071    //! <b>Returns</b>: The number of elements with key equivalent to x.
2072    //!
2073    //! <b>Complexity</b>: log(size())+count(k)
2074    template<typename K>
2075    size_type count(const K& x) const;
2076 
2077    //! <b>Returns</b>: Returns true if there is an element with key
2078    //!   equivalent to key in the container, otherwise false.
2079    //!
2080    //! <b>Complexity</b>: log(size()).
2081    bool contains(const key_type& x) const;
2082 
2083    //! <b>Requires</b>: This overload is available only if
2084    //! key_compare::is_transparent exists.
2085    //!
2086    //! <b>Returns</b>: Returns true if there is an element with key
2087    //!   equivalent to key in the container, otherwise false.
2088    //!
2089    //! <b>Complexity</b>: log(size()).
2090    template<typename K>
2091    bool contains(const K& x) const;
2092 
2093    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2094    //!   than x, or end() if such an element is not found.
2095    //!
2096    //! <b>Complexity</b>: Logarithmic
2097    iterator lower_bound(const key_type& x);
2098 
2099    //! <b>Returns</b>: A const iterator pointing to the first element with key not
2100    //!   less than x, or end() if such an element is not found.
2101    //!
2102    //! <b>Complexity</b>: Logarithmic
2103    const_iterator lower_bound(const key_type& x) const;
2104 
2105    //! <b>Requires</b>: This overload is available only if
2106    //! key_compare::is_transparent exists.
2107    //!
2108    //! <b>Returns</b>: An iterator pointing to the first element with key not less
2109    //!   than x, or end() if such an element is not found.
2110    //!
2111    //! <b>Complexity</b>: Logarithmic
2112    template<typename K>
2113    iterator lower_bound(const K& x);
2114 
2115    //! <b>Requires</b>: This overload is available only if
2116    //! key_compare::is_transparent exists.
2117    //!
2118    //! <b>Returns</b>: A const iterator pointing to the first element with key not
2119    //!   less than x, or end() if such an element is not found.
2120    //!
2121    //! <b>Complexity</b>: Logarithmic
2122    template<typename K>
2123    const_iterator lower_bound(const K& x) const;
2124 
2125    //! <b>Returns</b>: An iterator pointing to the first element with key greater
2126    //!   than x, or end() if such an element is not found.
2127    //!
2128    //! <b>Complexity</b>: Logarithmic
2129    iterator upper_bound(const key_type& x);
2130 
2131    //! <b>Returns</b>: A const iterator pointing to the first element with key
2132    //!   greater than x, or end() if such an element is not found.
2133    //!
2134    //! <b>Complexity</b>: Logarithmic
2135    const_iterator upper_bound(const key_type& x) const;
2136 
2137    //! <b>Requires</b>: This overload is available only if
2138    //! key_compare::is_transparent exists.
2139    //!
2140    //! <b>Returns</b>: An iterator pointing to the first element with key greater
2141    //!   than x, or end() if such an element is not found.
2142    //!
2143    //! <b>Complexity</b>: Logarithmic
2144    template<typename K>
2145    iterator upper_bound(const K& x);
2146 
2147    //! <b>Requires</b>: This overload is available only if
2148    //! key_compare::is_transparent exists.
2149    //!
2150    //! <b>Returns</b>: A const iterator pointing to the first element with key
2151    //!   greater than x, or end() if such an element is not found.
2152    //!
2153    //! <b>Complexity</b>: Logarithmic
2154    template<typename K>
2155    const_iterator upper_bound(const K& x) const;
2156 
2157    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2158    //!
2159    //! <b>Complexity</b>: Logarithmic
2160    std::pair<iterator,iterator> equal_range(const key_type& x);
2161 
2162    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2163    //!
2164    //! <b>Complexity</b>: Logarithmic
2165    std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
2166 
2167    //! <b>Requires</b>: This overload is available only if
2168    //! key_compare::is_transparent exists.
2169    //!
2170    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2171    //!
2172    //! <b>Complexity</b>: Logarithmic
2173    template<typename K>
2174    std::pair<iterator,iterator> equal_range(const K& x);
2175 
2176    //! <b>Requires</b>: This overload is available only if
2177    //! key_compare::is_transparent exists.
2178    //!
2179    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
2180    //!
2181    //! <b>Complexity</b>: Logarithmic
2182    template<typename K>
2183    std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
2184 
2185    //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
2186    //!
2187    //! <b>Complexity</b>: Linear
2188    void rebalance();
2189 
2190    //! <b>Effects</b>: Returns true if x and y are equal
2191    //!
2192    //! <b>Complexity</b>: Linear to the number of elements in the container.
2193    friend bool operator==(const multimap& x, const multimap& y);
2194 
2195    //! <b>Effects</b>: Returns true if x and y are unequal
2196    //!
2197    //! <b>Complexity</b>: Linear to the number of elements in the container.
2198    friend bool operator!=(const multimap& x, const multimap& y);
2199 
2200    //! <b>Effects</b>: Returns true if x is less than y
2201    //!
2202    //! <b>Complexity</b>: Linear to the number of elements in the container.
2203    friend bool operator<(const multimap& x, const multimap& y);
2204 
2205    //! <b>Effects</b>: Returns true if x is greater than y
2206    //!
2207    //! <b>Complexity</b>: Linear to the number of elements in the container.
2208    friend bool operator>(const multimap& x, const multimap& y);
2209 
2210    //! <b>Effects</b>: Returns true if x is equal or less than y
2211    //!
2212    //! <b>Complexity</b>: Linear to the number of elements in the container.
2213    friend bool operator<=(const multimap& x, const multimap& y);
2214 
2215    //! <b>Effects</b>: Returns true if x is equal or greater than y
2216    //!
2217    //! <b>Complexity</b>: Linear to the number of elements in the container.
2218    friend bool operator>=(const multimap& x, const multimap& y);
2219 
2220    //! <b>Effects</b>: x.swap(y)
2221    //!
2222    //! <b>Complexity</b>: Constant.
2223    friend void swap(multimap& x, multimap& y)
2224       BOOST_NOEXCEPT_IF(  allocator_traits_type::is_always_equal::value
2225                                  && boost::container::dtl::is_nothrow_swappable<Compare>::value );
2226 
2227    #endif   //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
2228 };
2229 
2230 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
2231 
2232 template <typename InputIterator>
2233 multimap(InputIterator, InputIterator) ->
2234    multimap< it_based_non_const_first_type_t<InputIterator>
2235            , it_based_second_type_t<InputIterator>>;
2236 
2237 template < typename InputIterator, typename AllocatorOrCompare>
2238 multimap(InputIterator, InputIterator, AllocatorOrCompare const&) ->
2239    multimap< it_based_non_const_first_type_t<InputIterator>
2240                 , it_based_second_type_t<InputIterator>
2241                 , typename dtl::if_c<   // Compare
2242                     dtl::is_allocator<AllocatorOrCompare>::value
2243                     , std::less<it_based_non_const_first_type_t<InputIterator>>
2244                     , AllocatorOrCompare
2245                     >::type
2246                 , typename dtl::if_c<   // Allocator
2247                     dtl::is_allocator<AllocatorOrCompare>::value
2248                     , AllocatorOrCompare
2249                     , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2250                     >::type
2251                 >;
2252 
2253 template < typename InputIterator, typename Compare, typename Allocator
2254          , typename = dtl::require_nonallocator_t<Compare>
2255          , typename = dtl::require_allocator_t<Allocator>>
2256 multimap(InputIterator, InputIterator, Compare const&, Allocator const&) ->
2257    multimap< it_based_non_const_first_type_t<InputIterator>
2258            , it_based_second_type_t<InputIterator>
2259            , Compare
2260            , Allocator>;
2261 
2262 template <typename InputIterator>
2263 multimap(ordered_range_t, InputIterator, InputIterator) ->
2264    multimap< it_based_non_const_first_type_t<InputIterator>
2265            , it_based_second_type_t<InputIterator>>;
2266 
2267 template < typename InputIterator, typename AllocatorOrCompare>
2268 multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
2269    multimap< it_based_non_const_first_type_t<InputIterator>
2270                 , it_based_second_type_t<InputIterator>
2271                 , typename dtl::if_c<   // Compare
2272                     dtl::is_allocator<AllocatorOrCompare>::value
2273                     , std::less<it_based_const_first_type_t<InputIterator>>
2274                     , AllocatorOrCompare
2275                     >::type
2276                 , typename dtl::if_c<   // Allocator
2277                     dtl::is_allocator<AllocatorOrCompare>::value
2278                     , AllocatorOrCompare
2279                     , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
2280                     >::type
2281                 >;
2282 
2283 template < typename InputIterator, typename Compare, typename Allocator
2284          , typename = dtl::require_nonallocator_t<Compare>
2285          , typename = dtl::require_allocator_t<Allocator>>
2286 multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
2287    multimap< it_based_non_const_first_type_t<InputIterator>
2288            , it_based_second_type_t<InputIterator>
2289            , Compare
2290            , Allocator>;
2291 #endif
2292 
2293 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2294 
2295 }  //namespace container {
2296 
2297 //!has_trivial_destructor_after_move<> == true_type
2298 //!specialization for optimizations
2299 template <class Key, class T, class Compare, class Allocator, class Options>
2300 struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator, Options> >
2301 {
2302    typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
2303    static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
2304 };
2305 
2306 namespace container {
2307 
2308 #endif   //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
2309 
2310 }}
2311 
2312 #include <boost/container/detail/config_end.hpp>
2313 
2314 #endif   // BOOST_CONTAINER_MAP_HPP
2315