Sorting an STL of pointers to comparable objects.

[OrangeKyo]

Hi, I have a class called Leaf with a member variable int frequency. I want to load pointers of this class into a priority_queue or a sortable vector so that it sorts based on frequency.

I've tried overloading the < operator and doing this:

vector<Leaf> leaves;
//load the leaves.
leaves.sort();

which works. but what i want is this:

vector<Leaf *> leaves; //Note the pointer type
//load the leaves.
leaves.sort();

I've also tried writing a comparator class and putting that in as an argument to the priority_queue:

class PairComparator {
bool operator()(const Leaf& *p1, const Leaf& *p2) const { //compiler doesn't like this line
return p1->frequency > p2->frequency;
}
}

priority_queue<Leaf*,vector<Leaf*>, PairComparator> leaves;

But that doesn't work. Is there any way to this? Since each Leaf may have pointers to other leaf objects, I MUST use and store the objects as pointers. But as i construct the tree, I must sort them at each iteration. I've searched through the forums quite a bit, and found solutions to sort arrays of pointers, or a priority q of objects with member variables, but not a priority_queue of pointers to objects with member variables.

-OrangeKyo

[monarch_dodra]

Hi, I have a class called Leaf with a member variable int frequency. I want to load pointers of this class into a priority_queue or a sortable vector so that it sorts based on frequency.

I've tried overloading the < operator and doing this:

vector<Leaf> leaves;
//load the leaves.
leaves.sort();

which works. but what i want is this:

vector<Leaf *> leaves; //Note the pointer type
//load the leaves.
leaves.sort();

I've also tried writing a comparator class and putting that in as an argument to the priority_queue:

class PairComparator {
bool operator()(const Leaf& *p1, const Leaf& *p2) const { //compiler doesn't like this line
return p1->frequency > p2->frequency;
}
}

priority_queue<Leaf*,vector<Leaf*>, PairComparator> leaves;

But that doesn't work. Is there any way to this? Since each Leaf may have pointers to other leaf objects, I MUST use and store the objects as pointers. But as i construct the tree, I must sort them at each iteration. I've searched through the forums quite a bit, and found solutions to sort arrays of pointers, or a priority q of objects with member variables, but not a priority_queue of pointers to objects with member variables.

-OrangeKyo

Well you almost had it.

1- Why would you even try to pass a pointer as a const reference? Just pass it by value. That, and passing a pointer by reference is:

   const Leaf*& p1
not
   const Leaf&* p1

2- what the heck are you doing with that priority queue of vectors?
just call sort with the compare operator:

leaves.sort(PairComparator());

3- How can you call sort on leaves? It's a vector! vectors don't have sort. Do it like this:

sort(leaves.begin(), leaves.end(), PairComparator());

4- You might be confused at what a priority queue is. First, you can't sort a priority queue. Second, building a priority Queue only takes two arguments: the objects, and the comparer.

priority_queue<Leaf*,vector<Leaf*>, PairComparator> leaves;

Which is your object? The leaf*, or the vector<Leaf*>? It's one or the other. See http://www.cplusplus.com/reference/stl/priority_queue/

[monarch_dodra]

I've tried overloading the < operator

You can NEVER overload the operator< for basic types, and that includes pointers, which includes pointers to leaf.

Your solution is to create a function/function object that does the same thing, but has a different name, as you did.

[OrangeKyo]

Awesome. I got it with this. Thanks a bunch.

class leafcompare {
public:
bool operator()(const Leaf *p1, const Leaf *p2) const {
return p1->frequency > p2->frequency;
}
};

priority_queue<Leaf* , vector<Leaf*>, leafcompare> leaves;

[OrangeKyo]

To Monarch. I probably should have clarified. My mistake.

The command

priority_queue<Leaf*,vector<Leaf*>, PairComparator> leaves;

does not create a priority queue of vectors. It creates a priority queue with the base container as vectors, and a comparison function of pair comparator.

Read this: http://www.blender.org/documentation...ity_queue.html

But I got it working with your other suggestion. Muchas gracias.

- OrangeKyo

[monarch_dodra]

To Monarch. I probably should have clarified. My mistake.

The command

priority_queue<Leaf*,vector<Leaf*>, PairComparator> leaves;

does not create a priority queue of vectors. It creates a priority queue with the base container as vectors, and a comparison function of pair comparator.

Read this: http://www.blender.org/documentation...ity_queue.html

But I got it working with your other suggestion. Muchas gracias.

- OrangeKyo

Hum, I had forgotten there was a parameter for the container. My apologies.

Still, if all you want to do is sort your vector, I think it is a much better idea to use std::sort than using a helper priority_queue.

But I don't know what you are trying to do, so you may be right.

[Lindley]

A priority queue (aka, heap) is the data structure of choice when you're going to be doing a lot of inserts at various times, and you only care about the smallest (largest) element in the data structure at any given time, not in maintaining a full sort at all times. It's likely to be slightly faster than a std::multiset for this use-case on most compilers, and certainly faster than a std::sort() call after every insertion to a std::vector.