diff options
Diffstat (limited to 'boost/container/map.hpp')
| -rw-r--r-- | boost/container/map.hpp | 363 |
1 files changed, 226 insertions, 137 deletions
diff --git a/boost/container/map.hpp b/boost/container/map.hpp index 6abfa1a346..4dc6096e1e 100644 --- a/boost/container/map.hpp +++ b/boost/container/map.hpp @@ -7,36 +7,45 @@ // 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> +// 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> -#include <boost/move/traits.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/core/no_exceptions_support.hpp> - +// std #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> #endif @@ -55,13 +64,13 @@ namespace container { //! by this container is the value_type is std::pair<const Key, T>. //! //! \tparam Key is the key_type of the map -//! \tparam Value is the <code>mapped_type</code> +//! \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 = std::allocator< std::pair< const Key, T> >, class MapOptions = tree_assoc_defaults > + , class Allocator = new_allocator< std::pair< const Key, T> >, class MapOptions = tree_assoc_defaults > #else template <class Key, class T, class Compare, class Allocator, class MapOptions> #endif @@ -93,10 +102,10 @@ class map // ////////////////////////////////////////////// - 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 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; @@ -126,7 +135,7 @@ class map map() : 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)); } @@ -134,11 +143,10 @@ class map //! and allocator. //! //! <b>Complexity</b>: Constant. - explicit map(const Compare& comp, - const allocator_type& a = allocator_type()) + 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)); } @@ -148,7 +156,7 @@ class map explicit map(const allocator_type& 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)); } @@ -162,7 +170,20 @@ class map const allocator_type& a = allocator_type()) : 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)); } @@ -181,7 +202,7 @@ class map , const Compare& comp = Compare(), const allocator_type& a = allocator_type()) : 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)); } @@ -194,15 +215,37 @@ class map 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) { - //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 [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) { - //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)); } #endif @@ -213,7 +256,7 @@ class map map(const map& x) : 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)); } @@ -223,9 +266,9 @@ class map //! //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF(map) x) - : base_t(boost::move(static_cast<base_t&>(x))) + : 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)); } @@ -235,7 +278,7 @@ class map map(const map& x, const allocator_type &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)); } @@ -246,9 +289,9 @@ class map //! //! <b>Postcondition</b>: x is emptied. map(BOOST_RV_REF(map) x, const allocator_type &a) - : base_t(boost::move(static_cast<base_t&>(x)), 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)); } @@ -267,8 +310,10 @@ class map //! propagate_on_container_move_assignment is true or //! this->get>allocator() == x.get_allocator(). Linear otherwise. map& operator=(BOOST_RV_REF(map) x) - BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value) - { return static_cast<map&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x)))); } + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_move_assignable<Compare>::value ) + + { 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. @@ -283,7 +328,7 @@ class map #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - //! <b>Effects</b>: Returns a copy of the Allocator that + //! <b>Effects</b>: Returns a copy of the allocator that //! was passed to the object's constructor. //! //! <b>Complexity</b>: Constant. @@ -296,7 +341,7 @@ class map //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Non-standard extension. - stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT; + stored_allocator_type &get_stored_allocator() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reference to the internal allocator. //! @@ -305,49 +350,49 @@ class map //! <b>Complexity</b>: Constant. //! //! <b>Note</b>: Non-standard extension. - const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT; + 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; + 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; + 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_CONTAINER_NOEXCEPT; + 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; + 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; + 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_CONTAINER_NOEXCEPT; + const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning //! of the reversed container. @@ -355,7 +400,7 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT; + reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning //! of the reversed container. @@ -363,7 +408,7 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT; + 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. @@ -371,7 +416,7 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT; + const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a reverse_iterator pointing to the end //! of the reversed container. @@ -379,7 +424,7 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT; + reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end //! of the reversed container. @@ -387,7 +432,7 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT; + 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. @@ -395,28 +440,28 @@ class map //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT; + 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; + 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; + 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; + size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW; #endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -424,7 +469,7 @@ class map //! 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); @@ -432,7 +477,7 @@ class map //! 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); @@ -440,7 +485,7 @@ class map 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) @@ -452,7 +497,7 @@ class map 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 @@ -598,7 +643,7 @@ class map { this->base_t::insert_unique(il.begin(), il.end()); } #endif - #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 x of type T constructed with //! std::forward<Args>(args)... in the container if and only if there is @@ -612,7 +657,7 @@ class map //! <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) + 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 @@ -626,26 +671,24 @@ class map //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace_hint(const_iterator p, 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 this->base_t::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 p \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return this->base_t::emplace_hint_unique(p \ - 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) #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -656,35 +699,37 @@ class map //! returns end(). //! //! <b>Complexity</b>: Amortized constant time - iterator erase(const_iterator p) BOOST_CONTAINER_NOEXCEPT; + 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; + 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; + iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Swaps the contents of *this and x. //! //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - void swap(map& x); + void swap(map& x) + 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; + void clear() BOOST_NOEXCEPT_OR_NOTHROW; //! <b>Effects</b>: Returns the comparison object out //! of which a was constructed. @@ -704,7 +749,7 @@ class map //! <b>Complexity</b>: Logarithmic. 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. @@ -726,7 +771,7 @@ class map //! <b>Complexity</b>: Logarithmic 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 @@ -738,7 +783,7 @@ class map //! <b>Complexity</b>: Logarithmic 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 @@ -835,10 +880,13 @@ class map //!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 { @@ -863,7 +911,7 @@ namespace container { //! (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 = std::allocator< std::pair< const Key, T> >, class MultiMapOptions = tree_assoc_defaults> + , class Allocator = new_allocator< std::pair< const Key, T> >, class MultiMapOptions = tree_assoc_defaults> #else template <class Key, class T, class Compare, class Allocator, class MultiMapOptions> #endif @@ -888,6 +936,8 @@ class multimap > value_compare_impl; #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type; + public: ////////////////////////////////////////////// // @@ -927,7 +977,7 @@ class multimap multimap() : 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)); } @@ -937,7 +987,7 @@ class multimap explicit multimap(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)); } @@ -948,7 +998,7 @@ class multimap explicit multimap(const allocator_type& 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)); } @@ -963,7 +1013,20 @@ class multimap const allocator_type& a = allocator_type()) : 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)); } @@ -992,15 +1055,36 @@ class multimap const allocator_type& a = allocator_type()) : base_t(false, il.begin(), il.end(), 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 [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) { - //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)); } #endif @@ -1011,7 +1095,7 @@ class multimap multimap(const multimap& x) : 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)); } @@ -1021,9 +1105,9 @@ class multimap //! //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF(multimap) x) - : base_t(boost::move(static_cast<base_t&>(x))) + : 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)); } @@ -1033,7 +1117,7 @@ class multimap multimap(const multimap& x, const allocator_type &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)); } @@ -1043,9 +1127,9 @@ class multimap //! //! <b>Postcondition</b>: x is emptied. multimap(BOOST_RV_REF(multimap) x, const allocator_type &a) - : base_t(boost::move(static_cast<base_t&>(x)), 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)); } @@ -1059,7 +1143,9 @@ class multimap //! //! <b>Complexity</b>: Constant. multimap& operator=(BOOST_RV_REF(multimap) x) - { return static_cast<multimap&>(this->base_t::operator=(boost::move(static_cast<base_t&>(x)))); } + 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))); } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) //! <b>Effects</b>: Assign content of il to *this. @@ -1093,31 +1179,31 @@ class multimap const_iterator cbegin() const; //! @copydoc ::boost::container::set::end() - iterator end() BOOST_CONTAINER_NOEXCEPT; + iterator end() BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::end() const - const_iterator end() const BOOST_CONTAINER_NOEXCEPT; + const_iterator end() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::cend() const - const_iterator cend() const BOOST_CONTAINER_NOEXCEPT; + const_iterator cend() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::rbegin() - reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT; + reverse_iterator rbegin() BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::rbegin() const - const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT; + const_reverse_iterator rbegin() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::crbegin() const - const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT; + const_reverse_iterator crbegin() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::rend() - reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT; + reverse_iterator rend() BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::rend() const - const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT; + const_reverse_iterator rend() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::crend() const - const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT; + const_reverse_iterator crend() const BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::empty() const bool empty() const; @@ -1130,7 +1216,7 @@ class multimap #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. @@ -1142,7 +1228,7 @@ class multimap //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace(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 @@ -1155,26 +1241,24 @@ class multimap //! <b>Complexity</b>: Logarithmic in general, but amortized constant if t //! is inserted right before p. template <class... Args> - iterator emplace_hint(const_iterator p, 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 this->base_t::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 p \ - BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ - { return this->base_t::emplace_hint_equal(p \ - 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. @@ -1277,10 +1361,12 @@ class multimap iterator erase(const_iterator first, const_iterator last); //! @copydoc ::boost::container::set::swap - void swap(flat_multiset& x); + void swap(multiset& x) + BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value + && boost::container::container_detail::is_nothrow_swappable<Compare>::value ); //! @copydoc ::boost::container::set::clear - void clear() BOOST_CONTAINER_NOEXCEPT; + void clear() BOOST_NOEXCEPT_OR_NOTHROW; //! @copydoc ::boost::container::set::key_comp key_compare key_comp() const; @@ -1294,7 +1380,7 @@ class multimap //! <b>Complexity</b>: Logarithmic. 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. @@ -1311,7 +1397,7 @@ class multimap //! <b>Complexity</b>: Logarithmic 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 @@ -1323,7 +1409,7 @@ class multimap //! <b>Complexity</b>: Logarithmic 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 @@ -1388,10 +1474,13 @@ class multimap //!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 { @@ -1402,5 +1491,5 @@ namespace container { #include <boost/container/detail/config_end.hpp> -#endif /* BOOST_CONTAINER_MAP_HPP */ +#endif // BOOST_CONTAINER_MAP_HPP |