diff options
Diffstat (limited to 'boost/container/set.hpp')
| -rw-r--r-- | boost/container/set.hpp | 211 |
1 files changed, 128 insertions, 83 deletions
diff --git a/boost/container/set.hpp b/boost/container/set.hpp index 3e2c2aad0d..79fa1aec66 100644 --- a/boost/container/set.hpp +++ b/boost/container/set.hpp @@ -11,27 +11,34 @@ #ifndef BOOST_CONTAINER_SET_HPP #define BOOST_CONTAINER_SET_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/move/utility_core.hpp> -#include <boost/move/detail/move_helpers.hpp> -#include <boost/move/traits.hpp> +// container/detail #include <boost/container/detail/mpl.hpp> #include <boost/container/detail/tree.hpp> +#include <boost/container/new_allocator.hpp> //new_allocator +// intrusive/detail +#include <boost/intrusive/detail/minimal_pair_header.hpp> //pair +#include <boost/intrusive/detail/minimal_less_equal_header.hpp>//less, equal +// move +#include <boost/move/traits.hpp> #include <boost/move/utility_core.hpp> -#ifndef BOOST_CONTAINER_PERFECT_FORWARDING -#include <boost/container/detail/preprocessor.hpp> +// move/detail +#include <boost/move/detail/move_helpers.hpp> +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> #endif +// std #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) #include <initializer_list> #endif @@ -53,7 +60,7 @@ namespace container { //! \tparam Compare is the comparison functor used to order keys //! \tparam Allocator is the allocator to be used to allocate memory for this container //! \tparam SetOptions is an packed option type generated using using boost::container::tree_assoc_options. -template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class SetOptions = tree_assoc_defaults > +template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key>, class SetOptions = tree_assoc_defaults > #else template <class Key, class Compare, class Allocator, class SetOptions> #endif @@ -134,6 +141,16 @@ class set : base_t(true, first, last, comp, a) {} + //! <b>Effects</b>: Constructs an empty set 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> + set(InputIterator first, InputIterator last, const allocator_type& a) + : base_t(true, first, last, key_compare(), a) + {} + //! <b>Effects</b>: Constructs an empty set using the specified comparison object and //! allocator, and inserts elements from the ordered unique range [first ,last). This function //! is more efficient than the normal range creation for ordered ranges. @@ -160,6 +177,15 @@ class set : base_t(true, il.begin(), il.end(), comp, a) {} + //! <b>Effects</b>: Constructs an empty set using the specified + //! allocator, and inserts elements from the range [il.begin(), il.end()). + //! + //! <b>Complexity</b>: Linear in N if the range [il.begin(), il.end()) is already sorted using + //! comp and otherwise N logN, where N is il.begin() - il.end(). + set(std::initializer_list<value_type> il, const allocator_type& a) + : base_t(true, il.begin(), il.end(), Compare(), a) + {} + //! <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. @@ -170,7 +196,8 @@ class set //! <b>Complexity</b>: Linear in N. //! //! <b>Note</b>: Non-standard extension. - set(ordered_unique_range_t, std::initializer_list<value_type> il, const Compare& comp = Compare(), const allocator_type& a = allocator_type()) + set( 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) {} #endif @@ -188,7 +215,7 @@ class set //! //! <b>Postcondition</b>: x is emptied. set(BOOST_RV_REF(set) x) - : base_t(boost::move(static_cast<base_t&>(x))) + : base_t(BOOST_MOVE_BASE(base_t, x)) {} //! <b>Effects</b>: Copy constructs a set using the specified allocator. @@ -203,7 +230,7 @@ class set //! //! <b>Complexity</b>: Constant if a == x.get_allocator(), linear otherwise. set(BOOST_RV_REF(set) x, const allocator_type &a) - : base_t(boost::move(static_cast<base_t&>(x)), a) + : base_t(BOOST_MOVE_BASE(base_t, x), a) {} //! <b>Effects</b>: Makes *this a copy of x. @@ -221,8 +248,9 @@ class set //! propagate_on_container_move_assignment is true or //! this->get>allocator() == x.get_allocator(). Linear otherwise. set& operator=(BOOST_RV_REF(set) x) - BOOST_CONTAINER_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value) - { return static_cast<set&>(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<set&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) set& operator=(std::initializer_list<value_type> il) @@ -235,7 +263,7 @@ class set #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. @@ -371,7 +399,7 @@ class set size_type max_size() const; #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 x of type Key constructed with //! std::forward<Args>(args)... if and only if there is @@ -388,7 +416,7 @@ class set //! //! <b>Complexity</b>: Logarithmic. 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 Key constructed with @@ -401,26 +429,24 @@ class set //! //! <b>Complexity</b>: Logarithmic. 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_SET_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_SET_EMPLACE_CODE) + #undef BOOST_CONTAINER_SET_EMPLACE_CODE - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts x if and only if there is no element in the container @@ -521,7 +547,9 @@ class set //! <b>Throws</b>: Nothing. //! //! <b>Complexity</b>: Constant. - void swap(set& x); + void swap(set& 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()). //! @@ -548,7 +576,7 @@ class set //! <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. @@ -576,7 +604,7 @@ class set //! <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 @@ -588,7 +616,7 @@ class set //! <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 @@ -680,10 +708,13 @@ class set //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class Key, class C, class SetOptions, class Allocator> -struct has_trivial_destructor_after_move<boost::container::set<Key, C, Allocator, SetOptions> > +template <class Key, class Compare, class SetOptions, class Allocator> +struct has_trivial_destructor_after_move<boost::container::set<Key, Compare, Allocator, SetOptions> > { - 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 { @@ -704,7 +735,7 @@ namespace container { //! \tparam Compare is the comparison functor used to order keys //! \tparam Allocator is the allocator to be used to allocate memory for this container //! \tparam MultiSetOptions is an packed option type generated using using boost::container::tree_assoc_options. -template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>, class MultiSetOptions = tree_assoc_defaults > +template <class Key, class Compare = std::less<Key>, class Allocator = new_allocator<Key>, class MultiSetOptions = tree_assoc_defaults > #else template <class Key, class Compare, class Allocator, class MultiSetOptions> #endif @@ -776,6 +807,12 @@ class multiset : base_t(false, first, last, comp, a) {} + //! @copydoc ::boost::container::set::set(InputIterator, InputIterator, const allocator_type&) + template <class InputIterator> + multiset(InputIterator first, InputIterator last, const allocator_type& a) + : base_t(false, first, last, key_compare(), a) + {} + //! <b>Effects</b>: Constructs an empty multiset using the specified comparison object and //! allocator, and inserts elements from the ordered range [first ,last ). This function //! is more efficient than the normal range creation for ordered ranges. @@ -798,13 +835,17 @@ class multiset : base_t(false, il.begin(), il.end(), comp, a) {} + //! @copydoc ::boost::container::set::set(std::initializer_list<value_type>, const allocator_type&) + multiset(std::initializer_list<value_type> il, const allocator_type& a) + : base_t(false, il.begin(), il.end(), Compare(), a) + {} + //! @copydoc ::boost::container::set::set(ordered_unique_range_t, std::initializer_list<value_type>, const Compare& comp, const allocator_type&) multiset(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) {} #endif - //! @copydoc ::boost::container::set::set(const set &) multiset(const multiset& x) : base_t(static_cast<const base_t&>(x)) @@ -812,7 +853,7 @@ class multiset //! @copydoc ::boost::container::set(set &&) multiset(BOOST_RV_REF(multiset) x) - : base_t(boost::move(static_cast<base_t&>(x))) + : base_t(BOOST_MOVE_BASE(base_t, x)) {} //! @copydoc ::boost::container::set(const set &, const allocator_type &) @@ -822,7 +863,7 @@ class multiset //! @copydoc ::boost::container::set(set &&, const allocator_type &) multiset(BOOST_RV_REF(multiset) x, const allocator_type &a) - : base_t(boost::move(static_cast<base_t&>(x)), a) + : base_t(BOOST_MOVE_BASE(base_t, x), a) {} //! @copydoc ::boost::container::set::operator=(const set &) @@ -831,7 +872,9 @@ class multiset //! @copydoc ::boost::container::set::operator=(set &&) multiset& operator=(BOOST_RV_REF(multiset) x) - { return static_cast<multiset&>(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<multiset&>(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) //! @copydoc ::boost::container::set::operator=(std::initializer_list<value_type>) @@ -863,31 +906,31 @@ class multiset 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; @@ -900,7 +943,7 @@ class multiset #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 Key constructed with //! std::forward<Args>(args)... and returns the iterator pointing to the @@ -908,7 +951,7 @@ class multiset //! //! <b>Complexity</b>: Logarithmic. 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 Key constructed with @@ -920,26 +963,24 @@ class multiset //! <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_MULTISET_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_MULTISET_EMPLACE_CODE) + #undef BOOST_CONTAINER_MULTISET_EMPLACE_CODE - #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) //! <b>Effects</b>: Inserts x and returns the iterator pointing to the @@ -996,7 +1037,7 @@ class multiset #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) //! @copydoc ::boost::container::set::insert(std::initializer_list<value_type>) void insert(std::initializer_list<value_type> il) - { this->base_t::insert_unique(il.begin(), il.end()); } + { this->base_t::insert_equal(il.begin(), il.end()); } #endif #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -1011,10 +1052,12 @@ class multiset 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; @@ -1108,10 +1151,13 @@ class multiset //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations -template <class Key, class C, class Allocator, class MultiSetOptions> -struct has_trivial_destructor_after_move<boost::container::multiset<Key, C, Allocator, MultiSetOptions> > +template <class Key, class Compare, class Allocator, class MultiSetOptions> +struct has_trivial_destructor_after_move<boost::container::multiset<Key, Compare, Allocator, MultiSetOptions> > { - 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 { @@ -1122,5 +1168,4 @@ namespace container { #include <boost/container/detail/config_end.hpp> -#endif /* BOOST_CONTAINER_SET_HPP */ - +#endif // BOOST_CONTAINER_SET_HPP |