È possibile rimuovere l'elemento coda per valore?

Question

Voglio rimuovere l'elemento dalla coda con un valore specifico. Come fare una cosa del genere? (Sto cercando di creare una miscela concomitante di mappa e di coda e attualmente cerco di implementare su this answer)

Così ho attualmente tale codice:

#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 

Allora, cosa devo fare? Come rimuovere dalla coda in base al valore? Oppure thare è un componente STL o Boost che è uguale alla coda? Significa che avrebbe .front(), pop_front(); e push_back(key); e supporta anche la ricerca e cancellare in base al valore?

Answer 1

Un deque è un contenitore di sequenza, in modo da poter rimuovere solo gli elementi da valore, che è fatto meglio con l'idioma rimuovere/cancellare:

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

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

Se si utilizza l'adattatore std::queue, allora si impossibile farlo, poiché l'adattatore espone solo l'interfaccia front/back e non è intesa per l'iterazione o la semantica della ricerca.

Se si sceglie di implementare la coda come std::list, utilizzare invece la funzione membro remove().

Answer 2

Fare così - con entrambe le code e la mappa sta rimuovendo i vantaggi dell'utilizzo di entrambi e mantiene gli svantaggi di entrambi (almeno in termini di prestazioni). Vorrei semplicemente usare deque<std::pair<map_t_1, map_t_2> > per rappresentare sia la mappa che il deque. Quindi la ricerca o la modifica delle mappe richiede la visualizzazione dell'intero deque, quindi non è molto efficiente.

Una soluzione più efficiente sarebbe più difficile da raggiungere, poiché si sta tentando di far fronte a due diversi schemi di indicizzazione: per chiave (mappa) e per indice (richiesto ordinando natura od deque). Per farlo in modo efficiente, propongo l'elenco autoimposto con collegamento doppio (come coda) con la mappa delle chiavi per le voci lista_letta. Le doppie voci dell'elenco collegato contengono anche la chiave per la ricerca nella mappa quando si accoda/accoda la coda.