Why are there two implementations of std::sort (with and without a comparator) rather than one implementation with a default template parameter?

Question

In my code I'm adopting a design strategy which is similar to some standard library algorithms in that the exact behavior can be customized by a function object. The simplest example is std::sort, where a function object can control how the comparison is made between objects.

I notice that the Visual C++ provides two implementations of std::sort, which naturally involves code duplication. I would have imagined that it was instead possible to have only one implementation, and provide a default comparator (using operator< ) as a default template parameter.

What is the rational behind two separate versions? Would my suggestion make the interface more complex in some way? Or result in confusing error messages when the object does not provide operator< ? Or maybe it just doesn't work?

Thanks,

David

"*I notice that the Visual C++ provides two implementations of std::sort, which naturally involves code duplication.*" Why would you think that? The obvious implementation is for the overload lacking a predicate argument to be implemented in terms of the overload taking a predicate argument (passing `std::less::value_type>()` for said argument). — ildjarn, Jun 29 '12 at 15:19
_"Why would you think that?"_ - I'm looking at the implementation of algorithm which ships with Visual C++ and seeing two seperate implementations. — David Williams, Jun 29 '12 at 15:26
That's a single, apparently poor implementation; I was picking on the word 'naturally', which is most certainly not accurate. — ildjarn, Jun 29 '12 at 15:28

score 12 · Accepted Answer · edited May 23 '17 at 10:09

12

Because function templates are not allowed by the standard to have default type arguments.

This, however, was amended in C++11, and now function templates can have default type arguments.

edited May 23 '17 at 10:09

Community

1
1

answered Jun 29 '12 at 15:13

Seth Carnegie

73,875
22
181
249

3

I'll mention that, while correct, this is now just an historical reason, because C++11 allows it. – R. Martinho Fernandes Jun 29 '12 at 15:15
Knowing next to nothing about templates in C++, are you not allowed to overload function templates? – JAB Jun 29 '12 at 15:16
@JAB yes you are, and that's encouraged over specialising them. – Seth Carnegie Jun 29 '12 at 15:16
@R.MartinhoFernandes yeah, I just wanted to make sure before I added that to the answeer. – Seth Carnegie Jun 29 '12 at 15:16
So if you were using non-C++11 code, you could simply have the overloaded template with less template arguments wrap the one with more arguments? Last I checked, that's the general convention for languages that prefer overloading to utilization of default arguments. – JAB Jun 29 '12 at 15:20
@JAB That's exactly what there is: two overloads of `std::sort`. – R. Martinho Fernandes Jun 29 '12 at 15:22
@R. Martinho Fernandes One does not appear to wrap the other though (but ultimatly they do both wrap a heap sort or insertion sort). – David Williams Jun 29 '12 at 15:24

score 2 · Answer 2 · answered Jun 29 '12 at 15:16

2

Prior to C++11, a function template could not have default template arguments, and a template argument cannot be deduced from a default function argument, so there was no way to make this work.

In C++11, which supports default template arguments for function templates, you could use a single function template, but changing it now would break backwards compatibility with older C++ code that relies on the functions having a particular type.

answered Jun 29 '12 at 15:16

James McNellis

348,265
75
913
977

Ok, thank you. I think I'd rather avoid requireing C++11 support from my users so I guess I'll follow the STL model. – David Williams Jun 29 '12 at 15:22
That's especially important if you are supporting Visual C++ (which you indicate in your question), because it does not yet support C++11's default function template arguments :-) – James McNellis Jun 29 '12 at 15:28
Ah, well, that settles it then :-) – David Williams Jun 29 '12 at 20:14

Why are there two implementations of std::sort (with and without a comparator) rather than one implementation with a default template parameter?

2 Answers2