Menu
The standard on std::reference_wrapper explains that std::sort now accepts std::reference_wrapper, allowing one to pass a comparator by reference.
Is there a reason std::sort didn't accept the comparator by reference in the first place?
279
The std::sort is a sorting function that uses the Introsort algorithm and have the complexity of O(N log(N)) where N= std::distance(first, last) since C++11 and the order of equal elements is not guaranteed to be preserved[3]. The gcc-libstdc++ also uses Introsort algorithm.
As of September 2020, it appears that libc++ std::sort happens to be stable for all ranges of size less than 31, and libstdc++ std::sort happens to be stable for all ranges of size less than 17. (Do not rely on this little factoid in production!) To be clear: There's nothing wrong with this.
std::sort() is a built-in function in C++'s Standard Template Library. The function takes in a beginning iterator, an ending iterator, and (by default) sorts the iterable in ascending order. The function can also be used for custom sorting by passing in a comparator function that returns a boolean.
In short, there was no need to take it by reference; it amounts to a "by design" decision.
I believe the reasoning centres around a few fundamentals that have existed in C++ and the Standard Library for a long time;
The value semantics can be seen pretty much everywhere. Almost all the algorithms, containers etc. expect the data contained therein to obey the normal rules of values, i.e. behave as if they were built-in type. That's one of the reasons behind the C++ type system as well, to enable user types to behave as if they where built-in types.
The implementation of the algorithm(s) are free to copy the function arguments around as they require. Limiting the signature to a reference when the implementation is allowed to copy the functor around is not very useful; so just allow the copy from the outset. What this means is that the function objects shouldn't contain any state, it may not be preserved; in turn this effectively makes the functors very light and there is no reason for the reference anyway.
25.1/10 Algorithms library (C++ draft n3797)
[ Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper (20.9.3), or some equivalent solution. —end note ]
A general note on API design. API design for specifications and standards, especially with templates, is a non-trivial task at the best of times. Would the committee have designed the function differently today with r-values, reference collapsing, perfect forwarding and move semantics? I don't know. In my opinion, taking the function object by value balances the issues relating to internal copies and moves, possible optimizations, and binding to temporary objects (pr-values/x-values). A "universal reference" here may have been better, but I get the feeling that the legacy argument would outweigh an argument in favour of the change.
113
In C++03, accepting the comparator by reference would prevent binding to a non-const rvalue, e.g. a function pointer expression:
bool comp(T const&, T const&);
sort(first, last, &comp);
Or a temporary functor:
struct Comparator { bool operator()(T const&, T const&) { ... } };
sort(first, last, Comparator());
In C++11, taking the comparator by universal reference would avoid this issue, but is an unnecessary change because we have reference_wrapper.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
