[patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 174 bytes --]

This is the last missing piece of the C++14 library, as proposed in
http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3657.htm

Tested x86_64-linux, *not* committed.


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 35528 bytes --]

commit 99d7d1ebce9f290220966e138ef9b9e741878917
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jan 19 17:05:34 2015 +0000

    Implement N3657: heterogeneous lookup in associative containers.
    
    	* include/bits/stl_map.h (map::find<>, map::count<>,
    	map::lower_bound<>, map::upper_bound<>, map::equal_range<>): New
    	member function templates to perform heterogeneous lookup.
    	* include/bits/stl_multimap.h (multimap::find<>, multimap::count<>,
    	multimap::lower_bound<>, multimap::upper_bound<>,
    	multimap::equal_range<>): Likewise.
    	* include/bits/stl_multiset.h (multiset::find<>, multiset::count<>,
    	multiset::lower_bound<>, multiset::upper_bound<>,
    	multiset::equal_range<>): Likewise.
    	* include/bits/stl_set.h (set::find<>, set::count<>,
    	set::lower_bound<>, set::upper_bound<>, set::equal_range<>): Likewise.
    	* include/bits/stl_tree.h (_Rb_tree::_S_lower_bound_tr,
    	_Rb_tree::_S_upper_bound_tr, _Rb_tree::_M_find_tr,
    	_Rb_tree::_M_count_tr, _Rb_tree::_M_lower_bound_tr,
    	_Rb_tree::_M_upper_bound_tr, _Rb_tree::_M_equal_range_tr): Likewise.
    	* testsuite/23_containers/map/operations/2.cc: New.
    	* testsuite/23_containers/multimap/operations/2.cc: New.
    	* testsuite/23_containers/multiset/operations/2.cc: New.
    	* testsuite/23_containers/set/operations/2.cc: New.

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index 3bac4e0..df18973 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -824,6 +824,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return value_compare(_M_t.key_comp()); }
 
       // [23.3.1.3] map operations
+
+      //@{
       /**
        *  @brief Tries to locate an element in a %map.
        *  @param  __x  Key of (key, value) %pair to be located.
@@ -835,10 +837,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  pointing to the sought after %pair.  If unsuccessful it returns the
        *  past-the-end ( @c end() ) iterator.
        */
+
       iterator
       find(const key_type& __x)
       { return _M_t.find(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Tries to locate an element in a %map.
        *  @param  __x  Key of (key, value) %pair to be located.
@@ -850,10 +862,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  iterator pointing to the sought after %pair. If unsuccessful it
        *  returns the past-the-end ( @c end() ) iterator.
        */
+
       const_iterator
       find(const key_type& __x) const
       { return _M_t.find(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief  Finds the number of elements with given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -866,6 +888,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       count(const key_type& __x) const
       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
+	{ return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the beginning of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -881,6 +912,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       lower_bound(const key_type& __x)
       { return _M_t.lower_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x)
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the beginning of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -896,6 +937,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       lower_bound(const key_type& __x) const
       { return _M_t.lower_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the end of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -906,6 +957,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       upper_bound(const key_type& __x)
       { return _M_t.upper_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x)
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the end of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -916,6 +977,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       upper_bound(const key_type& __x) const
       { return _M_t.upper_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds a subsequence matching given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -935,6 +1006,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds a subsequence matching given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -954,6 +1035,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
+      //@}
+
       template<typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
         operator==(const map<_K1, _T1, _C1, _A1>&,
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 5a81f8f..f3d21ab 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -734,6 +734,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       { return value_compare(_M_t.key_comp()); }
 
       // multimap operations
+
+      //@{
       /**
        *  @brief Tries to locate an element in a %multimap.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -749,6 +751,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x)
       { return _M_t.find(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Tries to locate an element in a %multimap.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -764,6 +775,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       find(const key_type& __x) const
       { return _M_t.find(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the number of elements with given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -773,6 +793,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       count(const key_type& __x) const
       { return _M_t.count(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
+	{ return _M_t._M_count_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the beginning of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -788,6 +817,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       lower_bound(const key_type& __x)
       { return _M_t.lower_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x)
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the beginning of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -803,6 +842,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       lower_bound(const key_type& __x) const
       { return _M_t.lower_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the end of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -813,6 +862,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       upper_bound(const key_type& __x)
       { return _M_t.upper_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x)
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds the end of a subsequence matching given key.
        *  @param  __x  Key of (key, value) pair to be located.
@@ -823,6 +882,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       upper_bound(const key_type& __x) const
       { return _M_t.upper_bound(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds a subsequence matching given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -840,6 +909,16 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x)
       { return _M_t.equal_range(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
+      //@}
+
+      //@{
       /**
        *  @brief Finds a subsequence matching given key.
        *  @param  __x  Key of (key, value) pairs to be located.
@@ -857,6 +936,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
+      //@}
+
       template<typename _K1, typename _T1, typename _C1, typename _A1>
         friend bool
         operator==(const multimap<_K1, _T1, _C1, _A1>&,
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index be04221..7e92836 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -636,6 +636,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       // multiset operations:
 
+      //@{
       /**
        *  @brief Finds the number of elements with given key.
        *  @param  __x  Key of elements to be located.
@@ -645,6 +646,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       count(const key_type& __x) const
       { return _M_t.count(__x); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const -> decltype(_M_t._M_count_tr(__x))
+	{ return _M_t._M_count_tr(__x); }
+#endif
+      //@}
+
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 214.  set::find() missing const overload
       //@{
@@ -666,6 +675,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       find(const key_type& __x) const
       { return _M_t.find(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -687,6 +708,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       lower_bound(const key_type& __x) const
       { return _M_t.lower_bound(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x)
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -703,6 +738,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       upper_bound(const key_type& __x) const
       { return _M_t.upper_bound(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x)
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -728,6 +777,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
       //@}
 
       template<typename _K1, typename _C1, typename _A1>
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 3944bcd..5189234 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -651,6 +651,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       // set operations:
 
+      //@{
       /**
        *  @brief  Finds the number of elements.
        *  @param  __x  Element to located.
@@ -663,6 +664,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       count(const key_type& __x) const
       { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	count(const _Kt& __x) const
+	-> decltype(_M_t._M_count_tr(__x))
+	{ return _M_t._M_find_tr(__x) == _M_t.end() ? 0 : 1; }
+#endif
+      //@}
+
       // _GLIBCXX_RESOLVE_LIB_DEFECTS
       // 214.  set::find() missing const overload
       //@{
@@ -684,6 +694,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       find(const key_type& __x) const
       { return _M_t.find(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	find(const _Kt& __x) const -> decltype(_M_t._M_find_tr(__x))
+	{ return _M_t._M_find_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -705,6 +727,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       lower_bound(const key_type& __x) const
       { return _M_t.lower_bound(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x)
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	lower_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_lower_bound_tr(__x))
+	{ return _M_t._M_lower_bound_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -721,6 +757,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator
       upper_bound(const key_type& __x) const
       { return _M_t.upper_bound(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x)
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	upper_bound(const _Kt& __x) const
+	-> decltype(_M_t._M_upper_bound_tr(__x))
+	{ return _M_t._M_upper_bound_tr(__x); }
+#endif
       //@}
 
       //@{
@@ -746,6 +796,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       std::pair<const_iterator, const_iterator>
       equal_range(const key_type& __x) const
       { return _M_t.equal_range(__x); }
+
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x)
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+
+      template<typename _Kt>
+	auto
+	equal_range(const _Kt& __x) const
+	-> decltype(_M_t._M_equal_range_tr(__x))
+	{ return _M_t._M_equal_range_tr(__x); }
+#endif
       //@}
 
       template<typename _K1, typename _C1, typename _A1>
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index e78b2db..5ca8e28 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1118,6 +1118,137 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       pair<const_iterator, const_iterator>
       equal_range(const key_type& __k) const;
 
+#if __cplusplus > 201103L
+      template<typename _Cmp, typename _Kt, typename = __void_t<>>
+	struct __is_transparent { };
+
+      template<typename _Cmp, typename _Kt>
+	struct
+	__is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
+	{ typedef void type; };
+
+      static auto _S_iter(_Link_type __x) { return iterator(__x); }
+
+      static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
+
+      template<typename _Cmp, typename _Link, typename _Kt>
+	static auto
+	_S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
+	{
+	  while (__x != 0)
+	    if (!__cmp(_S_key(__x), __k))
+	      __y = __x, __x = _S_left(__x);
+	    else
+	      __x = _S_right(__x);
+	  return _S_iter(__y);
+	}
+
+      template<typename _Cmp, typename _Link, typename _Kt>
+	static auto
+	_S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
+	{
+	  while (__x != 0)
+	    if (__cmp(__k, _S_key(__x)))
+	      __y = __x, __x = _S_left(__x);
+	    else
+	      __x = _S_right(__x);
+	  return _S_iter(__y);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	iterator
+	_M_find_tr(const _Kt& __k)
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	  return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
+	    ? end() : __j;
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	_M_find_tr(const _Kt& __k) const
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	  return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
+	    ? end() : __j;
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	size_type
+	_M_count_tr(const _Kt& __k) const
+	{
+	  auto __p = _M_equal_range_tr(__k);
+	  return std::distance(__p.first, __p.second);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	iterator
+	_M_lower_bound_tr(const _Kt& __k)
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	_M_lower_bound_tr(const _Kt& __k) const
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	iterator
+	_M_upper_bound_tr(const _Kt& __k)
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	_M_upper_bound_tr(const _Kt& __k) const
+	{
+	  auto& __cmp = _M_impl._M_key_compare;
+	  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	pair<iterator, iterator>
+	_M_equal_range_tr(const _Kt& __k)
+	{
+	  auto __low = _M_lower_bound_tr(__k);
+	  auto __high = __low;
+	  auto& __cmp = _M_impl._M_key_compare;
+	  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
+	    ++__high;
+	  return { __low, __high };
+	}
+
+      template<typename _Kt,
+	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	pair<const_iterator, const_iterator>
+	_M_equal_range_tr(const _Kt& __k) const
+	{
+	  auto __low = _M_lower_bound_tr(__k);
+	  auto __high = __low;
+	  auto& __cmp = _M_impl._M_key_compare;
+	  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
+	    ++__high;
+	  return { __low, __high };
+	}
+#endif
+
       // Debugging.
       bool
       __rb_verify() const;
diff --git a/libstdc++-v3/testsuite/23_containers/map/operations/2.cc b/libstdc++-v3/testsuite/23_containers/map/operations/2.cc
new file mode 100644
index 0000000..6cc277a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/operations/2.cc
@@ -0,0 +1,140 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+
+#include <map>
+#include <testsuite_hooks.h>
+
+struct Cmp
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i < l; }
+  bool operator()(long l, int i) const { return l < i; }
+  bool operator()(int i, int j) const { ++count; return i < j; }
+
+  static int count;
+};
+
+int Cmp::count = 0;
+
+using test_type = std::map<int, char, Cmp>;
+
+test_type x{ { 1, '2' }, { 3, '4' } };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Cmp::count = 0;
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test02()
+{
+  Cmp::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 1 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test03()
+{
+  Cmp::count = 0;
+
+  auto it = x.lower_bound(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.lower_bound(2L);
+  VERIFY( it != x.end() && it->second == '4' );
+
+  auto cit = cx.lower_bound(1L);
+  VERIFY( cit != cx.end() && cit->second == '2' );
+  cit = cx.lower_bound(2L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test04()
+{
+  Cmp::count = 0;
+
+  auto it = x.upper_bound(1L);
+  VERIFY( it != x.end() && it->second == '4' );
+  it = x.upper_bound(3L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.upper_bound(1L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+  cit = cx.upper_bound(3L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test05()
+{
+  Cmp::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && it.first->second == '2' );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first != x.end() );
+
+  auto cit = cx.equal_range(1L);
+  VERIFY( cit.first != cit.second && cit.first->second == '2' );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first != cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc b/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc
new file mode 100644
index 0000000..67c3bfd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multimap/operations/2.cc
@@ -0,0 +1,141 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+
+#include <map>
+#include <testsuite_hooks.h>
+
+struct Cmp
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i < l; }
+  bool operator()(long l, int i) const { return l < i; }
+  bool operator()(int i, int j) const { ++count; return i < j; }
+
+  static int count;
+};
+
+int Cmp::count = 0;
+
+using test_type = std::multimap<int, char, Cmp>;
+
+test_type x{ { 1, '2' }, { 3, '4' }, { 3, '5' } };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Cmp::count = 0;
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test02()
+{
+  Cmp::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 2 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test03()
+{
+  Cmp::count = 0;
+
+  auto it = x.lower_bound(1L);
+  VERIFY( it != x.end() && it->second == '2' );
+  it = x.lower_bound(2L);
+  VERIFY( it != x.end() && it->second == '4' );
+
+  auto cit = cx.lower_bound(1L);
+  VERIFY( cit != cx.end() && cit->second == '2' );
+  cit = cx.lower_bound(2L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test04()
+{
+  Cmp::count = 0;
+
+  auto it = x.upper_bound(1L);
+  VERIFY( it != x.end() && it->second == '4' );
+  it = x.upper_bound(3L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.upper_bound(1L);
+  VERIFY( cit != cx.end() && cit->second == '4' );
+  cit = cx.upper_bound(3L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test05()
+{
+  Cmp::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && it.first->second == '2' );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first != x.end() );
+
+  auto cit = cx.equal_range(3L);
+  VERIFY( cit.first != cit.second && cit.first->second == '4' );
+  VERIFY( std::distance(cit.first, cit.second) == 2 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first != cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc b/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc
new file mode 100644
index 0000000..ff2748f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/multiset/operations/2.cc
@@ -0,0 +1,141 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+
+#include <set>
+#include <testsuite_hooks.h>
+
+struct Cmp
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i < l; }
+  bool operator()(long l, int i) const { return l < i; }
+  bool operator()(int i, int j) const { ++count; return i < j; }
+
+  static int count;
+};
+
+int Cmp::count = 0;
+
+using test_type = std::multiset<int, Cmp>;
+
+test_type x{ 1, 3, 3, 5 };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Cmp::count = 0;
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test02()
+{
+  Cmp::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 2 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test03()
+{
+  Cmp::count = 0;
+
+  auto it = x.lower_bound(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.lower_bound(2L);
+  VERIFY( it != x.end() && *it == 3 );
+
+  auto cit = cx.lower_bound(1L);
+  VERIFY( cit != cx.end() && *cit == 1 );
+  cit = cx.lower_bound(2L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test04()
+{
+  Cmp::count = 0;
+
+  auto it = x.upper_bound(1L);
+  VERIFY( it != x.end() && *it == 3 );
+  it = x.upper_bound(5L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.upper_bound(1L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.upper_bound(5L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test05()
+{
+  Cmp::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && *it.first == 1 );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first != x.end() );
+
+  auto cit = cx.equal_range(3L);
+  VERIFY( cit.first != cit.second && *cit.first == 3 );
+  VERIFY( std::distance(cit.first, cit.second) == 2 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first != cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/set/operations/2.cc b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc
new file mode 100644
index 0000000..752bc7d
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc
@@ -0,0 +1,140 @@
+// Copyright (C) 2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++14" }
+
+#include <set>
+#include <testsuite_hooks.h>
+
+struct Cmp
+{
+  typedef void is_transparent;
+
+  bool operator()(int i, long l) const { return i < l; }
+  bool operator()(long l, int i) const { return l < i; }
+  bool operator()(int i, int j) const { ++count; return i < j; }
+
+  static int count;
+};
+
+int Cmp::count = 0;
+
+using test_type = std::set<int, Cmp>;
+
+test_type x{ 1, 3, 5 };
+const test_type& cx = x;
+
+void
+test01()
+{
+  Cmp::count = 0;
+
+  auto it = x.find(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.find(2L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.find(3L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.find(2L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test02()
+{
+  Cmp::count = 0;
+
+  auto n = x.count(1L);
+  VERIFY( n == 1 );
+  n = x.count(2L);
+  VERIFY( n == 0 );
+
+  auto cn = cx.count(3L);
+  VERIFY( cn == 1 );
+  cn = cx.count(2L);
+  VERIFY( cn == 0 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test03()
+{
+  Cmp::count = 0;
+
+  auto it = x.lower_bound(1L);
+  VERIFY( it != x.end() && *it == 1 );
+  it = x.lower_bound(2L);
+  VERIFY( it != x.end() && *it == 3 );
+
+  auto cit = cx.lower_bound(1L);
+  VERIFY( cit != cx.end() && *cit == 1 );
+  cit = cx.lower_bound(2L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test04()
+{
+  Cmp::count = 0;
+
+  auto it = x.upper_bound(1L);
+  VERIFY( it != x.end() && *it == 3 );
+  it = x.upper_bound(5L);
+  VERIFY( it == x.end() );
+
+  auto cit = cx.upper_bound(1L);
+  VERIFY( cit != cx.end() && *cit == 3 );
+  cit = cx.upper_bound(5L);
+  VERIFY( cit == cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+void
+test05()
+{
+  Cmp::count = 0;
+
+  auto it = x.equal_range(1L);
+  VERIFY( it.first != it.second && *it.first == 1 );
+  it = x.equal_range(2L);
+  VERIFY( it.first == it.second && it.first != x.end() );
+
+  auto cit = cx.equal_range(1L);
+  VERIFY( cit.first != cit.second && *cit.first == 1 );
+  cit = cx.equal_range(2L);
+  VERIFY( cit.first == cit.second && cit.first != cx.end() );
+
+  VERIFY( Cmp::count == 0);
+}
+
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+  test05();
+}

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

On 19/01/15 17:16 +0000, Jonathan Wakely wrote:
>This is the last missing piece of the C++14 library, as proposed in
>http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3657.htm
>
>Tested x86_64-linux, *not* committed.

Now committed to trunk.

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1160 bytes --]

On 20/01/2015 13:00, Jonathan Wakely wrote:
> On 19/01/15 17:16 +0000, Jonathan Wakely wrote:
>> This is the last missing piece of the C++14 library, as proposed in
>> http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3657.htm
>>
>> Tested x86_64-linux, *not* committed.
>
> Now committed to trunk.
>
Is it ok then to commit attached patch to do the same for debug mode ?

And also for profile mode later when I have it ready (this WE I think) ?

2015-01-22  François Dumont  <fdumont@gcc.gnu.org>

     * include/debug/stl_map.h (map::find<>,
     map::lower_bound<>, map::upper_bound<>, map::equal_range<>): New
     member function templates to perform heterogeneous lookup.
     * include/debug/stl_multimap.h (multimap::find<>,
     multimap::lower_bound<>, multimap::upper_bound<>,
     multimap::equal_range<>): Likewise.
     * include/debug/stl_multiset.h (multiset::find<>,
     multiset::lower_bound<>, multiset::upper_bound<>,
     multiset::equal_range<>): Likewise.
     * include/debug/stl_set.h (set::find<>,
     set::lower_bound<>, set::upper_bound<>, set::equal_range<>): Likewise.

Tested under Linux x86_64 debug mode.

François


[-- Attachment #2: debug_asso_cont.patch --]
[-- Type: text/x-patch, Size: 11374 bytes --]

Index: include/debug/map.h
===================================================================
--- include/debug/map.h	(revision 219967)
+++ include/debug/map.h	(working copy)
@@ -412,10 +412,24 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	find(const _Kt& __x)
+	{ return iterator(_Base::find(__x), this); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return const_iterator(_Base::find(__x), this); }
+#endif
+
       using _Base::count;
 
       iterator
@@ -422,18 +436,46 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return iterator(_Base::lower_bound(__x), this); }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::lower_bound(__x), this); }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return iterator(_Base::upper_bound(__x), this); }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::upper_bound(__x), this); }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -443,6 +485,18 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  std::pair<_Base_iterator, _Base_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(iterator(__res.first, this),
+				iterator(__res.second, this));
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -452,6 +506,18 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(const_iterator(__res.first, this),
+				const_iterator(__res.second, this));
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multimap.h
===================================================================
--- include/debug/multimap.h	(revision 219967)
+++ include/debug/multimap.h	(working copy)
@@ -393,10 +393,24 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	find(const _Kt& __x)
+	{ return iterator(_Base::find(__x), this); }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return const_iterator(_Base::find(__x), this); }
+#endif
+
       using _Base::count;
 
       iterator
@@ -403,18 +417,46 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return iterator(_Base::lower_bound(__x), this); }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::lower_bound(__x), this); }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return iterator(_Base::upper_bound(__x), this); }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::upper_bound(__x), this); }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -424,6 +466,18 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  std::pair<_Base_iterator, _Base_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(iterator(__res.first, this),
+				iterator(__res.second, this));
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -433,6 +487,18 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(const_iterator(__res.first, this),
+				const_iterator(__res.second, this));
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 
Index: include/debug/set.h
===================================================================
--- include/debug/set.h	(revision 219967)
+++ include/debug/set.h	(working copy)
@@ -393,6 +393,18 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	find(const _Kt& __x)
+	{ return iterator(_Base::find(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return const_iterator(_Base::find(__x), this); }
+#endif
+
       using _Base::count;
 
       iterator
@@ -405,6 +417,18 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return iterator(_Base::lower_bound(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::lower_bound(__x), this); }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -415,6 +439,18 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return iterator(_Base::upper_bound(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::upper_bound(__x), this); }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -429,12 +465,34 @@
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
-	std::pair<_Base_iterator, _Base_iterator> __res =
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 	_Base::equal_range(__x);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  std::pair<_Base_iterator, _Base_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(iterator(__res.first, this),
+				iterator(__res.second, this));
+	}
+
+      template<typename _Kt>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(const_iterator(__res.first, this),
+				const_iterator(__res.second, this));
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multiset.h
===================================================================
--- include/debug/multiset.h	(revision 219967)
+++ include/debug/multiset.h	(working copy)
@@ -386,6 +386,18 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	find(const _Kt& __x)
+	{ return iterator(_Base::find(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return const_iterator(_Base::find(__x), this); }
+#endif
+
       using _Base::count;
 
       iterator
@@ -398,6 +410,18 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return iterator(_Base::lower_bound(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::lower_bound(__x), this); }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -408,6 +432,18 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return iterator(_Base::upper_bound(__x), this); }
+
+      template<typename _Kt>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::upper_bound(__x), this); }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -428,6 +464,28 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  std::pair<_Base_iterator, _Base_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(iterator(__res.first, this),
+				iterator(__res.second, this));
+	}
+
+      template<typename _Kt>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  std::pair<_Base_const_iterator, _Base_const_iterator> __res =
+	    _Base::equal_range(__x);
+	  return std::make_pair(const_iterator(__res.first, this),
+				const_iterator(__res.second, this));
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

On 21/01/15 23:30 +0100, François Dumont wrote:
>On 20/01/2015 13:00, Jonathan Wakely wrote:
>>On 19/01/15 17:16 +0000, Jonathan Wakely wrote:
>>>This is the last missing piece of the C++14 library, as proposed in
>>>http://www.open-std.org/JTC1/sc22/wg21/docs/papers/2013/n3657.htm
>>>
>>>Tested x86_64-linux, *not* committed.
>>
>>Now committed to trunk.
>>
>Is it ok then to commit attached patch to do the same for debug mode ?

Definitely not like that, your patch adds the functions
unconditionally, but they must not participate in overload resolution
unless the comparison function defines an is_transparent member type.

I won't be too concerned if these new functions aren't available in
Debug Mode for the next release, we can add them later.

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

On 21/01/15 23:30 +0100, François Dumont wrote:
>+#if __cplusplus > 201103L
>+      template<typename _Kt>
>+	std::pair<iterator, iterator>
>+	equal_range(const _Kt& __x)
>+	{
>+	  std::pair<_Base_iterator, _Base_iterator> __res =
>+	    _Base::equal_range(__x);
>+	  return std::make_pair(iterator(__res.first, this),
>+				iterator(__res.second, this));
>+	}

BTW, this is C++14 code, what's wrong with:

  template<typename _Kt>
    std::pair<const_iterator, const_iterator>
    equal_range(const _Kt& __x) const
    {
      auto __res = _Base::equal_range(__x);
      return { iterator(__res.first, this), iterator(__res.second, this) };
    }

Or even:

  template<typename _Kt>
    std::pair<const_iterator, const_iterator>
    equal_range(const _Kt& __x) const
    {
      auto __res = _Base::equal_range(__x);
      return { { __res.first, this }, {__res.second, this} };
    }

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1453 bytes --]

Sorry, I hadn't notice the condition to expose the new methods. It was 
hidden within the _Rb_tree type that I hadn't check (and I do not often 
check the Standard directly for my limited patches).

On my side I am surprised you didn't reuse your code to detect member 
types. I am also surprised that it is not using enable_if, IMHO it makes 
the code clearer. Here is a proposal to use both extended to the debug 
mode too.

François


On 22/01/2015 03:07, Jonathan Wakely wrote:
> On 21/01/15 23:30 +0100, François Dumont wrote:
>> +#if __cplusplus > 201103L
>> +      template<typename _Kt>
>> +    std::pair<iterator, iterator>
>> +    equal_range(const _Kt& __x)
>> +    {
>> +      std::pair<_Base_iterator, _Base_iterator> __res =
>> +        _Base::equal_range(__x);
>> +      return std::make_pair(iterator(__res.first, this),
>> +                iterator(__res.second, this));
>> +    }
>
> BTW, this is C++14 code, what's wrong with:
>
>  template<typename _Kt>
>    std::pair<const_iterator, const_iterator>
>    equal_range(const _Kt& __x) const
>    {
>      auto __res = _Base::equal_range(__x);
>      return { iterator(__res.first, this), iterator(__res.second, 
> this) };
>    }
>
> Or even:
>
>  template<typename _Kt>
>    std::pair<const_iterator, const_iterator>
>    equal_range(const _Kt& __x) const
>    {
>      auto __res = _Base::equal_range(__x);
>      return { { __res.first, this }, {__res.second, this} };
>    }
>


[-- Attachment #2: asso_cont.patch --]
[-- Type: text/x-patch, Size: 16682 bytes --]

Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h	(revision 220078)
+++ include/bits/stl_tree.h	(working copy)
@@ -342,6 +342,9 @@
   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 			       _Rb_tree_node_base& __header) throw ();
 
+#if __cplusplus > 201103L
+ _GLIBCXX_HAS_NESTED_TYPE(is_transparent)
+#endif
 
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc = allocator<_Val> >
@@ -1119,14 +1122,6 @@
       equal_range(const key_type& __k) const;
 
 #if __cplusplus > 201103L
-      template<typename _Cmp, typename _Kt, typename = __void_t<>>
-	struct __is_transparent { };
-
-      template<typename _Cmp, typename _Kt>
-	struct
-	__is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
-	{ typedef void type; };
-
       static auto _S_iter(_Link_type __x) { return iterator(__x); }
 
       static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
@@ -1155,9 +1150,8 @@
 	  return _S_iter(__y);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
 	_M_find_tr(const _Kt& __k)
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1166,9 +1160,8 @@
 	    ? end() : __j;
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	const_iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
 	_M_find_tr(const _Kt& __k) const
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1177,9 +1170,8 @@
 	    ? end() : __j;
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	size_type
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, size_type>
 	_M_count_tr(const _Kt& __k) const
 	{
 	  auto __p = _M_equal_range_tr(__k);
@@ -1186,9 +1178,8 @@
 	  return std::distance(__p.first, __p.second);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
 	_M_lower_bound_tr(const _Kt& __k)
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1195,9 +1186,8 @@
 	  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	const_iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
 	_M_lower_bound_tr(const _Kt& __k) const
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1204,9 +1194,8 @@
 	  return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
 	_M_upper_bound_tr(const _Kt& __k)
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1213,9 +1202,8 @@
 	  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	const_iterator
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
 	_M_upper_bound_tr(const _Kt& __k) const
 	{
 	  auto& __cmp = _M_impl._M_key_compare;
@@ -1222,9 +1210,9 @@
 	  return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	pair<iterator, iterator>
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    pair<iterator, iterator>>
 	_M_equal_range_tr(const _Kt& __k)
 	{
 	  auto __low = _M_lower_bound_tr(__k);
@@ -1235,9 +1223,9 @@
 	  return { __low, __high };
 	}
 
-      template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
-	pair<const_iterator, const_iterator>
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    pair<const_iterator, const_iterator>>
 	_M_equal_range_tr(const _Kt& __k) const
 	{
 	  auto __low = _M_lower_bound_tr(__k);
Index: include/debug/map.h
===================================================================
--- include/debug/map.h	(revision 220078)
+++ include/debug/map.h	(working copy)
@@ -412,10 +412,24 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -422,18 +436,46 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	lower_bound(const _Kt& __x)
+	{ return iterator(_Base::lower_bound(__x), this); }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	lower_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::lower_bound(__x), this); }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	upper_bound(const _Kt& __x)
+	{ return iterator(_Base::upper_bound(__x), this); }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	upper_bound(const _Kt& __x) const
+	{ return const_iterator(_Base::upper_bound(__x), this); }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -443,6 +485,17 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<iterator, iterator>>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -452,6 +505,17 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<const_iterator, const_iterator>>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multimap.h
===================================================================
--- include/debug/multimap.h	(revision 220078)
+++ include/debug/multimap.h	(working copy)
@@ -393,10 +393,24 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -403,18 +417,46 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -424,6 +466,17 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<iterator, iterator>>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -433,6 +486,17 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<const_iterator, const_iterator>>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 
Index: include/debug/set.h
===================================================================
--- include/debug/set.h	(revision 220078)
+++ include/debug/set.h	(working copy)
@@ -393,6 +393,18 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -405,6 +417,18 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -415,6 +439,18 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -429,12 +465,32 @@
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
-	std::pair<_Base_iterator, _Base_iterator> __res =
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 	_Base::equal_range(__x);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<iterator, iterator>>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<const_iterator, const_iterator>>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multiset.h
===================================================================
--- include/debug/multiset.h	(revision 220078)
+++ include/debug/multiset.h	(working copy)
@@ -386,6 +386,18 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -398,6 +410,18 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -408,6 +432,18 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value, const_iterator>
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -428,6 +464,26 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<iterator, iterator>>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt>
+	enable_if_t<__has_is_transparent<_Compare>::value,
+		    std::pair<const_iterator, const_iterator>>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

On 24/01/15 23:03 +0100, François Dumont wrote:
>Sorry, I hadn't notice the condition to expose the new methods. It was 
>hidden within the _Rb_tree type that I hadn't check (and I do not 
>often check the Standard directly for my limited patches).
>
>On my side I am surprised you didn't reuse your code to detect member 

That adds another class template to the global namespace. I did that
initially, but (because I forgot about Debug + Profile modes) decided
against defining a new global type that is only needed in one place.

(N.B. _GLIBCXX_HAS_NESTED_TYPE is not mine, I only modified it
recently to use __void_t when I added that. Personally I find directly
using void_t is simpler than defining a new type using void_t and then
using that. I expect that to be the idiomatic solution in C++17 when
std::void_t is added.

>types. I am also surprised that it is not using enable_if, IMHO it 
>makes the code clearer.

It doesn't work though.

>@@ -1155,9 +1150,8 @@
> 	  return _S_iter(__y);
> 	}
> 
>-      template<typename _Kt,
>-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
>-	iterator
>+      template<typename _Kt>
>+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
> 	_M_find_tr(const _Kt& __k)

This doesn't work.

Consider:

  #include <set>

  struct I
  {
    int i;
    operator int() const { return i; }
  };

  int main()
  {
    std::set<int> s;
    I i = { };
    s.find(i);
  }

(I will add something like this to the testsuite.)

This program is valid according to any C++ standard, but fails to
compile with your patch applied because overload resolution
instantiates std::_Rb_tree<>::_M_find_tr<I> which instantiates
enable_if<false, iterator>::type, which is an error. SFINAE does not
apply, because the invalid type enable_if<false, iterator>::type is
not found during *substitution*. It's just invalid, so when _Compare
is not transparent, instantiating the function template is simply an
error.

Observe that my __is_transparent alias template takes two template
arguments, so that it depends on the template parameter of the
function, not only on _Compare. That means whether if the type is
invalid that will be found during template argument substitution, so
SFINAE applies.

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

On 24/01/15 22:46 +0000, Jonathan Wakely wrote:
>Observe that my __is_transparent alias template takes two template
>arguments, so that it depends on the template parameter of the
>function, not only on _Compare. That means whether if the type is

s/whether //

>invalid that will be found during template argument substitution, so
>SFINAE applies.

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[Jonathan Wakely]

[-- Attachment #1: Type: text/plain, Size: 850 bytes --]

On 24/01/15 22:46 +0000, Jonathan Wakely wrote:
>On 24/01/15 23:03 +0100, François Dumont wrote:
>>types. I am also surprised that it is not using enable_if, IMHO it 
>>makes the code clearer.
>
>It doesn't work though.
>
>>@@ -1155,9 +1150,8 @@
>>	  return _S_iter(__y);
>>	}
>>
>>-      template<typename _Kt,
>>-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
>>-	iterator
>>+      template<typename _Kt>
>>+	enable_if_t<__has_is_transparent<_Compare>::value, iterator>
>>	_M_find_tr(const _Kt& __k)
>
>This doesn't work.
>
>Consider:
>
> #include <set>
>
> struct I
> {
>   int i;
>   operator int() const { return i; }
> };
>
> int main()
> {
>   std::set<int> s;
>   I i = { };
>   s.find(i);
> }
>
>(I will add something like this to the testsuite.)

Done with this patch, tested x86_64-linux and committed to trunk.


[-- Attachment #2: patch.txt --]
[-- Type: text/x-patch, Size: 1021 bytes --]

commit ba331e783334feb20f30f1b92a93d8c9d8f895be
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jan 26 10:43:16 2015 +0000

    	* testsuite/23_containers/set/operations/2.cc: Add test for
    	non-transparent comparison function.

diff --git a/libstdc++-v3/testsuite/23_containers/set/operations/2.cc b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc
index 752bc7d..84ddd1f 100644
--- a/libstdc++-v3/testsuite/23_containers/set/operations/2.cc
+++ b/libstdc++-v3/testsuite/23_containers/set/operations/2.cc
@@ -128,6 +128,22 @@ test05()
   VERIFY( Cmp::count == 0);
 }
 
+void
+test06()
+{
+  // https://gcc.gnu.org/ml/libstdc++/2015-01/msg00176.html
+  // Verify the new function template overloads do not cause problems
+  // when the comparison function is not transparent.
+  struct I
+  {
+    int i;
+    operator int() const { return i; }
+  };
+
+  std::set<int> s;
+  I i = { };
+  s.find(i);
+}
 
 int
 main()
@@ -137,4 +153,5 @@ main()
   test03();
   test04();
   test05();
+  test06();
 }

Re: [patch] [C++14] Implement N3657: heterogeneous lookup in associative containers.

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 3221 bytes --]

Hi

     Thanks a lot for those explanations, very educative. I was indeed 
wondering what was the additional template parameter for.

     So here is a new attempt. While moving __is_transparent to std 
namespace I renamed to __has_is_transparent to not conflict with 
existing __is_transparent. I agree that it is another non-standard type 
in the std namespace but at the same time should'nt the whole content of 
stl_tree.h be in __gnu_cxx rather ? This is perhaps not a reason to make 
situation worst so tell me if you want me to move it to std::__detail 
namespace ?

     At the beginning I wanted to make something like in bits/map.h to 
not have to replicate the __is_transparent stuff. But I didn't found any 
way to do such a thing.

2015-01-22  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/stl_tree.h (_Rb_tree<>::__is_transparent<>): Move to 
outer
     scope and rename in ...
     (std::__hash_is_transparent<>): ... this.
     * include/debug/stl_map.h (map::find<>,
     map::lower_bound<>, map::upper_bound<>, map::equal_range<>): New
     member function templates to perform heterogeneous lookup.
     * include/debug/stl_multimap.h (multimap::find<>,
     multimap::lower_bound<>, multimap::upper_bound<>,
     multimap::equal_range<>): Likewise.
     * include/debug/stl_multiset.h (multiset::find<>,
     multiset::lower_bound<>, multiset::upper_bound<>,
     multiset::equal_range<>): Likewise.
     * include/debug/stl_set.h (set::find<>,
     set::lower_bound<>, set::upper_bound<>, set::equal_range<>): Likewise.
     * include/profile/stl_map.h (map::find<>, map::count<>,
     map::lower_bound<>, map::upper_bound<>, map::equal_range<>): Likewise.
     * include/profile/stl_multimap.h (multimap::find<>, multimap::cout<>,
     multimap::lower_bound<>, multimap::upper_bound<>,
     multimap::equal_range<>): Likewise.
     * include/profile/stl_multiset.h (multiset::find<>, multiset::count<>,
     multiset::lower_bound<>, multiset::upper_bound<>,
     multiset::equal_range<>): Likewise.
     * include/profile/stl_set.h (set::find<>, set::count<>,
     set::lower_bound<>, set::upper_bound<>, set::equal_range<>): Likewise.

Tested under Linux x86_64 normal, debug and profile modes.

François


On 26/01/2015 12:19, Jonathan Wakely wrote:
> On 24/01/15 22:46 +0000, Jonathan Wakely wrote:
>> On 24/01/15 23:03 +0100, François Dumont wrote:
>>> types. I am also surprised that it is not using enable_if, IMHO it 
>>> makes the code clearer.
>>
>> It doesn't work though.
>>
>>> @@ -1155,9 +1150,8 @@
>>>       return _S_iter(__y);
>>>     }
>>>
>>> -      template<typename _Kt,
>>> -           typename _Req = typename __is_transparent<_Compare, 
>>> _Kt>::type>
>>> -    iterator
>>> +      template<typename _Kt>
>>> + enable_if_t<__has_is_transparent<_Compare>::value, iterator>
>>>     _M_find_tr(const _Kt& __k)
>>
>> This doesn't work.
>>
>> Consider:
>>
>> #include <set>
>>
>> struct I
>> {
>>   int i;
>>   operator int() const { return i; }
>> };
>>
>> int main()
>> {
>>   std::set<int> s;
>>   I i = { };
>>   s.find(i);
>> }
>>
>> (I will add something like this to the testsuite.)
>
> Done with this patch, tested x86_64-linux and committed to trunk.
>


[-- Attachment #2: heterogeneous_lookup.patch --]
[-- Type: text/x-patch, Size: 34379 bytes --]

Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h	(revision 220131)
+++ include/bits/stl_tree.h	(working copy)
@@ -342,7 +342,17 @@
   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
 			       _Rb_tree_node_base& __header) throw ();
 
+#if __cplusplus > 201103L
+  template<typename _Cmp, typename _Kt, typename = __void_t<>>
+    struct __has_is_transparent
+    { };
 
+  template<typename _Cmp, typename _Kt>
+    struct __has_is_transparent<_Cmp, _Kt,
+				__void_t<typename _Cmp::is_transparent>>
+    { typedef void type; };
+#endif
+
   template<typename _Key, typename _Val, typename _KeyOfValue,
            typename _Compare, typename _Alloc = allocator<_Val> >
     class _Rb_tree
@@ -1119,14 +1129,6 @@
       equal_range(const key_type& __k) const;
 
 #if __cplusplus > 201103L
-      template<typename _Cmp, typename _Kt, typename = __void_t<>>
-	struct __is_transparent { };
-
-      template<typename _Cmp, typename _Kt>
-	struct
-	__is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
-	{ typedef void type; };
-
       static auto _S_iter(_Link_type __x) { return iterator(__x); }
 
       static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
@@ -1156,7 +1158,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	iterator
 	_M_find_tr(const _Kt& __k)
 	{
@@ -1167,7 +1170,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	const_iterator
 	_M_find_tr(const _Kt& __k) const
 	{
@@ -1178,7 +1182,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	size_type
 	_M_count_tr(const _Kt& __k) const
 	{
@@ -1187,7 +1192,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	iterator
 	_M_lower_bound_tr(const _Kt& __k)
 	{
@@ -1196,7 +1202,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	const_iterator
 	_M_lower_bound_tr(const _Kt& __k) const
 	{
@@ -1205,7 +1212,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	iterator
 	_M_upper_bound_tr(const _Kt& __k)
 	{
@@ -1214,7 +1222,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	const_iterator
 	_M_upper_bound_tr(const _Kt& __k) const
 	{
@@ -1223,7 +1232,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	pair<iterator, iterator>
 	_M_equal_range_tr(const _Kt& __k)
 	{
@@ -1236,7 +1246,8 @@
 	}
 
       template<typename _Kt,
-	       typename _Req = typename __is_transparent<_Compare, _Kt>::type>
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
 	pair<const_iterator, const_iterator>
 	_M_equal_range_tr(const _Kt& __k) const
 	{
Index: include/debug/map.h
===================================================================
--- include/debug/map.h	(revision 220131)
+++ include/debug/map.h	(working copy)
@@ -412,10 +412,28 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -422,18 +440,54 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -443,6 +497,18 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -452,6 +518,18 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multimap.h
===================================================================
--- include/debug/multimap.h	(revision 220131)
+++ include/debug/multimap.h	(working copy)
@@ -393,10 +393,28 @@
       find(const key_type& __x)
       { return iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+#endif
+
       const_iterator
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -403,18 +421,54 @@
       lower_bound(const key_type& __x)
       { return iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -424,6 +478,18 @@
 			      iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -433,6 +499,18 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 
Index: include/debug/set.h
===================================================================
--- include/debug/set.h	(revision 220131)
+++ include/debug/set.h	(working copy)
@@ -393,6 +393,22 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -405,6 +421,22 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -415,6 +447,22 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -429,12 +477,34 @@
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
-	std::pair<_Base_iterator, _Base_iterator> __res =
+	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 	_Base::equal_range(__x);
 	return std::make_pair(const_iterator(__res.first, this),
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/debug/multiset.h
===================================================================
--- include/debug/multiset.h	(revision 220131)
+++ include/debug/multiset.h	(working copy)
@@ -386,6 +386,22 @@
       find(const key_type& __x) const
       { return const_iterator(_Base::find(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{ return { _Base::find(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{ return { _Base::find(__x), this }; }
+#endif
+
       using _Base::count;
 
       iterator
@@ -398,6 +414,22 @@
       lower_bound(const key_type& __x) const
       { return const_iterator(_Base::lower_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{ return { _Base::lower_bound(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{ return { _Base::lower_bound(__x), this }; }
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       { return iterator(_Base::upper_bound(__x), this); }
@@ -408,6 +440,22 @@
       upper_bound(const key_type& __x) const
       { return const_iterator(_Base::upper_bound(__x), this); }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{ return { _Base::upper_bound(__x), this }; }
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{ return { _Base::upper_bound(__x), this }; }
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -428,6 +476,28 @@
 			      const_iterator(__res.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
 
Index: include/profile/map.h
===================================================================
--- include/profile/map.h	(revision 220131)
+++ include/profile/map.h	(working copy)
@@ -429,6 +429,18 @@
 	return iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       const_iterator
       find(const key_type& __x) const
       {
@@ -436,6 +448,18 @@
 	return const_iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       size_type
       count(const key_type& __x) const
       {
@@ -443,6 +467,18 @@
 	return _Base::count(__x);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	size_type
+	count(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return _Base::count(__x);
+	}
+#endif
+
       iterator
       lower_bound(const key_type& __x)
       {
@@ -451,6 +487,19 @@
 	return iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       {
@@ -459,6 +508,19 @@
 	return const_iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       {
@@ -467,6 +529,19 @@
 	return iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       {
@@ -475,6 +550,19 @@
 	return const_iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -485,6 +573,19 @@
 			      iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -495,6 +596,19 @@
 			      const_iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/profile/multimap.h
===================================================================
--- include/profile/multimap.h	(revision 220131)
+++ include/profile/multimap.h	(working copy)
@@ -388,6 +388,18 @@
 	return iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       const_iterator
       find(const key_type& __x) const
       {
@@ -395,6 +407,18 @@
 	return const_iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       size_type
       count(const key_type& __x) const
       {
@@ -402,6 +426,18 @@
 	return _Base::count(__x);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	size_type
+	count(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return _Base::count(__x);
+	}
+#endif
+
       iterator
       lower_bound(const key_type& __x)
       {
@@ -410,6 +446,19 @@
 	return iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       const_iterator
       lower_bound(const key_type& __x) const
       {
@@ -418,6 +467,19 @@
 	return const_iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       {
@@ -426,6 +488,19 @@
 	return iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       const_iterator
       upper_bound(const key_type& __x) const
       {
@@ -434,6 +509,19 @@
 	return const_iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -444,6 +532,19 @@
 			      iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       std::pair<const_iterator,const_iterator>
       equal_range(const key_type& __x) const
       {
@@ -454,6 +555,19 @@
 			      const_iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/profile/multiset.h
===================================================================
--- include/profile/multiset.h	(revision 220131)
+++ include/profile/multiset.h	(working copy)
@@ -379,6 +379,18 @@
 	return _Base::count(__x);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	size_type
+	count(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return _Base::count(__x);
+	}
+#endif
+
       // multiset operations:
       iterator
       find(const key_type& __x)
@@ -396,6 +408,28 @@
 	return const_iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       iterator
       lower_bound(const key_type& __x)
       {
@@ -413,6 +447,30 @@
 	return const_iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       {
@@ -431,6 +489,30 @@
 	return const_iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       std::pair<iterator,iterator>
       equal_range(const key_type& __x)
       {
@@ -453,6 +535,30 @@
 			      const_iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }
 
Index: include/profile/set.h
===================================================================
--- include/profile/set.h	(revision 220131)
+++ include/profile/set.h	(working copy)
@@ -369,6 +369,18 @@
 	return _Base::count(__x);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	size_type
+	count(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return _Base::count(__x);
+	}
+#endif
+
       // set operations:
       iterator
       find(const key_type& __x)
@@ -384,6 +396,28 @@
 	return const_iterator(_Base::find(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	find(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	find(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  return { _Base::find(__x), this };
+	}
+#endif
+
       iterator
       lower_bound(const key_type& __x)
       {
@@ -400,6 +434,30 @@
 	return const_iterator(_Base::lower_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	lower_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	lower_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::lower_bound(__x), this };
+	}
+#endif
+
       iterator
       upper_bound(const key_type& __x)
       {
@@ -416,6 +474,30 @@
 	return const_iterator(_Base::upper_bound(__x), this);
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	iterator
+	upper_bound(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	const_iterator
+	upper_bound(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  __profcxx_map2umap_invalidate(this->_M_map2umap_info);
+	  return { _Base::upper_bound(__x), this };
+	}
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __x)
       {
@@ -436,6 +518,30 @@
 			      const_iterator(__base_ret.second, this));
       }
 
+#if __cplusplus > 201103L
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<iterator, iterator>
+	equal_range(const _Kt& __x)
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+
+      template<typename _Kt,
+	       typename _Req =
+		 typename __has_is_transparent<_Compare, _Kt>::type>
+	std::pair<const_iterator, const_iterator>
+	equal_range(const _Kt& __x) const
+	{
+	  __profcxx_map2umap_find(this->_M_map2umap_info, this->size());
+	  auto __res = _Base::equal_range(__x);
+	  return { { __res.first, this }, { __res.second, this } };
+	}
+#endif
+
       _Base&
       _M_base() _GLIBCXX_NOEXCEPT	{ return *this; }