キュー要素を値で削除することはできますか？

Question

特定の値を持つキューから要素を削除したい。そんなことをする方法？ （私はマップとキューの同時混合物を作成しようとしています。現在、私はthis answerに実装しよう）

だから私は現在、このようなコードを持っている：

#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 

だから私はどうしたらよいのでしょうか値によってキューから削除するには？または、STARまたはBoostコンポーネントが同様のキューですか？つまり、.front(),pop_front();、push_back(key);となり、値による検索と消去がサポートされますか？あなたは、その後、std::queueアダプタを使用している場合

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

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

：あなただけの最高の削除/消去イディオムで行われ値によって要素を削除することができるように

Answer 1

両端キューは、シーケンスコンテナですアダプタはfront/backインターフェイスのみを公開し、反復またはルックアップのセマンティクスを目的としていないため、これをまったく実行できません。

キューをstd::listとして実装する場合は、代わりにメンバー関数remove()を使用してください。

Answer 2

Dointgそれは好きです - キューとマップの両方で、どちらかを使用する利点を取り除き、両方の不利な点を（少なくともパフォーマンス面で）維持します。私は単にdeque<std::pair<map_t_1, map_t_2> >を使用して、マップとデキューの両方を表現します。次に、マップのルックアップや編集で両端キュー全体を調べる必要があるため、あまり効率的ではありません。

キー（マップ）とインデックス（性質と順序を指定することによって必要とされます）によって、2つの異なるインデックススキームに対処しようとすると、より効率的なソリューションを実現することは難しくなります。それを効率的に行うために、私は、キーのマップを使ってlinked_listエントリへの自己実装ダブルリンクリスト（キューとして）を提案します。二重リンクされたリスト項目はまた、キューのプリペンド/追加時にマップのルックアップのキーを含む。