Mercurial > hg > vamp-build-and-test
diff DEPENDENCIES/generic/include/boost/container/map.hpp @ 101:c530137014c0
Update Boost headers (1.58.0)
| author | Chris Cannam |
|---|---|
| date | Mon, 07 Sep 2015 11:12:49 +0100 |
| parents | 2665513ce2d3 |
| children |
line wrap: on
line diff
--- a/DEPENDENCIES/generic/include/boost/container/map.hpp Fri Sep 04 12:01:02 2015 +0100 +++ b/DEPENDENCIES/generic/include/boost/container/map.hpp Mon Sep 07 11:12:49 2015 +0100 @@ -1,87 +1,99 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // // See http://www.boost.org/libs/container for documentation. // ////////////////////////////////////////////////////////////////////////////// - #ifndef BOOST_CONTAINER_MAP_HPP #define BOOST_CONTAINER_MAP_HPP -#if defined(_MSC_VER) +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) # pragma once #endif #include <boost/container/detail/config_begin.hpp> #include <boost/container/detail/workaround.hpp> +// container #include <boost/container/container_fwd.hpp> -#include <utility> -#include <functional> -#include <memory> +#include <boost/container/new_allocator.hpp> //new_allocator +#include <boost/container/throw_exception.hpp> +// container/detail +#include <boost/container/detail/mpl.hpp> #include <boost/container/detail/tree.hpp> +#include <boost/container/detail/type_traits.hpp> #include <boost/container/detail/value_init.hpp> -#include <boost/type_traits/has_trivial_destructor.hpp> -#include <boost/container/detail/mpl.hpp> -#include <boost/container/detail/utilities.hpp> #include <boost/container/detail/pair.hpp> -#include <boost/container/detail/type_traits.hpp> -#include <boost/container/throw_exception.hpp> -#include <boost/move/utility.hpp> +// move +#include <boost/move/traits.hpp> +#include <boost/move/utility_core.hpp> +// move/detail +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> +#endif #include <boost/move/detail/move_helpers.hpp> +// intrusive/detail +#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal +// other #include <boost/static_assert.hpp> -#include <boost/container/detail/value_init.hpp> -#include <boost/detail/no_exceptions_support.hpp> +#include <boost/core/no_exceptions_support.hpp> +// std +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include <initializer_list> +#endif namespace boost { namespace container { -/// @cond -// Forward declarations of operators == and <, needed for friend declarations. -template <class Key, class T, class Compare, class Allocator> -inline bool operator==(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -inline bool operator<(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y); -/// @endcond +#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED //! A map is a kind of associative container that supports unique keys (contains at //! most one of each key value) and provides for fast retrieval of values of another //! type T based on the keys. The map class supports bidirectional iterators. //! //! A map satisfies all of the requirements of a container and of a reversible -//! container and of an associative container. For a -//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>. +//! container and of an associative container. The <code>value_type</code> stored +//! by this container is the value_type is std::pair<const Key, T>. //! -//! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). -//! -//! Allocator is the allocator to allocate the value_types -//! (e.g. <i>allocator< std::pair<const Key, T> > </i>). -#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED -template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > > +//! \tparam Key is the key_type of the map +//! \tparam T is the <code>mapped_type</code> +//! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). +//! \tparam Allocator is the allocator to allocate the <code>value_type</code>s +//! (e.g. <i>allocator< std::pair<const Key, T> > </i>). +//! \tparam MapOptions is an packed option type generated using using boost::container::tree_assoc_options. +template < class Key, class T, class Compare = std::less<Key> + , class Allocator = new_allocator< std::pair< const Key, T> >, class MapOptions = tree_assoc_defaults > #else -template <class Key, class T, class Compare, class Allocator> +template <class Key, class T, class Compare, class Allocator, class MapOptions> #endif class map + ///@cond + : public container_detail::tree + < Key, std::pair<const Key, T> + , container_detail::select1st< std::pair<const Key, T> > + , Compare, Allocator, MapOptions> + ///@endcond { - /// @cond + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: BOOST_COPYABLE_AND_MOVABLE(map) typedef std::pair<const Key, T> value_type_impl; - typedef container_detail::rbtree - <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t; + typedef container_detail::tree + <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator, MapOptions> base_t; typedef container_detail::pair <Key, T> movable_value_type_impl; typedef container_detail::tree_value_compare < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl> > value_compare_impl; - tree_t m_tree; // red-black tree representing map - /// @endcond + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED public: ////////////////////////////////////////////// @@ -90,9 +102,10 @@ // ////////////////////////////////////////////// - typedef Key key_type; - typedef T mapped_type; - typedef std::pair<const Key, T> value_type; + typedef Key key_type; + typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; + typedef T mapped_type; + typedef std::pair<const Key, T> value_type; typedef typename boost::container::allocator_traits<Allocator>::pointer pointer; typedef typename boost::container::allocator_traits<Allocator>::const_pointer const_pointer; typedef typename boost::container::allocator_traits<Allocator>::reference reference; @@ -100,13 +113,13 @@ typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; typedef Allocator allocator_type; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; typedef Compare key_compare; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; typedef std::pair<key_type, mapped_type> nonconst_value_type; typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; @@ -120,9 +133,9 @@ //! //! <b>Complexity</b>: Constant. map() - : m_tree() + : base_t() { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -130,11 +143,10 @@ //! and allocator. //! //! <b>Complexity</b>: Constant. - explicit map(const Compare& comp, - const allocator_type& a = allocator_type()) - : m_tree(comp, a) + explicit map(const Compare& comp, const allocator_type& a = allocator_type()) + : base_t(comp, a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -142,9 +154,9 @@ //! //! <b>Complexity</b>: Constant. explicit map(const allocator_type& a) - : m_tree(a) + : base_t(a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -156,9 +168,22 @@ template <class InputIterator> map(InputIterator first, InputIterator last, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) - : m_tree(true, first, last, comp, a) + : base_t(true, first, last, comp, a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty map using the specified + //! allocator, and inserts elements from the range [first ,last ). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is last - first. + template <class InputIterator> + map(InputIterator first, InputIterator last, const allocator_type& a) + : base_t(true, first, last, Compare(), a) + { + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -175,19 +200,63 @@ template <class InputIterator> map( ordered_unique_range_t, InputIterator first, InputIterator last , const Compare& comp = Compare(), const allocator_type& a = allocator_type()) - : m_tree(ordered_range, first, last, comp, a) + : base_t(ordered_range, first, last, comp, a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Constructs an empty map using the specified comparison object and + //! allocator, and inserts elements from the range [il.begin(), il.end()). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is il.first() - il.end(). + map(std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) + : base_t(true, il.begin(), il.end(), comp, a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty map using the specified + //! allocator, and inserts elements from the range [il.begin(), il.end()). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is il.first() - il.end(). + map(std::initializer_list<value_type> il, const allocator_type& a) + : base_t(true, il.begin(), il.end(), Compare(), a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty set using the specified comparison object and + //! allocator, and inserts elements from the ordered unique range [il.begin(), il.end()). This function + //! is more efficient than the normal range creation for ordered ranges. + //! + //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate and must be + //! unique values. + //! + //! <b>Complexity</b>: Linear in N. + //! + //! <b>Note</b>: Non-standard extension. + map(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), + const allocator_type& a = allocator_type()) + : base_t(ordered_range, il.begin(), il.end(), comp, a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } +#endif + //! <b>Effects</b>: Copy constructs a map. //! //! <b>Complexity</b>: Linear in x.size(). map(const map& x) - : m_tree(x.m_tree) + : base_t(static_cast<const base_t&>(x)) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -197,9 +266,9 @@ //! //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF(map) x) - : m_tree(boost::move(x.m_tree)) + : base_t(BOOST_MOVE_BASE(base_t, x)) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -207,9 +276,9 @@ //! //! <b>Complexity</b>: Linear in x.size(). map(const map& x, const allocator_type &a) - : m_tree(x.m_tree, a) + : base_t(static_cast<const base_t&>(x), a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -220,9 +289,9 @@ //! //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF(map) x, const allocator_type &a) - : m_tree(boost::move(x.m_tree), a) + : base_t(BOOST_MOVE_BASE(base_t, x), a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -230,20 +299,40 @@ //! //! <b>Complexity</b>: Linear in x.size(). map& operator=(BOOST_COPY_ASSIGN_REF(map) x) - { m_tree = x.m_tree; return *this; } + { return static_cast<map&>(this->base_t::operator=(static_cast<const base_t&>(x))); } //! <b>Effects</b>: this->swap(x.get()). //! - //! <b>Complexity</b>: Constant. + //! <b>Throws</b>: If allocator_traits_type::propagate_on_container_move_assignment + //! is false and (allocation throws or value_type's move constructor throws) + //! + //! <b>Complexity</b>: Constant if allocator_traits_type:: + //! propagate_on_container_move_assignment is true or + //! this->get>allocator() == x.get_allocator(). Linear otherwise. map& operator=(BOOST_RV_REF(map) x) - { m_tree = boost::move(x.m_tree); return *this; } + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) - //! <b>Effects</b>: Returns a copy of the Allocator that + { return static_cast<map&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } + +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Assign content of il to *this. + //! + map& operator=(std::initializer_list<value_type> il) + { + this->clear(); + insert(il.begin(), il.end()); + return *this; + } +#endif + + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Returns a copy of the allocator that //! was passed to the object's constructor. //! //! <b>Complexity</b>: Constant. - allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_allocator(); } + allocator_type get_allocator() const; //! <b>Effects</b>: Returns a reference to the internal allocator. //! @@ -252,8 +341,7 @@ //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Non-standard extension. - stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_stored_allocator(); } + stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reference to the internal allocator. //! @@ -262,46 +350,49 @@ //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Non-standard extension. - const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_stored_allocator(); } - - ////////////////////////////////////////////// - // - // iterators - // - ////////////////////////////////////////////// + const stored_allocator_type &get_stored_allocator() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns an iterator to the first element contained in the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - iterator begin() BOOST_CONTAINER_NOEXCEPT - { return m_tree.begin(); } + iterator begin() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator begin() const BOOST_CONTAINER_NOEXCEPT - { return this->cbegin(); } + const_iterator begin() const BOOST_NOEXCEPT_OR_NOTHROW; + + //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cbegin() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns an iterator to the end of the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - iterator end() BOOST_CONTAINER_NOEXCEPT - { return m_tree.end(); } + iterator end() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_iterator to the end of the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_iterator end() const BOOST_CONTAINER_NOEXCEPT - { return this->cend(); } + const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; + + //! <b>Effects</b>: Returns a const_iterator to the end of the container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning //! of the reversed container. @@ -309,8 +400,7 @@ //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT - { return m_tree.rbegin(); } + reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning //! of the reversed container. @@ -318,8 +408,15 @@ //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT - { return this->crbegin(); } + const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; + + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reverse_iterator pointing to the end //! of the reversed container. @@ -327,8 +424,7 @@ //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT - { return m_tree.rend(); } + reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end //! of the reversed container. @@ -336,33 +432,7 @@ //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT - { return this->crend(); } - - //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.begin(); } - - //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator cend() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.end(); } - - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.rbegin(); } + const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end //! of the reversed container. @@ -370,50 +440,36 @@ //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.rend(); } - - ////////////////////////////////////////////// - // - // capacity - // - ////////////////////////////////////////////// + const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns true if the container contains no elements. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - bool empty() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.empty(); } + bool empty() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns the number of the elements contained in the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - size_type size() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.size(); } + size_type size() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns the largest possible size of the container. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - size_type max_size() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.max_size(); } + size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW; - ////////////////////////////////////////////// - // - // element access - // - ////////////////////////////////////////////// + #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! Effects: If there is no key equivalent to x in the map, inserts //! value_type(x, T()) into the map. //! - //! Returns: Allocator reference to the mapped_type corresponding to x in *this. + //! Returns: A reference to the mapped_type corresponding to x in *this. //! //! Complexity: Logarithmic. mapped_type& operator[](const key_type &k); @@ -421,7 +477,7 @@ //! Effects: If there is no key equivalent to x in the map, inserts //! value_type(boost::move(x), T()) into the map (the key is move-constructed) //! - //! Returns: Allocator reference to the mapped_type corresponding to x in *this. + //! Returns: A reference to the mapped_type corresponding to x in *this. //! //! Complexity: Logarithmic. mapped_type& operator[](key_type &&k); @@ -429,7 +485,7 @@ BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) #endif - //! Returns: Allocator reference to the element whose key is equivalent to x. + //! Returns: A reference to the element whose key is equivalent to x. //! Throws: An exception object of type out_of_range if no such element is present. //! Complexity: logarithmic. T& at(const key_type& k) @@ -441,7 +497,7 @@ return i->second; } - //! Returns: Allocator reference to the element whose key is equivalent to x. + //! Returns: A reference to the element whose key is equivalent to x. //! Throws: An exception object of type out_of_range if no such element is present. //! Complexity: logarithmic. const T& at(const key_type& k) const @@ -468,7 +524,7 @@ //! //! <b>Complexity</b>: Logarithmic. std::pair<iterator,bool> insert(const value_type& x) - { return m_tree.insert_unique(x); } + { return this->base_t::insert_unique(x); } //! <b>Effects</b>: Inserts a new value_type created from the pair if and only if //! there is no element in the container with key equivalent to the key of x. @@ -479,7 +535,7 @@ //! //! <b>Complexity</b>: Logarithmic. std::pair<iterator,bool> insert(const nonconst_value_type& x) - { return m_tree.insert_unique(x); } + { return this->base_t::insert_unique(x); } //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and //! only if there is no element in the container with key equivalent to the key of x. @@ -490,7 +546,7 @@ //! //! <b>Complexity</b>: Logarithmic. std::pair<iterator,bool> insert(BOOST_RV_REF(nonconst_value_type) x) - { return m_tree.insert_unique(boost::move(x)); } + { return this->base_t::insert_unique(boost::move(x)); } //! <b>Effects</b>: Inserts a new value_type move constructed from the pair if and //! only if there is no element in the container with key equivalent to the key of x. @@ -501,7 +557,7 @@ //! //! <b>Complexity</b>: Logarithmic. std::pair<iterator,bool> insert(BOOST_RV_REF(movable_value_type) x) - { return m_tree.insert_unique(boost::move(x)); } + { return this->base_t::insert_unique(boost::move(x)); } //! <b>Effects</b>: Move constructs a new value from x if and only if there is //! no element in the container with key equivalent to the key of x. @@ -512,7 +568,7 @@ //! //! <b>Complexity</b>: Logarithmic. std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) - { return m_tree.insert_unique(boost::move(x)); } + { return this->base_t::insert_unique(boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container if and only if there is //! no element in the container with key equivalent to the key of x. @@ -523,8 +579,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, const value_type& x) - { return m_tree.insert_unique(position, x); } + iterator insert(const_iterator p, const value_type& x) + { return this->base_t::insert_unique(p, x); } //! <b>Effects</b>: Move constructs a new value from x if and only if there is //! no element in the container with key equivalent to the key of x. @@ -535,8 +591,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x) - { return m_tree.insert_unique(position, boost::move(x)); } + iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) + { return this->base_t::insert_unique(p, boost::move(x)); } //! <b>Effects</b>: Move constructs a new value from x if and only if there is //! no element in the container with key equivalent to the key of x. @@ -547,8 +603,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x) - { return m_tree.insert_unique(position, boost::move(x)); } + iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) + { return this->base_t::insert_unique(p, boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container. //! p is a hint pointing to where the insert should start to search. @@ -556,8 +612,8 @@ //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(const_iterator position, const nonconst_value_type& x) - { return m_tree.insert_unique(position, x); } + iterator insert(const_iterator p, const nonconst_value_type& x) + { return this->base_t::insert_unique(p, x); } //! <b>Effects</b>: Inserts an element move constructed from x in the container. //! p is a hint pointing to where the insert should start to search. @@ -565,8 +621,8 @@ //! <b>Returns</b>: An iterator pointing to the element with key equivalent to the key of x. //! //! <b>Complexity</b>: Logarithmic. - iterator insert(const_iterator position, BOOST_RV_REF(value_type) x) - { return m_tree.insert_unique(position, boost::move(x)); } + iterator insert(const_iterator p, BOOST_RV_REF(value_type) x) + { return this->base_t::insert_unique(p, boost::move(x)); } //! <b>Requires</b>: first, last are not iterators into *this. //! @@ -576,9 +632,18 @@ //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) template <class InputIterator> void insert(InputIterator first, InputIterator last) - { m_tree.insert_unique(first, last); } + { this->base_t::insert_unique(first, last); } - #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end()) if and only + //! if there is no element with key equivalent to the key of that element. + //! + //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) + void insert(std::initializer_list<value_type> il) + { this->base_t::insert_unique(il.begin(), il.end()); } +#endif + + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object x of type T constructed with //! std::forward<Args>(args)... in the container if and only if there is @@ -592,8 +657,8 @@ //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - std::pair<iterator,bool> emplace(Args&&... args) - { return m_tree.emplace_unique(boost::forward<Args>(args)...); } + std::pair<iterator,bool> emplace(BOOST_FWD_REF(Args)... args) + { return this->base_t::emplace_unique(boost::forward<Args>(args)...); } //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... in the container if and only if there is @@ -606,52 +671,49 @@ //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace_hint(const_iterator hint, Args&&... args) - { return m_tree.emplace_hint_unique(hint, boost::forward<Args>(args)...); } + iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) + { return this->base_t::emplace_hint_unique(p, boost::forward<Args>(args)...); } - #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - std::pair<iterator,bool> emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return m_tree.emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return m_tree.emplace_hint_unique(hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \ - //! - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() + #define BOOST_CONTAINER_MAP_EMPLACE_CODE(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + std::pair<iterator,bool> emplace(BOOST_MOVE_UREF##N)\ + { return this->base_t::emplace_unique(BOOST_MOVE_FWD##N); }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + { return this->base_t::emplace_hint_unique(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MAP_EMPLACE_CODE) + #undef BOOST_CONTAINER_MAP_EMPLACE_CODE - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - //! <b>Effects</b>: Erases the element pointed to by position. + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Erases the element pointed to by p. //! //! <b>Returns</b>: Returns an iterator pointing to the element immediately //! following q prior to the element being erased. If no such element exists, //! returns end(). //! //! <b>Complexity</b>: Amortized constant time - iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(position); } + iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. //! //! <b>Returns</b>: Returns the number of erased elements. //! //! <b>Complexity</b>: log(size()) + count(k) - size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(x); } + size_type erase(const key_type& x) BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Erases all the elements in the range [first, last). //! //! <b>Returns</b>: Returns last. //! //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. - iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(first, last); } + iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Swaps the contents of *this and x. //! @@ -659,116 +721,134 @@ //! //! <b>Complexity</b>: Constant. void swap(map& x) - { m_tree.swap(x.m_tree); } + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_swappable<Compare>::value ) //! <b>Effects</b>: erase(a.begin(),a.end()). //! //! <b>Postcondition</b>: size() == 0. //! //! <b>Complexity</b>: linear in size(). - void clear() BOOST_CONTAINER_NOEXCEPT - { m_tree.clear(); } - - ////////////////////////////////////////////// - // - // observers - // - ////////////////////////////////////////////// + void clear() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns the comparison object out //! of which a was constructed. //! //! <b>Complexity</b>: Constant. - key_compare key_comp() const - { return m_tree.key_comp(); } + key_compare key_comp() const; //! <b>Effects</b>: Returns an object of value_compare constructed out //! of the comparison object. //! //! <b>Complexity</b>: Constant. - value_compare value_comp() const - { return value_compare(m_tree.key_comp()); } - - ////////////////////////////////////////////// - // - // map operations - // - ////////////////////////////////////////////// + value_compare value_comp() const; //! <b>Returns</b>: An iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - iterator find(const key_type& x) - { return m_tree.find(x); } + iterator find(const key_type& x); - //! <b>Returns</b>: Allocator const_iterator pointing to an element with the key + //! <b>Returns</b>: A const_iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - const_iterator find(const key_type& x) const - { return m_tree.find(x); } + const_iterator find(const key_type& x) const; + + #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Returns</b>: The number of elements with key equivalent to x. //! //! <b>Complexity</b>: log(size())+count(k) size_type count(const key_type& x) const - { return static_cast<size_type>(m_tree.find(x) != m_tree.end()); } + { return static_cast<size_type>(this->find(x) != this->cend()); } + + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator lower_bound(const key_type& x) - { return m_tree.lower_bound(x); } + iterator lower_bound(const key_type& x); - //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not + //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator lower_bound(const key_type& x) const - { return m_tree.lower_bound(x); } + const_iterator lower_bound(const key_type& x) const; //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator upper_bound(const key_type& x) - { return m_tree.upper_bound(x); } + iterator upper_bound(const key_type& x); - //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not + //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator upper_bound(const key_type& x) const - { return m_tree.upper_bound(x); } + const_iterator upper_bound(const key_type& x) const; //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<iterator,iterator> equal_range(const key_type& x) - { return m_tree.equal_range(x); } + std::pair<iterator,iterator> equal_range(const key_type& x); //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const - { return m_tree.equal_range(x); } + std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; - /// @cond - template <class K1, class T1, class C1, class A1> - friend bool operator== (const map<K1, T1, C1, A1>&, - const map<K1, T1, C1, A1>&); - template <class K1, class T1, class C1, class A1> - friend bool operator< (const map<K1, T1, C1, A1>&, - const map<K1, T1, C1, A1>&); + //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. + //! + //! <b>Complexity</b>: Linear + void rebalance(); + + //! <b>Effects</b>: Returns true if x and y are equal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator==(const map& x, const map& y); + + //! <b>Effects</b>: Returns true if x and y are unequal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator!=(const map& x, const map& y); + + //! <b>Effects</b>: Returns true if x is less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<(const map& x, const map& y); + + //! <b>Effects</b>: Returns true if x is greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>(const map& x, const map& y); + + //! <b>Effects</b>: Returns true if x is equal or less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<=(const map& x, const map& y); + + //! <b>Effects</b>: Returns true if x is equal or greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>=(const map& x, const map& y); + + //! <b>Effects</b>: x.swap(y) + //! + //! <b>Complexity</b>: Constant. + friend void swap(map& x, map& y); + + #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: mapped_type& priv_subscript(const key_type &k) { //we can optimize this - iterator i = lower_bound(k); + iterator i = this->lower_bound(k); // i->first is greater than or equivalent to k. - if (i == end() || key_comp()(k, (*i).first)){ + if (i == this->end() || this->key_comp()(k, (*i).first)){ container_detail::value_init<mapped_type> m; movable_value_type val(k, boost::move(m.m_t)); i = insert(i, boost::move(val)); @@ -780,9 +860,9 @@ { key_type &k = mk; //we can optimize this - iterator i = lower_bound(k); + iterator i = this->lower_bound(k); // i->first is greater than or equivalent to k. - if (i == end() || key_comp()(k, (*i).first)){ + if (i == this->end() || this->key_comp()(k, (*i).first)){ container_detail::value_init<mapped_type> m; movable_value_type val(boost::move(k), boost::move(m.m_t)); i = insert(i, boost::move(val)); @@ -790,68 +870,30 @@ return (*i).second; } - /// @endcond + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }; -template <class Key, class T, class Compare, class Allocator> -inline bool operator==(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return x.m_tree == y.m_tree; } -template <class Key, class T, class Compare, class Allocator> -inline bool operator<(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return x.m_tree < y.m_tree; } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator!=(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return !(x == y); } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator>(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return y < x; } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator<=(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return !(y < x); } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator>=(const map<Key,T,Compare,Allocator>& x, - const map<Key,T,Compare,Allocator>& y) - { return !(x < y); } - -template <class Key, class T, class Compare, class Allocator> -inline void swap(map<Key,T,Compare,Allocator>& x, map<Key,T,Compare,Allocator>& y) - { x.swap(y); } - -/// @cond - -// Forward declaration of operators < and ==, needed for friend declaration. - -template <class Key, class T, class Compare, class Allocator> -inline bool operator==(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -inline bool operator<(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y); +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED } //namespace container { //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class K, class T, class C, class Allocator> -struct has_trivial_destructor_after_move<boost::container::map<K, T, C, Allocator> > +template <class Key, class T, class Compare, class Allocator> +struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator> > { - static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && + ::boost::has_trivial_destructor_after_move<pointer>::value && + ::boost::has_trivial_destructor_after_move<Compare>::value; }; namespace container { -/// @endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED //! A multimap is a kind of associative container that supports equivalent keys //! (possibly containing multiple copies of the same key value) and provides for @@ -859,33 +901,42 @@ //! supports bidirectional iterators. //! //! A multimap satisfies all of the requirements of a container and of a reversible -//! container and of an associative container. For a -//! map<Key,T> the key_type is Key and the value_type is std::pair<const Key,T>. +//! container and of an associative container. The <code>value_type</code> stored +//! by this container is the value_type is std::pair<const Key, T>. //! -//! Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). -//! -//! Allocator is the allocator to allocate the value_types -//!(e.g. <i>allocator< std::pair<<b>const</b> Key, T> ></i>). -#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED -template <class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator< std::pair< const Key, T> > > +//! \tparam Key is the key_type of the map +//! \tparam Value is the <code>mapped_type</code> +//! \tparam Compare is the ordering function for Keys (e.g. <i>std::less<Key></i>). +//! \tparam Allocator is the allocator to allocate the <code>value_type</code>s +//! (e.g. <i>allocator< std::pair<const Key, T> > </i>). +//! \tparam MultiMapOptions is an packed option type generated using using boost::container::tree_assoc_options. +template < class Key, class T, class Compare = std::less<Key> + , class Allocator = new_allocator< std::pair< const Key, T> >, class MultiMapOptions = tree_assoc_defaults> #else -template <class Key, class T, class Compare, class Allocator> +template <class Key, class T, class Compare, class Allocator, class MultiMapOptions> #endif class multimap + ///@cond + : public container_detail::tree + < Key, std::pair<const Key, T> + , container_detail::select1st< std::pair<const Key, T> > + , Compare, Allocator, MultiMapOptions> + ///@endcond { - /// @cond + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: BOOST_COPYABLE_AND_MOVABLE(multimap) typedef std::pair<const Key, T> value_type_impl; - typedef container_detail::rbtree - <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator> tree_t; + typedef container_detail::tree + <Key, value_type_impl, container_detail::select1st<value_type_impl>, Compare, Allocator, MultiMapOptions> base_t; typedef container_detail::pair <Key, T> movable_value_type_impl; typedef container_detail::tree_value_compare < Key, value_type_impl, Compare, container_detail::select1st<value_type_impl> > value_compare_impl; - tree_t m_tree; // red-black tree representing map - /// @endcond + #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + + typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; public: ////////////////////////////////////////////// @@ -904,13 +955,13 @@ typedef typename boost::container::allocator_traits<Allocator>::size_type size_type; typedef typename boost::container::allocator_traits<Allocator>::difference_type difference_type; typedef Allocator allocator_type; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::stored_allocator_type) stored_allocator_type; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::stored_allocator_type) stored_allocator_type; typedef BOOST_CONTAINER_IMPDEF(value_compare_impl) value_compare; typedef Compare key_compare; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::iterator) iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_iterator) const_iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::reverse_iterator) reverse_iterator; - typedef typename BOOST_CONTAINER_IMPDEF(tree_t::const_reverse_iterator) const_reverse_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::iterator) iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_iterator) const_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::reverse_iterator) reverse_iterator; + typedef typename BOOST_CONTAINER_IMPDEF(base_t::const_reverse_iterator) const_reverse_iterator; typedef std::pair<key_type, mapped_type> nonconst_value_type; typedef BOOST_CONTAINER_IMPDEF(movable_value_type_impl) movable_value_type; @@ -924,9 +975,9 @@ //! //! <b>Complexity</b>: Constant. multimap() - : m_tree() + : base_t() { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -934,9 +985,9 @@ //! //! <b>Complexity</b>: Constant. explicit multimap(const Compare& comp, const allocator_type& a = allocator_type()) - : m_tree(comp, a) + : base_t(comp, a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -945,9 +996,9 @@ //! //! <b>Complexity</b>: Constant. explicit multimap(const allocator_type& a) - : m_tree(a) + : base_t(a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -960,9 +1011,22 @@ multimap(InputIterator first, InputIterator last, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) - : m_tree(false, first, last, comp, a) + : base_t(false, first, last, comp, a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty multimap using the specified + //! allocator, and inserts elements from the range [first ,last ). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is last - first. + template <class InputIterator> + multimap(InputIterator first, InputIterator last, const allocator_type& a) + : base_t(false, first, last, Compare(), a) + { + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -978,16 +1042,60 @@ template <class InputIterator> multimap(ordered_range_t, InputIterator first, InputIterator last, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) - : m_tree(ordered_range, first, last, comp, a) + : base_t(ordered_range, first, last, comp, a) {} +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Constructs an empty multimap using the specified comparison object and + //! allocator, and inserts elements from the range [il.begin(), il.end()). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is il.first() - il.end(). + multimap(std::initializer_list<value_type> il, const Compare& comp = Compare(), + const allocator_type& a = allocator_type()) + : base_t(false, il.begin(), il.end(), comp, a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty multimap using the specified + //! allocator, and inserts elements from the range [il.begin(), il.end()). + //! + //! <b>Complexity</b>: Linear in N if the range [first ,last ) is already sorted using + //! comp and otherwise N logN, where N is il.first() - il.end(). + multimap(std::initializer_list<value_type> il, const allocator_type& a) + : base_t(false, il.begin(), il.end(), Compare(), a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } + + //! <b>Effects</b>: Constructs an empty set using the specified comparison object and + //! allocator, and inserts elements from the ordered range [il.begin(), il.end()). This function + //! is more efficient than the normal range creation for ordered ranges. + //! + //! <b>Requires</b>: [il.begin(), il.end()) must be ordered according to the predicate. + //! + //! <b>Complexity</b>: Linear in N. + //! + //! <b>Note</b>: Non-standard extension. + multimap(ordered_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), + const allocator_type& a = allocator_type()) + : base_t(ordered_range, il.begin(), il.end(), comp, a) + { + //A type must be std::pair<CONST Key, T> + BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); + } +#endif + //! <b>Effects</b>: Copy constructs a multimap. //! //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap& x) - : m_tree(x.m_tree) + : base_t(static_cast<const base_t&>(x)) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -997,9 +1105,9 @@ //! //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF(multimap) x) - : m_tree(boost::move(x.m_tree)) + : base_t(BOOST_MOVE_BASE(base_t, x)) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -1007,9 +1115,9 @@ //! //! <b>Complexity</b>: Linear in x.size(). multimap(const multimap& x, const allocator_type &a) - : m_tree(x.m_tree, a) + : base_t(static_cast<const base_t&>(x), a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -1019,9 +1127,9 @@ //! //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) - : m_tree(boost::move(x.m_tree), a) + : base_t(BOOST_MOVE_BASE(base_t, x), a) { - //Allocator type must be std::pair<CONST Key, T> + //A type must be std::pair<CONST Key, T> BOOST_STATIC_ASSERT((container_detail::is_same<std::pair<const Key, T>, typename Allocator::value_type>::value)); } @@ -1029,186 +1137,86 @@ //! //! <b>Complexity</b>: Linear in x.size(). multimap& operator=(BOOST_COPY_ASSIGN_REF(multimap) x) - { m_tree = x.m_tree; return *this; } + { return static_cast<multimap&>(this->base_t::operator=(static_cast<const base_t&>(x))); } //! <b>Effects</b>: this->swap(x.get()). //! //! <b>Complexity</b>: Constant. multimap& operator=(BOOST_RV_REF(multimap) x) - { m_tree = boost::move(x.m_tree); return *this; } + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) + { return static_cast<multimap&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } - //! <b>Effects</b>: Returns a copy of the Allocator that - //! was passed to the object's constructor. +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: Assign content of il to *this. //! - //! <b>Complexity</b>: Constant. - allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_allocator(); } + multimap& operator=(std::initializer_list<value_type> il) + { + this->clear(); + insert(il.begin(), il.end()); + return *this; + } +#endif - //! <b>Effects</b>: Returns a reference to the internal allocator. - //! - //! <b>Throws</b>: Nothing - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Note</b>: Non-standard extension. - stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_stored_allocator(); } + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - //! <b>Effects</b>: Returns a reference to the internal allocator. - //! - //! <b>Throws</b>: Nothing - //! - //! <b>Complexity</b>: Constant. - //! - //! <b>Note</b>: Non-standard extension. - const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.get_stored_allocator(); } + //! @copydoc ::boost::container::set::get_allocator() + allocator_type get_allocator() const; - ////////////////////////////////////////////// - // - // iterators - // - ////////////////////////////////////////////// + //! @copydoc ::boost::container::set::get_stored_allocator() + stored_allocator_type &get_stored_allocator(); - //! <b>Effects</b>: Returns an iterator to the first element contained in the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - iterator begin() BOOST_CONTAINER_NOEXCEPT - { return m_tree.begin(); } + //! @copydoc ::boost::container::set::get_stored_allocator() const + const stored_allocator_type &get_stored_allocator() const; - //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator begin() const BOOST_CONTAINER_NOEXCEPT - { return this->cbegin(); } + //! @copydoc ::boost::container::set::begin() + iterator begin(); - //! <b>Effects</b>: Returns an iterator to the end of the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - iterator end() BOOST_CONTAINER_NOEXCEPT - { return m_tree.end(); } + //! @copydoc ::boost::container::set::begin() const + const_iterator begin() const; - //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator end() const BOOST_CONTAINER_NOEXCEPT - { return this->cend(); } + //! @copydoc ::boost::container::set::cbegin() const + const_iterator cbegin() const; - //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT - { return m_tree.rbegin(); } + //! @copydoc ::boost::container::set::end() + iterator end() BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT - { return this->crbegin(); } + //! @copydoc ::boost::container::set::end() const + const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a reverse_iterator pointing to the end - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT - { return m_tree.rend(); } + //! @copydoc ::boost::container::set::cend() const + const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT - { return this->crend(); } + //! @copydoc ::boost::container::set::rbegin() + reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.begin(); } + //! @copydoc ::boost::container::set::rbegin() const + const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_iterator to the end of the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_iterator cend() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.end(); } + //! @copydoc ::boost::container::set::crbegin() const + const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.rbegin(); } + //! @copydoc ::boost::container::set::rend() + reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end - //! of the reversed container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.rend(); } + //! @copydoc ::boost::container::set::rend() const + const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; - ////////////////////////////////////////////// - // - // capacity - // - ////////////////////////////////////////////// + //! @copydoc ::boost::container::set::crend() const + const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns true if the container contains no elements. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - bool empty() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.empty(); } + //! @copydoc ::boost::container::set::empty() const + bool empty() const; - //! <b>Effects</b>: Returns the number of the elements contained in the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - size_type size() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.size(); } + //! @copydoc ::boost::container::set::size() const + size_type size() const; - //! <b>Effects</b>: Returns the largest possible size of the container. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - size_type max_size() const BOOST_CONTAINER_NOEXCEPT - { return m_tree.max_size(); } + //! @copydoc ::boost::container::set::max_size() const + size_type max_size() const; - ////////////////////////////////////////////// - // - // modifiers - // - ////////////////////////////////////////////// + #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - #if defined(BOOST_CONTAINER_PERFECT_FORWARDING) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... in the container. @@ -1220,8 +1228,8 @@ //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace(Args&&... args) - { return m_tree.emplace_equal(boost::forward<Args>(args)...); } + iterator emplace(BOOST_FWD_REF(Args)... args) + { return this->base_t::emplace_equal(boost::forward<Args>(args)...); } //! <b>Effects</b>: Inserts an object of type T constructed with //! std::forward<Args>(args)... in the container. @@ -1233,54 +1241,52 @@ //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace_hint(const_iterator hint, Args&&... args) - { return m_tree.emplace_hint_equal(hint, boost::forward<Args>(args)...); } + iterator emplace_hint(const_iterator p, BOOST_FWD_REF(Args)... args) + { return this->base_t::emplace_hint_equal(p, boost::forward<Args>(args)...); } - #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #define BOOST_PP_LOCAL_MACRO(n) \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return m_tree.emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); } \ - \ - BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ - iterator emplace_hint(const_iterator hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return m_tree.emplace_hint_equal(hint \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _));} \ - //! - #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) - #include BOOST_PP_LOCAL_ITERATE() + #define BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace(BOOST_MOVE_UREF##N)\ + { return this->base_t::emplace_equal(BOOST_MOVE_FWD##N); }\ + \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + iterator emplace_hint(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + { return this->base_t::emplace_hint_equal(hint BOOST_MOVE_I##N BOOST_MOVE_FWD##N); }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE) + #undef BOOST_CONTAINER_MULTIMAP_EMPLACE_CODE - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) //! <b>Effects</b>: Inserts x and returns the iterator pointing to the //! newly inserted element. //! //! <b>Complexity</b>: Logarithmic. iterator insert(const value_type& x) - { return m_tree.insert_equal(x); } + { return this->base_t::insert_equal(x); } //! <b>Effects</b>: Inserts a new value constructed from x and returns //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. iterator insert(const nonconst_value_type& x) - { return m_tree.insert_equal(x); } + { return this->base_t::insert_equal(x); } //! <b>Effects</b>: Inserts a new value move-constructed from x and returns //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. iterator insert(BOOST_RV_REF(nonconst_value_type) x) - { return m_tree.insert_equal(boost::move(x)); } + { return this->base_t::insert_equal(boost::move(x)); } //! <b>Effects</b>: Inserts a new value move-constructed from x and returns //! the iterator pointing to the newly inserted element. //! //! <b>Complexity</b>: Logarithmic. iterator insert(BOOST_RV_REF(movable_value_type) x) - { return m_tree.insert_equal(boost::move(x)); } + { return this->base_t::insert_equal(boost::move(x)); } //! <b>Effects</b>: Inserts a copy of x in the container. //! p is a hint pointing to where the insert should start to search. @@ -1290,8 +1296,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, const value_type& x) - { return m_tree.insert_equal(position, x); } + iterator insert(const_iterator p, const value_type& x) + { return this->base_t::insert_equal(p, x); } //! <b>Effects</b>: Inserts a new value constructed from x in the container. //! p is a hint pointing to where the insert should start to search. @@ -1301,8 +1307,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, const nonconst_value_type& x) - { return m_tree.insert_equal(position, x); } + iterator insert(const_iterator p, const nonconst_value_type& x) + { return this->base_t::insert_equal(p, x); } //! <b>Effects</b>: Inserts a new value move constructed from x in the container. //! p is a hint pointing to where the insert should start to search. @@ -1312,8 +1318,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, BOOST_RV_REF(nonconst_value_type) x) - { return m_tree.insert_equal(position, boost::move(x)); } + iterator insert(const_iterator p, BOOST_RV_REF(nonconst_value_type) x) + { return this->base_t::insert_equal(p, boost::move(x)); } //! <b>Effects</b>: Inserts a new value move constructed from x in the container. //! p is a hint pointing to where the insert should start to search. @@ -1323,8 +1329,8 @@ //! //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. - iterator insert(const_iterator position, BOOST_RV_REF(movable_value_type) x) - { return m_tree.insert_equal(position, boost::move(x)); } + iterator insert(const_iterator p, BOOST_RV_REF(movable_value_type) x) + { return this->base_t::insert_equal(p, boost::move(x)); } //! <b>Requires</b>: first, last are not iterators into *this. //! @@ -1333,200 +1339,157 @@ //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from first to last) template <class InputIterator> void insert(InputIterator first, InputIterator last) - { m_tree.insert_equal(first, last); } + { this->base_t::insert_equal(first, last); } - //! <b>Effects</b>: Erases the element pointed to by position. +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! <b>Effects</b>: inserts each element from the range [il.begin(), il.end(). //! - //! <b>Returns</b>: Returns an iterator pointing to the element immediately - //! following q prior to the element being erased. If no such element exists, - //! returns end(). - //! - //! <b>Complexity</b>: Amortized constant time - iterator erase(const_iterator position) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(position); } + //! <b>Complexity</b>: At most N log(size()+N) (N is the distance from il.begin() to il.end()) + void insert(std::initializer_list<value_type> il) + { this->base_t::insert_equal(il.begin(), il.end()); } +#endif - //! <b>Effects</b>: Erases all elements in the container with key equivalent to x. - //! - //! <b>Returns</b>: Returns the number of erased elements. - //! - //! <b>Complexity</b>: log(size()) + count(k) - size_type erase(const key_type& x) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(x); } + #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - //! <b>Effects</b>: Erases all the elements in the range [first, last). - //! - //! <b>Returns</b>: Returns last. - //! - //! <b>Complexity</b>: log(size())+N where N is the distance from first to last. - iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT - { return m_tree.erase(first, last); } + //! @copydoc ::boost::container::set::erase(const_iterator) + iterator erase(const_iterator p); - //! <b>Effects</b>: Swaps the contents of *this and x. - //! - //! <b>Throws</b>: Nothing. - //! - //! <b>Complexity</b>: Constant. - void swap(multimap& x) - { m_tree.swap(x.m_tree); } + //! @copydoc ::boost::container::set::erase(const key_type&) + size_type erase(const key_type& x); - //! <b>Effects</b>: erase(a.begin(),a.end()). - //! - //! <b>Postcondition</b>: size() == 0. - //! - //! <b>Complexity</b>: linear in size(). - void clear() BOOST_CONTAINER_NOEXCEPT - { m_tree.clear(); } + //! @copydoc ::boost::container::set::erase(const_iterator,const_iterator) + iterator erase(const_iterator first, const_iterator last); - ////////////////////////////////////////////// - // - // observers - // - ////////////////////////////////////////////// + //! @copydoc ::boost::container::set::swap + void swap(multiset& x) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_swappable<Compare>::value ); - //! <b>Effects</b>: Returns the comparison object out - //! of which a was constructed. - //! - //! <b>Complexity</b>: Constant. - key_compare key_comp() const - { return m_tree.key_comp(); } + //! @copydoc ::boost::container::set::clear + void clear() BOOST_NOEXCEPT_OR_NOTHROW; - //! <b>Effects</b>: Returns an object of value_compare constructed out - //! of the comparison object. - //! - //! <b>Complexity</b>: Constant. - value_compare value_comp() const - { return value_compare(m_tree.key_comp()); } + //! @copydoc ::boost::container::set::key_comp + key_compare key_comp() const; - ////////////////////////////////////////////// - // - // map operations - // - ////////////////////////////////////////////// + //! @copydoc ::boost::container::set::value_comp + value_compare value_comp() const; //! <b>Returns</b>: An iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - iterator find(const key_type& x) - { return m_tree.find(x); } + iterator find(const key_type& x); - //! <b>Returns</b>: Allocator const iterator pointing to an element with the key + //! <b>Returns</b>: A const iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic. - const_iterator find(const key_type& x) const - { return m_tree.find(x); } + const_iterator find(const key_type& x) const; //! <b>Returns</b>: The number of elements with key equivalent to x. //! //! <b>Complexity</b>: log(size())+count(k) - size_type count(const key_type& x) const - { return m_tree.count(x); } + size_type count(const key_type& x) const; //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator lower_bound(const key_type& x) - {return m_tree.lower_bound(x); } + iterator lower_bound(const key_type& x); - //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not + //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than k, or a.end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator lower_bound(const key_type& x) const - { return m_tree.lower_bound(x); } + const_iterator lower_bound(const key_type& x) const; //! <b>Returns</b>: An iterator pointing to the first element with key not less //! than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - iterator upper_bound(const key_type& x) - { return m_tree.upper_bound(x); } + iterator upper_bound(const key_type& x); - //! <b>Returns</b>: Allocator const iterator pointing to the first element with key not + //! <b>Returns</b>: A const iterator pointing to the first element with key not //! less than x, or end() if such an element is not found. //! //! <b>Complexity</b>: Logarithmic - const_iterator upper_bound(const key_type& x) const - { return m_tree.upper_bound(x); } + const_iterator upper_bound(const key_type& x) const; //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<iterator,iterator> equal_range(const key_type& x) - { return m_tree.equal_range(x); } + std::pair<iterator,iterator> equal_range(const key_type& x); //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! //! <b>Complexity</b>: Logarithmic - std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const - { return m_tree.equal_range(x); } + std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const; - /// @cond - template <class K1, class T1, class C1, class A1> - friend bool operator== (const multimap<K1, T1, C1, A1>& x, - const multimap<K1, T1, C1, A1>& y); + //! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees. + //! + //! <b>Complexity</b>: Linear + void rebalance(); - template <class K1, class T1, class C1, class A1> - friend bool operator< (const multimap<K1, T1, C1, A1>& x, - const multimap<K1, T1, C1, A1>& y); - /// @endcond + //! <b>Effects</b>: Returns true if x and y are equal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator==(const multimap& x, const multimap& y); + + //! <b>Effects</b>: Returns true if x and y are unequal + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator!=(const multimap& x, const multimap& y); + + //! <b>Effects</b>: Returns true if x is less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<(const multimap& x, const multimap& y); + + //! <b>Effects</b>: Returns true if x is greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>(const multimap& x, const multimap& y); + + //! <b>Effects</b>: Returns true if x is equal or less than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator<=(const multimap& x, const multimap& y); + + //! <b>Effects</b>: Returns true if x is equal or greater than y + //! + //! <b>Complexity</b>: Linear to the number of elements in the container. + friend bool operator>=(const multimap& x, const multimap& y); + + //! <b>Effects</b>: x.swap(y) + //! + //! <b>Complexity</b>: Constant. + friend void swap(multimap& x, multimap& y); + + #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) }; -template <class Key, class T, class Compare, class Allocator> -inline bool operator==(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return x.m_tree == y.m_tree; } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator<(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return x.m_tree < y.m_tree; } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator!=(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return !(x == y); } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator>(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return y < x; } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator<=(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return !(y < x); } - -template <class Key, class T, class Compare, class Allocator> -inline bool operator>=(const multimap<Key,T,Compare,Allocator>& x, - const multimap<Key,T,Compare,Allocator>& y) -{ return !(x < y); } - -template <class Key, class T, class Compare, class Allocator> -inline void swap(multimap<Key,T,Compare,Allocator>& x, multimap<Key,T,Compare,Allocator>& y) -{ x.swap(y); } - -/// @cond +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED } //namespace container { //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class K, class T, class C, class Allocator> -struct has_trivial_destructor_after_move<boost::container::multimap<K, T, C, Allocator> > +template <class Key, class T, class Compare, class Allocator> +struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator> > { - static const bool value = has_trivial_destructor_after_move<Allocator>::value && has_trivial_destructor_after_move<C>::value; + typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer; + static const bool value = ::boost::has_trivial_destructor_after_move<Allocator>::value && + ::boost::has_trivial_destructor_after_move<pointer>::value && + ::boost::has_trivial_destructor_after_move<Compare>::value; }; namespace container { -/// @endcond +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }} #include <boost/container/detail/config_end.hpp> -#endif /* BOOST_CONTAINER_MAP_HPP */ +#endif // BOOST_CONTAINER_MAP_HPP