Usuń element ze std :: map na podstawie czasu wstawienia

Question

Potrzebuję usunąć elementy ze std :: map na podstawie czasu wstawienia (lub czegoś innego bardziej wydajnego niż to).

Mapa prawdopodobnie pomieści tysiące elementów, a jeśli zapamiętasz czas i powtórzysz mapę, by sprawdzić czas poszczególnych elementów, prawdopodobnie będzie to dość czasochłonne.

Czy ktoś ma dobry pomysł, jak usunąć elementy ze std :: map, gdy się starzeją?

Answer 1

Typ std::map<> nie ma pojęcia, kiedy element został wstawiony. Służy jedynie do przechowywania mapowania pary klucz/wartość. Nie ma również pojęcia kolejności wstawiania, więc nie może nawet podać względnego rodzaju wstawki.

Aby zrobić to, co chcesz, musisz dodać powiązanie między elementami i czasem ich wstawienia. Jeśli chcesz tylko względnej kolejności, możesz użyć sparowanego z mapą std::queue. Za każdym razem, gdy wstawiasz mapę, wstawiasz ją również do std::queue. Elementy z przodu kolejki są starsze niż z tyłu i można z nich korzystać dla względnego wieku.

Answer 2

Można użyć kolejki kolejki i wstawić wskaźniki do obiektów podczas ich wstawiania do mapy. Następny element w kolejce będzie najstarszy. Lub możesz zapisać parę w kolejce, jeśli potrzebujesz również czasu wstawienia.

Answer 3

Całkiem blisko LRU Cache.

Biblioteka Boost.MultiIndex pokazuje przykład MRU Cache (najczęściej używany), więc dostosowanie go do LRU powinno być trywialne.

Zasadniczo chodzi o to, aby utrzymać dwie struktury danych równolegle:

• map z rzeczami w
• deque z odniesieniami do mapy

kod podstawowy:

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(); 
    } 
} 

Oczywiście te struktury wymagają e zsynchronizowane, jeśli celem jest uzyskanie kodu wielowątkowego.