I'm trying to work my way around using STL priority_queue. here's my
problem:
I am trying to keep a certain struct in it, and want the queue to sort it by
a specific member of that struct, an int.
how do I do that? from what I saw in the documentation around the web, you
can either use the queue with a primitive type, in which case the queue is
sorted by that primitive type, or you can store a pointer to a primitive
type and add a function for comparing. neither is my case: my struct has
more than one integer. how do I point the sorting functor to the correct
int? how do I write a functor that compares by the specific value?
any help would be appreciated!
Amit.
--
====================================
"We believe that life, creation,
everything is based on mathematics"
- Universal Zulu Nation
====================================
Not sure where you read this. By default sorting is done based on operator<,
which is predefined for basic types. Just define an operator< for your
struct. No need for pointers etc. Here's an example
struct ABC
{
int data1;
int data2;
int sort_on_this;
};
bool operator<(const ABC& lhs, const ABC& rhs)
{
return lhs.sort_on_this < rhs.sort_on_this;
}
This operator< could be useful in all sorts of contexts apart from priority
queues.
john
Isn't it the predicate function less which then calls operator < inside.
The distinction is that the 'STL' way is to define your own predicate
function for sorting pass this into the container's constructor.
That way sorting and operator < are not dependent
e.g. a table of scores with highest percentage first (doubles), you don't
want to redefine the double operator < just top sort highest first.
True enough, but perhaps more detail than the OP needs.
john
since operator>() cannot be overloaded for pointer types, I cannot
accomplish the desired sort. Is there a way around this?
Thanks,
Regards,
S. K. Mody.
You can define you own class which has all the facilities you want from your
pointer but also lets you overload operator< as well. Something like this,
where T is the type you want to point to
class MyPtr
{
MyPtr(T* p) : ptr(p) {}
T& operator*() { return ptr; }
T* operator->() { return ptr; }
private:
T* ptr;
};
bool operator<(const MyPtr& lhs, const MyPtr& rhs)
{
// whatever
}
john
>I would like to add to the question, based on a situation I once
>encountered. Suppose I have a container(eg: list)
>of pointers to objects and I need to sort based on the contents
>of the objects. In the absence of member templates(eg: MSVC5)
>in the list class:-
> template<class Pred> void sort(Pred pr);
>is replaced by:
> void sort(greater<T> pr);
>
>since operator>() cannot be overloaded for pointer types, I cannot
>accomplish the desired sort. Is there a way around this?
Yup, just specialize greater<T> for your type. Something like:
class std::greater<mytype*>
{
public:
bool operator(const mytype* a, const mytype* b)
{return a->sorter < b->sorter;}
};
If you need different sorts, then it's a bit nastier. You can use
runtime constructor stuff, or another template for compile time
function dispatch. For the former, something like:
template <class T>
class std::greater<mytype*>
{
public:
typedef bool (*comparison)(const mytype*, const mytype*);
greater(comparison comp) :c(comp) {}
bool operator (const mytype* a, const mytype* b)
{ return c(a, b);}
private:
comparison c;
};
bool mycompfunc(const mytype* a, const mytype* b)
{
//implemation.
}
.
.
.
mylist.sort(std::greater<mytype*>(&mycompfunc));
Hope that helps,
Tom
Actually, going through the standard library files supplied
with MSVC5, I can't find specialization's of greater<T>
for basic types or pointers to basic types. I assume that
this means you are allowed to write your own specialization's
for basic types.(?)
Regards,
S. K. Mody.
Tom <rhino...@hotmail.com> wrote in message
news:38fb1f3e...@news.demon.co.uk...
> file://implemation.
The only slight problem with this is that the declarations of mytype*
have to be changed to MyPtr. Also you would need a conversion
operator mytype*() const, so it could mesh with existing code. Another
poster suggested a less intrusive approach - specializing greater<T>
for mytype*.
Regards,
S. K. Mody.
Afraid not. I believe specializations of library templates
require the parameter to depend on a user-defined type. The
built-in types rely on the general template, whose operator()
return value uses operator> of the argument type, and can't
legitimately be specialized. (However, I suspect it would
work on most implementations, as long as the specialization
is visible at point of use. Relying on it in a real program
would be foolish, though.)
Slight syntax correction:
template<>
class std::greater<mytype*>
{
/* ... */
};
It also has to be declared in std, I think, but I'd have
to guess at the syntax. Perhaps:
namespace std { template<> class std::greater<mytype*>; }
> If you need different sorts, then it's a bit nastier. You can use
> runtime constructor stuff, or another template for compile time
> function dispatch. For the former, something like:
>
> template <class T>
> class std::greater<mytype*>
> {
> public:
> typedef bool (*comparison)(const mytype*, const mytype*);
> greater(comparison comp) :c(comp) {}
>
> bool operator (const mytype* a, const mytype* b)
> { return c(a, b);}
> private:
> comparison c;
> };
>
For the second method, you probably want an explicit
specialization as well. An oversight, I'm sure, since
you didn't use T anywhere.
>
> Hope that helps,
>
> Tom