diff mbox

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

Message ID 54C416CD.4010907@gmail.com
State New
Headers show

Commit Message

François Dumont Jan. 24, 2015, 10:03 p.m. UTC 
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} };
>    }
>

Comments

Jonathan Wakely Jan. 24, 2015, 10:46 p.m. UTC | #1 
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.
Jonathan Wakely Jan. 24, 2015, 10:50 p.m. UTC | #2 
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.
diff mbox

Patch

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; }