1. Stop overconstraining allocators that do not participate in deduction
1.1. The problem
Consider this code:
std :: pmr :: monotonic_buffer_resource mr ; std :: pmr :: polymorphic_allocator < int > a = & mr ; std :: pmr :: vector < int > pv ( a ); auto s1 = std :: stack < int , std :: pmr :: vector < int >> ( pv ); auto s2 = std :: stack < int , std :: pmr :: vector < int >> ( pv , a ); auto s3 = std :: stack < int , std :: pmr :: vector < int >> ( pv , & mr ); auto ds1 = std :: stack ( pv ); auto ds2 = std :: stack ( pv , a ); auto ds3 = std :: stack ( pv , & mr );
The initializers of
,
, and
(which do not use CTAD) are all well-formed,
as are the initializers of
and
(which do).
However, the natural and useful
is ill-formed, even though the
argument is irrelevant to determining the
template arguments for
! It seems clearly wrong that we give all the right information to unambiguously deduce
the desired specialization of stack and then reject what would be a perfectly valid constructor invocation for that
class. The allocator parameter’s type does not contribute to class template argument deduction in these cases;
it brings no new information, and therefore should be treated no differently than it is in the non-CTAD case.
Indeed, we believe this is an oversight and should simply be fixed.
1.2. The explanation
has one relevant deduction guide.
template < class Container , class Allocator > stack ( Container , Allocator ) -> stack < typename Container :: value_type , Container > ;
This deduction guide satisfies the following constraints.
[container.adaptors.general] says:
A deduction guide for a container adaptor shall not participate in overload resolution if any of the following are true: ...
It has an
template parameter and a type that does not qualify as an allocator is deduced for that parameter.
Allocator It has both
and
Container template parameters, and
Allocator is
uses_allocator_v < Container , Allocator > false
.
To qualify as an allocator, a type
must have a nested typedef
([container.requirements.general]/17).
Since
has no such nested typedef,
doesn’t qualify as an allocator.
However,
is true
.
Because the type of
doesn’t qualify as an allocator, the deduction guide drops out
of overload resolution, failing deduction even though it has all the information
needed to safely deduce the correct template arguments for
.
1.3. The solution
To fix all three container adaptors, modify [container.adaptors.general] as follows:
A deduction guide for a container adaptor shall not participate in overload resolution if any of the following are true:
It has an
template parameter and a type that does not qualify as an input iterator is deduced for that parameter.
InputIterator It has a
template parameter and a type that qualifies as an allocator is deduced for that parameter.
Compare It has a
template parameter and a type that qualifies as an allocator is deduced for that parameter.
Container It has antemplate parameter and a type that does not qualify as an allocator is deduced for that parameter.
Allocator It has both
and
Container template parameters, and
Allocator is
uses_allocator_v < Container , Allocator > false
.
Note: The rationale is that if the
advertises that it can "use" the supplied allocator,
we shouldn’t interrogate it any more closely. Trust the
's specialization of
.
Note: No container adaptor deduction guide has an
template parameter without also having
a
template parameter.
2. Stop deducing from allocators that should not participate in deduction
2.1. The problem
Consider the following code:
The initializers ofstd :: pmr :: monotonic_buffer_resource mr ; std :: pmr :: polymorphic_allocator < int > a = & mr ; std :: pmr :: vector < int > pv ( a ); auto v1 = std :: vector < int , std :: pmr :: polymorphic_allocator < int >> ( pv ); auto v2 = std :: vector < int , std :: pmr :: polymorphic_allocator < int >> ( pv , a ); auto v3 = std :: vector < int , std :: pmr :: polymorphic_allocator < int >> ( pv , & mr ); auto dv1 = std :: vector ( pv ); auto dv2 = std :: vector ( pv , a ); auto dv3 = std :: vector ( pv , & mr );
v1
, v2
, and v3
(which do not use CTAD) are all well-formed,
as are the initializers of dv1
and dv2
(which do).
But the initializer of
is ill-formed!
Again, we know from the
argument that the correct type for the vector is
, i.e.
. Therefore we
know what is the possible range of types for the allocator parameter. The allocator parameter’s type does not contribute to class template argument deduction in these cases; it brings no new information, and therefore should be treated no differently
than it is in the non-CTAD case.
The problem we see with
also occurs for all other sequence containers, associative containers, and unordered associative containers.
2.2. The explanation
has only one deduction guide, and it’s not relevant to what happens here. Here, we end up
looking at the implicit guide generated from the constructor
template < class T , class Allocator > class vector { vector ( const vector < T , Allocator >& , const Allocator & ); };
From the first parameter, we deduce
and
.
From the second parameter, we deduce
.
We’ve deduced conflicting types for
, so deduction fails.
In this case, the second argument unnecessarily participates in deduction, and again unexpectedly prevents natural and useful code from working as desired.
2.3. The solution
We present two approaches for changing the wording that are equivalent in effect.
2.3.1. Wording option 1
If we were introducing the containers from scratch today, the natural approach would be for the constructors to indicate which arguments should be considered deducible, as is usual for function templates. For example, modify [deque.overview] as follows:
deque ( deque && ); deque ( const deque & , const Allocator & ); deque ( const deque & , const type_identity_t < Allocator >& ); deque ( deque && , const Allocator & ); deque ( deque && , const type_identity_t < Allocator >& ); deque ( initializer_list < T > , const Allocator & = Allocator ());
(Notice that the constructor
is not
changed, because its
parameter actually does contribute to deduction: without
that parameter’s type, we would not know what the
's allocator type should be.)
If this is not deemed to cause compatibility issues, we like this approach.
2.3.2. Wording option 2
First modify [sequence.reqmts]/13 as follows:
A deduction guide for a sequence container shall not participate in overload resolution if it has antemplate parameter and a type that does not qualify as an input iterator is deduced for that parameter, or if it has an
InputIterator template parameter and a type that does not qualify as an allocator is deduced for that parameter, or if it has an
Allocator template parameter and
Alloc is
uses_allocator_v < X , Alloc > false
whereis the deduced type of the sequence container.
X
(We think that change is not strictly necessary, but it clarifies our intent.)
Add one new deduction guide for each sequence container. For example, modify [deque.overview] as follows:
template < class InputIterator , class Allocator = allocator < iter - value - type < InputIterator >>> deque ( InputIterator , InputIterator , Allocator = Allocator ()) -> deque < iter - value - type < InputIterator > , Allocator > ; template < class T , class Allocator , class Alloc > deque ( deque < T , Allocator > , Alloc ) -> deque < T , Allocator > ;
Then, modify [associative.reqmts]/15 as follows:
A deduction guide for an associative container shall not participate in overload resolution if any of the following are true:
It has an
template parameter and a type that does not qualify as an input iterator is deduced for that parameter.
InputIterator It has an
template parameter and a type that does not qualify as an allocator is deduced for that parameter.
Allocator It has a
template parameter and a type that qualifies as an allocator is deduced for that parameter.
Compare - It has an
template parameter and
Alloc is
uses_allocator_v < X , Alloc > false
whereis the deduced type of the associative container.
X
(We think that change is not strictly necessary, but it clarifies our intent.)
Add one new deduction guide for each associative container. For example, modify [set.overview] as follows:
template < class InputIterator , class Compare = less < iter - value - type < InputIterator >> , class Allocator = allocator < iter - value - type < InputIterator >>> set ( InputIterator , InputIterator , Compare = Compare (), Allocator = Allocator ()) -> set < iter - value - type < InputIterator > , Compare , Allocator > ; template < class Key , class Compare = less < Key > , class Allocator = allocator < Key >> set ( initializer_list < Key > , Compare = Compare (), Allocator = Allocator ()) -> set < Key , Compare , Allocator > ; template < class InputIterator , class Allocator > set ( InputIterator , InputIterator , Allocator ) -> set < iter - value - type < InputIterator > , less < iter - value - type < InputIterator >> , Allocator > ; template < class Key , class Allocator > set ( initializer_list < Key > , Allocator ) -> set < Key , less < Key > , Allocator > ; template < class Key , class Compare , class Allocator , class Alloc > set ( set < Key , Compare , Allocator > , Alloc ) -> set < Key , Compare , Allocator > ;
Then, modify [unord.req]/18 as follows:
A deduction guide for an unordered associative container shall not participate in overload resolution if any of the following are true:
It has an
template parameter and a type that does not qualify as an input iterator is deduced for that parameter.
InputIterator It has an
template parameter and a type that does not qualify as an allocator is deduced for that parameter.
Allocator It has a
template parameter and an integral type or a type that qualifies as an allocator is deduced for that parameter.
Hash It has a
template parameter and a type that qualifies as an allocator is deduced for that parameter.
Pred - It has an
template parameter and
Alloc is
uses_allocator_v < X , Alloc > false
whereis the deduced type of the associative container.
X
(We think that change is not strictly necessary, but it clarifies our intent.)
Add one new deduction guide for each unordered associative container. For example, modify [unord.set.overview] as follows:
template < class InputIterator , class Hash = hash < iter - value - type < InputIterator >> , class Pred = equal_to < iter - value - type < InputIterator >> , class Allocator = allocator < iter - value - type < InputIterator >>> unordered_set ( InputIterator , InputIterator , typename see below :: size_type = see below , Hash = Hash (), Pred = Pred (), Allocator = Allocator ()) -> unordered_set < iter - value - type < InputIterator > , Hash , Pred , Allocator > ; template < class T , class Hash = hash < T > , class Pred = equal_to < T > , class Allocator = allocator < T >> unordered_set ( initializer_list < T > , typename see below :: size_type = see below , Hash = Hash (), Pred = Pred (), Allocator = Allocator ()) -> unordered_set < T , Hash , Pred , Allocator > ; template < class InputIterator , class Allocator > unordered_set ( InputIterator , InputIterator , typename see below :: size_type , Allocator ) -> unordered_set < iter - value - type < InputIterator > , hash < iter - value - type < InputIterator >> , equal_to < iter - value - type < InputIterator >> , Allocator > ; template < class InputIterator , class Hash , class Allocator > unordered_set ( InputIterator , InputIterator , typename see below :: size_type , Hash , Allocator ) -> unordered_set < iter - value - type < InputIterator > , Hash , equal_to < iter - value - type < InputIterator >> , Allocator > ; template < class T , class Allocator > unordered_set ( initializer_list < T > , typename see below :: size_type , Allocator ) -> unordered_set < T , hash < T > , equal_to < T > , Allocator > ; template < class T , class Hash , class Allocator > unordered_set ( initializer_list < T > , typename see below :: size_type , Hash , Allocator ) -> unordered_set < T , Hash , equal_to < T > , Allocator > ; template < class T , class Hash , class Pred , class Allocator , class Alloc > unordered_set ( set < T , Hash , Pred , Allocator > , Alloc ) -> unordered_set < T , Hash , Pred , Allocator > ;
2.4. Implementation note
While implementers may of course implement this proposal exactly as described in the wording options above, we wish to point out that a number of library implementations already behave in many cases as we are proposing here as shown in the following table and this Godbolt:Construct | Well-formed | SFINAE-friendly ill-formed | Hard error |
---|---|---|---|
std::deque(pd, &mr) | MSVC, libstdc++, libc++ | ||
std::forward_list(pfl, &mr) | MSVC, libstdc++, libc++ | ||
std::list(pl, &mr) | MSVC, libstdc++, libc++ | ||
std::vector(pv, &mr) | MSVC, libstdc++, libc++ | ||
std::map(pm, &mr) | MSVC | libstdc++, libc++ | |
std::multimap(pmm, &mr) | MSVC | libstdc++, libc++ | |
std::multiset(pms, &mr) | MSVC | libstdc++, libc++ | |
std::set(ps, &mr) | MSVC | libstdc++, libc++ | |
std::unordered_map(pum, &mr) | MSVC, libstdc++ | libc++ | |
std::unordered_multimap(pumm, &mr) | MSVC, libstdc++ | libc++ | |
std::unordered_multiset(pums, &mr) | MSVC, libstdc++ | libc++ | |
std::unordered_set(pus, &mr) | MSVC, libstdc++ | libc++ | |
std::priority_queue(ppq, &mr) | MSVC, libstdc++, libc++ | ||
std::queue(pq, &mr) | MSVC, libstdc++, libc++ | ||
std::stack(ps, &mr) | MSVC, libstdc++, libc++ | ||
std::priority_queue(pv, &mr) | MSVC, libstdc++, libc++ | ||
std::queue(pd, &mr) | MSVC, libstdc++, libc++ | ||
std::stack(pv, &mr) | MSVC, libstdc++, libc++ |
The following analysis explains why MSVC, in effect, already implements the approach described in wording option 1 above. Consider the implicit guide generated from the constructor
template < class Key , class Hash , class Pred , class Allocator > class unordered_set { unordered_set ( const unordered_set < Key , Hash , Pred , Allocator >& , const Allocator & ); };
From the first parameter, we deduce
,
,
,
and
.
From the second parameter, we should deduce
.
We’ve deduced conflicting types for
, so deduction fails.
However, in practice, both MSVC and libstdc++ launder the
type through a typedef
that is opaque to deduction, so
that the constructor seen by the compiler in practice is equivalent to
template < class Key , class Hash , class Pred , class Allocator > class unordered_set { using allocator_type = typename type_identity < Allocator >:: type ; unordered_set ( const unordered_set < Key , Hash , Pred , Allocator >& , const allocator_type & ); };
From the first parameter, we deduce
,
,
,
and
.
From the second parameter, we don’t deduce anything.
In practice, therefore, deduction succeeds.
Implementers who have taken the above approach can use that to simplify their implementation of this proposal, as an alternative to directly implementing the above wording (which is of course also perfectly fine).