Document number: | P0046R1 | |
---|---|---|
Date: | 2016-01-30 | |
Project: | Programming Language C++, Library Evolution Working Group | |
Reply-to: | Tomasz Kamiński <tomaszkam at gmail dot com> |
This proposal discusses an alternative design for enabling a heterogeneous lookup function in the associative containers, that relies on use of metafunction.
This paper is result of the LWG recommendation provided in the resolution of the LWG issue #2430.
permits_heterogeneous_lookup_v
variable template into main proposal.permits_heterogeneous_lookup<T>::value
with permits_heterogeneous_lookup_v<T>
.In the scope of this paper we propose a new metafunction permits_heterogenous_lookup
.
This metafunction is designed to be used to enable the heterogeneous lookup in associative container, instead
of the current standard method relying on presence of is_transparent
nested type in the comparator
type ($23.2.4 [associative.reqmts]).
The addition of the heterogeneous lookup to the container may silently change the behavior of the existing code
and, to avoid such situations, it was designed as an opt-in feature. However, the mechanism created for the purpose
is not always working correctly - existing programs may define is_transparent
nested type in their
comparator types, and as a consequence the meaning of such programs will be changed.
The introduction of the type trait allows the users to resolve the backward compatibility problem described above
via providing an explicit specialization of the trait that derives from std::false_type
.
It is worth noting that this is only a viable solution for the situation when the programmer does not have the
control over the comparator's code.
Furthermore, it is possible to avoid false positives via providing the default definition
of permits_heterogeneous_lookup
that has BaseCharacteristic of std::false_type
.
However, such design will no longer support user-defined comparators that intentionally enable new lookup function
by declaring nested type is_transparent
.
The resolution of this problem is discussed in Backward compatibility subsection of the proposal.
In the current design enabling heterogeneous lookup requires a modification of the comparator class to declare a nested type. As a consequence of this intrusiveness, discussed functionality cannot be enabled for the third-party types that are outside of their control, even if they support such operations.
In contrast, the use of a type trait allows the new lookup mechanism to be enabled in the program without any modification to the third party libraries.
The introduction of the type trait would also simplify the definition of call wrapper types that would like to 'inherit' the heterogeneous comparison trait from the wrapped callable.
Suppose we are creating call_wrapper<F>
. In the case of the proposed permits_heterogeneous_lookup
trait, the implementation is pretty straight-forward:
namespace std { template<typename F> struct permits_heterogeneous_lookup<call_wrapper<F>> : permits_heterogeneous_lookup<F> {}; }
But for current design it becomes more complicated. The user is required to declare is_transparent
nested
type in the definition of call_wrapper<F>
if such type was defined in the F
type.
namespace detail { template<typename F, typename IT = void> struct is_transparent_base {}; template<typename F> struct is_transparent_base<F, void_t<typename F::is_transparent>> { using is_transparent = typename F::is_transparent; }; } template<typename F> struct call_wrapper : detail::is_transparent_base<F> { /*...*/ };
In addition to being longer and intrusive, the nested type implementation requires of type F
to
be complete at the point of instantiation of call_wrapper<F>
.
As a consequence, it is impossible to create a reference wrapper class that would support both incomplete types and
heterogeneous container lookup.
Proposed solution will make this functionality consistent with rest of the standard that relies on the usage
of the traits like: is_placeholder
and is_bind_expression
in similar situations.
Existing is_transparent
nested was used to mark classes that has one of the following characteristics:
Although we may point out types that fulfills only one of above criteria. For example diamond version
logical_not
or plus
are transparently wrapping some build-in operators,
but usually they cannot be used as comparators. From the other side we may imagine the icase_less
comparator that would provides overloads for std::string
and char*
.
The trait proposed in this paper is designed to identify only the types in the second category.
The relation with the existing is_transparent
is preserved only for backward compatibility reasons.
Following criteria was considered in the process of name selection for new metafunction:
is_generic
, is_polymorphic
,
is_transparent
.supports_heterogeneous_lookup
,
provides_heterogeneous_lookup
, allows_heterogeneous_lookup
and
enables_heterogeneous_lookup
.unordered_set
, as consequence it should not refer to concept specific
to one implementation.
Names that was rejected because of this criteria: is_heterogeneous_comparator
.is_compatible_with_heterogeneous_lookup
.This paper propose a new name for the trait permits_heterogeneous_lookup
, instead of keeping the
name used for nested type. This resolution was selected because the original name (is_transparent
)
does not fulfill criteria of a good name listed above.
As the result of the introduction of is_transparent
tag in the C++14 the design of permits_heterogeneous_lookup
must carefully decide to choose one of the following:
is_transparent
nested type.
To achieve that, the default implementation of the metafunction should always return false
.is_transparent
nested type. To achieve that, the default
implementation of the metafunction should return true
for the functors with this type present.Considering small possibility of occurrence of compatibility problems and the fact the harm was already done (C++14 was shipped), the proposal decides to choose second option and provide the default implementation that relies on presence of the nested type.
As a consequence of this decision, two ways of enabling heterogeneous lookup are provided by the standard: via the declaration of the nested type, and the explicit specialization of the trait. The author strongly believes that new mechanism provides an better alternative and decides to express this view via non normative note in the wording.
The semantics of new permits_heterogeneous_lookup
trait is directly related to the associative containers
and it would be preferable to declare it in related header. However currently no common utility header for associative
container is defined in the standard. Furthermore the scale of the proposed changes does not not justify
introduction of the new header. As consequence we propose that permits_heterogeneous_lookup
should be included
in <functional>
header, as it contains definitions of default hash function and comparators that currently
enables heterogeneous lookup.
This proposal has no dependencies beyond a C++11 compiler and Standard Library implementation.
Nothing depends on this proposal.
The proposed wording changes refer to N4567 (C++ Working Draft, 2015-11-09).
After the declaration of hash<T*>
in the section 20.9 [function.objects]/2 (Header <functional>
synopsis), add:
// 20.9.14, heterogeneous container lookup; template <class F> struct permits_heterogeneous_lookup;
After the declaration of is_placeholder_v<T*>
in the section 20.9 [function.objects]/2 (Header <functional>
synopsis), add:
// 20.9.14, heterogeneous container lookup; template <class F> constexpr bool permits_heterogeneous_lookup_v = permits_heterogeneous_lookup<F>::value;
After section 20.9.13 Class template hash
, insert a new section.
20.9.14 Class template
permits_heterogeneous_lookup
[containers.heterlookup]namespace std { template <class F> struct permits_heterogeneous_lookup; // see below }
The associative containers defined in [associative] 23.4 use
permits_heterogeneous_lookup
to detect if member functions exposing heterogeneous container lookup should be enabled for a given comparator type.Instantiations of the
permits_heterogeneous_lookup
template shall meet theUnaryTypeTrait
requirements ([meta.rqmts] 20.10.1). The implementation shall provide a definition ofpermits_heterogeneous_lookup<F>
that has aBaseCharacteristic
oftrue_type
if the qualified-idF::is_transparent
is valid and denotes a type ([temp.deduct] 14.8.2), otherwise it shall have aBaseCharacteristic
offalse_type
. A program may specialize this template for a user-defined type to have aBaseCharacteristic
oftrue_type
orfalse_type
.[ Note: Specializing
permits_heterogeneous_lookup
usually provides a better solution than declaringis_transparent
nested type. — end note ]
Change the paragraph 23.2.4 Associative containers [associative.reqmts] p8.
In Table 102,
X
denotes an associative container class,a
denotes a value ofX
,a_uniq
denotes a value ofX
whenX
supports unique keys,a_eq
denotes a value ofX
whenX
supports multiple keys,a_tran
denotes a value ofX
when thequalified-idX::key_compare::is_transparent
is valid and denotes a type (14.8.2)permits_heterogeneous_lookup_v<typename X::key_compare>
istrue
([containers.heterlookup] 20.9.14),i
andj
satisfy input iterator requirements and refer to elements implicitly convertible tovalue_type
,[i,j)
denotes a valid range,p
denotes a valid const iterator toa
,q
denotes a valid dereferenceable const iterator toa
,[q1, q2)
denotes a valid range of const iterators ina
,il
designates an object of typeinitializer_list<value_type>
,t
denotes a value ofX::value_type
,k
denotes a value ofX::key_type
andc
denotes a value of typeX::key_compare
;kl
is a value such thata
is partitioned (25.4) with respect toc(r, kl)
, withr
the key value ofe
ande
ina
;ku
isa
value such that a is partitioned with respect to!c(ku, r)
;ke
is a value such thata
is partitioned with respect toc(r, ke)
and!c(ke, r)
, withc(r, ke)
implying!c(ke, r)
.A
denotes the storage allocator used byX
, if any, orstd::allocator<X::value_type>
otherwise, andm
denotes an allocator of a type convertible toA
.
For the purposes of SG10, we recommend the macro name __cpp_lib_permits_heterogeneous_lookup
to be defined in the
<functional>
header.
Usage example:
namespace third_party { struct icase_less { bool operator()(std::string const&, std::string const&) const; bool operator()(std::string const&, char const*) const; bool operator()(char const*, std::string const&) const; bool operator()(char const*, char const*) const; }; } #if __cpp_lib_permits_heterogeneous_lookup namespace std { template<> struct permits_heterogeneous_lookup<third_party::icase_less> : std::true_type {}; } #else struct my_icase_less : third_party::icase_less { using is_transparent = void; }; #endif
Jonathan Wakely provided an improved wording for the LWG issue #2430, from which this paper originates. Futhermore he has offered many useful suggestions and corrections to the proposal.
Andrzej Krzemieński offered many useful suggestions and corrections to the proposal.
Stephan T. Lavavej suggested numerous corrections to the proposed wording and
addition of permits_heterogeneous_lookup_v
variable template.