comparison class for a priority queue

[bgbnbigben]

Hey all.
Im looking at writing up a comparison class for a PQ of pair<int, int>'s, or whatever is in the pair.
Usually, a PQ will check the first one against the rest of the elements, and then check the second one - the 'highest' (closest towards infinity) will be placed at the .top() of the PQ.
My question is this: i know that i can specify to use greater<int/some_type> and less<some_type> in the declaration.
Is there a way i could use both? - im fairly sure the standard declaration for a PQ wont let me, but this is more for confirmation purposes.

Ok, given that, i know you can also write up your own comparison class.
but thats all i know.
can anyone give me some tips on how to use your own comparison class/struct?
Is there some way i could write this class to compare with a greater than for the some_pair.first and with a less than for the some_pair.second - to do 2 different operations in the case that the firsts' match up?

If thats confusing, my apologies. Its quite late at night and im doing my head in here.
But thanks for any help.

[jsmith]

What is the declaration of the PQ class? I assume it is a templated class with a comparator as one of the template parameters? I don't have a compiler handy right now, so this is off the cuff, but I think what you want is a functor:

template< typename FirstType, typename SecondType >
struct PairComparator {
  bool operator()( const std::pair<FirstType, SecondType>& p1,
    const std::pair<FirstType, SecondType>& p2 ) const 
    {  if( p1.first < p2.first ) return true;
        if( p2.first < p1.first ) return false;
        return p1.second < p2.second;
    }
 

And then just pass PairComparator as the comparator template parameter:
For example (again, no compiler so guessing at declaration of PQ):

typedef PQ< std::pair<int,int>, PairComparator<int,int> > IntPQ;

IntPQ pq;
// ... 

[bgbnbigben]

Thanks a heap for that jsmith.
I didnt realise that PQ's check with boolean values.
although its quite obvious now.
your pass was correct - well almost :)
it needed to be

 typedef PQ< std::pair<int, int>, std::vector<pair<int, int> >, PairComparator<int, int> > IntPQ;
//..... 

or something like that, anyway :)
Anyway, my only question is with bool operator's line. why the () operator?
is that part of PQ's standard declaration?
and why is p1 and p2 declared as a constant, then a constant?
Sorry if its too much to ask....

[jsmith]

1. Because the container is going to want to invoke the comparator like this:
if( compare_( value1, value2 ) ) ie, as if the comparator were
a binary function (function taking two arguments). To make a class/struct
callable as if it were a function, you have to overload the function call
operator, which is operator().

2. It's not strictly part of the declaration, but rather it is the "standard"
implementation.

3. Passing the parameters by const reference does two things: number 1,
it only pushes a pointer onto the stack versus a complete copy of the
object, and number 2, it indicates to the caller of the function that the
function will not modify either of its parameters. Const correctness is
very important.

The last const in the declaration of operator() says that the function,
although being a member function of PairComparator, will not modify
any of its data members. This is trivially the case since PairComparator
has no data members, but again const correctness is important.

[bgbnbigben]

so if you were to declare it as:

bool operator()( std::pair<FirstType, SecondType> p1,
    std::pair<FirstType, SecondType> p2 ) const 

could you forgoe the consts if you didnt pass by reference?
or am i missing the point?

[jsmith]

You could, although in your example, any time the function is called, the arguments will be copied onto the stack. With pair<int,int> it isn't a huge deal; this amounts to pushing two ints onto the stack for each parameter. But for more complicated types that have more data members, it can be expensive. Consider pair< string, vector<string> >. In your code, you would copy the string and the entire vector<string> onto the stack because you pass by value. In my code, only a pointer to the pair<...> would be pushed onto the stack -- my code would be much, much faster.

But as soon as you pass by reference rather than by value, you'll need to pass by const reference. Do you understand the overall use of const or should I explain that?

[bgbnbigben]

yeah, i get const - its just a constant variable.
hmm, oxymoron.
either thats what you meant, or i just made myself look like a total tool....

If that's what you meant, then thanks a bunch for your help.
If not, then you may need to explain const ;)

[jsmith]

There's a couple of ways const is used. One is, as you mentioned, to make a variable "constant", ie guarantee to the caller of the function that the function will not modify the caller's copy of the parameter. The other is to declare a member function of a class const, which is used to indicate that the member function will not modify any of its (immutable) objects' data members.

But there is also a subtlety in the use of const references vs. non-const references, because of the rule that the compiler will not allow you to bind temporaries to non-const references. Consider the following code:

string s1 = "Hello World!";
foo( s1 );
foo( string( "Hello World!" ) );

I've deliberately avoided giving a prototype for foo(). If foo were prototyped in any of the following ways, everything is fine:

void foo( string s );
void foo( const string& s );

But if foo has this prototype:

void foo( string& s ); // non-const reference! 

Then suddenly you'll find that the first call to foo() above compiles and the second one doesn't! This is because in the second call, the compiler is generating a temporary for string( "Hello World" ). You are then asking the compiler to bind that temporary to the non-const reference parameter, and the compiler says that is a violation of the above rule I stated. [Note this is part of the reason why I said const-correctness is important.]

[bgbnbigben]

ok, now i will sound like an idiot:
what's a temporary?

Hmm, i think im almost a *little* out of my depth here.

[jsmith]

A temporary is an unnamed variable that the compiler creates beneath the scenes.

Consider the code

#include <iostream>
#include <string>

using namespace std;

void foo( string s ) {
  cout << s;
}

int main() {
    foo( "hello world" );
}

foo takes a string as a parameter, but it is being called with a const char*.
How does this work?

Well, string has the following constructor:

   string( const char* pStr );

which allows you to construct a string object from a const char*. So in order for the compiler to call foo() in the above code, it first creates a temporary string object by calling the above constructor with the const char*. This temporary is destroyed as soon as the function returns.

[bgbnbigben]

ahh.
so thats why you can bind, say
void foo(int& a)
but not
void foo(string& s)

If so, then thanks a heap for the help.