값별로 대기열 요소를 제거 할 수 있습니까?

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);이며 검색 및 값으로 지우기를 지원합니까?

Answer 1

양단 큐는 시퀀스 컨테이너는, 그래서 당신은 단지 최고의 제거/삭제 관용구 함께 할 것입니다 값에 의해 요소를 제거 할 수 있습니다

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

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

당신이 std::queue 어댑터를 사용하는 경우, 당신은 어댑터는 front/back 인터페이스 만 노출하고 반복 또는 조회 의미를위한 것이 아니기 때문에이 작업을 전혀 수행 할 수 없습니다.

큐를 std::list으로 구현하도록 선택한 경우 대신 remove() 멤버 함수를 사용하십시오.

Answer 2

딩고 (Dointg it) - 큐와 맵 모두를 사용하는 장점을 제거하고 두 가지의 단점을 (적어도 성능면에서) 유지합니다. 나는 단지 deque<std::pair<map_t_1, map_t_2> >을 사용하여 map과 deque를 모두 표현할 것이다. 그런 다음지도 조회 또는 수정 작업을 전체 양 큐를 살펴 봐야하므로 그리 효율적이지 않습니다.

키 (맵)와 인덱스 (자연 순서대로 정렬해야 함)에 따라 서로 다른 두 가지 인덱싱 체계에 대처하기 위해보다 효율적인 솔루션을 얻는 것이 더 어려울 수 있습니다. 효율적으로하기 위해 나는 키의 맵과 함께 linked_list 항목에 대한 자체 구현 double-linked-list (대기열로)를 제안 할 것입니다. 이중 연결된 목록 항목에는 대기열에 추가/추가 할 때지도에 조회를위한 키가 포함됩니다.