CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Aug 2009
    Posts
    6

    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

  2. #2
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Sorting an STL of pointers to comparable objects.

    Quote Originally Posted by OrangeKyo View Post
    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/

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Sorting an STL of pointers to comparable objects.

    Quote Originally Posted by OrangeKyo View Post
    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.

  4. #4
    Join Date
    Aug 2009
    Posts
    6

    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;

  5. #5
    Join Date
    Aug 2009
    Posts
    6

    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

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Sorting an STL of pointers to comparable objects.

    Quote Originally Posted by OrangeKyo View Post
    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.

  7. #7
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    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
  •  





Click Here to Expand Forum to Full Width

Featured