Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


template functions and STL list.sort


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
32 replies to this topic

#1 lightxbulb   Members   -  Reputation: 851

Like
1Likes
Like

Posted 31 May 2013 - 12:12 PM

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?



Sponsor:

#2 Brother Bob   Moderators   -  Reputation: 8424

Like
3Likes
Like

Posted 31 May 2013 - 12:17 PM

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>);


#3 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
1Likes
Like

Posted 31 May 2013 - 12:17 PM

Have you defined operator> for T? It's already defined for ints ;)

 

EDIT: What Brother Bob said as well ;)


Edited by Paradigm Shifter, 31 May 2013 - 12:18 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#4 Álvaro   Crossbones+   -  Reputation: 13629

Like
3Likes
Like

Posted 31 May 2013 - 12:18 PM

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, 31 May 2013 - 12:19 PM.


#5 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
3Likes
Like

Posted 31 May 2013 - 12:31 PM

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, 31 May 2013 - 12:35 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#6 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 12:33 PM

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, 31 May 2013 - 12:39 PM.


#7 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
1Likes
Like

Posted 31 May 2013 - 12:38 PM

Not according to this (confusing, VS2010 is called VC10 and VS2012 is called VC11) page: http://msdn.microsoft.com/en-us/library/vstudio/hh567368.aspx

 

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


Edited by Paradigm Shifter, 31 May 2013 - 12:39 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#8 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 12:42 PM

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, 31 May 2013 - 12:43 PM.


#9 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
1Likes
Like

Posted 31 May 2013 - 12:51 PM

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).


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#10 Brother Bob   Moderators   -  Reputation: 8424

Like
2Likes
Like

Posted 31 May 2013 - 12:53 PM

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, 31 May 2013 - 12:56 PM.


#11 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 01:04 PM

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, 31 May 2013 - 01:18 PM.


#12 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
1Likes
Like

Posted 31 May 2013 - 01:14 PM

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, 31 May 2013 - 01:15 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#13 Brother Bob   Moderators   -  Reputation: 8424

Like
3Likes
Like

Posted 31 May 2013 - 01:16 PM

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, 31 May 2013 - 01:17 PM.


#14 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 01:29 PM

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, 31 May 2013 - 01:30 PM.


#15 Brother Bob   Moderators   -  Reputation: 8424

Like
0Likes
Like

Posted 31 May 2013 - 01:43 PM

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.



#16 Ravyne   GDNet+   -  Reputation: 7738

Like
0Likes
Like

Posted 31 May 2013 - 02:00 PM

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.



#17 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 02:04 PM

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.



#18 Paradigm Shifter   Crossbones+   -  Reputation: 5405

Like
0Likes
Like

Posted 31 May 2013 - 02:07 PM

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, 31 May 2013 - 02:09 PM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#19 Brother Bob   Moderators   -  Reputation: 8424

Like
0Likes
Like

Posted 31 May 2013 - 02:13 PM

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.



#20 lightxbulb   Members   -  Reputation: 851

Like
0Likes
Like

Posted 31 May 2013 - 02:31 PM

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, 31 May 2013 - 02:54 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS