-
August 11th, 2009, 12:37 AM
#1
Sorting an STL of pointers to comparable objects.
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
-
August 11th, 2009, 02:52 AM
#2
Re: Sorting an STL of pointers to comparable objects.
Originally Posted by 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
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:
Code:
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:
Code:
leaves.sort(PairComparator());
3- How can you call sort on leaves? It's a vector! vectors don't have sort. Do it like this:
Code:
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/
-
August 11th, 2009, 02:55 AM
#3
Re: Sorting an STL of pointers to comparable objects.
Originally Posted by OrangeKyo
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.
-
August 11th, 2009, 01:05 PM
#4
Re: Sorting an STL of pointers to comparable objects.
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;
-
August 11th, 2009, 01:10 PM
#5
Re: Sorting an STL of pointers to comparable objects.
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
-
August 11th, 2009, 02:14 PM
#6
Re: Sorting an STL of pointers to comparable objects.
Originally Posted by 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
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.
-
August 11th, 2009, 02:19 PM
#7
Re: Sorting an STL of pointers to comparable objects.
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.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|