5

The recommended way (eg: Sorting a vector in descending order) of sorting a container in reverse seems to be:

std::sort(numbers.begin(), numbers.end(), std::greater<int>());

I understand the third argument is a function or a functor that helps sort() make the comparisons, and that std::greater is a template functor, but I don't understand what's going on here. My C++ is quite rusty so please bear with me if these are stupid questions: Why are there parentheses after std::greater<int> there? Are we creating a new std::greater object here? In that case, why don't we need the new keyword here?

Community
  • 1
  • 1
Sundar R
  • 13,776
  • 6
  • 49
  • 76
  • 3
    I hope you don't associate `new` with creating objects. – Rapptz Aug 04 '13 at 19:30
  • `new` returns a pointer, not an object. – David G Aug 04 '13 at 19:31
  • I've been through quite a few languages after C++ that `new` means many things to me, I think that was the reason for the confusion. In C++ new is only needed only for dynamically allocated objects, otherwise you can call the constructor directly, is that correct? – Sundar R Aug 04 '13 at 19:35
  • @sundar Correct. Do not use `new` unless you're dynamically allocating, and even then just use a smart pointer. – Rapptz Aug 04 '13 at 19:35

1 Answers1

7

Why are there parentheses after std::greater there? Are we creating a new std::greater object here?

That's correct. The expression std::greater<int>() corresponds to creating an object of type std::greater<int>.

In that case, why don't we need the new keyword here?

We don't need the new keyword because the object is being created on the stack, rather than on the heap. Only objects created dynamically need to be on the heap. The difference is clearly explained here.

Basically, at compile time, the compiler already knows how much memory to allocate for the object, as well as when it should be destroyed (which is when the std::sort function goes out of scope). new should be used whenever

  • this information is not available -- a simple example is when you want to create an array of objects, but you don't know how many objects, until the program actually runs; and/or
  • you want objects to have persistent storage duration, i.e. you want the object to outlast the lifetime of the scope where it was created.
Community
  • 1
  • 1
maditya
  • 8,626
  • 2
  • 28
  • 28
  • exactly what i started writing. +1 – Ran Eldan Aug 04 '13 at 19:40
  • Thanks for the nice explanation. One clarification: "a simple example is when you want to create an array of objects, but you don't know when;" - do you meant to say "don't know how many;" here? If not, I'm afraid I don't get what that part means. – Sundar R Aug 04 '13 at 19:49
  • @sundar Sorry you're right, I meant "you don't know how many" – maditya Aug 04 '13 at 19:50
  • Thanks a lot, accepted the answer. I'm curious about two things now, but they're tangential to the original question: 1. why is greater implemented as a functor and not just a function, since std::sort accepts function pointers too? 2. "the object is being created on the stack" -> in this use case, does it get created in our function's stack and then copied to std::sort's argument stack, or is there only one copy created in std::sort's stack? – Sundar R Aug 04 '13 at 20:02
  • No problem. As for your questions: (1) I'm debating whether this question is actually the same as "Why use functors rather than just functions?" Functors allow storage of state, can be inherited from, can be serialized and sent remotely over a network, etc., none of which functions can do. But then greater doesn't store state, and in std::sort it is passed by value, so an object inheriting from it would just be sliced anyway. So I don't know. Maybe there are other functions where it is passed by reference. ...Please hold for answer to (2) in next comment... – maditya Aug 04 '13 at 20:12
  • 1
    (2) From [here](http://stackoverflow.com/questions/15999691/why-the-destructors-are-called-twice-for-this-functor), and from the [interface to std::sort](http://www.cplusplus.com/reference/algorithm/sort/), I believe it does get copied. In fact, now I'm curious why it isn't simply passed by reference. I may ask this as a question myself, if you don't :) – maditya Aug 04 '13 at 20:18
  • 1
    You're right that the object is not placed on the heap; that doesn't imply it is placed on the stack, however. In this case it's probably only used for type information during compilation, and optimized away completely. – Ben Voigt Aug 04 '13 at 20:40
  • It would be very rare for slicing to occur with `std::sort`, because it is a template. You'd have to intentionally make the argument type different from the most-derived type of the functor. But yes I agree that a plain function (passed to `std::sort` as a function pointer) would also work. Functions take part in type inference though, which isn't desired here. – Ben Voigt Aug 04 '13 at 20:42
  • @BenVoigt Could you elaborate on the type information thing? If I understand correctly, you're saying `std::sort` is specialized according to the type of the comparator provided, so that instead of calling the `operator()` for every comparison, `>` is used instead. Which would be _awesome_. – maditya Aug 04 '13 at 20:46
  • @BenVoigt On the template thing, I completely forgot that Comparator is a template parameter, in which case there is no slicing, as you say. Still, is there any reason it needs to be passed by copy rather than by reference? Is there no scenario where someone might want to mutate the comparator, e.g. to keep track of how many times the comparison returned true or something? – maditya Aug 04 '13 at 20:52
  • @madita: Yes, `std::sort` is specialized based on the type of the provided comparison functor, and compilers will be pretty good at inlining the call to `operator()`. – Ben Voigt Aug 04 '13 at 21:36