Is it possible to delete a queue element by value?

Question

I want to remove an item from a queue with a specific value. How to do it? (I'm trying to create a parallel mix of cards and queues, and I'm currently trying to implement this answer )

So, I have a code like this:

#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 should I do? How to remove from the queue by value? Or could there be any STL or queue-like Boost component? The meaning of this: .front() , pop_front(); and push_back(key); as well as support for searching and erasing by value?

Answer 1

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

 std::deque<T> q; T val; q.erase(std::remove(q.begin(), q.end(), val), q.end()); 

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

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

Answer 2

Dointg does it this way: with both queues and a card, the advantages of using both are removed, and they have disadvantages of both (at least in terms of performance). I would just use deque<std::pair<map_t_1, map_t_2> > to represent both the map and deque. Then searching or editing a map requires viewing the entire deck, so it is not very effective.

A more effective solution would be more difficult to achieve, since you are trying to cope with two different indexing schemes - using a key (card) and an index (required when ordering nature od deque). To do this efficiently, I would suggest a self-implemented double-linked-list (as a queue) with a map of the keys to the linked_list entries. Items with a double linked list will also contain a key to search on the map when adding / adding a queue.