STL priority_queue Q for ya...
Amit Bar-nir
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
====================================
John Harrison
Amit Bar-nir <sta...@zahav.net.il> wrote in message
news:8dd508$2a4$1...@news3.inter.net.il...
> Hi all,
>
> 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
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
Paul Baxter
operator<,
> which is predefined for basic types. Just define an operator< for your
> struct. No need for pointers etc. Here's an example
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.
John Harrison
Paul Baxter <paul_...@i.am> wrote in message
news:uNjgPA#p$GA.251@cppssbbsa03...
True enough, but perhaps more detail than the OP needs.
john
S.K.Mody
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?
Thanks,
Regards,
S. K. Mody.
John Harrison
S.K.Mody <Mod...@hotmail.com> wrote in message
news:nJvK4.17161$0o4.1...@iad-read.news.verio.net...
> 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?
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
Tom
wrote:
>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
S.K.Mody
with a pointer type. However since mytype* is a pointer
to a _user_ defined type, I _am_ allowed to specialize
greater<T> with T = mytype*.
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.
S.K.Mody
John Harrison <jah...@dtn.ntl.com> wrote in message
news:QnzK4.3306$LM6.1...@news2-win.server.ntlworld.com...
>
> S.K.Mody <Mod...@hotmail.com> wrote in message
> news:nJvK4.17161$0o4.1...@iad-read.news.verio.net...
> > 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?
>
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
>
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.
Jim Gewin
>
> 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.
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.)
Jim Gewin
> 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;}
> };
>
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