Is it possible to remove queue element by value?

Question

I want to remove element from queue with specific value. How to do such thing? (I am trying to create a concurrent mixture of map and queue and currently I try to implement on this answer)

So I currently have such code:

#ifndef CONCURRENT_QUEUED_MAP_H
#define CONCURRENT_QUEUED_MAP_H

#include <map>
#include <deque>
#include <boost/thread.hpp>
#include <boost/thread/locks.hpp>

template <class map_t_1, class map_t_2>
class concurrent_queued_map
{
private:
    std::map<map_t_1, map_t_2> _ds;
    std::deque<map_t_1> _queue;
    mutable boost::mutex mut_;
public:
    concurrent_queued_map() {}

    map_t_2 get(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        return _ds[key];
    }

    map_t_1 put(map_t_1 key, map_t_2 value) {
        boost::mutex::scoped_lock lock(mut_);
        _ds.insert(std::pair<map_t_1, map_t_2>(key,value));
        _queue.push_back(key);
        return key;
    }

    map_t_2 get_last(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        const map_t_1 k = _queue.front();
        return _ds[k];
    }

    void remove_last(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        const map_t_1 k = _queue.front();
        _ds.erase(k);
        _queue.pop_front();
    }

    void remove(map_t_1 key) {
        boost::mutex::scoped_lock lock(mut_);
        _queue.erase(std::remove(_queue.begin(), _queue.end(), key), _queue.end());
        _ds.erase(k);
    }

    int size() {
        boost::mutex::scoped_lock lock(mut_);
        return _ds.size();
    }

};

#endif // CONCURRENT_QUEUED_MAP_H

So what shall I do? How to remove from queue by value? Or thare is any STL or Boost component that is alike queue? Meaning it would have .front(), pop_front(); and push_back(key); and also support search and erase by value?

Can you phrase your question a bit more clearly and succinctly? A queue doesn't have "keys", so your question doesn't make sense; it's a sequence container that only has values. — Kerrek SB
– Kerrek SB, Commented Oct 9, 2011 at 17:33

Kerrek SB · Accepted Answer · 2011-10-09 17:34:57Z

24

A deque is a sequence container, so you can only remove elements by value, which is best done with the remove/erase idiom:

std::deque<T> q;
T val;

q.erase(std::remove(q.begin(), q.end(), val), q.end());

If you are using the std::queue adapter, then you cannot do this at all, because the adapter only exposes the front/back interface and is not intended for iteration or lookup semantics.

If you choose to implement your queue as an std::list, then use the member function remove() instead.

answered Oct 9, 2011 at 17:34

Kerrek SB

480k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rella Over a year ago

vhat is difference between q.erase(val) and q.erase(std::remove(q.begin(), q.end(), val), q.end());?

Christian Rau Over a year ago

@Kabumbus The difference is, that the first won't compile, as erase takes an iterator and not a value of the contained type.

j_kubik · Accepted Answer · 2011-10-09 17:50:33Z

2

Dointg it like that - with both queue and map is removing advantages of using either, and keeps disadvantages of both (at least in terms of performace). I would simply use deque<std::pair<map_t_1, map_t_2> > to represent both map and deque. Then map lookup or editing requires looking through entire deque, so it's not very efficient.

More efficient solution would be more difficult to achieve, as you are trying to cope with two different indexing schemes - by key (map) and by index (required by ordering nature od deque). To do it efficiently i would propose self-implemented double-linked-list (as queue) with map of keys to linked_list entries. Double linked list entries would also contain key for lookup in the map when prepending/appending queue.

answered Oct 9, 2011 at 17:50

j_kubik

6,1811 gold badge26 silver badges45 bronze badges

2 Comments

Rella Over a year ago

Are there any boost out of the box components for that?

j_kubik Over a year ago

I am not a boost expert, but i am guessing that there isn't.

Collectives™ on Stack Overflow

Is it possible to remove queue element by value?

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related