Sign in to follow this  
lightxbulb

template functions and STL list.sort

Recommended Posts

lightxbulb    1164

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? 

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Brother Bob    10344

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

Share this post


Link to post
Share on other sites
lightxbulb    1164

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

Share this post


Link to post
Share on other sites
Brother Bob    10344

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.

Share this post


Link to post
Share on other sites
lightxbulb    1164

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

Share this post


Link to post
Share on other sites
lightxbulb    1164

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

Share this post


Link to post
Share on other sites
lightxbulb    1164

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

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