13

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?

Community
  • 1
  • 1
TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • Neither. Your code contains UB because of dangling reference. – cpplearner Feb 15 '17 at 08:45
  • 2
    @cpplearner I don't think so, `my_stack` is a named variable, and the reference is stored inside the `Reverse` object, so what is dangling here? – TemplateRex Feb 15 '17 at 08:47
  • 1
    But `Reverse(my_stack)` is not a named varible, and you store a reference to it inside `Reverse(Reverse(my_stack))`. – cpplearner Feb 15 '17 at 08:49
  • Maybe you can fix it by adding a move constructor that copies begin() and end() from the range. – pschill Feb 15 '17 at 08:55
  • I think this is similar to `std::tuple t(std::tuple(1));` -- should `t` be `tuple>` or a copy of `tuple(1)` ? (I think the latter) – Piotr Skotnicki Feb 15 '17 at 09:04
  • How does it even compile without specifying the template arguments in the contructor – like you did in the function? If I use `Reverse>>(Reverse>(my_stack))` instead, I get a runtime error; probably bescause of _dangling reference_. – Albjenow Feb 15 '17 at 09:09
  • @Albjenow this is a c++1z feature, works also e.g. for `std::pair` so that you don't have to use the `make_pair` function helper – TemplateRex Feb 15 '17 at 09:11
  • @TemplateRex thanks, didn't noticed the tag and haven't used the new standard yet. – Albjenow Feb 15 '17 at 09:14
  • @cpplearner but I store it inside the class using `const&` so that should bind the temporary, right? – TemplateRex Feb 15 '17 at 09:14
  • 1
    @TemplateRex it doesn't bind directly to that reference, so it's UB in the second snippet, and probably ok in the first, where move construction is used, but overall it's not the cause of the behavior – Piotr Skotnicki Feb 15 '17 at 09:19
  • @PiotrSkotnicki simply storing the `rng` member by value [doesn't fix this](http://melpon.org/wandbox/permlink/3lIutnd3DqVcl36C) – TemplateRex Feb 15 '17 at 09:26
  • 2
    The contructor of the outer `Reverse` is a copy constructor and therefore uses the same template argument. – Albjenow Feb 15 '17 at 09:26
  • 1
    @TemplateRex yes, as I said, UB is not the root cause of the behavior you spot, the thing is that `Reverse(Reverse(my_stack))` or even `Reverse(Reverse(Reverse(Reverse(my_stack))))` is still a copy of a single `Reverse(my_stack)` – Piotr Skotnicki Feb 15 '17 at 09:27
  • @TemplateRex yes, as I checked, `std::tuple t(std::tuple(1));` yields `std::tuple`, not `std::tuple>`, which I think is correct behavior, but I have no reference to prove this – Piotr Skotnicki Feb 15 '17 at 09:34
  • 2
    @PiotrSkotnicki OK, that makes sense, but it's still surprising. I guess range wrappers still need helper functions – TemplateRex Feb 15 '17 at 09:35

2 Answers2

8

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.

Piotr Skotnicki
  • 46,953
  • 7
  • 118
  • 160
  • I may be totally wrong, please correct me, I'm curious too. – Piotr Skotnicki Feb 15 '17 at 10:12
  • I think you're right, +1. Real question is - is this the intended behavior of the feature, or no? It's certainly surprising. – Barry Feb 15 '17 at 12:48
  • Basically correct, except that it's the move constructor. @Barry "surprising" how? – T.C. Feb 15 '17 at 13:46
  • @T.C. I can't really articulate it. It both makes sense that it's a move, and doesn't. And the fact that ultimately we have to write a factory anyway to do the right thing, when half the point of the proposal was obviating the need for factories, is unfortunate. – Barry Feb 15 '17 at 13:54
  • 1
    @Barry You have to choose one way or the other, and it seems to me that the current choice leads to fewer surprises than the alternative. Also, you don't need a factory; an explicit guide will do. – T.C. Feb 15 '17 at 13:59
  • @T.C. What would that explicit guide look like? – Barry Feb 15 '17 at 14:02
  • 2
    @Barry `template Reverse(R) -> Reverse;` should do it. – T.C. Feb 15 '17 at 14:03
  • @Barry ...so? [The point is to get the tie broken the other way around](https://timsong-cpp.github.io/cppwp/over.match.best#1.6). – T.C. Feb 15 '17 at 14:32
  • @T.C. Ah. I just tested the code in gcc and it did the same thing - they apparently don't implement that rule yet. Thanks. – Barry Feb 15 '17 at 14:41
  • The "intended behavior" is mostly that `optional o(1); optional p(o);` should not produce `optional>`. – Davis Herring Sep 18 '17 at 06:56
6

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.

Barry
  • 286,269
  • 29
  • 621
  • 977
  • Under the current wording, you want `R`, not `R const &`, otherwise #3 wins because [its ICS is better](https://timsong-cpp.github.io/cppwp/over.ics.rank#3.2.3) (binding rvalue ref to an rvalue). Clang seems to [intentionally do this part differently](https://github.com/llvm-mirror/clang/commit/5b38d7133e9cd36796e369aaa8f58b51dfe972d1). – T.C. Feb 15 '17 at 15:19
  • Would this force all copies to actually reverse the container again? – David Stone Feb 15 '17 at 18:06
  • @DavidStone I don't understand the question. – Barry Feb 15 '17 at 18:16
  • @Barry thanks, nice to get a grip on these new deduction guides. I wonder though, if this is the new SFINAE where you really have to think very carefully about all the overloads in play and that you have to give a by-value constructor a deduction guide to get around rvalue matches. It would be much more intuitive (say what you mean principle) if one were able to give a `const&` deduction guide. – TemplateRex Feb 15 '17 at 19:27
  • @TemplateRex I am worried with the added complexity :-/ It's certainly nice for `std::lock_guard`, but... – Barry Feb 15 '17 at 19:41
  • This no longer seems to work with clang 6 and above or any gcc :( [minimal example](https://godbolt.org/z/QLoLFq) – namark Dec 14 '18 at 19:33
  • 1
    @namark That's because it was always wrong!! OOPS. Now it's correct. The copy deduction candidate is more specialized than the guide I had before (and more specialized comes before deduction-guide in the list of precedence) – Barry Dec 14 '18 at 20:58