Sign in to follow this  
51mon

Custom function together with std::sort?

Recommended Posts

Hi I got a problem to use a custom function together with std::sort. I tried this:
        struct wordElement
	{
		int fileIndex;
		string word;
		bool unique;

		bool operator < (const wordElement& comp) const
		{
			return word < comp.word;
		};
	};

	bool AlternativeComp( wordElement comp0, wordElement comp1)
	{
		return comp0.fileIndex < comp1.fileIndex;
	}

	sort( allWordsSet.begin(), allWordsSet.end(), AlternativeComp);
But the AlternativeComp seams to have the wrong format. What is the correct one?

Share this post


Link to post
Share on other sites
Quote:
Original post by spookycat
The return should be an int and not a bool I believe.
Not for std::sort. Although it should probably take two const references to avoid copying the object.

What makes you think it's the wrong format? Do you get any compile errors? If so, what are they?

Share this post


Link to post
Share on other sites
Quote:
Original post by Evil Steve
Quote:
Original post by spookycat
The return should be an int and not a bool I believe.
Not for std::sort. Although it should probably take two const references to avoid copying the object.

What makes you think it's the wrong format? Do you get any compile errors? If so, what are they?


I tried with const references and a couple of other alternatives. Couldn't solve it. I was just guessing it was the wrong format, it might have been a bad guess. The message:


1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1> d:\programming\my_sun_flare\my_sun_flare.cpp(1716) : see reference to function template instantiation 'void std::sort<std::_Tree<_Traits>::iterator,bool(__cdecl *)(const wordElement &,const wordElement &)>(_RanIt,_RanIt,_Pr)' being compiled
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>,
1> _RanIt=std::_Tree<std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>>::iterator,
1> _Pr=bool (__cdecl *)(const wordElement &,const wordElement &)
1> ]
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: 'reverse_iterator<_RanIt>::difference_type std::operator -(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2212) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2784: '_Base1::difference_type std::operator -(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'std::_Tree<_Traits>::iterator'
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1> c:\program files\microsoft visual studio 9.0\vc\include\xutility(2013) : see declaration of 'std::operator -'
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2676: binary '-' : 'std::_Tree<_Traits>::iterator' does not define this operator or a conversion to a type acceptable to the predefined operator
1> with
1> [
1> _Traits=std::_Tset_traits<wordElement,std::less<wordElement>,std::allocator<wordElement>,false>
1> ]
1>c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3277) : error C2780: 'void std::_Sort(_RanIt,_RanIt,_Diff)' : expects 3 arguments - 4 provided
1> c:\program files\microsoft visual studio 9.0\vc\include\algorithm(3079) : see declaration of 'std::_Sort'

Share this post


Link to post
Share on other sites
Are you trying to sort an std::set? Then that's the problem. A set is not meant to be sorted/ordered (to the user at least; internally, it's often a sorted tree), and hence should not be sorted. Sorting it would likely screw up its internal organisation.

Now that (that it shouldn't be sorted by the user) is probably not the direct reason for why it doesn't compile, but still, it shouldn't be manipulated that way even if possible.

Share this post


Link to post
Share on other sites
By the look of your indentation it suggests that bool AlternativeComp is a method. If this is the case then make it a free function or else a static method. If its a method then its not acceptable as the comparator argument for sort at least in its current form (you'd have to bind the implicit 'this' pointer with boost::bind for instance). But make it a free function if its not and keep the const reference for the two args.

Edit: eg
#include <vector>
#include <algorithm>
#include <boost/bind.hpp>

struct A
{
int i;

bool operator < ( const A &a) const
{
return i < a.i;
}

static bool compare( const A &a, const A &b)
{
return a.i < b.i;
}

bool compare3( const A &a, const A &b) const
{
return a.i < b.i;
}
};

bool compare2( const A &a, const A &b)
{
return a.i < b.i;
}

int main()
{
std::vector< A> v;

std::sort( v.begin(), v.end()); // ok - default
std::sort( v.begin(), v.end(), A::compare); // ok
std::sort( v.begin(), v.end(), compare2); // ok
std::sort( v.begin(), v.end(), boost::bind( &A::compare3, A(), _1, _2)); // ok but stupid ...
}



[Edited by - chairthrower on March 12, 2009 9:46:25 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Lajnold
Are you trying to sort an std::set?
Yes that would be the case, as indicated by this clue in the error message: std::_Tree
You can't sort a set. A set has an ordering, defined by that objects less-than operator, and that's it. The items are always ordered acording to that, end of story.
You would have to copy the items into another container such as a vector, to order them differently.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Yes that would be the case, as indicated by this clue in the error message: std::_Tree
You can't sort a set. A set has an ordering, defined by that objects less-than operator, and that's it. The items are always ordered acording to that, end of story.
You would have to copy the items into another container such as a vector, to order them differently.


You can also try boost.multi_index if you require both an ordered and associative container.

Share this post


Link to post
Share on other sites
Thanks for the answers. The reason I asked the question is that I was preparing for an interview. One week before the interview assignments were sent to me. Unfortunately they never reach me until hours before the interview. So I was a bit desperate for quick solutions. I guess I could solve the task with a second container or even better with a custom implementation. But it doesn't matter now since the assignment is handed in, thanks for the good answers though :)

Share this post


Link to post
Share on other sites
Read the fucking reference. std::sort requires RandomAccessIterators. std::set iterators do not fulfill that concept. The end.

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