summaryrefslogtreecommitdiff
path: root/boost/container/map.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/container/map.hpp')
-rw-r--r--boost/container/map.hpp239
1 files changed, 160 insertions, 79 deletions
diff --git a/boost/container/map.hpp b/boost/container/map.hpp
index a88b6a5558..8592c2cb83 100644
--- a/boost/container/map.hpp
+++ b/boost/container/map.hpp
@@ -256,6 +256,22 @@ class map
: 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()).
@@ -1119,6 +1135,22 @@ class map
#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.
//!
@@ -1263,55 +1295,65 @@ class map
#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED
};
-#if __cplusplus >= 201703L
+#ifndef BOOST_CONTAINER_NO_CXX17_CTAD
template <typename InputIterator>
map(InputIterator, InputIterator) ->
- map< typename dtl::remove_const< typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type>;
-
-template <typename InputIterator, typename Allocator>
-map(InputIterator, InputIterator, Allocator const&) ->
- map< typename dtl::remove_const< typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , std::less<typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type>
- , Allocator>;
-
-template <typename InputIterator, typename Compare>
-map(InputIterator, InputIterator, Compare const&) ->
- map< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , Compare>;
-
-template <typename InputIterator, typename Compare, typename Allocator>
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type>;
-
-template <typename InputIterator, typename Allocator>
-map(ordered_unique_range_t, InputIterator, InputIterator, Allocator const&) ->
- map< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , std::less<typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type>
- , Allocator>;
-
-template <typename InputIterator, typename Compare>
-map(ordered_unique_range_t, InputIterator, InputIterator, Compare const&) ->
- map< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , Compare>;
-
-template <typename InputIterator, typename Compare, typename Allocator>
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
+ map< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
, Compare
, Allocator>;
@@ -1536,6 +1578,20 @@ class multimap
: 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()).
@@ -2017,6 +2073,22 @@ class multimap
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.
//!
@@ -2152,58 +2224,67 @@ class multimap
#endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
};
-#if __cplusplus >= 201703L
+#ifndef BOOST_CONTAINER_NO_CXX17_CTAD
template <typename InputIterator>
multimap(InputIterator, InputIterator) ->
- multimap<typename dtl::remove_const< typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type>;
-
-template <typename InputIterator, typename Allocator>
-multimap(InputIterator, InputIterator, Allocator const&) ->
- multimap<typename dtl::remove_const< typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , std::less<typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type>
- , Allocator>;
-
-template <typename InputIterator, typename Compare>
-multimap(InputIterator, InputIterator, Compare const&) ->
- multimap< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , Compare>;
-
-template <typename InputIterator, typename Compare, typename Allocator>
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type>;
-
-template <typename InputIterator, typename Allocator>
-multimap(ordered_range_t, InputIterator, InputIterator, Allocator const&) ->
- multimap< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , std::less<typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type>
- , Allocator>;
-
-template <typename InputIterator, typename Compare>
-multimap(ordered_range_t, InputIterator, InputIterator, Compare const&) ->
- multimap< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
- , Compare>;
-
-template <typename InputIterator, typename Compare, typename Allocator>
+ 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< typename dtl::remove_const<typename iterator_traits<InputIterator>::value_type::first_type>::type
- , typename iterator_traits<InputIterator>::value_type::second_type
+ multimap< it_based_non_const_first_type_t<InputIterator>
+ , it_based_second_type_t<InputIterator>
, Compare
, Allocator>;
-
#endif
#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED