Добрый день, читатели. В процессе изучения С++ столкнулся с такой вот (достаточно интересной) задачей (а точнее по рекомендации товарища) — написание Кэш функции (не Хэш).
В данной задаче кэш — некоторая структура данных, фиксированного размера N, предназначенная для хранения некоторых данных и быстрого обращения к ним, причем: размер кэша всегда фиксированный и составляет N; при получении нового элемента идет проверка на наличие его в кэше, если есть — возвращаются данные (данный элемент можно поместить в начало списка), иначе идет добавление в кэш; и последнее, если нужно добавить N+1 элемент в N-ый хэш, то последний элемент удаляется, а новый встает в начало.
Условие, как таковое, состояло в том, что нужно было создать функтор (класс с перегруженным оператором ()), кэширующий соответствующим образом, а так же получающий в конструкторе указатель на функцию одной переменной и собственно размер кэша N. Попытаюсь рассказать свои мысли по решению этой проблемы. Итак, поехали:
1) Заметим, что поиск по хэшу должен быть максимально быстро (конечно, желательно О(1)), следовательно нужно использовать хэш таблицы, так же нам понадобится список для хранения данных
template <class A, class B1> //A — returned data, B1 — type of date
class CashedFunction
{
int sizeOfCash;
A (*function)(B1);
unordered_map<A, B1> cash;
list listOfValue;
unordered_map<B1, typename list::iterator > its;
public:
CashedFunction (A (*f)(B1), A data); // main instructor
B1 operator () (A key);
};
Я думаю, можно не пояснять значения переменных, последняя хэш таблица содержить итераторы на список.
2) Взглянем на реализацию класса, а точнее только на перегрузку (), т.к в условии задачи явно сказано что происходит в конструкторе.
template <class A, class B1>
B1 CashedFunction<A, B1>::operator()(A key)
{
typename unordered_map<B1, typename list::iterator>::iterator it = its.find(key); // ищем итератор в хэш табл.
if (it != its.end()) //нашли итератор в каком-то месте в списке
{
typename list::iterator iTT = (*it).second;
listOfValue.erase(iTT); //удаляем
listOfValue.push_front(key); //и помещаем в начало списка
cout << 1 << " ";
return (*cash.find(key)).second; //возвращаем значение
}
else //нужно добавить элемент
{
if (listOfValue.size() == sizeOfCash)
listOfValue.pop_back();
listOfValue.push_front(key);
cash.insert(make_pair(f(key), key));
cout << 0 << " ";
return f(key);
}
}
Итак процесс начинается с поиска значения в хэш таблице и далее идет рассмотрение двух случаев: первый — мы не находим наше значение, следовательно добавляем в список; иначе (нашли значение) делаем проверку на полноту и добавляем, при этом сохраняя итераторы в хэш таблице.
Вот и все, прошу написать замечания по поводу кода, если таковые будут.
Автор: iwitaly
