Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: // (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
Chris@16: // Software License, Version 1.0. (See accompanying file
Chris@16: // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/container for documentation.
Chris@16: //
Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_CONTAINER_MAP_HPP
Chris@16: #define BOOST_CONTAINER_MAP_HPP
Chris@16: 
Chris@16: #if defined(_MSC_VER)
Chris@16: #  pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/container/detail/config_begin.hpp>
Chris@16: #include <boost/container/detail/workaround.hpp>
Chris@16: 
Chris@16: #include <boost/container/container_fwd.hpp>
Chris@16: #include <utility>
Chris@16: #include <functional>
Chris@16: #include <memory>
Chris@16: #include <boost/container/detail/tree.hpp>
Chris@16: #include <boost/container/detail/value_init.hpp>
Chris@16: #include <boost/type_traits/has_trivial_destructor.hpp>
Chris@16: #include <boost/container/detail/mpl.hpp>
Chris@16: #include <boost/container/detail/utilities.hpp>
Chris@16: #include <boost/container/detail/pair.hpp>
Chris@16: #include <boost/container/detail/type_traits.hpp>
Chris@16: #include <boost/container/throw_exception.hpp>
Chris@16: #include <boost/move/utility.hpp>
Chris@16: #include <boost/move/detail/move_helpers.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/container/detail/value_init.hpp>
Chris@16: #include <boost/detail/no_exceptions_support.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace container {
Chris@16: 
Chris@16: /// @cond
Chris@16: // Forward declarations of operators == and <, needed for friend declarations.
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator==(const map<Key,T,Compare,Allocator>& x,
Chris@16:                        const map<Key,T,Compare,Allocator>& y);
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<(const map<Key,T,Compare,Allocator>& x,
Chris@16:                       const map<Key,T,Compare,Allocator>& y);
Chris@16: /// @endcond
Chris@16: 
Chris@16: //! A map is a kind of associative container that supports unique keys (contains at
Chris@16: //! most one of each key value) and provides for fast retrieval of values of another
Chris@16: //! type T based on the keys. The map class supports bidirectional iterators.
Chris@16: //!
Chris@16: //! A map satisfies all of the requirements of a container and of a reversible
Chris@16: //! container and of an associative container. For a
Chris@16: //! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
Chris@16: //!
Chris@16: //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
Chris@16: //!
Chris@16: //! Allocator is the allocator to allocate the value_types
Chris@16: //! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@16: template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > >
Chris@16: #else
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: #endif
Chris@16: class map
Chris@16: {
Chris@16:    /// @cond
Chris@16:    private:
Chris@16:    BOOST_COPYABLE_AND_MOVABLE(map)
Chris@16: 
Chris@16:    typedef std::pair<const Key, T>  value_type_impl;
Chris@16:    typedef container_detail::rbtree
Chris@16:       <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t;
Chris@16:    typedef container_detail::pair <Key, T> movable_value_type_impl;
Chris@16:    typedef container_detail::tree_value_compare
Chris@16:       < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl>
Chris@16:       >  value_compare_impl;
Chris@16:    tree_t m_tree;  // red-black tree representing map
Chris@16:    /// @endcond
Chris@16: 
Chris@16:    public:
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                    types
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    typedef Key                                                                      key_type;
Chris@16:    typedef T                                                                        mapped_type;
Chris@16:    typedef std::pair<const Key, T>                                                  value_type;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::pointer          pointer;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::const_pointer    const_pointer;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::reference        reference;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::const_reference  const_reference;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::size_type        size_type;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::difference_type  difference_type;
Chris@16:    typedef Allocator                                                                allocator_type;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
Chris@16:    typedef BOOST_CONTAINER_IMPDEF(value_compare_impl)                               value_compare;
Chris@16:    typedef Compare                                                                  key_compare;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator)                        iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator)                  const_iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator)                reverse_iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator)          const_reverse_iterator;
Chris@16:    typedef std::pair<key_type, mapped_type>                                         nonconst_value_type;
Chris@16:    typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl)                          movable_value_type;
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //          construct/copy/destroy
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Default constructs an empty map.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    map()
Chris@16:       : m_tree()
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty map using the specified comparison object
Chris@16:    //! and allocator.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    explicit map(const Compare& comp,
Chris@16:                 const allocator_type& a = allocator_type())
Chris@16:       : m_tree(comp, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty map using the specified allocator.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    explicit map(const allocator_type& a)
Chris@16:       : m_tree(a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
Chris@16:    //! allocator, and inserts elements from the range [first ,last ).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
Chris@16:    //! comp and otherwise N logN, where N is last - first.
Chris@16:    template <class InputIterator>
Chris@16:    map(InputIterator first, InputIterator last, const Compare& comp = Compare(),
Chris@16:          const allocator_type& a = allocator_type())
Chris@16:       : m_tree(true, first, last, comp, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty map using the specified comparison object and
Chris@16:    //! allocator, and inserts elements from the ordered unique range [first ,last). This function
Chris@16:    //! is more efficient than the normal range creation for ordered ranges.
Chris@16:    //!
Chris@16:    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
Chris@16:    //! unique values.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in N.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    template <class InputIterator>
Chris@16:    map( ordered_unique_range_t, InputIterator first, InputIterator last
Chris@16:       , const Compare& comp = Compare(), const allocator_type& a = allocator_type())
Chris@16:       : m_tree(ordered_range, first, last, comp, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Copy constructs a map.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    map(const map& x)
Chris@16:       : m_tree(x.m_tree)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a map. Constructs *this using x's resources.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: x is emptied.
Chris@16:    map(BOOST_RV_REF(map) x)
Chris@16:       : m_tree(boost::move(x.m_tree))
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Copy constructs a map using the specified allocator.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    map(const map& x, const allocator_type &a)
Chris@16:       : m_tree(x.m_tree, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a map using the specified allocator.
Chris@16:    //!                 Constructs *this using x's resources.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant if x == x.get_allocator(), linear otherwise.
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: x is emptied.
Chris@16:    map(BOOST_RV_REF(map) x, const allocator_type &a)
Chris@16:       : m_tree(boost::move(x.m_tree), a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Makes *this a copy of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    map& operator=(BOOST_COPY_ASSIGN_REF(map) x)
Chris@16:    {  m_tree = x.m_tree;   return *this;  }
Chris@16: 
Chris@16:    //! <b>Effects</b>: this->swap(x.get()).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    map& operator=(BOOST_RV_REF(map) x)
Chris@16:    {  m_tree = boost::move(x.m_tree);   return *this;  }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a copy of the Allocator that
Chris@16:    //!   was passed to the object's constructor.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_allocator(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reference to the internal allocator.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_stored_allocator(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reference to the internal allocator.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_stored_allocator(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                iterators
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    iterator begin() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.begin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->cbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    iterator end() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.end(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator end() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->cend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->crbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->crend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.begin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.end(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rend(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                capacity
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns true if the container contains no elements.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    bool empty() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.empty(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the number of the elements contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    size_type size() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.size(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the largest possible size of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    size_type max_size() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.max_size(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //               element access
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16:    //! Effects: If there is no key equivalent to x in the map, inserts
Chris@16:    //! value_type(x, T()) into the map.
Chris@16:    //!
Chris@16:    //! Returns: Allocator reference to the mapped_type corresponding to x in *this.
Chris@16:    //!
Chris@16:    //! Complexity: Logarithmic.
Chris@16:    mapped_type& operator[](const key_type &k);
Chris@16: 
Chris@16:    //! Effects: If there is no key equivalent to x in the map, inserts
Chris@16:    //! value_type(boost::move(x), T()) into the map (the key is move-constructed)
Chris@16:    //!
Chris@16:    //! Returns: Allocator reference to the mapped_type corresponding to x in *this.
Chris@16:    //!
Chris@16:    //! Complexity: Logarithmic.
Chris@16:    mapped_type& operator[](key_type &&k);
Chris@16:    #else
Chris@16:    BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript)
Chris@16:    #endif
Chris@16: 
Chris@16:    //! Returns: Allocator reference to the element whose key is equivalent to x.
Chris@16:    //! Throws: An exception object of type out_of_range if no such element is present.
Chris@16:    //! Complexity: logarithmic.
Chris@16:    T& at(const key_type& k)
Chris@16:    {
Chris@16:       iterator i = this->find(k);
Chris@16:       if(i == this->end()){
Chris@16:          throw_out_of_range("map::at key not found");
Chris@16:       }
Chris@16:       return i->second;
Chris@16:    }
Chris@16: 
Chris@16:    //! Returns: Allocator reference to the element whose key is equivalent to x.
Chris@16:    //! Throws: An exception object of type out_of_range if no such element is present.
Chris@16:    //! Complexity: logarithmic.
Chris@16:    const T& at(const key_type& k) const
Chris@16:    {
Chris@16:       const_iterator i = this->find(k);
Chris@16:       if(i == this->end()){
Chris@16:          throw_out_of_range("map::at key not found");
Chris@16:       }
Chris@16:       return i->second;
Chris@16:    }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                modifiers
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts x if and only if there is no element in the container
Chris@16:    //!   with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    std::pair<iterator,bool> insert(const value_type& x)
Chris@16:    { return m_tree.insert_unique(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if
Chris@16:    //! there is no element in the container  with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    std::pair<iterator,bool> insert(const nonconst_value_type& x)
Chris@16:    { return m_tree.insert_unique(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
Chris@16:    //! only if there is no element in the container with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x)
Chris@16:    { return m_tree.insert_unique(boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and
Chris@16:    //! only if there is no element in the container with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x)
Chris@16:    { return m_tree.insert_unique(boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
Chris@16:    //!   no element in the container with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
Chris@16:    { return m_tree.insert_unique(boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is
Chris@16:    //!   no element in the container with key equivalent to the key of x.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, const value_type& x)
Chris@16:    { return m_tree.insert_unique(position, x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
Chris@16:    //!   no element in the container with key equivalent to the key of x.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x)
Chris@16:    { return m_tree.insert_unique(position, boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a new value from x if and only if there is
Chris@16:    //!   no element in the container with key equivalent to the key of x.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x)
Chris@16:    { return m_tree.insert_unique(position, boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a copy of x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(const_iterator position, const nonconst_value_type& x)
Chris@16:    { return m_tree.insert_unique(position, x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts an element move constructed from x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(const_iterator position, BOOST_RV_REF(value_type) x)
Chris@16:    { return m_tree.insert_unique(position, boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Requires</b>: first, last are not iterators into *this.
Chris@16:    //!
Chris@16:    //! <b>Effects</b>: inserts each element from the range [first,last) if and only
Chris@16:    //!   if there is no element with key equivalent to the key of that element.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
Chris@16:    template <class InputIterator>
Chris@16:    void insert(InputIterator first, InputIterator last)
Chris@16:    {  m_tree.insert_unique(first, last);  }
Chris@16: 
Chris@16:    #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts an object x of type T constructed with
Chris@16:    //!   std::forward<Args>(args)... in the container if and only if there is
Chris@16:    //!   no element in the container with an equivalent key.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: The bool component of the returned pair is true if and only
Chris@16:    //!   if the insertion takes place, and the iterator component of the pair
Chris@16:    //!   points to the element with key equivalent to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    template <class... Args>
Chris@16:    std::pair<iterator,bool> emplace(Args&&... args)
Chris@16:    {  return m_tree.emplace_unique(boost::forward<Args>(args)...); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts an object of type T constructed with
Chris@16:    //!   std::forward<Args>(args)... in the container if and only if there is
Chris@16:    //!   no element in the container with an equivalent key.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    template <class... Args>
Chris@16:    iterator emplace_hint(const_iterator hint, Args&&... args)
Chris@16:    {  return m_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); }
Chris@16: 
Chris@16:    #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
Chris@16: 
Chris@16:    #define BOOST_PP_LOCAL_MACRO(n)                                                                 \
Chris@16:    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
Chris@16:    std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))            \
Chris@16:    {  return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); }       \
Chris@16:                                                                                                    \
Chris@16:    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
Chris@16:    iterator emplace_hint(const_iterator hint                                                       \
Chris@16:                          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))              \
Chris@16:    {  return m_tree.emplace_hint_unique(hint                                                       \
Chris@16:                                BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));}   \
Chris@16:    //!
Chris@16:    #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
Chris@16:    #include BOOST_PP_LOCAL_ITERATE()
Chris@16: 
Chris@16:    #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases the element pointed to by position.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
Chris@16:    //!   following q prior to the element being erased. If no such element exists,
Chris@16:    //!   returns end().
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Amortized constant time
Chris@16:    iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(position); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns the number of erased elements.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size()) + count(k)
Chris@16:    size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases all the elements in the range [first, last).
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns last.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
Chris@16:    iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(first, last); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Swaps the contents of *this and x.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    void swap(map& x)
Chris@16:    { m_tree.swap(x.m_tree); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: erase(a.begin(),a.end()).
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: size() == 0.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: linear in size().
Chris@16:    void clear() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { m_tree.clear(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                observers
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the comparison object out
Chris@16:    //!   of which a was constructed.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    key_compare key_comp() const
Chris@16:    { return m_tree.key_comp(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an object of value_compare constructed out
Chris@16:    //!   of the comparison object.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    value_compare value_comp() const
Chris@16:    { return value_compare(m_tree.key_comp()); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //              map operations
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to an element with the key
Chris@16:    //!   equivalent to x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator find(const key_type& x)
Chris@16:    { return m_tree.find(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key
Chris@16:    //!   equivalent to x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    const_iterator find(const key_type& x) const
Chris@16:    { return m_tree.find(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: The number of elements with key equivalent to x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size())+count(k)
Chris@16:    size_type count(const key_type& x) const
Chris@16:    {  return static_cast<size_type>(m_tree.find(x) != m_tree.end());  }
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to the first element with key not less
Chris@16:    //!   than k, or a.end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    iterator lower_bound(const key_type& x)
Chris@16:    {  return m_tree.lower_bound(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
Chris@16:    //!   less than k, or a.end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    const_iterator lower_bound(const key_type& x) const
Chris@16:    {  return m_tree.lower_bound(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to the first element with key not less
Chris@16:    //!   than x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    iterator upper_bound(const key_type& x)
Chris@16:    {  return m_tree.upper_bound(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
Chris@16:    //!   less than x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    const_iterator upper_bound(const key_type& x) const
Chris@16:    {  return m_tree.upper_bound(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    std::pair<iterator,iterator> equal_range(const key_type& x)
Chris@16:    {  return m_tree.equal_range(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
Chris@16:    {  return m_tree.equal_range(x); }
Chris@16: 
Chris@16:    /// @cond
Chris@16:    template <class K1, class T1, class C1, class A1>
Chris@16:    friend bool operator== (const map<K1, T1, C1, A1>&,
Chris@16:                            const map<K1, T1, C1, A1>&);
Chris@16:    template <class K1, class T1, class C1, class A1>
Chris@16:    friend bool operator< (const map<K1, T1, C1, A1>&,
Chris@16:                           const map<K1, T1, C1, A1>&);
Chris@16:    private:
Chris@16:    mapped_type& priv_subscript(const key_type &k)
Chris@16:    {
Chris@16:       //we can optimize this
Chris@16:       iterator i = lower_bound(k);
Chris@16:       // i->first is greater than or equivalent to k.
Chris@16:       if (i == end() || key_comp()(k, (*i).first)){
Chris@16:          container_detail::value_init<mapped_type> m;
Chris@16:          movable_value_type val(k, boost::move(m.m_t));
Chris@16:          i = insert(i, boost::move(val));
Chris@16:       }
Chris@16:       return (*i).second;
Chris@16:    }
Chris@16: 
Chris@16:    mapped_type& priv_subscript(BOOST_RV_REF(key_type) mk)
Chris@16:    {
Chris@16:       key_type &k = mk;
Chris@16:       //we can optimize this
Chris@16:       iterator i = lower_bound(k);
Chris@16:       // i->first is greater than or equivalent to k.
Chris@16:       if (i == end() || key_comp()(k, (*i).first)){
Chris@16:          container_detail::value_init<mapped_type> m;
Chris@16:          movable_value_type val(boost::move(k), boost::move(m.m_t));
Chris@16:          i = insert(i, boost::move(val));
Chris@16:       }
Chris@16:       return (*i).second;
Chris@16:    }
Chris@16: 
Chris@16:    /// @endcond
Chris@16: };
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator==(const map<Key,T,Compare,Allocator>& x,
Chris@16:                        const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return x.m_tree == y.m_tree;  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<(const map<Key,T,Compare,Allocator>& x,
Chris@16:                       const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return x.m_tree < y.m_tree;   }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator!=(const map<Key,T,Compare,Allocator>& x,
Chris@16:                        const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return !(x == y); }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator>(const map<Key,T,Compare,Allocator>& x,
Chris@16:                       const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return y < x;  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<=(const map<Key,T,Compare,Allocator>& x,
Chris@16:                        const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return !(y < x);  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator>=(const map<Key,T,Compare,Allocator>& x,
Chris@16:                        const map<Key,T,Compare,Allocator>& y)
Chris@16:    {  return !(x < y);  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline void swap(map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y)
Chris@16:    {  x.swap(y);  }
Chris@16: 
Chris@16: /// @cond
Chris@16: 
Chris@16: // Forward declaration of operators < and ==, needed for friend declaration.
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator==(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                        const multimap<Key,T,Compare,Allocator>& y);
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                       const multimap<Key,T,Compare,Allocator>& y);
Chris@16: 
Chris@16: }  //namespace container {
Chris@16: 
Chris@16: //!has_trivial_destructor_after_move<> == true_type
Chris@16: //!specialization for optimizations
Chris@16: template <class K, class T, class C, class Allocator>
Chris@16: struct has_trivial_destructor_after_move<boost::container::map<K, T, C, Allocator> >
Chris@16: {
Chris@16:    static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
Chris@16: };
Chris@16: 
Chris@16: namespace container {
Chris@16: 
Chris@16: /// @endcond
Chris@16: 
Chris@16: //! A multimap is a kind of associative container that supports equivalent keys
Chris@16: //! (possibly containing multiple copies of the same key value) and provides for
Chris@16: //! fast retrieval of values of another type T based on the keys. The multimap class
Chris@16: //! supports bidirectional iterators.
Chris@16: //!
Chris@16: //! A multimap satisfies all of the requirements of a container and of a reversible
Chris@16: //! container and of an associative container. For a
Chris@16: //! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>.
Chris@16: //!
Chris@16: //! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>).
Chris@16: //!
Chris@16: //! Allocator is the allocator to allocate the value_types
Chris@16: //!(e.g. <i>allocator< std::pair<<b>const</b> Key, T> ></i>).
Chris@16: #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
Chris@16: template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > >
Chris@16: #else
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: #endif
Chris@16: class multimap
Chris@16: {
Chris@16:    /// @cond
Chris@16:    private:
Chris@16:    BOOST_COPYABLE_AND_MOVABLE(multimap)
Chris@16: 
Chris@16:    typedef std::pair<const Key, T>  value_type_impl;
Chris@16:    typedef container_detail::rbtree
Chris@16:       <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t;
Chris@16:    typedef container_detail::pair <Key, T> movable_value_type_impl;
Chris@16:    typedef container_detail::tree_value_compare
Chris@16:       < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl>
Chris@16:       >  value_compare_impl;
Chris@16:    tree_t m_tree;  // red-black tree representing map
Chris@16:    /// @endcond
Chris@16: 
Chris@16:    public:
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                    types
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    typedef Key                                                                      key_type;
Chris@16:    typedef T                                                                        mapped_type;
Chris@16:    typedef std::pair<const Key, T>                                                  value_type;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::pointer          pointer;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::const_pointer    const_pointer;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::reference        reference;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::const_reference  const_reference;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::size_type        size_type;
Chris@16:    typedef typename boost::container::allocator_traits<Allocator>::difference_type  difference_type;
Chris@16:    typedef Allocator                                                                allocator_type;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type)           stored_allocator_type;
Chris@16:    typedef BOOST_CONTAINER_IMPDEF(value_compare_impl)                               value_compare;
Chris@16:    typedef Compare                                                                  key_compare;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator)                        iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator)                  const_iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator)                reverse_iterator;
Chris@16:    typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator)          const_reverse_iterator;
Chris@16:    typedef std::pair<key_type, mapped_type>                                         nonconst_value_type;
Chris@16:    typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl)                          movable_value_type;
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //          construct/copy/destroy
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Default constructs an empty multimap.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    multimap()
Chris@16:       : m_tree()
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty multimap using the specified allocator.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    explicit multimap(const Compare& comp, const allocator_type& a = allocator_type())
Chris@16:       : m_tree(comp, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison
Chris@16:    //!   object and allocator.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    explicit multimap(const allocator_type& a)
Chris@16:       : m_tree(a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object
Chris@16:    //!   and allocator, and inserts elements from the range [first ,last ).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using
Chris@16:    //! comp and otherwise N logN, where N is last - first.
Chris@16:    template <class InputIterator>
Chris@16:    multimap(InputIterator first, InputIterator last,
Chris@16:             const Compare& comp = Compare(),
Chris@16:             const allocator_type& a = allocator_type())
Chris@16:       : m_tree(false, first, last, comp, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and
Chris@16:    //! allocator, and inserts elements from the ordered range [first ,last). This function
Chris@16:    //! is more efficient than the normal range creation for ordered ranges.
Chris@16:    //!
Chris@16:    //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in N.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    template <class InputIterator>
Chris@16:    multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(),
Chris@16:          const allocator_type& a = allocator_type())
Chris@16:       : m_tree(ordered_range, first, last, comp, a)
Chris@16:    {}
Chris@16: 
Chris@16:    //! <b>Effects</b>: Copy constructs a multimap.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    multimap(const multimap& x)
Chris@16:       : m_tree(x.m_tree)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a multimap. Constructs *this using x's resources.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: x is emptied.
Chris@16:    multimap(BOOST_RV_REF(multimap) x)
Chris@16:       : m_tree(boost::move(x.m_tree))
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Copy constructs a multimap.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    multimap(const multimap& x, const allocator_type &a)
Chris@16:       : m_tree(x.m_tree, a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Move constructs a multimap using the specified allocator.
Chris@16:    //!                 Constructs *this using x's resources.
Chris@16:    //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise.
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: x is emptied.
Chris@16:    multimap(BOOST_RV_REF(multimap) x, const allocator_type &a)
Chris@16:       : m_tree(boost::move(x.m_tree), a)
Chris@16:    {
Chris@16:       //Allocator type must be std::pair<CONST Key, T>
Chris@16:       BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value));
Chris@16:    }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Makes *this a copy of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Linear in x.size().
Chris@16:    multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x)
Chris@16:    {  m_tree = x.m_tree;   return *this;  }
Chris@16: 
Chris@16:    //! <b>Effects</b>: this->swap(x.get()).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    multimap& operator=(BOOST_RV_REF(multimap) x)
Chris@16:    {  m_tree = boost::move(x.m_tree);   return *this;  }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a copy of the Allocator that
Chris@16:    //!   was passed to the object's constructor.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_allocator(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reference to the internal allocator.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_stored_allocator(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reference to the internal allocator.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    //!
Chris@16:    //! <b>Note</b>: Non-standard extension.
Chris@16:    const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.get_stored_allocator(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                iterators
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    iterator begin() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.begin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->cbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    iterator end() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.end(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator end() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->cend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->crbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return this->crend(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.begin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.end(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rbegin(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
Chris@16:    //! of the reversed container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.rend(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                capacity
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns true if the container contains no elements.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    bool empty() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.empty(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the number of the elements contained in the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    size_type size() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.size(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the largest possible size of the container.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    size_type max_size() const BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.max_size(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                modifiers
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts an object of type T constructed with
Chris@16:    //!   std::forward<Args>(args)... in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    template <class... Args>
Chris@16:    iterator emplace(Args&&... args)
Chris@16:    {  return m_tree.emplace_equal(boost::forward<Args>(args)...); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts an object of type T constructed with
Chris@16:    //!   std::forward<Args>(args)... in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    template <class... Args>
Chris@16:    iterator emplace_hint(const_iterator hint, Args&&... args)
Chris@16:    {  return m_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); }
Chris@16: 
Chris@16:    #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
Chris@16: 
Chris@16:    #define BOOST_PP_LOCAL_MACRO(n)                                                                 \
Chris@16:    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
Chris@16:    iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _))                            \
Chris@16:    {  return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); }        \
Chris@16:                                                                                                    \
Chris@16:    BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >)          \
Chris@16:    iterator emplace_hint(const_iterator hint                                                       \
Chris@16:                          BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _))              \
Chris@16:    {  return m_tree.emplace_hint_equal(hint                                                        \
Chris@16:                                BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));}   \
Chris@16:    //!
Chris@16:    #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
Chris@16:    #include BOOST_PP_LOCAL_ITERATE()
Chris@16: 
Chris@16:    #endif   //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts x and returns the iterator pointing to the
Chris@16:    //!   newly inserted element.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(const value_type& x)
Chris@16:    { return m_tree.insert_equal(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value constructed from x and returns
Chris@16:    //!   the iterator pointing to the newly inserted element.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(const nonconst_value_type& x)
Chris@16:    { return m_tree.insert_equal(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
Chris@16:    //!   the iterator pointing to the newly inserted element.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(BOOST_RV_REF(nonconst_value_type) x)
Chris@16:    { return m_tree.insert_equal(boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value move-constructed from x and returns
Chris@16:    //!   the iterator pointing to the newly inserted element.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator insert(BOOST_RV_REF(movable_value_type) x)
Chris@16:    { return m_tree.insert_equal(boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a copy of x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, const value_type& x)
Chris@16:    { return m_tree.insert_equal(position, x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value constructed from x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, const nonconst_value_type& x)
Chris@16:    { return m_tree.insert_equal(position, x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x)
Chris@16:    { return m_tree.insert_equal(position, boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Inserts a new value move constructed from x in the container.
Chris@16:    //!   p is a hint pointing to where the insert should start to search.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: An iterator pointing to the element with key equivalent
Chris@16:    //!   to the key of x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t
Chris@16:    //!   is inserted right before p.
Chris@16:    iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x)
Chris@16:    { return m_tree.insert_equal(position, boost::move(x)); }
Chris@16: 
Chris@16:    //! <b>Requires</b>: first, last are not iterators into *this.
Chris@16:    //!
Chris@16:    //! <b>Effects</b>: inserts each element from the range [first,last) .
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last)
Chris@16:    template <class InputIterator>
Chris@16:    void insert(InputIterator first, InputIterator last)
Chris@16:    {  m_tree.insert_equal(first, last); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases the element pointed to by position.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns an iterator pointing to the element immediately
Chris@16:    //!   following q prior to the element being erased. If no such element exists,
Chris@16:    //!   returns end().
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Amortized constant time
Chris@16:    iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(position); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases all elements in the container with key equivalent to x.
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns the number of erased elements.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size()) + count(k)
Chris@16:    size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Erases all the elements in the range [first, last).
Chris@16:    //!
Chris@16:    //! <b>Returns</b>: Returns last.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size())+N where N is the distance from first to last.
Chris@16:    iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
Chris@16:    { return m_tree.erase(first, last); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Swaps the contents of *this and x.
Chris@16:    //!
Chris@16:    //! <b>Throws</b>: Nothing.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    void swap(multimap& x)
Chris@16:    { m_tree.swap(x.m_tree); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: erase(a.begin(),a.end()).
Chris@16:    //!
Chris@16:    //! <b>Postcondition</b>: size() == 0.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: linear in size().
Chris@16:    void clear() BOOST_CONTAINER_NOEXCEPT
Chris@16:    { m_tree.clear(); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //                observers
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns the comparison object out
Chris@16:    //!   of which a was constructed.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    key_compare key_comp() const
Chris@16:    { return m_tree.key_comp(); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Returns an object of value_compare constructed out
Chris@16:    //!   of the comparison object.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Constant.
Chris@16:    value_compare value_comp() const
Chris@16:    { return value_compare(m_tree.key_comp()); }
Chris@16: 
Chris@16:    //////////////////////////////////////////////
Chris@16:    //
Chris@16:    //              map operations
Chris@16:    //
Chris@16:    //////////////////////////////////////////////
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to an element with the key
Chris@16:    //!   equivalent to x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    iterator find(const key_type& x)
Chris@16:    { return m_tree.find(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const iterator pointing to an element with the key
Chris@16:    //!   equivalent to x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic.
Chris@16:    const_iterator find(const key_type& x) const
Chris@16:    { return m_tree.find(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: The number of elements with key equivalent to x.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: log(size())+count(k)
Chris@16:    size_type count(const key_type& x) const
Chris@16:    { return m_tree.count(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to the first element with key not less
Chris@16:    //!   than k, or a.end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    iterator lower_bound(const key_type& x)
Chris@16:    {return m_tree.lower_bound(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
Chris@16:    //!   less than k, or a.end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    const_iterator lower_bound(const key_type& x) const
Chris@16:    {  return m_tree.lower_bound(x);  }
Chris@16: 
Chris@16:    //! <b>Returns</b>: An iterator pointing to the first element with key not less
Chris@16:    //!   than x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    iterator upper_bound(const key_type& x)
Chris@16:    {  return m_tree.upper_bound(x); }
Chris@16: 
Chris@16:    //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not
Chris@16:    //!   less than x, or end() if such an element is not found.
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    const_iterator upper_bound(const key_type& x) const
Chris@16:    {  return m_tree.upper_bound(x); }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    std::pair<iterator,iterator> equal_range(const key_type& x)
Chris@16:    {  return m_tree.equal_range(x);   }
Chris@16: 
Chris@16:    //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Chris@16:    //!
Chris@16:    //! <b>Complexity</b>: Logarithmic
Chris@16:    std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const
Chris@16:    {  return m_tree.equal_range(x);   }
Chris@16: 
Chris@16:    /// @cond
Chris@16:    template <class K1, class T1, class C1, class A1>
Chris@16:    friend bool operator== (const multimap<K1, T1, C1, A1>& x,
Chris@16:                            const multimap<K1, T1, C1, A1>& y);
Chris@16: 
Chris@16:    template <class K1, class T1, class C1, class A1>
Chris@16:    friend bool operator< (const multimap<K1, T1, C1, A1>& x,
Chris@16:                           const multimap<K1, T1, C1, A1>& y);
Chris@16:    /// @endcond
Chris@16: };
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator==(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                        const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return x.m_tree == y.m_tree;  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                       const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return x.m_tree < y.m_tree;   }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                        const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return !(x == y);  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator>(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                       const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return y < x;  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                        const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return !(y < x);  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
Chris@16:                        const multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  return !(x < y);  }
Chris@16: 
Chris@16: template <class Key, class T, class Compare, class Allocator>
Chris@16: inline void swap(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y)
Chris@16: {  x.swap(y);  }
Chris@16: 
Chris@16: /// @cond
Chris@16: 
Chris@16: }  //namespace container {
Chris@16: 
Chris@16: //!has_trivial_destructor_after_move<> == true_type
Chris@16: //!specialization for optimizations
Chris@16: template <class K, class T, class C, class Allocator>
Chris@16: struct has_trivial_destructor_after_move<boost::container::multimap<K, T, C, Allocator> >
Chris@16: {
Chris@16:    static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value;
Chris@16: };
Chris@16: 
Chris@16: namespace container {
Chris@16: 
Chris@16: /// @endcond
Chris@16: 
Chris@16: }}
Chris@16: 
Chris@16: #include <boost/container/detail/config_end.hpp>
Chris@16: 
Chris@16: #endif /* BOOST_CONTAINER_MAP_HPP */
Chris@16: