Удалить элемент из std :: map в зависимости от времени вставки - PullRequest
Новая
       29

Удалить элемент из std :: map в зависимости от времени вставки

10 голосов
/ 15 марта 2012

Мне нужно удалить элементы из std :: map на основе времени вставки (или чего-то более эффективного, чем это).

Карта, вероятно, будет содержать тысячи элементов, и если я сохраню время и выполню итерацию карты для проверки времени каждого элемента, это, вероятно, в конечном итоге займет довольно много времени.

Кто-нибудь знает, как стереть элементы из std :: map, когда они стареют?

Ответы [ 3 ]

7 голосов
/ 15 марта 2012

Тип std::map<> не имеет понятия, когда элемент был вставлен. Он служит только для хранения сопоставления пары ключ / значение. В нем также нет понятия порядка вставки, поэтому он даже не может предоставить относительный тип вставки.

Чтобы сделать то, что вы хотите, вам нужно добавить связь между элементами и временем их вставки. Если вам нужен только относительный порядок, вы можете использовать std::queue в паре с картой. Каждый раз, когда вы вставляете в карту, вы также вставляете в std::queue. Элементы в начале очереди старше, чем задние, и вы можете использовать это для относительного возраста

4 голосов
/ 15 марта 2012

Довольно близко к LRU Cache .

В библиотеке Boost.MultiIndex показан пример MRU Cache (чаще всего используется),поэтому адаптация его к LRU должна быть тривиальной.

По сути, идея состоит в том, чтобы поддерживать две структуры данных параллельно:

  • a map с элементами в
  • deque со ссылками на карту

Базовый код: 

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

Конечно, эти структуры должны быть синхронизированы, если необходимо получить многопоточный код.

1 голос
/ 15 марта 2012

Вы можете использовать очередь и вставлять указатели на объекты по мере их вставки в карту. Следующий элемент в очереди будет самым старым. Или вы можете сохранить пару в очереди, если вам также нужно время вставки.

...