Блок задач

8. Чёрные ящики

Темы
Сложность 4

Задача «Хеш-таблица с управляемым удалением элементов»

Реализовать надстройку над unordered_map, которая бы позволяла автоматически удалять элементы при обращении к ним.

Это может быть полезным для реализации кэша, у которого каждый элемент «жив» только в течение определённого времени после его вставки или допускает только фиксированное количество обращений.

Требования

  • Класс стратегии управляемого удаления должен являться параметром шаблона для создаваемого класса, объект класса стратегии должен передаваться в конструкторе и храниться в классе (композиция). Класс стратегии должен инкапсулировать необходимые данные для принятия решения о том, удалять ключ или нет.
  • Должны работать базовые операции: чтение и запись по ключу, удаление элементов. Весь интерфейс unordered_map поддерживать не нужно.
  • Должны работать итераторы (при посещении элемента он также должен удаляться, а итератор — «перепрыгивать» к следующему).
  • Создать несколько стратегий: не удалять никогда, удалять по прошествии заданного времени, удалять после заданного количества обращений.