Remove element from std::map based on the time of insertion
The std::map<>
type has no notion of when an element was inserted. It only serves to hold a key / value pair mapping. It also has no notion of insert order so it can't even provide a relative type of insert.
To do what you want you'll need to add an association between the elements and the time they were inserted. If all you want is relative order then you could use a std::queue
paired with the map. Every time you insert into the map you insert into the std::queue
as well. Elements at front of the queue are older than the back and you can use that for relative age
Pretty close to LRU Cache.
The Boost.MultiIndex library shows an example of MRU Cache (Most Recently Used), so adapting it to LRU should be trivial.
Basically the idea is to maintain two data structures in parallel:
- a
map
with the items in - a
deque
with references into the map
Basic code:
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();
}
}
Of course, those structures need be synchronized if the intent is to get multi-threaded code.