Sign in to follow this  
lightxbulb

template functions and STL list.sort

Recommended Posts

lightxbulb    1164

Hi!

With C++ I've currently gotten to the part  where I am learning different STL containers. I've been playing around with lists but I get an error, I just want to know why do I get an error when I do this:

template <typename T>
bool sortDescending(const T& in1, const T& in2)
{
    return in1>in2;
}

 

and then I just try to sort some list with it:

myList.sort(sortDescending);

 

If I change my sort function it's all fine:

bool sortDescending(const int& in1, const int& in2)
{
    return in1>in2;
}

 

 

Can anybody explain why exactly C++ forbids me from writing a more generic sort function?

Share this post


Link to post
Share on other sites
Brother Bob    10344

You can write a generic template sorting function, but you have to instantiate it with the proper type when you pass it to the sort function. The C++ type system cannot deduce the template parameter in that case so you have to provide it.

myList.sort(sortDescending<int>);

Share this post


Link to post
Share on other sites
alvaro    21246

I am not sure I can explain the exact reason for that being disallowed, but I can tell you how to fix it:

 

myList.sort(sortDescending<int>);

 

Now I'll try to explain it anyway. The compiler tries to figure out the type of what you are passing to std::list<int>::sort, and it can't figure it out because you are passing something with an "unresolved overloaded function type" (that's what the error message in g++ calls it). If you specify sortDescending<int>, now the compiler knows the type being passed and can continue to figure out what version of the overloaded std::list<int>::sort you are calling.

 

EDIT: Double ninja'd. I must be getting slow. :)

Edited by Álvaro

Share this post


Link to post
Share on other sites

Or you could save some typing and use

 

myList.sort(std::greater<int>);

 

EDIT: Although you probably have to type #include <functional> as well...

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
lightxbulb    1164

Thanks a lot guys!

Guess it's just me then not being used to templates xD

Even though it looks logical (to me) that the compiler will infer the evaluated type of the variables from the type of objects contained in the list, I guess it's not.

I mean the compiler usually will be able to "guess" what s the type if I write:

template <typename T>
bool greaterThan(const T& in1, const T& in2)
{
return in1>in2;
}

and:

int a=5, b=6;
cout << greaterThan(a,b) << endl; 

No error in this one...

Btw that's a little off-topic but can anybody with a C++11 compiler tell me if this works for him:

vector<int> myVec = {5, 13, -7};

 

C++ 11 should support it right? I'm on VS2012 and it seems it doesn't support some of the features for C++ 11.

Edited by lightxbulb

Share this post


Link to post
Share on other sites
lightxbulb    1164

It just seems silly being able to do this:

int someArray[] = {3, 5 -17};
vector <int> someVector(someArray, someArray + sizeof(someArray) / sizeof(int));

 

and not this:

vector<int> someVector = {3, 5, -17};
Edited by lightxbulb

Share this post


Link to post
Share on other sites

It took years for it to get into the language that feature though. And you have extra baggage associated with those (initializer_list<> template class).

 

You should use sizeof(someArray) / sizeof(someArray[0]) as well in your first example (in case you change the type of the array to something other than int).

Share this post


Link to post
Share on other sites
Brother Bob    10344

Thanks a lot guys!

Guess it's just me then not being used to templates xD

Even though it looks logical (to me) that the compiler will infer the evaluated type of the variables from the type of objects contained in the list, I guess it's not.

I mean the compiler usually will be able to "guess" what s the type if I write:

template <typename T>
bool greaterThan(const T& in1, const T& in2)
{
return in1>in2;
}

and:

int a=5, b=6;
cout << greaterThan(a,b) << endl; 

No error in this one...

There's a major difference between that example and deducing the argument of the predicate in your first post. The template parameter of greaterThan is deduced from the parameters being passed to it, while you expected that the template parameter of sortDescending to be deduced from the type of the parameter of another function to which the predicate is passed.

Edited by Brother Bob

Share this post


Link to post
Share on other sites
lightxbulb    1164

There's a major difference between that example and deducing the argument of the predicate in your first post. The template parameter of greaterThan is deduced from the parameters being passed to it, while you expected that the template parameter of sortDescending to be deduced from the type of the parameter of another function to which the predicate is passed.

Well, the predicate is called anyways - so it actually gets passed arguments from the list from which sort is called.

I mean inside of sort sortDescending is called multiple times like a normal function ( basically sortDescending(*myList.begin(), *(++myList.begin())), sortDescending(*(++myList.begin()), *(++++myList.begin())) etc.) or is it not?

I mean inside of sort you don't have to explicitly sortDescending<T>(*myList.begin(), *(++myList.begin())), sortDescending<T>(*(++myList.begin()), *(++++myList.begin())) etc.

It just seemed strange to me, don't mind it.

Edited by lightxbulb

Share this post


Link to post
Share on other sites

That's just the way it is ;) Usually you would be sorting a list which is a member of a class and you can just typedef the predicate function inside the class if you use it a lot. std::map takes the comparison predicate as a template parameter which is available as a typedef called key_compare, for example. You can use multiple typedefs for multiple predicates if you want.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Brother Bob    10344

You have to keep one thing in mind; sortDescending is not a function, it is a template. A template is a blue-print instructing the compiler how to generate the instance once you instantiate the template, and only an instantiation of the template is actually a function. In other words, sortDescending<int> and sortDescending<double> are both functions that are generated by the compiler from your template, but sortDescending is not a function; it is a template for a function.

 

The sort function takes a function, and thus your template has to be instantiated at the point it is passed to the sort function.

Edited by Brother Bob

Share this post


Link to post
Share on other sites
lightxbulb    1164

The sort function takes a function, and thus your template has to be instantiated at the point it is passed to the sort function.

Ah!ohmy.png Thanks a lot - that's what I was missing! sort is expecting a function and I provide a template... even though it will call the function multiple times later and would be able to figure out what to do with a template it still expects a function as an argument. Thanks a lot about this, I figured it out thanks to this comment. Though I wouldn't say it will be illogical if they added an overload of sort() where it can take a function template, or would it?

Edited by lightxbulb

Share this post


Link to post
Share on other sites
Brother Bob    10344

Though I wouldn't say it will be illogical if they added an overload of sort() where it can take a function template, or would it?

I cannot see how you would pass the function template to it though. It is not a value so you cannot pass it as a parameter, and it is not a type so you cannot pass it as a template parameter.

Share this post


Link to post
Share on other sites
Ravyne    14300

I know they released a C++11 features update but I don't know whether initializer lists made it in.

 

Initializer lists are not supported in VS2012, even with the features update. The big (possibly all) unsupported features are:

  • Initializer lists / uniform initialization
  • Variadic templates
  • Default template arguments for function templates
  • Raw string literals
  • Explicit conversion operators
  • Delegating constructors

Some of this missing functionality has been "emulated" to a reasonable degree in the standard library for some time though (e.g. variadic templates), which at least allowed you to start writing client code in a way that will leverage the proper features when they are added in.

 

Microsoft previewed support for some of these features to their MSDN partners awhile back, though they've not been added to the VS2012 toolchain -- the Visual Studio updates have only addressed C++ Standard Library enhancements and bug fixes.

 

With TechEd and //Build around the corner, that's when I would expect Microsoft to make an announcement about enhanced C++11 support and C++14 plans, if any.

Share this post


Link to post
Share on other sites
lightxbulb    1164

I guess asking for function templates as function arguments is too much. Maybe in a future version of C++, or maybe there's something inherently broken with the idea of passing a template function as a function argument? 

I know I can pass template classes to functions:

template<class T>
void display(const T& input)
{
for(auto i = input.cbegin(); i!=input.cend(); ++i)
{
    cout << *i << ' ';
}
cout << endl;
return 0;
}

...

vector<whateverClass> myVector;
fillVector(myVector);
display(myVector);

 

I could pass any type of vector to display(). However I still haven't learned how to pass functions to functions so I don't know if function templates can be passed too as can be class templates.

Share this post


Link to post
Share on other sites

Some of this missing functionality has been "emulated" to a reasonable degree in the standard library for some time though (e.g. variadic templates), which at least allowed you to start writing client code in a way that will leverage the proper features when they are added in.

 

This feature gave rise to my favourite quote from the MSDN:

 

"Therefore, we reduced infinity. In Visual C++ 2008 SP1 and Visual C++ 2010, infinity was 10 (that is, "variadic" templates supported 0 to 10 arguments, inclusive). By default, infinity is 5 in Visual C++ in Visual Studio 2012."

 

EDIT: Infinity is 10... no, it's 5... for small values of infinity.

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Brother Bob    10344

I guess asking for function templates as function arguments is too much. Maybe in a future version of C++, or maybe there's something inherently broken with the idea of passing a template function as a function argument? 

I know I can pass template classes to functions:

template<class T>
void display(const T& input)
{
for(auto i = input.cbegin(); i!=input.cend(); ++i)
{
    cout << *i << ' ';
}
cout << endl;
return 0;
}

...

vector<whateverClass> myVector;
fillVector(myVector);
display(myVector);

 

I could pass any type of vector to display(). However I still haven't learned how to pass functions to functions so I don't know if function templates can be passed too as can be class templates.

You're not passing a template class to the display function; you're passing an object whose type is an instance of the vector class template. There are no unknowns in that situation; the type of the object being passed is vector<whateverClass> which is a proper type and not a template class.

 

Given the nature of the language itself, you must either directly or indirectly know the type of the list you're trying to sort, so why not just instantiate the function template with the proper type? Your list myList must have a type somewhere in your code, and that type can be used to deduce the type to instantiate sortDescending with.

Share this post


Link to post
Share on other sites
lightxbulb    1164

Of course I am not passing a template class to the display() function, but the parameter for the display function can accept multiple specializations of a template.

I wanted to know if the same is possible for a function - here's some code to illustrate this:

template <typename T>
void someFunction(const T& input)
{
	//do sth
}

template <typename T>
class SomeClass
{

};

...

SomeClass<int> myClass;

someFunction(myClass);

 

and I guess it's not possible the same for a function?

template <typename T>
class someContainer
{
public:
	void sort(bool(*inputFunction)(const T&, const T&)) //I know you can't pass a function like this
        //I was just thinking that it would be nice if you could - or would it "break" something?
        //something like a default parameter for the template but in a function parameter
	{
		//do sth
		inputFunction<R>(...);
		//do sth
	}
};

template <typename T>
bool someFunction(const T& input1, const T& input2)
{
	//do sth
}

 

The 2nd code won't work don't even try it - it's there just to illustrate what I had in mind...

Btw would it work with a functor?

 

P.S. And thanks a lot about the info on C++ 11 ParadigmShifter, I just don't have any more rep points to give for today so I can't rep you - sorry.

Edited by lightxbulb

Share this post


Link to post
Share on other sites
Ravyne    14300

Some of this missing functionality has been "emulated" to a reasonable degree in the standard library for some time though (e.g. variadic templates), which at least allowed you to start writing client code in a way that will leverage the proper features when they are added in.

 

This feature gave rise to my favourite quote from the MSDN:

 

"Therefore, we reduced infinity. In Visual C++ 2008 SP1 and Visual C++ 2010, infinity was 10 (that is, "variadic" templates supported 0 to 10 arguments, inclusive). By default, infinity is 5 in Visual C++ in Visual Studio 2012."

 

EDIT: Infinity is 10... no, it's 5... for small values of infinity.

 

Yes, that's a good one. IIRC, in 2012 at least, the value of 'Infinity' can at least be redefined if you need (although it's not 'supported', its supposed to work for reasonably large values of 'Infinity'). It has a default that's fairly small, I think, but its more about compile-time performance than the capabilities of the template magic going on behind the scenes. I'm pretty sure you can go higher than 10 in VS2012, as long as you can live with the compile times.

 

The situation is less than optimal, but for most client code 'Infinity' in a range of 5-10 is alright. In general, the people who really need *real* variadic templates or even 'Infinities' larger than 5-10 are library writers and maintainers, not library users. It could be better, but the work around at least satisfies the 80/20 rule.

Share this post


Link to post
Share on other sites

<offtopic>

The infinity thing is even better than my second favourite quote from the MSDN:

 

"If you are a developer who implements toast-like functionality in one of your products, you are encouraged to use the ToastSemaphore mutex to avoid toast collisions."

</offtopic>

 

EDIT: Is it a semaphore? Is it a mutex? NO! It's the ToastSemaphore mutex ;)

Edited by Paradigm Shifter

Share this post


Link to post
Share on other sites
Brother Bob    10344

Of course I am not passing a template class to the display() function, but the parameter for the display function can accept multiple specializations of a template.

I wanted to know if the same is possible for a function - here's some code to illustrate this:

template <typename T>
void someFunction(const T& input)
{
	//do sth
}

template <typename T>
class SomeClass
{

};

...

SomeClass<int> myClass;

someFunction(myClass);

 

and I guess it's not possible the same for a function?

template <typename T>
class someContainer
{
public:
	void sort(bool(*inputFunction)(T&,T&)) //I know you can't pass a function like this
        //I was just thinking that it would be nice if you could - or would it "break" something?
        //something like a default parameter for the template but in a function parameter
	{
		//do sth
		inputFunction<R>(...);
		//do sth
	}
};

template <typename T>
void someFunction(T& input1, T& input2)
{
	//do sth
}

 

The 2nd code won't work don't even try it - it's there just to illustrate what I had in mind...

Btw would it work with a functor?

 

P.S. And thanks a lot about the info on C++ 11 ParadigmShifter, I just don't have any more rep points to give for today so I can't rep you - sorry.

But that example is about what I'm trying to say; you cannot compare the two because in the first case you fully instantiate the template and pass it, but in the second case you pass a template and expect the receiver to instantiate it for you. It's fine to pass instantiated function templates, just as you showed that you can pass instantiated template classes, but passing function templates and class templates and have the receiver instantiate them is something completely different.

 

In your first example the function adapts itself based on the parameter, but in the second example you expect the function to adapt the parameter.

Edited by Brother Bob

Share this post


Link to post
Share on other sites
lightxbulb    1164

Uh this works fineblink.png :

#include <iostream>
using namespace std;

template <typename T>
class SomeContainer
{
private:
	T val1;
	T val2;
public:
	SomeContainer(const T& in1, const T& in2)
		: val1(in1), val2(in2) {}

	void sort( bool (*func)(const T&, const T&))
	{
		func(val1, val2);
		return;
	}

};

template <typename R>
bool someFunction(const R& input1,const R& input2)
{
	cout <<input1 << ' ' << input2 << endl;
	return 0;
}

int main()
{
	SomeContainer<int> my(5,4);
	my.sort(someFunction);

	cin.ignore();
	return 0;
}
Edited by lightxbulb

Share this post


Link to post
Share on other sites
Brother Bob    10344

That sort function does not take a template type. Once the SomeContainer template is instantiated with the type int (by making an object of type SomeContainer<int>), its sort function is defined to take a function pointer of type bool(int const &, int const &) and nothing else. That is different from std::list::sort which in itself is a template function inside the template class std::list.

Edited by Brother Bob

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this