Priority_queue

This is a discussion on Priority_queue within the C++ Programming forums, part of the General Programming Boards category; How do I go about adding a comparator to a priority queue. I have a class which Im using as ...

  1. #1
    HIM
    HIM is offline
    Registered User
    Join Date
    Aug 2006
    Posts
    13

    Priority_queue

    How do I go about adding a comparator to a priority queue. I have a class which Im using as my Type for the queue, and want to order the class elements according to my own comparator. Is there a method I have to add to my class that the priority_queue will automatically use?

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    If you make an operator< for your class that sorts based on priority the priority_queue will use it automatically.
    Code:
    bool operator<(const myclass&, const myclass&);
    If there are multiple correct priority orders you should make structs whose operator() has the same arguments as an operator<. Then you will have to pass the correct struct name to the priority_queue template parameters.

  3. #3
    HIM
    HIM is offline
    Registered User
    Join Date
    Aug 2006
    Posts
    13
    Still having some trouble with the queue. I've implemented operator overloading in the class, and it works fine, so I know thats not the problem. For some reason though, Im getting an error when I try to store an instance of my class in the priority_queue.

    I have the queue declared in my header

    Code:
    #inlclude <queue>
    
    class myClass
    {
          public:
                   ...
    
          private:
                   std::priority_queue<myOtherClass> myQueue;
    };
    Yet when I make the call to push(myOtherClass) onto the queue, I get an obscure error originating in stl_heap. The thing is, I dont get the error if I store pointers in the queue, rather than actual instances of myOtherClass.

    Can anyone explain?

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    How is operator< defined for your myOtherClass?
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    HIM
    HIM is offline
    Registered User
    Join Date
    Aug 2006
    Posts
    13
    Ok. After thinking this through. I assume its working with pointers because the queue is no longer using my operator overloading to compare the values, yes?

    Which still leaves me having no clue as to why it doesn't work with my class instances, since testing the overloading using cout gives the correct answer each time, so Im sure thats working ok.

  6. #6
    HIM
    HIM is offline
    Registered User
    Join Date
    Aug 2006
    Posts
    13
    Code:
    bool AStarNode::operator<(AStarNode &m)
    {
    	if(f != m.getF())
    		return f < m.getF();
    	else
    		return h < m.getH();
    }

  7. #7
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    Hmm... for starters it's probably best to change that parameter to const AStarNode &m. You should always have them const unless you can't. Read my sig and here: http://www.parashift.com/c++-faq-lit...rrectness.html.

    EDITED:
    Changing to a reference to const should be enough
    Last edited by Mario F.; 11-08-2006 at 06:20 AM.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #8
    HIM
    HIM is offline
    Registered User
    Join Date
    Aug 2006
    Posts
    13
    By god it works.. it WORKS....

    I've come to the conclusion that the problem was a mixture of two things. The first being my lack of knowledge of c++, and the way in which operator overriding must be done, and the second is my installation of Dev-C++ seems to have been a little funky.

    I've just installed Borland, and after changing the operator override to an external friend function, and giving it the two parameters, its now working. My queue is storing the instances of my class, and ordering them correctly. I did try doing it in Dev, but it just wasnt having any of it... ah well... Thanks for the help.

  9. #9
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    It's probably not Dev-C++'s fault (actually the gcc compiler), it is probably your code. It would be smart to try to fix the problem that shows up in Dev-C++ rather than ignore it. It might be a problem on Borland as well, but one that shows up somewhere else. It might also cause you problems in the future if you don't learn the right way to do things.

    The const is important. If you make the operator a member function, not only do you have to make the parameter a const reference, you have to make the function const as well. I'd prefer the non-member function I gave an example of earlier, though.

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21