21

I was reading cpp-next where this min template is presented as an example of how verbose C++ code can be compared to python code

template <class T, class U>
auto min(T x, U y)->decltype(x < y ? x : y)
{ return x < y ? x : y; }

At first this looks innocent but Daveed Vandevoorde made this remark

The min template that uses decltype in its return type specification doesn’t work: It returns a reference (because the argument is an lvalue) that ends up referring to a local variable in most common uses.

I figured it may not be clear to everyone how the problem manifests. Can you please give a detailed explanation and possible fixes?

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • 3
    I am waiting for you to post the answer now, pleaseee.. :) – Alok Save Nov 19 '11 at 15:53
  • I'm a bit curious in regards to what happens if T and U are different types? Will that even work? – ronag Nov 19 '11 at 16:05
  • @ronag: If they are somehow convertible to a common "base". :) float and int should both be convertible to float, which will be the type of the expression. – Xeo Nov 19 '11 at 16:07
  • So in the end, for those of us who don't really get the details (the code in e.g. @Potatoswatter is too complex for me), what are we supposed to write? a `min` function with only one template parameter (i.e. with no trick to compute the return type)? – rafak Nov 20 '11 at 13:50
  • For C++03, the [promote](http://stackoverflow.com/questions/2426330/uses-of-a-c-arithmetic-promotion-header/2450157#2450157) template can be used to compute the return type :) – Johannes Schaub - litb Nov 21 '11 at 22:35

5 Answers5

8

The problem is that the arguments aren't taken as references. This invokes slicing, in the case of polymorphic types, and then a reference return to local variable. The solution is to take the arguments as rvalue references, invoking perfect forwarding, and then simply deduce and return the return type. When this is done, returning a reference is just fine, as the value still exists.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
Puppy
  • 144,682
  • 38
  • 256
  • 465
  • +1 for correct idea - I suppose the first sentence doesn't lack the absence of a negation – sehe Nov 19 '11 at 17:47
  • I disagree. The problem is *returning* by reference, because then you can do: `float& f = std::min(3.0f, 1);` which is incorrect. – Matthieu M. Nov 19 '11 at 18:30
  • @Matthieu the problem would be solved if we would have the parameters be `T&&` and `U&&` as far as I can see (or even be simple `U const&` and `T const&`). If you use perfect forwarding as proposed, your code would be illegal (it would be anyway in that case even without `std::forward` because `decltype(e ? x : y)` for both lvalue and rvalue `x` and `y` would be `float` and hence it would return a non-reference type). With `std::forward` even `float &f = min(3.0f, 2.0f)` is rejected. So I like this approach. – Johannes Schaub - litb Nov 19 '11 at 18:39
  • 2
    +1 Tried and failed to do this for C++11: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2199.html – Howard Hinnant Nov 19 '11 at 20:26
  • 1
    @Matthieu: No, you can't, because the result of `?:` when both it's parameters are rvalues is an rvalue. – Puppy Nov 19 '11 at 21:37
  • I edited the post so I could change my downvote to an upvote (I hate that you cannot change your vote at will :x), the paper by Howard is quite amazing... all this for a "trivial" function, uh! – Matthieu M. Nov 20 '11 at 11:48
  • No offense, but I really dislike this answer. The problem with the original version of the function had nothing to do with how the arguments were passed; it was about the computed result type—you can tell that I wasn't trying to return a reference from earlier examples in the article. The issue was that I had neglected lvalue/rvalue considerations in the use of decltype (a very common pitfall with the use of expressions to generate types), so I needed to remove the reference. The change to pass-by-reference by itself doesn't help with that. – Dave Abrahams Nov 20 '11 at 22:32
  • Also, I consider the issue of supporting runtime polymorphism for what is essentially a numeric function to be suspect at best, especially in the context of this example. Finally, a function that returns a reference gives fundamentally different guarantees than one that returns a value. Taking the arguments as rvalue references and returning a reference isn't a solution to anything if you think you should be able to bind a local reference to the return value and thereby keep it alive. – Dave Abrahams Nov 20 '11 at 22:32
  • 2
    @DaveAbrahams: But not trying to return a reference is *wrong*. You should be able to do things like `std::min(a, b) = 5;` if `a` and `b` are both `int`, for example. – Puppy Nov 21 '11 at 09:54
  • @Dave hmm then I think I misunderstand something. From the article it seems that your first version was `template auto min(T x, U y)->decltype(x < y ? x : y) { return x < y ? x : y; }`. The problem with this is that `x` and `y` do not refer to temporaries of the full expression of the call to `min`, but that they are local to `min`. If you change `x` and `y` to be suitable references of any kind (for example, lvalue references), then you can leave your return type as you wrote it, and the problem Daveed pointed out is fixed, isn't it? – Johannes Schaub - litb Nov 21 '11 at 21:56
  • Because then, if `decltype(x < y ? x : y)` turns out to be a reference, you will not anymore reference local parameters of `min`, but you will reference the temporaries in the full expression of the call to `min`. So the reference that `min` returns will keep referring to a valid object until the end of the full expression. So while this may not be the fix that makes `min` be like you originally intended it, it may indeed fix the problem with the original version of the function. – Johannes Schaub - litb Nov 21 '11 at 21:59
  • But I think it would be better to change the return type to be not a reference if one of the arguments was an rvalue. This would fix `int const& a = std::min(10, 20);` - with this answer's proposed solution, this would create a dangling reference. But if we would use a non-reference type if one of the arguments is an rvalue, this would work fine. Note that `float const& a = std::min(10, 20.f);` works already fine with this answer, because the conditional operator gives us a non-reference type since the two sides of the conditional expression will be converted. – Johannes Schaub - litb Nov 21 '11 at 22:29
  • @Johannes, yes, I could have done what you say, and I'd have been writing a different function with a different contract. The point of the article was not “what's the most generic way to write min,” which is an interesting question in and of itself. I was just using `min` as an example. @DeadMG: not *wrong*, just *different*. – Dave Abrahams Nov 28 '11 at 20:57
  • @HowardHinnant What exactly happened to your min/max proposal? I looked up meeting minutes but didn't find any comments on it. – bames53 Oct 12 '12 at 15:49
  • @bames53: It was rejected on the grounds that it was too complicated. As I recall there was an opening to amend this proposal to become less complicated by solving fewer problems. But it wasn't clear to me what to cut that would have reached consensus, and it did not become a big enough priority for anyone (including myself) to pursue. – Howard Hinnant Oct 13 '12 at 01:09
6

rev 3: KonradRudolph

template <class T, class U>
auto min(T x, U y) -> typename std::remove_reference<decltype(x < y ? x : y)>::type
{ 
    return x < y ? x : y; 
}

rev 2: KennyTM

template <class T, class U>
auto min(T x, U y)->decltype(x < y ? std::declval<T>() : std::declval<U>())
{ 
    return x < y ? x : y; 
}

rev 1: T and U must be default constructible

template <class T, class U>
auto min(T x, U y)->decltype(x < y ? T() : U())
{ 
    return x < y ? x : y; 
}

test:

int main()
{
   int x; int y;
   static_assert(std::is_same<decltype(min(x, y)), int>::value, "");
   return 0;
}

EDIT:

I'm a bit surprised but it actually compiles with remove_reference.

ronag
  • 49,529
  • 25
  • 126
  • 221
  • No, `T` and `U` will be `int`. – Xeo Nov 19 '11 at 16:00
  • Xeo: Yes you are right. I pretty much contradicted myself with the cause and fix. I've changed my answer. – ronag Nov 19 '11 at 16:03
  • This of course requires `T` and `U` to be default-constructible. Can’t we use a call to some `id` function to get a temporary from either `x` or `y` to force use of a non-reference? … Or just `remove_reference` … – Konrad Rudolph Nov 19 '11 at 17:05
  • @KonradRudolph: `std::declval()`. – kennytm Nov 19 '11 at 17:13
  • @KennyTM But that returns an rvalue reference, hence we’ve got the same problem as before, don’t we? – Konrad Rudolph Nov 19 '11 at 17:17
  • @KonradRudolph: `decltype(x < y ? std::declval() : std::declval())` does return a non-reference type *on gcc* though. Not quite sure where in the spec says this. – kennytm Nov 19 '11 at 17:30
  • Instead, they should simply *take the arguments* as references. – Puppy Nov 19 '11 at 17:34
  • @KonradRudolph: Even if it returns an rvalue reference it shouldn't be a problem should it? Returning as rvalue reference is the same as returning by value as far as i know? – ronag Nov 19 '11 at 17:35
  • `template auto min(T x,U y) -> typename std::common_type::type { return x – bames53 Nov 19 '11 at 21:02
  • I see my version is the first C++ version the writer in the article uses. I don't understand why he goes past that, except to deliberately find the most complex way to do this possible. – bames53 Nov 19 '11 at 21:09
  • bames52: With your version you might as well write: template typename std::common_type::type min(T x,U y){ return x – ronag Nov 19 '11 at 21:27
  • Stupid question wrt `remove_reference`: but what if the original types had a reference ? – Matthieu M. Nov 20 '11 at 11:44
3

The arguments are passed by value (T and U deduced as int), but the type of ?: expression is deduced as a reference in this case since they are local lvalues inside the function. Specifics will be in @Johannes' answer that should come in a few minutes. :D

Xeo
  • 129,499
  • 52
  • 291
  • 397
  • i'm just confused :( i don't know about the tricky rules behind all this. – Johannes Schaub - litb Nov 19 '11 at 16:05
  • 12
    @Johannes: Sure. And I'm sure everyone will believe you don't know. ;) – Xeo Nov 19 '11 at 16:06
  • why deduced as reference? next code say no **void f2(int x, long y) {cout << is_reference::value << endl;}** – Yola Dec 15 '11 at 17:41
  • @yola, that's because `int` and `long` are quite different types. No single reference type can link to both. But if x and y were of the same integral types, then it would be a reference. – Aaron McDaid Dec 21 '11 at 01:57
3

What's all the fuss, and why isn't anyone trying the obvious solution, which is perfect forwarding?

template <class T, class U>
typename std::enable_if< ! std::is_integral< T >() || ! std::is_integral< U >(),
                         typename std::common_type< T, U >::type >::type
min(T &&x, U &&y)
    { return x < y ? std::forward< T >( x ) : std::forward< U >( y ); }

template <class T, class U>
decltype( typename std::enable_if< std::is_integral< T >() && std::is_integral< U >(),
                         decltype( typename std::common_type< T, U >
         ::type{ U( -1 ) } ) >::type{ T( -1 ) } )
min(T &&x, U &&y)
    { return x < y ? std::forward< T >( x ) : std::forward< U >( y ); }

Now it works just as if you put the expression in the calling function, which is exactly what the user expects (and simply the best thing overall).

Edit: Now it prohibits dangerous unsigned vs. signed operations, per Howard's paper, by requiring that the conversion from each operand type to the result type be non-narrowing if both operands are of integral type. However, GCC won't compile this, complaining "sorry, unimplemented: mangling constructor." This seems to occur if uniform initialization is used in any way in the function signature.

Potatoswatter
  • 134,909
  • 25
  • 265
  • 421
1

Returning by reference might sometimes be a feature, not a bug. We'll return to this later. First a recap of the basics:

int x; int y;
x    // this is an lvalue
y    // lvalue also
x+y  // not an lvalue - you couldn't do (x+y) = 3
x<y?x:y // lvalue - you can do (x<y?x:y) = 0

The last line shows that a ?: can often be an lvalue. i.e. You can do (x<y?x:y)=0 to set the smallest variable to 0 and leave the other one alone. Of course, you can't do (1<3?6:8)=0 as you can't do 6=0 or 8=0. So it's just an rvalue in that case.

Inside min, x and y are the names of the function parameters and hence are lvalues. decltype(x<y?:x:y) is int&. (I found this other cpp-Next article useful also.)

So why might this be a problem? Well, if the return type of min is a reference, then it will return a reference to one of x or y, the function parameters. The question now is, were x and y references themselves?

Consider this use case:

int m = 5; int n = 10;
min(m,n) = 0; // do you want this to work?

We have a decision to make. Maybe we want min to return references, if the arguments to min were references. I guess it's somewhat a matter of taste. If you rigorous want to return only non-references, this is easy to enforce with std::remove_reference around the decltype(x<y?x:y). But that's boring. Let's allow ourselves to (sometimes) return references; it might be more efficient and useful in many cases.

If you use the original example definition of min, along with non-reference types for x or y, then min will return a reference to the local values among its parameters. This is bad as the references will be invalid and the behaviour undefined. For example, this would be bad:

int p = min(5,8); // reading from a now-invalid reference.

So, we have to go through a variety of use-cases and decide what behaviour we want:

// Desired behaviour
int m = 5;
int n = 10;
min(3,7); // return by value. i.e. return an int
min(m,n); // return an int& which maps to either m or n
min(3,n); // return by value
min(foo(), bar()) // what makes sense here?

Can we all agree on what behaviour we would want from such a min? And then, how do we implement it?

Aaron McDaid
  • 26,501
  • 9
  • 66
  • 88