Студент

Кониченко Александр

Задача

Кэш

Состояние

Завершено

Баллов

5

Дедлайн

Назначено

24.10.2015, 10:55

Завершено

16.12.2015, 10:53

Реализовать кэш.

Входные данные

Текстовый файл следующего вида:

ключ1 = значение1
ключ2 = значение2
...

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

Постановка задачи

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

Необходимо реализовать кэширование читаемых из файла данных. Для доступа к записям вида ключ - значение определим абстрактный интерфейс IReader:

template<typename K, typename V>
class IReader
{
public:
    virtual V operator[](const K & key) = 0;
};

• operator [] - поиск значения по ключу. Если значение не найдено - генерируется исключение.

Для “медленного” чтения записей из файла необходимо реализовать класс FileReader:

class FileReader : public IReader<std::string, std::string>
{
public:
    FileReader(std::istream & is);
    virtual std::string operator[](const std::string & key);
};

• Конструктор - создание объекта по ссылке на стандартный поток std::istream
• operator[] - реализация интерфейса `IReader

При запросе записи с несуществующим ключом объект FileReader должен генерировать исключение range_error.

Также необходимо реализовать класс кэша со следующим интерфейсом:

template<typename K, typename V, size_t limit = 1024>
class Cache : public IReader<K, V>
{
public:
    Cache(IReader<K, V> & reader);
    void reset(void);
    virtual V operator[](const K & key);
};

• Конструктор - создание кэша по ссылке на другой объект реализующий интерфейс IReader
• reset - принудительная очистка всех ячеек кэша.
• operator [] - реализация интерфейса IReader

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

Пример использования

std::ifstream dataFile;
dataFile.open("data.txt");
FileReader rd(dataFile);
Cache<std::string, std::string> cache(rd);

try
{
    std::cout << "key = " << cache["key"] << std::endl;
}
catch (const std::range_error & e)
{
    std::cerr << e.what() << std::endl;
}

Выходные данные

Реализованный вышеописанный пример