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

    [RESOLVED] How to use a derived function for std::priority_queue Compare

    I have a template class that contains a std:riority_queue and would like for the user of this class to be able to pass in the functor object that is used for comparison. Here is the code I have but it is not working. I kind of didn't think it would be thought I would give it a try. Maybe I am going about this the wrong way.

    Code:
        template <typename T>
        class ProcessingQueue {
        public:
            class Comparer
            {
            public:
                virtual bool operator()(T* obj1, T* obj2) {
                    return true;
                }
            };
    .
    .
    .
            void push(T* element);
            virtual void processElement(T* element) = 0;
    .
    .
    .
        private:
            std::priority_queue<T*, std::vector<T*>, Comparer> m_vector;
    .
    .
    .
        }
    This class creates and manages a thread that takes elements that are put on the queue and processes them. I had this working fine using a vector but want to convert it to a priority_queue to allow elements to be processed based on a user defined priority.
    My initial thought was to create the Comparer class to provide as the thrid template parameter to priority_queue and let users derive a specific Comparer for there type implementing an appropriate operator() overload. This did not work and after digging into it a little more I understand why.

    Am I going about this the wrong way?

    Can someone help with how to go about this?

    Please let me know if more information is needed. I tried to only post relevant code.

    Thanks.
    Last edited by Yadrif; September 15th, 2009 at 10:42 AM.

  2. #2
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    Re: How to use a derived function for std::priority_queue Compare

    There could well be a problem in that your Compare class's operator () always returns true.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

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

    Re: How to use a derived function for std::priority_queue Compare

    Are you expecting the user to be specifying the comparison method at compile time, or run time?

  4. #4
    Join Date
    Oct 2007
    Posts
    34

    Re: How to use a derived function for std::priority_queue Compare

    I was expecting the user to supply the comparison function at compile time. My theory was that they would derive a class from Comparer and override operator().

    Either was is probably okay as the requirements for usage of this class are not well defined so actually which ever would be the best approach (if one is better than the other).

    Thanks.

  5. #5
    Join Date
    Oct 2007
    Posts
    34

    Re: [RESOLVED] How to use a derived function for std::priority_queue Compare

    I figured it out.

    I ended up adding a template parameter to ProcessingQueue and using that as the thrid template parameter to std:riority_queue.
    I created a default Comparer with the signature bool Comparer(void*, void*) that always returns false and used it as a default for ProcessingQueue's additional template parameter so users do no need to provide a comparer function but they can and if they do it is passed on to priority_queue.

    Lindley,
    I'd interested in knowing what you had in mind about supplying the compare at runtime. If you see this message.

    Thanks.
    Last edited by Yadrif; September 15th, 2009 at 12:52 PM.

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

    Re: [RESOLVED] How to use a derived function for std::priority_queue Compare

    Quote Originally Posted by Yadrif View Post
    Lindley,
    I'd interested in knowing what you had in mind about supplying the compare at runtime. If you see this message.
    Well, the priority_queue constructor optionally takes a functor to be used for comparison. You could simply require such a thing to be passed into the constructor of ProcessingQueue, and then hand it off to the STL queue in the initializer list.

    Granted, I'm not entirely positive that handing it an object derived from the templated type will work properly. There may be slicing if the STL implementation doesn't anticipate that possibility. You could test this by making the base class's function operator be pure virtual, and see if the thing still compiles.

    Even if that doesn't work, making the comparison type be a boost::function<bool (T, T)> will certainly work.
    Last edited by Lindley; September 16th, 2009 at 08:00 AM.

  7. #7
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,727

    Re: [RESOLVED] How to use a derived function for std::priority_queue Compare

    Instead of using void * (very C like solution), you could ty something like this.

    Code:
    #include <queue>
    #include <functional>
    
    // Comparer base class.
    template <typename T>
    class Comparer_Base
    {
    public:
        virtual bool operator()(T* obj1, T* obj2)
        {
            return std::less<T>()(*obj1, *obj2); // Call the standard function.
        }
    };
    
    // Processing queue class.
    template <typename T, typename Comparer = Comparer_Base<T>>
    class ProcessingQueue {
    public:
    
        void push(T* element)
        {
            m_vector.push(element);
        }
        virtual void processElement(T* element) = 0;
    
    private:
        std::priority_queue<T*, std::vector<T*>, Comparer> m_vector;
    };
    
    // Derived comparer class.
    template <typename T>
    class Greater : Comparer_Base<T>
    {
    public:
        bool operator()(T *obj1, T* obj2) {
            return (*obj1 > *obj2);
        }
    };
    
    // Derived ProcessingQueue
    class NormalQueue : public ProcessingQueue<int>
    {
    public:
        void processElement(int* element) {
        }
    };
    
    // Derived ProcessingQueue
    class GreaterQueue : public ProcessingQueue<int, Greater<int> >
    {
    public:
        void processElement(int* element) {
        }
    };
    
    int main()
    {
        NormalQueue nq;
        GreaterQueue gq;
    
        int i, j;
    
        nq.push(&i);
        nq.push(&j);
    
        gq.push(&i);
        gq.push(&j);
    }
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

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