sorting stl list with predicate
ManicQin
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
m_OpStack.sort(greaterScale());
you should have:
m_OpStack.sort(greaterScale); //notice, no '()' after greaterScale
Best,
Jen
Jeff Schwab
> 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
> 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?
If that were the problem, the compiler would yell at you. Can you
please post a small, complete program?
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?
#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
> {
> 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;
> }
--
Thomas
Jeff Schwab
> 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;
That's going to return true if the right-hand-side is greater than the
left-hand-side. In other words, it's going to sort the PCOperations in
order of increasing scale. In your sample code, the order of the
PCOperations will be LiftNozzle (scale 1), then ReturnNozzle (scale 5),
both before and after the sort. Is that what you want?
By the way, you don't need to derive from std::greater.
Thomas J. Gritzan
And it returns false if one of the operands' scale is -1, which means
that any PCOperations with a scale of -1 compares equal to any other.
That's not a strict ordering.
--
Thomas
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::operator() 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::Pointer, 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 (GABI Software) email:james...@gmail.com
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
James Kanze
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
wrote:
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
> 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
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
--
Thomas
James Kanze
> > and inheriting from it.
> 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.
--
James Kanze (GABI Software) email:james...@gmail.com
Jorgen Grahn
> On Jan 28, 3:38 pm, ManicQin <Manic...@gmail.com> wrote:
>> class COperation
>> {
>> public:
>> virtual int GetScale() const { return -1; }
>> };
>
>> typedef COperation* PCOperation;
>> typedef std::list<PCOperation> tOpStack;
...
> 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
--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!