Thread: Overloading a priority queue

  1. #1
    Registered User
    Join Date
    Jul 2007
    Posts
    186

    Overloading a priority queue

    I'm just learning how to use a priority_queue in C++ and I'm reading some info on how to overload it so you can compare custom objects. Basically so far I've seen this:

    Code:
    bool operator< (const Object& r1, const Object& r2)
    {
    	return r1.something > r2.something
    }
    
    priority_queue<Object> queueName;
    but I was also told that for data structures I should try and use pointers so my queue is:
    Code:
    priority_queue<Object*> queueName;
    but how do I change the overloaded part? I don't really understand what the const Object& r1, const Object& r2 part means.

    Thanks guys

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You can use something like this:
    Code:
    bool operator< (const Object *r1, const Object *r2)
    {
    	return r1->something > r2->something;
    }
    (added semicolon to make it compilable).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jul 2007
    Posts
    186
    Ok, I'll try that. Do you think you could explain what that means? And how it's different?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    The & means that you are passing a reference, which is, in implementation, almost the same as a pointer, but the syntax for accessing the content is different (member access of struct/class is as if it was passed by value, so using x.y, not pointer access of (*x).y or x->y ).

    The const part says "we're not changing the Object passed in" - which is good for the compiler to know, but also very good for the programmer to know, as otherwise you may need to make a copy if you want to retain the original value before calling a function that changes your input parameter.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Jul 2007
    Posts
    186
    That makes sense. Your suggestion didn't compile though
    error: 'bool operator<(const Request*, const Request*)' must have an argument of class or enumerated type

    Code:
    bool operator< (const Request *req1, const Request *req2)
    {
    	return req1->track > req2->track;	
    }
    Last edited by jcafaro10; 01-27-2009 at 02:50 PM.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The cause of the error depends on the rest of the program. Have you included the header that declares the Request class?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Are you allowed to overload operators with just pointers as arguments? I thought you needed real objects to overload.

  8. #8
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It appears to be so.

    You can use pass non-default arguments to priority_queue, e.g like this:

    Code:
    #include <queue>
    #include <deque>
    
    struct Request
    {
        int track;
    };
    
    struct CompareRequestP
    {
        bool operator() (const Request* req1, const Request* req2) const
        {
        	return req1->track > req2->track;
        }
    };
    
    
    int main()
    {
        std::priority_queue<Request*, std::deque<Request*>, CompareRequestP> queue;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  9. #9
    Registered User
    Join Date
    Jul 2007
    Posts
    186
    Here's what this section of my code looks like

    Code:
    struct Request;
    struct Requester
    {
    	bool beingServiced;
    	int id;
    	list<Request*> requests;
    };
    
    struct Request
    {
    	Requester* r;
    	int track;
    };
    
    bool operator< (const Request *req1, const Request *req2)
    {
    	return req1->track > req2->track;	
    }
    
    static priority_queue<Request*> activeRequests;
    I changed it to this and it works but I don't understand the operator thing. I'm not overloading "<" anymore...

    Code:
    struct Request;
    struct Requester
    {
    	bool beingServiced;
    	int id;
    	list<Request*> requests;
    };
    
    struct Request
    {
    	Requester* r;
    	int track;
    };
    
    struct CompareRequest
    {
    	bool operator() (const Request *req1, const Request *req2) const
    	{
    		return req1->track > req2->track;	
    	}
    };
    
    static priority_queue<Request*, deque<Request*>,CompareRequest> activeRequests;

  10. #10
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I changed it to this and it works but I don't understand the operator thing. I'm not overloading "<" anymore...
    Now you are creating a function object (overloads operator()) and telling deque directly to use an instance of this struct to compare the request pointers.

    As to overloading operators for pointers, I guess it would make sense that you can't change how pointers arithmetics works.

    Code:
    int array[3] = {1, 2, 3}
    for (int* i = array; i < array + 3; ++i)...
    
    //vs
    Request array[3] = {...};
    for (Request* r = array; r < array + 3; ++r) ???
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-15-2007, 12:48 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM