Jump to content

  • Log In with Google      Sign In   
  • Create Account

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

#21 Ravyne   GDNet+   -  Reputation: 7369

Like
0Likes
Like

Posted 31 May 2013 - 02:36 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.

 

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.



Sponsor:

#22 Paradigm Shifter   Crossbones+   -  Reputation: 5371

Like
0Likes
Like

Posted 31 May 2013 - 02:41 PM

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

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

#23 Brother Bob   Moderators   -  Reputation: 8194

Like
0Likes
Like

Posted 31 May 2013 - 02:52 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)(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, 31 May 2013 - 02:53 PM.


#24 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 31 May 2013 - 03:25 PM

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, 31 May 2013 - 03:28 PM.


#25 Brother Bob   Moderators   -  Reputation: 8194

Like
1Likes
Like

Posted 31 May 2013 - 03:38 PM

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, 31 May 2013 - 03:40 PM.


#26 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 31 May 2013 - 03:46 PM

Yeah my idea is what is exactly so different - I want to understand the whole thing in depth. Do you know where I can find the corresponding source code file to the <list> header so I can check its internal mechanics? 



#27 Paradigm Shifter   Crossbones+   -  Reputation: 5371

Like
0Likes
Like

Posted 31 May 2013 - 03:47 PM

In Visual studio, right click on list and go to definition, works for me.

 

EDIT: list variable definition that is. You can probably open the header by right clicking on the #include <list> though too.


Edited by Paradigm Shifter, 31 May 2013 - 03:49 PM.

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

#28 Brother Bob   Moderators   -  Reputation: 8194

Like
0Likes
Like

Posted 31 May 2013 - 03:51 PM

Likely where you have installed your compiler. If you have a decent IDE, you may even be able to open it by just right-clicking the file name in an #include statement or something.

 

edit: beaten, that's what happens when you wait with submitting the post for no good reason...


Edited by Brother Bob, 31 May 2013 - 03:53 PM.


#29 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 31 May 2013 - 03:52 PM

Thanks - though it sends me at the header, but I think I'll find what I'm looking for there(I think the cpp is compiled already).

I suppose I should be looking at this blink.pngunsure.png  : 

	template<class _Pr2>
		void sort(_Pr2 _Pred)
		{	// order sequence, using _Pred
		if (2 <= this->_Mysize)
			{	// worth sorting, do it
			const size_t _MAXBINS = 25;
			_Myt _Templist(this->_Getal()), _Binlist[_MAXBINS + 1];
			size_t _Maxbin = 0;

			while (!empty())
				{	// sort another element, using bins
				_Templist._Splice_same(_Templist.begin(), *this, begin(),
					++begin(), 1);

				size_t _Bin;
				for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty();
					++_Bin)
					{	// merge into ever larger bins
					_Binlist[_Bin].merge(_Templist, _Pred);
					_Binlist[_Bin].swap(_Templist);
					}

				if (_Bin == _MAXBINS)
					_Binlist[_Bin - 1].merge(_Templist, _Pred);
				else
					{	// spill to new bin, while they last
					_Binlist[_Bin].swap(_Templist);
					if (_Bin == _Maxbin)
						++_Maxbin;
					}
				}

			for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
				_Binlist[_Bin].merge(_Binlist[_Bin - 1],
					_Pred);	// merge up

			_Analysis_assume_(0 < _Maxbin);

			splice(begin(), _Binlist[_Maxbin - 1]);	// result in last bin
			}
		}

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

 

And the function pointer or functor is actually _Pr2 Pred?


Edited by lightxbulb, 31 May 2013 - 03:59 PM.


#30 Brother Bob   Moderators   -  Reputation: 8194

Like
0Likes
Like

Posted 31 May 2013 - 03:54 PM

The code is likely there; it's a template and templates cannot generally be pre-compiled. Generally I say, because you can instantiate templates and pre-compile them but I find it unlikely in this case. The code you're looking for is probably there, or in some other file included by that header.



#31 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 01 June 2013 - 03:33 AM

I think I finally found where the predicate function is called:

02076   /// This is a helper function for the sort routine.
02077   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
02078     void
02079     __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
02080                   _Compare __comp)
02081     {
02082       _RandomAccessIterator __next = __last;
02083       --__next;
02084       while (__comp(__val, *__next))
02085     {
02086       *__last = *__next;
02087       __last = __next;
02088       --__next;
02089     }
02090       *__last = __val;
02091     }

 

 

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.

Btw you mean that std::list::sort cannot exhibit the same behaviour as my sort function from the example because std::list::sort is a template function - did I get it right? Is it just because std::list::sort is a template function, or is there something more to it?

Thanks a lot for all the advice!smile.png

 

/Edit:

If default template arguments for function templates were actually available(http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#226), I could do this:

#include <iostream>
#include <typeinfo>
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) {}

	template <typename R = T>
	void sort(bool (*_comp)(const R&, const R&))
	{
		cout << "Comp is of type: " << typeid(_comp).name() << endl;
		cout << _comp(val1, val2) << endl;
		return;
	}
};

template <typename T>
bool compare(const T& a, const T& b)
{
	return a>b;
}

int main()
{
	someContainer<int> myCont(5,6);
	myCont.sort(compare);

	cin.ignore();
	return 0;
}

 

However for now, only this variant works:

#include <iostream>
#include <typeinfo>
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) {}

	template <typename R>
	void sort(bool (*_comp)(const R&, const R&))
	{
		cout << "Comp is of type: " << typeid(_comp).name() << endl;
		cout << _comp(val1, val2) << endl;
		return;
	}
};

template <typename T>
bool compare(const T& a, const T& b)
{
	return a>b;
}

int main()
{
	someContainer<int> myCont(5,6);
	myCont.sort(compare<int>);

	cin.ignore();
	return 0;
}

Edited by lightxbulb, 01 June 2013 - 04:32 AM.


#32 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 01 June 2013 - 05:18 AM

Sorry for making a 2nd post after the prev was mine too, but it got too big to be comfortable to work with.

Here's what I was thinking over - any idea why it doesn't work(or where's the flaw in my logic)?

#include <iostream>
#include <typeinfo>
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) {}

	template <typename Ret>
	void sort(Ret (*_comp)(const T&, const T&))
	{
		cout << "Comp is of type: " << typeid(_comp).name() << endl;
		cout << _comp(val1, val2) << endl;
		return;
	}
};

template <typename R>
bool compare(const R& a, const R& b)
{
	return a>b;
}

int main()
{
	someContainer<int> myCont(7,6);
	myCont.sort<bool>(compare<int>);

	/*
	I. myCont.sort<bool>(compare<int>);
	Both specilaizations(for sort and for compare) are explicitly stated
	*/

	myCont.sort(compare<int>); 
	/*II. myCont.sort(compare<int>); 
	passes <int> as an argument to the template of compare(), so we get a int specialization for function compare(),
	from there the compiler gets("infers" - doesn't need to have sort<bool> explicitly stated)
	the return type of compare<int>, which is bool, and passes it as an argument for sort(so we get a sort<bool> specialization for sort)
	*/
	myCont.sort<bool>(compare); 
	/*
	III. myCont.sort<bool>(compare); 
	passes <bool> as an argument to the template of sort(), so we get a bool specialization for function compare(),
	the compiler cannot infer what specialization to use for compare just from the fact that compare returns bool(sort<bool>).
	The compiler actually "infers" the specialization of compare() from the type for which myCont is an object
	(someContainer<int> myCont - basically int). From this we see that compare<int>() doesn't need to be explicitly stated
	as it can be inferred from the specialization of the template for someContainer. However from the previous example we know
	that sort<bool> doesn't need to be explicitly stated too, as it can be inferred from compare<int>.

	Basically if we take into account the previous two examples and try to use:
	myCont.sort(compare);
	the compiler "should" be able to infer the specialization for compare() from "the specialization of the template for someContainer." 
	And bool can be inferred from the specialization we get for compare().
	Here's what "should" happen:
	1)myConst.sort(compare)
	2)use the type(<int>) for which the class of myConst (someContainer<int>) is a specialization of someContainer as an argument for the specialization of compare()
	3)we get compare<int>()
	4)from this get the return type of compare() for a specialization of type <int> - basically get the return type of compare<int>()
	5)pass this type as an argument for a specilaization of sort()
	6) you get sort<bool>(compare<int>)
	*/

	//Well, seems it doesn't work tht way - as this doesn't work:
	//myCont.sort(compare);

	cin.ignore();
	return 0;
}
/*
Here's a code-like expression of the various points from 1-5:
1)
myConst.sort(compare)
2)
From: someContainer<int> myCont(7,6) -> T = int

From: 
T = int 
AND
void sort(Ret (*_comp)(const T&, const T&))
-> 
void sort(Ret (*_comp)(const int&, const int&))

From: 
void sort(Ret (*_comp)(const int&, const int&))
AND
template <typename R>
bool compare(const R& a, const R& b)
{
	return a>b;
}
->
R=int

From: 
R=int 
->
bool compare(const int& a, const int& b)
{
	return a>b;
}

From:
bool compare(const int& a, const int& b)
{
	return a>b;
}
->
myCont.sort(compare) == myCont.sort(compare<int>)

From: 
myCont.sort(compare) == myCont.sort(compare<int>)
AND
myCont.sort<bool>(compare) == myCont.sort<bool>(compare<int>) (III.)
->
myCont.sort(compare) == myCont.sort<bool>(compare<int>)

*/

 

 


Edited by lightxbulb, 01 June 2013 - 05:46 AM.


#33 lightxbulb   Members   -  Reputation: 704

Like
0Likes
Like

Posted 03 June 2013 - 02:50 AM

Workaround for functors:

#include <iostream>
#include <typeinfo>
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) {}

	template <template <typename Ty> class Comp>
	void sort()
	{
		cout << "Before compare ctor" << endl;
		bool result = Comp<T>()(val1, val2);
		cout <<"After compare ctor" << endl;
		cout << result << endl;
		
		return;
	}
};

template <typename R>
class Compare
{
public:
	Compare()
	{
		cout <<"Compare ctor for " << typeid(R).name() << endl;
	}

	Compare(const Compare& another)
	{
		cout <<"Compare cctor for " << typeid(R).name() << endl;
	}

	Compare(const Compare&& another)
	{
		cout <<"Compare mctor for " << typeid(R).name() << endl;
	}


	bool operator () (const R& a, const R& b)
	{
		cout << a << ' '<< b << endl;
		return a>b;
	}

};


int main()
{
	someContainer<int> myCont(7,6);
	myCont.sort<Compare>();


	cin.ignore();
	return 0;
}






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