Nested template argument deduction for class templates not working

Question

In this Q&A I wrote a little wrapper class that provides reverse iterator access to a range, relying on the c++1z language feature template argument deduction for class templates (p0091r3, p0512r0)

#include <iostream>
#include <iterator>
#include <vector>

template<class Rng>
class Reverse
{
    Rng const& rng;    
public:    
    Reverse(Rng const& r) noexcept
    : 
        rng(r)
    {}

    auto begin() const noexcept { using std::end; return std::make_reverse_iterator(end(rng)); }
    auto end()   const noexcept { using std::begin; return std::make_reverse_iterator(begin(rng)); }
};

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.puhs_back(3);

    // prints 3,2,1
    for (auto const& elem : Reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

However, doing a nested application of Reverse does not yield the original iteration order

// still prints 3,2,1 instead of 1,2,3
for (auto const& elem : Reverse(Reverse(my_stack))) {
    std::cout << elem << ',';    
}

Live Example (same output for g++ 7.0 SVN and clang 5.0 SVN)

The culprit seems to be the template argument deduction for class templates because the usual wrapper function does allow for correct nesting

template<class Rng>
auto MakeReverse(Rng const& rng) { return Reverse<Rng>(rng); }

// prints 1,2,3
for (auto const& elem : MakeReverse(MakeReverse(my_stack))) {
    std::cout << elem << ',';    
}

Live Example (same output for g++ and clang)

Question: is nested template argument deduction for class templates supposed to work only "one level" deep, or is this a bug in the current implementations of both g++ and clang?

Answer 1

This may be explained in [over.match.class.deduct]/p1:

A set of functions and function templates is formed comprising:

• For each constructor of the class template designated by the template-name, a function template with the following properties:

• The template parameters are the template parameters of the class template followed by the template parameters (including default template arguments) of the constructor, if any.

• The types of the function parameters are those of the constructor.

• The return type is the class template specialization designated by the template-name and template arguments corresponding to the template parameters obtained from the class template.

My understanding is that the compiler invents the following two functions (two - including a copy constructor that is implicitly generated for this class):

template <typename Rng>
Reverse<Rng> foo(const Rng& r);           // #1

template <typename Rng>
Reverse<Rng> foo(const Reverse<Rng>& r);  // #2

and then tries to select the best overload based on the call:

foo(Reverse<std::vector<int>>(my_stack));

which resolves to #2 because this one is more specialized. The conclusion is that:

Reverse(Reverse(my_stack))

involves a copy constructor to construct the outer Reverse instance.

Answer 2

Piotr's answer correctly explains what is happening - the move constructor is a better match than your constructor template.

But (h/t T.C. as usual) there's a better fix than just writing a factory anyway: you can add an explicit deduction guide to handle the wrapping:

template <class R>
Reverse(Reverse<R> ) -> Reverse<Reverse<R>>;

The point of this is to override the copy deduction candidate, thanks to the newly added preference in [over.match.best] for this:

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if [...] F1 is generated from a deduction-guide (13.3.1.8) and F2 is not.

Hence, we'd have four generated functions, borrowing again from Piotr's naming:

template <typename Rng>
Reverse<Rng> foo(const Rng& r);             // #1

template <typename Rng>
Reverse<Rng> foo(const Reverse<Rng>& r);    // #2

template <typename Rng>
Reverse<Rng> foo(Reverse<Rng>&& r);         // #3

template <typename Rng>
Reverse<Reverse<Rng>> foo(Reverse<Rng> r);  // #4 - same-ish as #2/3, but deduction guide

Before, #3 was preferred as being more specialized. Now, #4 is preferred as being a deduction guide. So, we can still write:

for (auto const& elem : Reverse(Reverse(my_stack))) {
    std::cout << elem << ',';    
}

and that works.