Блок задач

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

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

Задача «Vector и файл»

Реализовать класс-аналог std::vector, который был бы связан с файлом. Элементы вектора берутся из файла, запись элемента в вектор приводит к сохранению элемента в файл.

Мотивация

Такой класс может быть полезным для работы с огромным файлом, который целиком не помещается в память (допустим, 1 терабайт), но с которым хочется работать прозрачно, как со структурой данных, используя итераторы и т.д.

Однако постоянные чтение/запись элементов будут неэффективны. Чтобы справиться с этим, предлагается использовать «окно доступа». На старте выделяется память под окно (допустим, это будет 1 мегабайт). Обращение к первому элементу вектора вызовет загрузку окна (и, следовательно, второй, третий и т.д. элементы будут браться уже из памяти). Обращение к элементу, не попадающему в окно, вызовет перезагрузку окна. Перед этим, если содержимое окна модицифировалось, оно должно быть записано в файл.

Интерфейс

  • Конструкторы, позволяющие привязать существующий файл (на чтение или на чтение/запись), или создать новый с заданным размером. Предусмотреть возможность задания размера окна.
  • Доступ на чтение и на запись с использованием итераторов (константных и неконстантных).
  • Произвольный доступ по индексу (operator[]).
  • resize — изменение размера (в большую или меньшую сторону).
  • flush — явно сохранить текущие изменения в файл.
  • push_back — вставка в конец.
  • pop_back — получение элемента с конца с его последующим удалением.
  • seek_window – явно установить положение окна (перегрузить данный метод, чтобы можно было передавать и индекс, и итератор).

Операции вставки и удаления в произвольном месте (не в конце) здесь не предлагаются — в силу своей неэффективности для файлов большого размера.

Примечания

Работа с файлом должна производиться в двоичном режиме. Мы предполагаем, что тип элемента имеет фиксированный sizeof и что можно использовать побайтовое чтение и запись.