Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-01 08:10:24

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