Czy można usunąć element kolejki według wartości?

Question

Chcę usunąć element z kolejki o określonej wartości. Jak zrobić coś takiego? (Próbuję utworzyć współbieżne mieszaniny mapie i kolejki i obecnie staram się realizować na this answer)

więc obecnie mam taki kod:

#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 

Więc co mam robić? Jak usunąć z kolejki według wartości? Lub thare jest jakikolwiek składnik STL lub Boost, który jest podobną kolejką? Oznacza to, że ma on .front(), pop_front(); i push_back(key);, a także obsługuje wyszukiwanie i usuwanie według wartości?

Answer 1

deque jest kontener sekwencja, więc można tylko usunąć elementy przez wartości, która jest najlepiej zrobić z idiomu remove/kasowania:

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

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

Jeśli używasz zasilacza std::queue, wtedy nie może tego zrobić w ogóle, ponieważ adapter ujawnia tylko interfejs front/back i nie jest przeznaczony do semantyki iteracyjnej lub wyszukiwania.

Jeśli zdecydujesz się wdrożyć swoją kolejkę jako std::list, użyj zamiast tego funkcji składowej remove().

Answer 2

Dointg to tak - zarówno kolejka, jak i mapa usuwa zalety korzystania z jednego z nich i utrzymuje wady obu (przynajmniej pod względem wydajności). Po prostu użyłbym deque<std::pair<map_t_1, map_t_2> > do reprezentowania mapy i deque. Następnie wyszukiwanie lub edytowanie mapy wymaga przeglądania całej bazy danych, więc nie jest zbyt wydajna.

Bardziej wydajne rozwiązanie byłoby trudniejsze do osiągnięcia, ponieważ starasz się poradzić sobie z dwoma różnymi schematami indeksowania - według klucza (mapa) i według indeksu (wymagane przez zamawianie nature de deque). Aby to zrobić skutecznie, zaproponowałbym własną, podwójnie dołączoną listę (jako kolejkę) z mapą kluczy do pozycji linked_list. Podwójnie połączone wpisy listy będą również zawierać klucz do wyszukiwania na mapie podczas dodawania/dołączania kolejki.