Có thể xóa phần tử hàng đợi theo giá trị không?

Question

Tôi muốn xóa phần tử khỏi hàng đợi với giá trị cụ thể. Làm thế nào để làm điều đó? (Tôi cố gắng để tạo ra một hỗn hợp đồng thời của bản đồ và hàng đợi và hiện nay tôi cố gắng thực hiện trên this answer)

Vì vậy, tôi hiện đang có mã ví dụ:

#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 

Vì vậy, những gì tôi sẽ làm gì? Làm thế nào để loại bỏ khỏi hàng đợi theo giá trị? Hoặc thare là bất kỳ thành phần STL hoặc Boost nào giống như hàng đợi? Có nghĩa là nó sẽ có .front(), pop_front(); và push_back(key); và cũng hỗ trợ tìm kiếm và xóa theo giá trị?

Answer 1

Một deque là một container chuỗi, vì vậy bạn chỉ có thể loại bỏ các yếu tố của giá trị, mà tốt nhất là thực hiện với sự thành ngữ remove/xóa:

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

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

Nếu bạn đang sử dụng adapter std::queue, sau đó bạn hoàn toàn không thể làm điều này, vì bộ điều hợp chỉ hiển thị giao diện front/back và không dành cho ngữ nghĩa lặp lại hoặc tra cứu.

Nếu bạn chọn triển khai hàng đợi dưới dạng std::list, thì hãy sử dụng hàm thành viên remove() thay thế.

Answer 2

Dointg nó như thế - với cả hàng đợi và bản đồ đang loại bỏ các ưu điểm của việc sử dụng một trong hai và giữ những nhược điểm của cả hai (ít nhất là về mặt biểu diễn). Tôi chỉ cần sử dụng deque<std::pair<map_t_1, map_t_2> > để thể hiện cả bản đồ và deque. Sau đó, bản đồ tra cứu hoặc chỉnh sửa yêu cầu xem xét toàn bộ deque, vì vậy nó không phải là rất hiệu quả.

Giải pháp hiệu quả hơn sẽ khó đạt được hơn, vì bạn đang cố gắng đối phó với hai sơ đồ lập chỉ mục khác nhau - theo khóa (bản đồ) và theo chỉ mục (bắt buộc bằng cách đặt hàng thiên nhiên). Để làm điều đó một cách hiệu quả tôi sẽ đề xuất tự thực hiện đôi liên kết-danh sách (như hàng đợi) với bản đồ của các phím để linked_list mục. Các mục nhập danh sách được liên kết kép cũng sẽ chứa khóa để tra cứu trong bản đồ khi hàng đợi thêm/xếp hàng chờ.