Re: [Boost-users] Tips on implementing a function queue with unique queue items (compare function problem)

Subject: Re: [Boost-users] Tips on implementing a function queue with unique queue items (compare function problem)
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-05-12 19:34:24

AMDG

Peter Åberg wrote:
> Anyone have a tip or pointer regarding how to implement a function 
> queue with unique items?
>
> Comparing C++ delegates seems to be hard in general 
> (http://www.boost.org/doc/libs/1_39_0/doc/html/function/faq.html#id1877737) 
> but there are probably workarounds that are alright. It would be nice 
> of course if the queue user stays unaffected by the workaround but 
> that is probably not possible. Another layer perhaps.
> Any suggestion for the code below?
>
> class UniqueFunctionQueue
> {
> public:
>    typedef boost::function<void()> QueueItem;
>
> public:
>    void push(QueueItem item)
>    {
>        /* ToDo, would be nice to do:
>        if (item is already in the queue)
>            return;
>        */
>        queue.push_back(item);
>    }
>    void execute()
>    {
>        for(std::deque<QueueItem>::iterator i = queue.begin(); i != 
> queue.end(); i++)
>            (*i)();
>        queue.clear();
>    }
>
> private:
>    std::deque<QueueItem> queue;
> };
>
> ....
>
> UniqueFunctionQueue queue;
> queue.push(boost::bind(&Synchronizer::sync, &synchronizer, LeftToRight));
> queue.push(boost::bind(&Synchronizer::sync, &synchronizer, RightToLeft));
> queue.push(boost::bind(&Initializer::init, &initializer));
> queue.push(boost::bind(&Synchronizer::sync, &synchronizer, 
> LeftToRight)); // Should not be added since there is one in the queue 
> already.
> queue.execute();

If the caller of push knows the type of the function object,
then you can template the push function.

template<class F>
void push(const F& f) {
    if(std::find_if(queue.begin(), queue.end(), f == _1) != queue.end()) {
        queue.push_back(item);
    }
}

This is going to be pretty inefficient because of the linear search,
but the same idea applies if you want to store the function objects
in a data structure that supports faster lookup.

In Christ,
Steven Watanabe