198 changes: 195 additions & 3 deletions include/boost/container/flat_map.hpp
View file
Expand Up @@ -1302,12 +1302,44 @@ class flat_map
BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }

//! <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<class K>
BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
{ return dtl::force_copy<iterator>(m_flat_tree.find(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<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }

//! <b>Returns</b>: The number of elements with key equivalent to x.
//!
//! <b>Complexity</b>: log(size())+count(k)
BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
{ return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }

//! <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<class K>
BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
{ return static_cast<size_type>(m_flat_tree.find(x) != m_flat_tree.end()); }

//! <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.
//!
Expand All @@ -1322,6 +1354,28 @@ class flat_map
BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }

//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic.
template<class K>
BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
{ return dtl::force_copy<iterator>(m_flat_tree.lower_bound(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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic.
template<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }

//! <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.
//!
Expand All @@ -1336,6 +1390,28 @@ class flat_map
BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }

//! <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.
template<class K>
BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
{ return dtl::force_copy<iterator>(m_flat_tree.upper_bound(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<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }

//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic.
Expand All @@ -1348,6 +1424,26 @@ class flat_map
BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
{ return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(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<class K>
BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
{ return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.lower_bound_range(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<class K>
BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
{ return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.lower_bound_range(x)); }

//! <b>Effects</b>: Extracts the internal sequence container.
//!
//! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
Expand Down Expand Up @@ -2443,25 +2539,79 @@ class flat_multimap
BOOST_CONTAINER_FORCEINLINE const_iterator find(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }

//! <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<class K>
BOOST_CONTAINER_FORCEINLINE iterator find(const K& x)
{ return dtl::force_copy<iterator>(m_flat_tree.find(x)); }

//! <b>Requires</b>: This overload is available only if
//! key_compare::is_transparent exists.
//!
//! <b>Returns</b>: An 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<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator find(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.find(x)); }

//! <b>Returns</b>: The number of elements with key equivalent to x.
//!
//! <b>Complexity</b>: log(size())+count(k)
BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
{ return m_flat_tree.count(x); }

//! <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<class K>
BOOST_CONTAINER_FORCEINLINE size_type count(const K& x) const
{ return m_flat_tree.count(x); }

//! <b>Returns</b>: An iterator pointing to the first element with key not less
//! than k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const key_type& x)
{ return dtl::force_copy<iterator>(m_flat_tree.lower_bound(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.
//! <b>Returns</b>: An iterator pointing to the first element with key not less
//! than k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }
{ return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }

//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
template<class K>
BOOST_CONTAINER_FORCEINLINE iterator lower_bound(const K& x)
{ return dtl::force_copy<iterator>(m_flat_tree.lower_bound(x)); }

//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
template<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator lower_bound(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.lower_bound(x)); }

//! <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.
Expand All @@ -2477,6 +2627,28 @@ class flat_multimap
BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const key_type& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }

//! <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
template<class K>
BOOST_CONTAINER_FORCEINLINE iterator upper_bound(const K& x)
{return dtl::force_copy<iterator>(m_flat_tree.upper_bound(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<class K>
BOOST_CONTAINER_FORCEINLINE const_iterator upper_bound(const K& x) const
{ return dtl::force_copy<const_iterator>(m_flat_tree.upper_bound(x)); }

//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
//!
//! <b>Complexity</b>: Logarithmic
Expand All @@ -2489,6 +2661,26 @@ class flat_multimap
BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
{ return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(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<class K>
BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const K& x)
{ return dtl::force_copy<std::pair<iterator,iterator> >(m_flat_tree.equal_range(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<class K>
BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const K& x) const
{ return dtl::force_copy<std::pair<const_iterator,const_iterator> >(m_flat_tree.equal_range(x)); }

//! <b>Effects</b>: Extracts the internal sequence container.
//!
//! <b>Complexity</b>: Same as the move constructor of sequence_type, usually constant.
Expand Down
90 changes: 90 additions & 0 deletions include/boost/container/flat_set.hpp
View file
Expand Up @@ -823,6 +823,26 @@ class flat_set
//! <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>Requires</b>: size() >= n.
//!
//! <b>Effects</b>: Returns an iterator to the nth element
Expand Down Expand Up @@ -881,6 +901,16 @@ class flat_set
BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
{ return static_cast<size_type>(this->tree_t::find(x) != this->tree_t::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->tree_t::find(x) != this->tree_t::cend()); }

#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
//! <b>Returns</b>: An iterator pointing to the first element with key not less
//! than k, or a.end() if such an element is not found.
Expand All @@ -894,6 +924,26 @@ class flat_set
//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
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 k, or a.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 not less
//! than x, or end() if such an element is not found.
//!
Expand All @@ -906,6 +956,26 @@ class flat_set
//! <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 not less
//! 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 not
//! less 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;

#endif // #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Expand All @@ -920,6 +990,26 @@ class flat_set
BOOST_CONTAINER_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type& x)
{ return this->tree_t::lower_bound_range(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<iterator,iterator> equal_range(const K& x)
{ return this->tree_t::lower_bound_range(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
{ return this->tree_t::lower_bound_range(x); }

#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

//! <b>Effects</b>: Returns true if x and y are equal
Expand Down
175 changes: 175 additions & 0 deletions include/boost/container/map.hpp
View file
Expand Up @@ -1079,6 +1079,26 @@ class map
//! <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.
Expand All @@ -1087,6 +1107,16 @@ class map
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>: An iterator pointing to the first element with key not less
Expand All @@ -1101,6 +1131,26 @@ class map
//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
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 k, or a.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 not less
//! than x, or end() if such an element is not found.
//!
Expand All @@ -1113,6 +1163,26 @@ class map
//! <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 not less
//! 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 not
//! less 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
Expand All @@ -1123,6 +1193,24 @@ class map
//! <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
Expand Down Expand Up @@ -1841,11 +1929,40 @@ class multimap
//! <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>: An iterator pointing to the first element with key not less
//! than k, or a.end() if such an element is not found.
//!
Expand All @@ -1858,6 +1975,26 @@ class multimap
//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
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 k, or a.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 not less
//! than x, or end() if such an element is not found.
//!
Expand All @@ -1870,6 +2007,26 @@ class multimap
//! <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 not less
//! 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 not
//! less 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
Expand All @@ -1880,6 +2037,24 @@ class multimap
//! <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
Expand Down
124 changes: 120 additions & 4 deletions include/boost/container/set.hpp
View file
Expand Up @@ -734,6 +734,26 @@ class set
//! <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.
Expand All @@ -742,6 +762,16 @@ class set
BOOST_CONTAINER_FORCEINLINE size_type count(const key_type& x) const
{ return static_cast<size_type>(this->base_t::find(x) != this->base_t::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()); }

//! <b>Returns</b>: The number of elements with key equivalent to x.
//!
//! <b>Complexity</b>: log(size())+count(k)
Expand All @@ -762,6 +792,26 @@ class set
//! <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 k, or a.end() if such an element is not found.
//!
//! <b>Complexity</b>: Logarithmic
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 k, or a.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 not less
//! than x, or end() if such an element is not found.
//!
Expand All @@ -774,6 +824,26 @@ class set
//! <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 not less
//! 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 not
//! less 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;

#endif //#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

//! <b>Effects</b>: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)).
Expand All @@ -788,17 +858,27 @@ class set
BOOST_CONTAINER_FORCEINLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
{ return this->base_t::lower_bound_range(x); }

#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

//! <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
std::pair<iterator,iterator> equal_range(const key_type& x);
template<typename K>
std::pair<iterator,iterator> equal_range(const K& x)
{ return this->base_t::lower_bound_range(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
std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;
template<typename K>
std::pair<const_iterator,const_iterator> equal_range(const K& x) const
{ return this->base_t::lower_bound_range(x); }

#if defined(BOOST_CONTAINER_DOXYGEN_INVOKED)

//! <b>Effects</b>: Rebalances the tree. It's a no-op for Red-Black and AVL trees.
//!
Expand Down Expand Up @@ -1330,27 +1410,63 @@ class multiset
//! @copydoc ::boost::container::set::find(const key_type& ) const
const_iterator find(const key_type& x) const;

//! @copydoc ::boost::container::set::find(const K& )
template<typename K>
iterator find(const K& x);

//! @copydoc ::boost::container::set::find(const K& )
template<typename K>
const_iterator find(const K& x) const;

//! @copydoc ::boost::container::set::count(const key_type& ) const
size_type count(const key_type& x) const;

//! @copydoc ::boost::container::set::count(const K& ) const
template<typename K>
size_type count(const K& x) const;

//! @copydoc ::boost::container::set::lower_bound(const key_type& )
iterator lower_bound(const key_type& x);

//! @copydoc ::boost::container::set::lower_bound(const key_type& ) const
const_iterator lower_bound(const key_type& x) const;

//! @copydoc ::boost::container::set::lower_bound(const K& )
template<typename K>
iterator lower_bound(const K& x);

//! @copydoc ::boost::container::set::lower_bound(const K& ) const
template<typename K>
const_iterator lower_bound(const K& x) const;

//! @copydoc ::boost::container::set::upper_bound(const key_type& )
iterator upper_bound(const key_type& x);

//! @copydoc ::boost::container::set::upper_bound(const key_type& ) const
const_iterator upper_bound(const key_type& x) const;

//! @copydoc ::boost::container::set::upper_bound(const K& )
template<typename K>
iterator upper_bound(const K& x);

//! @copydoc ::boost::container::set::upper_bound(const K& ) const
template<typename K>
const_iterator upper_bound(const K& x) const;

//! @copydoc ::boost::container::set::equal_range(const key_type& ) const
std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const;

//! @copydoc ::boost::container::set::equal_range(const key_type& )
std::pair<iterator,iterator> equal_range(const key_type& x);

//! @copydoc ::boost::container::set::equal_range(const K& ) const
template<typename K>
std::pair<const_iterator, const_iterator> equal_range(const K& x) const;

//! @copydoc ::boost::container::set::equal_range(const K& )
template<typename K>
std::pair<iterator,iterator> equal_range(const K& x);

//! @copydoc ::boost::container::set::rebalance()
void rebalance();

Expand Down
11 changes: 11 additions & 0 deletions test/check_equal_containers.hpp
View file
Expand Up @@ -108,6 +108,17 @@ bool CheckEqualPairContainers(const MyBoostCont &boostcont, const MyStdCont &std
return true;
}

struct less_transparent
{
typedef void is_transparent;

template<class T, class U>
bool operator()(const T &t, const U &u) const
{
return t < u;
}
};

} //namespace test{
} //namespace container {
} //namespace boost{
Expand Down
82 changes: 82 additions & 0 deletions test/flat_map_test.cpp
View file
Expand Up @@ -422,6 +422,85 @@ struct get_real_stored_allocator<flat_multimap<Key, T, Compare, Allocator> >
typedef typename flat_multimap<Key, T, Compare, Allocator>::impl_stored_allocator_type type;
};

bool test_heterogeneous_lookups()
{
typedef flat_map<int, char, less_transparent> map_t;
typedef flat_multimap<int, char, less_transparent> mmap_t;
typedef map_t::value_type value_type;

map_t map1;
mmap_t mmap1;

const map_t &cmap1 = map1;
const mmap_t &cmmap1 = mmap1;

map1.insert_or_assign(1, 'a');
map1.insert_or_assign(1, 'b');
map1.insert_or_assign(2, 'c');
map1.insert_or_assign(2, 'd');
map1.insert_or_assign(3, 'e');

mmap1.insert(value_type(1, 'a'));
mmap1.insert(value_type(1, 'b'));
mmap1.insert(value_type(2, 'c'));
mmap1.insert(value_type(2, 'd'));
mmap1.insert(value_type(3, 'e'));

const test::non_copymovable_int find_me(2);

//find
if(map1.find(find_me)->second != 'd')
return false;
if(cmap1.find(find_me)->second != 'd')
return false;
if(mmap1.find(find_me)->second != 'c')
return false;
if(cmmap1.find(find_me)->second != 'c')
return false;

//count
if(map1.count(find_me) != 1)
return false;
if(cmap1.count(find_me) != 1)
return false;
if(mmap1.count(find_me) != 2)
return false;
if(cmmap1.count(find_me) != 2)
return false;

//lower_bound
if(map1.lower_bound(find_me)->second != 'd')
return false;
if(cmap1.lower_bound(find_me)->second != 'd')
return false;
if(mmap1.lower_bound(find_me)->second != 'c')
return false;
if(cmmap1.lower_bound(find_me)->second != 'c')
return false;

//upper_bound
if(map1.upper_bound(find_me)->second != 'e')
return false;
if(cmap1.upper_bound(find_me)->second != 'e')
return false;
if(mmap1.upper_bound(find_me)->second != 'e')
return false;
if(cmmap1.upper_bound(find_me)->second != 'e')
return false;

//equal_range
if(map1.equal_range(find_me).first->second != 'd')
return false;
if(cmap1.equal_range(find_me).second->second != 'e')
return false;
if(mmap1.equal_range(find_me).first->second != 'c')
return false;
if(cmmap1.equal_range(find_me).second->second != 'e')
return false;

return true;
}

}}} //namespace boost::container::test

template<class VoidAllocatorOrContainer>
Expand Down Expand Up @@ -527,6 +606,9 @@ int main()
if (!boost::container::test::instantiate_constructors<flat_map<int, int>, flat_multimap<int, int> >())
return 1;

if (!test_heterogeneous_lookups())
return 1;

////////////////////////////////////
// Testing allocator implementations
////////////////////////////////////
Expand Down
82 changes: 82 additions & 0 deletions test/flat_set_test.cpp
View file
Expand Up @@ -450,6 +450,84 @@ bool flat_tree_extract_adopt_test()
return true;
}

bool test_heterogeneous_lookups()
{
typedef flat_set<int, test::less_transparent> set_t;
typedef flat_multiset<int, test::less_transparent> mset_t;

set_t set1;
mset_t mset1;

const set_t &cset1 = set1;
const mset_t &cmset1 = mset1;

set1.insert(1);
set1.insert(1);
set1.insert(2);
set1.insert(2);
set1.insert(3);

mset1.insert(1);
mset1.insert(1);
mset1.insert(2);
mset1.insert(2);
mset1.insert(3);

const test::non_copymovable_int find_me(2);

//find
if(*set1.find(find_me) != 2)
return false;
if(*cset1.find(find_me) != 2)
return false;
if(*mset1.find(find_me) != 2)
return false;
if(*cmset1.find(find_me) != 2)
return false;

//count
if(set1.count(find_me) != 1)
return false;
if(cset1.count(find_me) != 1)
return false;
if(mset1.count(find_me) != 2)
return false;
if(cmset1.count(find_me) != 2)
return false;

//lower_bound
if(*set1.lower_bound(find_me) != 2)
return false;
if(*cset1.lower_bound(find_me) != 2)
return false;
if(*mset1.lower_bound(find_me) != 2)
return false;
if(*cmset1.lower_bound(find_me) != 2)
return false;

//upper_bound
if(*set1.upper_bound(find_me) != 3)
return false;
if(*cset1.upper_bound(find_me) != 3)
return false;
if(*mset1.upper_bound(find_me) != 3)
return false;
if(*cmset1.upper_bound(find_me) != 3)
return false;

//equal_range
if(*set1.equal_range(find_me).first != 2)
return false;
if(*cset1.equal_range(find_me).second != 3)
return false;
if(*mset1.equal_range(find_me).first != 2)
return false;
if(*cmset1.equal_range(find_me).second != 3)
return false;

return true;
}

}}}

template<class VoidAllocatorOrContainer>
Expand Down Expand Up @@ -636,6 +714,10 @@ int main()
if (!boost::container::test::instantiate_constructors<flat_set<int>, flat_multiset<int> >())
return 1;

if(!test_heterogeneous_lookups()){
return 1;
}

////////////////////////////////////
// Testing allocator implementations
////////////////////////////////////
Expand Down
82 changes: 82 additions & 0 deletions test/map_test.cpp
View file
Expand Up @@ -320,6 +320,85 @@ void test_merge_from_different_comparison()
map1.merge(map2);
}

bool test_heterogeneous_lookups()
{
typedef map<int, char, less_transparent> map_t;
typedef multimap<int, char, less_transparent> mmap_t;
typedef map_t::value_type value_type;

map_t map1;
mmap_t mmap1;

const map_t &cmap1 = map1;
const mmap_t &cmmap1 = mmap1;

map1.insert_or_assign(1, 'a');
map1.insert_or_assign(1, 'b');
map1.insert_or_assign(2, 'c');
map1.insert_or_assign(2, 'd');
map1.insert_or_assign(3, 'e');

mmap1.insert(value_type(1, 'a'));
mmap1.insert(value_type(1, 'b'));
mmap1.insert(value_type(2, 'c'));
mmap1.insert(value_type(2, 'd'));
mmap1.insert(value_type(3, 'e'));

const test::non_copymovable_int find_me(2);

//find
if(map1.find(find_me)->second != 'd')
return false;
if(cmap1.find(find_me)->second != 'd')
return false;
if(mmap1.find(find_me)->second != 'c')
return false;
if(cmmap1.find(find_me)->second != 'c')
return false;

//count
if(map1.count(find_me) != 1)
return false;
if(cmap1.count(find_me) != 1)
return false;
if(mmap1.count(find_me) != 2)
return false;
if(cmmap1.count(find_me) != 2)
return false;

//lower_bound
if(map1.lower_bound(find_me)->second != 'd')
return false;
if(cmap1.lower_bound(find_me)->second != 'd')
return false;
if(mmap1.lower_bound(find_me)->second != 'c')
return false;
if(cmmap1.lower_bound(find_me)->second != 'c')
return false;

//upper_bound
if(map1.upper_bound(find_me)->second != 'e')
return false;
if(cmap1.upper_bound(find_me)->second != 'e')
return false;
if(mmap1.upper_bound(find_me)->second != 'e')
return false;
if(cmmap1.upper_bound(find_me)->second != 'e')
return false;

//equal_range
if(map1.equal_range(find_me).first->second != 'd')
return false;
if(cmap1.equal_range(find_me).second->second != 'e')
return false;
if(mmap1.equal_range(find_me).first->second != 'c')
return false;
if(cmmap1.equal_range(find_me).second->second != 'e')
return false;

return true;
}

}}} //namespace boost::container::test

int main ()
Expand Down Expand Up @@ -437,6 +516,9 @@ int main ()

test::test_merge_from_different_comparison();

if(!test::test_heterogeneous_lookups())
return 1;

////////////////////////////////////
// Test optimize_size option
////////////////////////////////////
Expand Down
24 changes: 24 additions & 0 deletions test/movable_int.hpp
View file
Expand Up @@ -97,6 +97,12 @@ class movable_int
friend bool operator==(int l, const movable_int &r)
{ return l == r.get_int(); }

friend bool operator<(const movable_int &l, int r)
{ return l.get_int() < r; }

friend bool operator<(int l, const movable_int &r)
{ return l < r.get_int(); }

private:
int m_int;
};
Expand Down Expand Up @@ -193,6 +199,12 @@ class movable_and_copyable_int
friend bool operator==(int l, const movable_and_copyable_int &r)
{ return l == r.get_int(); }

friend bool operator<(const movable_and_copyable_int &l, int r)
{ return l.get_int() < r; }

friend bool operator<(int l, const movable_and_copyable_int &r)
{ return l < r.get_int(); }

private:
int m_int;
};
Expand Down Expand Up @@ -280,6 +292,12 @@ class copyable_int
friend bool operator==(int l, const copyable_int &r)
{ return l == r.get_int(); }

friend bool operator<(const copyable_int &l, int r)
{ return l.get_int() < r; }

friend bool operator<(int l, const copyable_int &r)
{ return l < r.get_int(); }

private:
int m_int;
};
Expand Down Expand Up @@ -351,6 +369,12 @@ class non_copymovable_int
friend bool operator==(int l, const non_copymovable_int &r)
{ return l == r.get_int(); }

friend bool operator<(const non_copymovable_int &l, int r)
{ return l.get_int() < r; }

friend bool operator<(int l, const non_copymovable_int &r)
{ return l < r.get_int(); }

private:
int m_int;
};
Expand Down
81 changes: 81 additions & 0 deletions test/set_test.cpp
View file
Expand Up @@ -318,6 +318,84 @@ void test_merge_from_different_comparison()
set1.merge(set2);
}

bool test_heterogeneous_lookups()
{
typedef set<int, test::less_transparent> set_t;
typedef multiset<int, test::less_transparent> mset_t;

set_t set1;
mset_t mset1;

const set_t &cset1 = set1;
const mset_t &cmset1 = mset1;

set1.insert(1);
set1.insert(1);
set1.insert(2);
set1.insert(2);
set1.insert(3);

mset1.insert(1);
mset1.insert(1);
mset1.insert(2);
mset1.insert(2);
mset1.insert(3);

const test::non_copymovable_int find_me(2);

//find
if(*set1.find(find_me) != 2)
return false;
if(*cset1.find(find_me) != 2)
return false;
if(*mset1.find(find_me) != 2)
return false;
if(*cmset1.find(find_me) != 2)
return false;

//count
if(set1.count(find_me) != 1)
return false;
if(cset1.count(find_me) != 1)
return false;
if(mset1.count(find_me) != 2)
return false;
if(cmset1.count(find_me) != 2)
return false;

//lower_bound
if(*set1.lower_bound(find_me) != 2)
return false;
if(*cset1.lower_bound(find_me) != 2)
return false;
if(*mset1.lower_bound(find_me) != 2)
return false;
if(*cmset1.lower_bound(find_me) != 2)
return false;

//upper_bound
if(*set1.upper_bound(find_me) != 3)
return false;
if(*cset1.upper_bound(find_me) != 3)
return false;
if(*mset1.upper_bound(find_me) != 3)
return false;
if(*cmset1.upper_bound(find_me) != 3)
return false;

//equal_range
if(*set1.equal_range(find_me).first != 2)
return false;
if(*cset1.equal_range(find_me).second != 3)
return false;
if(*mset1.equal_range(find_me).first != 2)
return false;
if(*cmset1.equal_range(find_me).second != 3)
return false;

return true;
}

int main ()
{
//Recursive container instantiation
Expand Down Expand Up @@ -349,6 +427,9 @@ int main ()

test_merge_from_different_comparison();

if(!test_heterogeneous_lookups())
return 1;

////////////////////////////////////
// Testing allocator implementations
////////////////////////////////////
Expand Down