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?

Answer 1

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.

Answer 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.