¿Es posible eliminar el elemento de cola por valor?

Question

Quiero eliminar elemento de la cola con valor específico. ¿Cómo hacer tal cosa? (Estoy tratando de crear una mezcla simultánea de mapa y la cola y en la actualidad trato de aplicar en this answer)

Así que actualmente tienen tal código:

#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 

Entonces, ¿qué voy a hacer? ¿Cómo eliminar de la cola por valor? ¿O thare es cualquier componente STL o Boost que sea similar a la cola? ¿Quiere decir que tendría .front(), pop_front(); y push_back(key); y también admite la búsqueda y borrado por valor?

Answer 1

Un deque es un contenedor de secuencias, por lo que sólo puede eliminar los elementos por valor, que se hace mejor con el lenguaje de Eliminar/Borrar:

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

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

Si está utilizando el adaptador std::queue, entonces no puede hacer esto en absoluto, porque el adaptador solo expone la interfaz front/back y no está destinado a la semántica de iteración o búsqueda.

Si elige implementar su cola como std::list, utilice la función de miembro remove().

Answer 2

Piénselo de esta manera: con la cola y el mapa se eliminan las ventajas de usar cualquiera de ellos, y se mantienen las desventajas de ambos (al menos en términos de rendimiento). Simplemente usaría deque<std::pair<map_t_1, map_t_2> > para representar mapa y deque. Luego, la búsqueda o edición del mapa requiere mirar todo el deque, por lo que no es muy eficiente.

Solución más eficiente sería más difícil de lograr, ya que está tratando de hacer frente a dos esquemas de indexación diferentes - por clave (mapa) y por índice (requerido ordenando la naturaleza od deque). Para hacerlo de manera eficiente, propondría una lista de doble enlace auto implementada (como cola) con un mapa de claves para las entradas de la lista de enlaces. Las entradas dobles de la lista vinculada también contendrían la clave para la búsqueda en el mapa cuando se antepone/agrega la cola.