//! (e.g. <i>allocator< std::pair<const Key, T> > </i>).
//! \tparam Options 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 Options = tree_assoc_defaults >
+ , class Allocator = void, class Options = tree_assoc_defaults >
#else
template <class Key, class T, class Compare, class Allocator, class Options>
#endif
///@cond
: public dtl::tree
< std::pair<const Key, T>
- , dtl::select1st<Key>
+ , int
, Compare, Allocator, Options>
///@endcond
{
private:
BOOST_COPYABLE_AND_MOVABLE(map)
- typedef dtl::select1st<Key> select_1st_t;
+ typedef int select_1st_t;
typedef std::pair<const Key, T> value_type_impl;
typedef dtl::tree
<value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
- typedef dtl::pair <Key, T> movable_value_type_impl;
+ typedef dtl::pair <Key, T> movable_value_type_impl;
typedef typename base_t::value_compare value_compare_impl;
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
//
//////////////////////////////////////////////
- typedef Key key_type;
- typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
- typedef T mapped_type;
- typedef typename boost::container::allocator_traits<Allocator>::value_type 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;
- typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
- 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(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(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;
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef typename base_t::allocator_type allocator_type;
+ typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer;
+ typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
+ typedef typename boost::container::allocator_traits<allocator_type>::reference reference;
+ typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference;
+ typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_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(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;
typedef BOOST_CONTAINER_IMPDEF(node_handle<
typename base_t::stored_allocator_type
BOOST_MOVE_I pair_key_mapped_of_value
//!
//! <b>Complexity</b>: Constant.
BOOST_CONTAINER_FORCEINLINE
- map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value &&
+ map() BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
dtl::is_nothrow_default_constructible<Compare>::value)
: base_t()
{}
: base_t(ordered_range, first, last, comp, a)
{}
+ //! <b>Effects</b>: Constructs an empty map using the specified allocator object and
+ //! inserts elements from the ordered unique range [first ,last). This function
+ //! is more efficient than the normal range creation for ordered ranges.
+ //!
+ //! <b>Requires</b>: [first ,last) must be ordered according to the predicate and must be
+ //! unique values.
+ //!
+ //! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: Non-standard extension.
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE map(ordered_unique_range_t, InputIterator first, InputIterator last, const allocator_type& a)
+ : base_t(ordered_range, first, last, Compare(), a)
+ {}
+
+
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
//! <b>Effects</b>: Constructs an empty map and
//! inserts elements from the range [il.begin(), il.end()).
//! the new element is inserted just before hint.
template <class M>
BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, const key_type& k, BOOST_FWD_REF(M) obj)
- { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)); }
+ { return this->base_t::insert_or_assign(hint, k, ::boost::forward<M>(obj)).first; }
//! <b>Effects</b>: If a key equivalent to k already exists in the container, assigns forward<M>(obj)
//! to the mapped_type corresponding to the key k. If the key does not exist, inserts the new value
//! the new element is inserted just before hint.
template <class M>
BOOST_CONTAINER_FORCEINLINE iterator insert_or_assign(const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
- { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)); }
+ { return this->base_t::insert_or_assign(hint, ::boost::move(k), ::boost::forward<M>(obj)).first; }
//! <b>Returns</b>: 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.
//!
//! <b>Returns</b>: A node_type owning the element if found, otherwise an empty node_type.
//!
- //! <b>Complexity</b>: log(a.size()).
+ //! <b>Complexity</b>: log(size()).
node_type extract(const key_type& k)
{
typename base_t::node_type base_nh(this->base_t::extract(k));
//!
//! <b>Throws</b>: Nothing unless the comparison object throws.
//!
- //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
+ //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
template<class C2>
BOOST_CONTAINER_FORCEINLINE void merge(map<Key, T, C2, Allocator, Options>& source)
{
BOOST_NOEXCEPT_IF( allocator_traits_type::is_always_equal::value
&& boost::container::dtl::is_nothrow_swappable<Compare>::value )
- //! <b>Effects</b>: erase(a.begin(),a.end()).
+ //! <b>Effects</b>: erase(begin(),end()).
//!
//! <b>Postcondition</b>: size() == 0.
//!
//! <b>Complexity</b>: Logarithmic.
const_iterator find(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <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.
+ template<typename K>
+ iterator find(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <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.
+ template<typename K>
+ const_iterator find(const K& x) const;
+
#endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Returns</b>: The number of elements with key equivalent to x.
BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
{ return static_cast<size_type>(this->find(x) != this->cend()); }
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: The number of elements with key equivalent to x.
+ //!
+ //! <b>Complexity</b>: log(size())+count(k)
+ template<typename K>
+ BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
+ { return static_cast<size_type>(this->find(x) != this->cend()); }
+
#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+ //! <b>Returns</b>: Returns true if there is an element with key
+ //! equivalent to key in the container, otherwise false.
+ //!
+ //! <b>Complexity</b>: log(size()).
+ bool contains(const key_type& x) const;
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: Returns true if there is an element with key
+ //! equivalent to key in the container, otherwise false.
+ //!
+ //! <b>Complexity</b>: log(size()).
+ template<typename K>
+ bool contains(const K& 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.
+ //! than x, or end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
iterator lower_bound(const key_type& x);
//! <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.
+ //! less than x, or end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
const_iterator lower_bound(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
//! <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);
+ template<typename K>
+ iterator lower_bound(const K& x);
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
//! <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
+ template<typename K>
+ const_iterator lower_bound(const K& x) const;
+
+ //! <b>Returns</b>: An iterator pointing to the first element with key greater
+ //! than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ iterator upper_bound(const key_type& x);
+
+ //! <b>Returns</b>: A const iterator pointing to the first element with key
+ //! greater than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
const_iterator upper_bound(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: An iterator pointing to the first element with key greater
+ //! than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ iterator upper_bound(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: A const iterator pointing to the first element with key
+ //! greater than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ const_iterator upper_bound(const K& x) const;
+
//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic
//! <b>Complexity</b>: Logarithmic
std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ std::pair<iterator,iterator> equal_range(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
+
//! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
//!
//! <b>Complexity</b>: Linear
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
};
+#ifndef BOOST_CONTAINER_NO_CXX17_CTAD
+
+template <typename InputIterator>
+map(InputIterator, InputIterator) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>>;
+
+template < typename InputIterator, typename AllocatorOrCompare>
+ map(InputIterator, InputIterator, AllocatorOrCompare const&) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , typename dtl::if_c< // Compare
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , std::less<it_based_non_const_first_type_t<InputIterator>>
+ , AllocatorOrCompare
+ >::type
+ , typename dtl::if_c< // Allocator
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , AllocatorOrCompare
+ , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
+ >::type
+ >;
+
+template < typename InputIterator, typename Compare, typename Allocator
+ , typename = dtl::require_nonallocator_t<Compare>
+ , typename = dtl::require_allocator_t<Allocator>>
+map(InputIterator, InputIterator, Compare const&, Allocator const&) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , Compare
+ , Allocator>;
+
+template <typename InputIterator>
+map(ordered_unique_range_t, InputIterator, InputIterator) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>>;
+
+template < typename InputIterator, typename AllocatorOrCompare>
+map(ordered_unique_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , typename dtl::if_c< // Compare
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , std::less<it_based_non_const_first_type_t<InputIterator>>
+ , AllocatorOrCompare
+ >::type
+ , typename dtl::if_c< // Allocator
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , AllocatorOrCompare
+ , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
+ >::type
+ >;
+
+template < typename InputIterator, typename Compare, typename Allocator
+ , typename = dtl::require_nonallocator_t<Compare>
+ , typename = dtl::require_allocator_t<Allocator>>
+map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , Compare
+ , Allocator>;
+
+#endif
+
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
-template <class Key, class T, class Compare, class Allocator>
-struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator> >
+template <class Key, class T, class Compare, class Allocator, class Options>
+struct has_trivial_destructor_after_move<boost::container::map<Key, T, Compare, Allocator, Options> >
{
- 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;
+ typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
+ static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
};
namespace container {
///@cond
: public dtl::tree
< std::pair<const Key, T>
- , dtl::select1st<Key>
+ , int
, Compare, Allocator, Options>
///@endcond
{
private:
BOOST_COPYABLE_AND_MOVABLE(multimap)
- typedef dtl::select1st<Key> select_1st_t;
+ typedef int select_1st_t;
typedef std::pair<const Key, T> value_type_impl;
typedef dtl::tree
<value_type_impl, select_1st_t, Compare, Allocator, Options> base_t;
typedef typename base_t::value_compare value_compare_impl;
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
- typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
-
public:
//////////////////////////////////////////////
//
//
//////////////////////////////////////////////
- typedef Key key_type;
- typedef T mapped_type;
- typedef typename boost::container::allocator_traits<Allocator>::value_type 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;
- typedef typename boost::container::allocator_traits<Allocator>::const_reference const_reference;
- 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(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(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;
+ typedef Key key_type;
+ typedef T mapped_type;
+ typedef typename base_t::allocator_type allocator_type;
+ typedef ::boost::container::allocator_traits<allocator_type> allocator_traits_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::value_type value_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::pointer pointer;
+ typedef typename boost::container::allocator_traits<allocator_type>::const_pointer const_pointer;
+ typedef typename boost::container::allocator_traits<allocator_type>::reference reference;
+ typedef typename boost::container::allocator_traits<allocator_type>::const_reference const_reference;
+ typedef typename boost::container::allocator_traits<allocator_type>::size_type size_type;
+ typedef typename boost::container::allocator_traits<allocator_type>::difference_type difference_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(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;
typedef BOOST_CONTAINER_IMPDEF(node_handle<
typename base_t::stored_allocator_type
BOOST_MOVE_I pair_key_mapped_of_value
//!
//! <b>Complexity</b>: Constant.
BOOST_CONTAINER_FORCEINLINE multimap()
- BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<Allocator>::value &&
+ BOOST_NOEXCEPT_IF(dtl::is_nothrow_default_constructible<allocator_type>::value &&
dtl::is_nothrow_default_constructible<Compare>::value)
: base_t()
{}
: base_t(ordered_range, first, last, comp, a)
{}
+ //! <b>Effects</b>: Constructs an empty multimap using the specified allocator and
+ //! inserts elements from the ordered range [first ,last). This function
+ //! is more efficient than the normal range creation for ordered ranges.
+ //!
+ //! <b>Requires</b>: [first ,last) must be ordered according to the predicate.
+ //!
+ //! <b>Complexity</b>: Linear in N.
+ //!
+ //! <b>Note</b>: Non-standard extension.
+ template <class InputIterator>
+ BOOST_CONTAINER_FORCEINLINE multimap(ordered_range_t, InputIterator first, InputIterator last, const allocator_type& a)
+ : base_t(ordered_range, first, last, Compare(), a)
+ {}
+
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
//! <b>Effects</b>: Constructs an empty multimap and
//! and inserts elements from the range [il.begin(), il.end()).
//!
//! <b>Throws</b>: Nothing unless the comparison object throws.
//!
- //! <b>Complexity</b>: N log(a.size() + N) (N has the value source.size())
+ //! <b>Complexity</b>: N log(size() + N) (N has the value source.size())
template<class C2>
BOOST_CONTAINER_FORCEINLINE void merge(multimap<Key, T, C2, Allocator, Options>& source)
{
//! <b>Complexity</b>: Logarithmic.
const_iterator find(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <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.
+ template<typename K>
+ iterator find(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <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.
+ template<typename K>
+ const_iterator find(const K& 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;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: The number of elements with key equivalent to x.
+ //!
+ //! <b>Complexity</b>: log(size())+count(k)
+ template<typename K>
+ size_type count(const K& x) const;
+
+ //! <b>Returns</b>: Returns true if there is an element with key
+ //! equivalent to key in the container, otherwise false.
+ //!
+ //! <b>Complexity</b>: log(size()).
+ bool contains(const key_type& x) const;
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: Returns true if there is an element with key
+ //! equivalent to key in the container, otherwise false.
+ //!
+ //! <b>Complexity</b>: log(size()).
+ template<typename K>
+ bool contains(const K& 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.
+ //! than x, or end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
iterator lower_bound(const key_type& x);
//! <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.
+ //! less than x, or end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
const_iterator lower_bound(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
//! <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);
+ template<typename K>
+ iterator lower_bound(const K& x);
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
//! <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
+ template<typename K>
+ const_iterator lower_bound(const K& x) const;
+
+ //! <b>Returns</b>: An iterator pointing to the first element with key greater
+ //! than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ iterator upper_bound(const key_type& x);
+
+ //! <b>Returns</b>: A const iterator pointing to the first element with key
+ //! greater than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
const_iterator upper_bound(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: An iterator pointing to the first element with key greater
+ //! than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ iterator upper_bound(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Returns</b>: A const iterator pointing to the first element with key
+ //! greater than x, or end() if such an element is not found.
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ const_iterator upper_bound(const K& x) const;
+
//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic
//! <b>Complexity</b>: Logarithmic
std::pair<const_iterator,const_iterator> equal_range(const key_type& x) const;
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ std::pair<iterator,iterator> equal_range(const K& x);
+
+ //! <b>Requires</b>: This overload is available only if
+ //! key_compare::is_transparent exists.
+ //!
+ //! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
+ //!
+ //! <b>Complexity</b>: Logarithmic
+ template<typename K>
+ std::pair<const_iterator,const_iterator> equal_range(const K& x) const;
+
//! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
//!
//! <b>Complexity</b>: Linear
#endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
};
+#ifndef BOOST_CONTAINER_NO_CXX17_CTAD
+
+template <typename InputIterator>
+multimap(InputIterator, InputIterator) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>>;
+
+template < typename InputIterator, typename AllocatorOrCompare>
+multimap(InputIterator, InputIterator, AllocatorOrCompare const&) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , typename dtl::if_c< // Compare
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , std::less<it_based_non_const_first_type_t<InputIterator>>
+ , AllocatorOrCompare
+ >::type
+ , typename dtl::if_c< // Allocator
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , AllocatorOrCompare
+ , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
+ >::type
+ >;
+
+template < typename InputIterator, typename Compare, typename Allocator
+ , typename = dtl::require_nonallocator_t<Compare>
+ , typename = dtl::require_allocator_t<Allocator>>
+multimap(InputIterator, InputIterator, Compare const&, Allocator const&) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , Compare
+ , Allocator>;
+
+template <typename InputIterator>
+multimap(ordered_range_t, InputIterator, InputIterator) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>>;
+
+template < typename InputIterator, typename AllocatorOrCompare>
+multimap(ordered_range_t, InputIterator, InputIterator, AllocatorOrCompare const&) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , typename dtl::if_c< // Compare
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , std::less<it_based_const_first_type_t<InputIterator>>
+ , AllocatorOrCompare
+ >::type
+ , typename dtl::if_c< // Allocator
+ dtl::is_allocator<AllocatorOrCompare>::value
+ , AllocatorOrCompare
+ , new_allocator<std::pair<it_based_const_first_type_t<InputIterator>, it_based_second_type_t<InputIterator>>>
+ >::type
+ >;
+
+template < typename InputIterator, typename Compare, typename Allocator
+ , typename = dtl::require_nonallocator_t<Compare>
+ , typename = dtl::require_allocator_t<Allocator>>
+multimap(ordered_range_t, InputIterator, InputIterator, Compare const&, Allocator const&) ->
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
+ , Compare
+ , Allocator>;
+#endif
+
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
} //namespace container {
//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
-template <class Key, class T, class Compare, class Allocator>
-struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator> >
+template <class Key, class T, class Compare, class Allocator, class Options>
+struct has_trivial_destructor_after_move<boost::container::multimap<Key, T, Compare, Allocator, Options> >
{
- 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;
+ typedef ::boost::container::dtl::tree<std::pair<const Key, T>, int, Compare, Allocator, Options> tree;
+ static const bool value = ::boost::has_trivial_destructor_after_move<tree>::value;
};
namespace container {
projects / ceph.git / blobdiff