Xóa phần tử khỏi std :: map dựa trên thời điểm chèn

Question

Tôi cần xóa các phần tử từ std :: map dựa trên thời gian chèn (hoặc cái gì đó khác hiệu quả hơn thế).

Bản đồ có thể sẽ chứa hàng nghìn phần tử và nếu tôi lưu trữ thời gian và lặp lại bản đồ để kiểm tra từng phần tử, có thể sẽ mất khá nhiều thời gian.

Có ai có ý tưởng hay về cách xóa các phần tử khỏi sơ đồ :: khi chúng đang già đi không?

Answer 1

Loại std::map<> không có khái niệm khi phần tử được chèn vào. Nó chỉ phục vụ để tổ chức ánh xạ cặp khóa/giá trị. Nó cũng không có khái niệm về thứ tự chèn để nó thậm chí không thể cung cấp một kiểu chèn tương đối.

Để thực hiện những gì bạn muốn, bạn cần thêm liên kết giữa các yếu tố và thời gian chúng được chèn vào. Nếu tất cả những gì bạn muốn là thứ tự tương đối thì bạn có thể sử dụng một số std::queue được ghép nối với bản đồ. Mỗi khi bạn chèn vào bản đồ, bạn cũng chèn vào std::queue. Các phần tử ở phía trước hàng đợi cũ hơn lưng và bạn có thể sử dụng nó cho độ tuổi tương đối

Answer 2

Bạn có thể sử dụng hàng đợi và chèn con trỏ vào đối tượng khi chúng được chèn vào bản đồ. Mục tiếp theo trong hàng đợi sẽ là mục cũ nhất. Hoặc bạn có thể lưu trữ một cặp trong hàng đợi nếu bạn cũng cần thời gian chèn.

Answer 3

Khá gần với LRU Cache.

Thư viện Boost.MultiIndex hiển thị ví dụ về MRU Cache (Được sử dụng gần đây nhất), do đó, điều chỉnh nó thành LRU sẽ không đáng kể.

Về cơ bản các ý tưởng là để duy trì hai cấu trúc dữ liệu song song:

• một map với các mục trong
• một deque với sự tham khảo vào bản đồ

mã cơ bản:

static double const EXPIRY = 3600; // seconds 

std::map<Key, Value> map; 
std::deque<std::pair<std::map<Key, Value>::iterator, time_t>> deque; 

bool insert(Key const& k, Value const& v) { 
    std::pair<std::map<Key, Value>::iterator, bool> result = 
    map.insert(std::make_pair(k, v)); 

    if (result.second) { 
    deque.push_back(std::make_pair(result.first, time())); 
    } 

    return result.second; 
} 

// to be launched periodically 
void clean() { 
    while (not deque.empty() and difftime(time(), deque.front().second) < EXPIRY) { 
    map.erase(deque.front().first); 
    deque.pop_front(); 
    } 
} 

Tất nhiên, những cấu trúc đó cần b e được đồng bộ hóa nếu mục đích là lấy mã đa luồng.