Custom function together with std::sort?

Original Post

Mar 12, 2009 at 5:27 PM

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?

spookycat

Mar 12, 2009 at 5:31 PM

The return should be an int and not a bool I believe.

Evil Steve

Mar 12, 2009 at 5:42 PM

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?

51mon

Mar 12, 2009 at 5:53 PM

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,std::allocator,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::iterator,bool(__cdecl *)(const wordElement &,const wordElement &)>(_RanIt,_RanIt,_Pr)' being compiled
1> with
1> [
1> _Traits=std::_Tset_traits,std::allocator,false>,
1> _RanIt=std::_Tree,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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,std::allocator,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'

Bonedry

Mar 12, 2009 at 6:48 PM

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.

chairthrower

Mar 12, 2009 at 8:46 PM

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]

iMalc

Mar 13, 2009 at 1:59 AM

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.

_moagstar_

Mar 13, 2009 at 4:16 AM

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.

51mon

Mar 15, 2009 at 5:17 AM

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

loufoque

Mar 15, 2009 at 9:15 AM

Read the fucking reference. std::sort requires RandomAccessIterators. std::set iterators do not fulfill that concept. The end.

Topic Locked