sorting stl list with predicate

[ManicQin]

Hi all.

I need a fast help,
I have a list of COperation* and I add Operations, each Operation has
a scale and before I execute the list i want to sort them

I have the next snip:

class COperation
{
public:

virtual int GetScale() const { return -1; }
};

typedef COperation* PCOperation;
typedef std::list<PCOperation> tOpStack;

struct greaterScale : public std::greater<PCOperation>
{
bool operator()(const PCOperation& x,const PCOperation& y)
{
if (x->GetScale() != -1 && y->GetScale() != -1 && y->GetScale() > x-

GetScale())

{
return true;
}

return false;
}
};

later I try to call:
tOpStack m_OpStack;
m_OpStack.sort(greaterScale());

when I enter the sort I see that instead of using my greaterScale pred
he is using the normal greater pred...
I'm guessing that my greaterScale isn't using the correct signature
and the compiler cant deduce the correct operator()
but why? what am I doing wrong?

thanks....

 

[JenC]

I think instead of:
m_OpStack.sort(greaterScale());
you should have:
m_OpStack.sort(greaterScale); //notice, no '()' after greaterScale

Best,
Jen

 

[ManicQin]

If that were the problem, the compiler would yell at you.  Can you
please post a small, complete program?

If it was a function I should call without the brackets but because
it's a functor
I need to call it with...
I Copy Pasted the next code chopped it for un-relevant things so dont
try to understand
the point behind it.
I tested it with VS6 and it didn't work... (it's compiling ok)
Any thoughts people?

#include <list>
#include <functional>
#include <algorithm>

enum EOperations{eLiftNozzle,eReturnNozzle};
class COperation
{
public:
EOperations GetOpCode()
{
return m_OpCode;
}

virtual int GetScale() const { return -1; }
protected:

COperation(EOperations OpCode):m_OpCode(OpCode) {}


private:
COperation(){};
EOperations m_OpCode;
};

class CLiftNozzle_ : public COperation
{
public:
CLiftNozzle_(char NozzleNumber) :
COperation(eLiftNozzle),sNozzleNumber(NozzleNumber){}
int GetScale() const { return 1; }
private:
CLiftNozzle_();
char sNozzleNumber;
};

class CReturnNozzle_ : public COperation
{
public:
CReturnNozzle_(char NozzleNumber):
COperation(eReturnNozzle),sNozzleNumber(NozzleNumber){}
int GetScale() const { return 5; }
private:
CReturnNozzle_();
char sNozzleNumber;

};



typedef COperation* PCOperation;
typedef std::list<PCOperation> tOpStack;
typedef std::list<PCOperation>::iterator OpIter;

struct greaterScale : public std::greater<PCOperation>
{
bool operator()(PCOperation x,PCOperation y)
{
if (x->GetScale() != -1 && y->GetScale() != -1 && y->GetScale() > x-

GetScale())

{
return true;
}

return false;
}
};

int main()
{
tOpStack blabla;

blabla.push_back(new CLiftNozzle_(1));
blabla.push_back(new CReturnNozzle_(1));

blabla.sort(greaterScale());
return 0;
}

Thanks

 

[Thomas J. Gritzan]

If it was a function I should call without the brackets but because
it's a functor
I need to call it with...
I Copy Pasted the next code chopped it for un-relevant things so dont
try to understand
the point behind it.
I tested it with VS6 and it didn't work... (it's compiling ok)
Any thoughts people?
[...]
struct greaterScale : public std::greater<PCOperation>

struct greaterScale : public std::binary_function<PCOperation,
PCOperation, bool>

{
bool operator()(PCOperation x,PCOperation y)

bool operator()(PCOperation x, PCOperation y) const

 

[Juha Nieminen]

struct greaterScale : public std::greater<PCOperation>

Btw, you don't have to inherit from std::greater (or any comparator in
the STL) in order to write a comparator. This is template
metaprogramming, not object-oriented programming.

 

[James Kanze]

I have a list of COperation* and I add Operations, each
Operation has a scale and before I execute the list i want to
sort them

I have the next snip:

class COperation
{
public:
virtual int GetScale() const { return -1; }
};

typedef COperation* PCOperation;
typedef std::list<PCOperation> tOpStack;

struct greaterScale : public std::greater<PCOperation>
{
bool operator()(const PCOperation& x,const PCOperation& y)
{
if (x->GetScale() != -1 && y->GetScale() != -1 && y->GetScale() > x->GetScale())

{
return true;
}
return false;
}
};

later I try to call:
tOpStack m_OpStack;
m_OpStack.sort(greaterScale());

That's not a legal predicate for sort. Sort (and all other
ordering functions in the standard library) require that the
expression pred(a, b) && pred(b, a) define an equivalence
relationship. Equivalence relationships must be transitive,
i.e. a===b and b===c iff a===c. Your predicate doesn't have
this characteristic---if b.GetScale() returns -1, b will be
equivalent to a and c, even if a and c aren't equivalent.

when I enter the sort I see that instead of using my
greaterScale pred he is using the normal greater pred...

That would surprise me. How do you conclude this?

I'm guessing that my greaterScale isn't using the correct
signature and the compiler cant deduce the correct operator()
but why?

The greaterScale:perator() should be const, so you formally
have undefined behavior. But in practice, if it compiles, it
will work.

what am I doing wrong?

Not fulfilling the requirements on the ordering predicate.
Resulting in undefined behavior.

A few other minor comments (not related to your actual problem,
but important for writing good code):

-- The C prefix for classes is used by MFC. It's best to avoid
it in your own code. (Now that we have namespaces, there's
not really a need of a prefix anyway.)

-- The typedef for the pointer is more obfuscation than
anything else. If you're using pointers, the reader should
be able to easily see this. (The typedef might be justified
in order to easily migrate to boost::shared_ptr, or some
other intelligent pointer. In that case, however, the name
should indicate that it is a pointer, e.g. OperationPointer.
My own convention in such cases is to use a typedef in the
class, e.g. in class Operation, something like:
typedef Operation* Pointer ;
or
typedef boost::shared_ptr< Operation > Pointer ;
This results in Operation:ointer, which seems reasonably
readable.)

-- And using a single if to return true or false is confusing
as well, at least to anyone who knows what a bool is. Just
return the expression.

 

[James Kanze]

Btw, you don't have to inherit from std::greater (or any
comparator in the STL) in order to write a comparator. This is
template metaprogramming, not object-oriented programming.

True, but providing additional information in the form of
typedefs is sometimes useful. I'd generally inherit from
std::binary_operator< Operation*, Operation*, bool > for
example. Since std::greater< Operation* > inherits from this,
he's effectively done so, with less characters to type, but with
the result of misleading the reader (since his object manifestly
has nothing to do with std::greater).

If you're doing much of this sort of thing, it might be worth
defining a ComparisonOperator class template:

template< typename ArgumentType >
struct ComparisonOperator
: std::binary_operator< ArgumentType, ArgumentType, bool >
{
} ;

and inheriting from it.

(I generally define a compare() member function, then derive
from a ComparisonOperators class template which defines all of
the comparison operators in terms of compare(), and provides the
typedefs.)

 

[ManicQin]

If it was a function I should call without the brackets but because
it's a functor
I need to call it with...
I Copy Pasted the next code chopped it for un-relevant things so dont
try to understand
the point behind it.
I tested it with VS6 and it didn't work... (it's compiling ok)
Any thoughts people?
[...]
struct greaterScale : public std::greater<PCOperation>

struct greaterScale : public std::binary_function<PCOperation,
PCOperation, bool>

{
    bool operator()(PCOperation x,PCOperation y)

bool operator()(PCOperation x, PCOperation y) const

    {
   if (x->GetScale() != -1 && y->GetScale() != -1 && y->GetScale() > x-
   {
           return true;
   }

   return false;
   }
};

int main()
{
   tOpStack        blabla;

   blabla.push_back(new CLiftNozzle_(1));
   blabla.push_back(new CReturnNozzle_(1));

   blabla.sort(greaterScale());
   return 0;
}

Ok... Forget about the -1 in the pred.
My question is specifically about the reason why it is not using my
pred and not why the sort is weird...
Thomas I tried it already but I get,
error C2664: 'void __thiscall std::list<class COperation *,class
std::allocator<class COperation *> >::sort(struct std::greater<class
COperation *>)' : cannot convert parameter 1 from 'struct
greaterScale'
to 'struct std::greater<class COperation *>'
If I dont inherit I get the same error BTW

About the -1 in the predicate.
I need to sort only a few items and I have "Anchors" that should not
be moved.
If my list is -1 -1 -1 5 4 3 -1 -1 9 -1
I want it to be -1 -1 -1 3 4 5 -1 -1 9 -1
But again this is not relevant to my question please ignore it.

 

[ManicQin]

True, but providing additional information in the form of
typedefs is sometimes useful.  I'd generally inherit from
std::binary_operator< Operation*, Operation*, bool > for
example.  Since std::greater< Operation* > inherits from this,
he's effectively done so, with less characters to type, but with
the result of misleading the reader (since his object manifestly
has nothing to do with std::greater).

If you're doing much of this sort of thing, it might be worth
defining a ComparisonOperator class template:

    template< typename ArgumentType >
    struct ComparisonOperator
        : std::binary_operator< ArgumentType, ArgumentType, bool >
    {
    } ;

and inheriting from it.

(I generally define a compare() member function, then derive
from a ComparisonOperators class template which defines all of
the comparison operators in terms of compare(), and provides the
typedefs.)

--
James Kanze (GABI Software)             email:[email protected]
Conseils en informatique orientée objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Ok I agree with that point as an advice for good programming I'll
take
it to my consideration.
But I still have the problem i stated above that when I try to inherit
from binary_function I get
error C2664: 'void __thiscall std::list<class COperation *,class
std::allocator<class COperation *> >::sort(struct std::greater<class
COperation *>)' : cannot convert parameter 1 from 'struct
greaterScale'
to 'struct std::greater<class COperation *>

 

[Thomas J. Gritzan]

My question is specifically about the reason why it is not using my
pred and not why the sort is weird...
Thomas I tried it already but I get,
error C2664: 'void __thiscall std::list<class COperation *,class
std::allocator<class COperation *> >::sort(struct std::greater<class
COperation *>)' : cannot convert parameter 1 from 'struct
greaterScale'
to 'struct std::greater<class COperation *>'
If I dont inherit I get the same error BTW

Then you did something wrong. Show the code that exhibits this error.

Also read this:
http://www.parashift.com/c++-faq-lite/how-to-post.html#faq-5.8

 

[James Kanze]

Ok I agree with that point as an advice for good programming
I'll take it to my consideration. But I still have the
problem i stated above that when I try to inherit from
binary_function I get
error C2664: 'void __thiscall std::list<class COperation *,class
std::allocator<class COperation *> >::sort(struct std::greater<class
COperation *>)' : cannot convert parameter 1 from 'struct
greaterScale'
to 'struct std::greater<class COperation *>

It's your typedef's which are causing the confusion, I suspect.
Drop the typedefs, and the problem is obvious. You have a list
of COperation*, and you try to sort it using an operator which
can only be called with COperation const*. Drop the references,
or make them references to COperation*, and everything should be
fine (once you've corrected the predicate so that it is
conform). You could also make the references references to a
const, so that you could initialize them with the results of the
conversion COperation* to COperation const*. But I'd just drop
the reference.

 

[Jorgen Grahn]

....
A few other minor comments (not related to your actual problem,
but important for writing good code): ....
-- The typedef for the pointer is more obfuscation than
anything else. If you're using pointers, the reader should
be able to easily see this.

Yes, that really hurt my eyes when I read it. It made the code
surprisingly hard to read, especially when it went on to pass around
const references to PCOperation.

/Jorgen