LRU keš

Napisati generičku klasu LRU_kes<K, V> koja implementira LRU (engl. Least Recently Used) keš sa ključevima tipa K i vrednostima tipa V. Klasa treba da podržava sledeće operacije:

LRU_kes(size_t kapacitet) - konstruktor koji postavlja maksimalni kapacitet keša.
void stavi(const K& kljuc, const V& vrednost) - dodaje par (kljuc, vrednost) u keš. Ako je keš pun, uklanja se najmanje korišćeni par.
const V& uzmi(const K& kljuc) - vraća vrednost povezanu sa datim ključem. Ako ključ nije prisutan, baca izuzetak std::out_of_range.
bool postoji(const K& kljuc) const - proverava da li keš sadrži dati ključ.

Sve operacije treba da budu složenosti ne veće od $O(1)$.

Ulaz

Sa standardnog ulaza prvo se učitava maksimalni kapacitet keša $n$, a zatim, sve do kraja ulaza, i niz upita u formatu:

s k v - dodaje par (k, v) u keš
u k - ispisuje vrednost za ključ k ili izuzetak ako ključ nije prisutan

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi u k. Ako neka naredba baci izuzetak, ispisati poruku izuzetka na standardni izlaz za greške.

Primer

`stdin`

`stdout`

1
Kljuc nije u kesu
Kljuc nije u kesu
3
4

Rešenje

`main.cpp`

#include <iostream>
#include <iterator>
#include <list>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>

namespace matf
{
	/* Klasa za LRU kes */
	template <typename K, typename V>
	class LRU_kes
	{
		typedef typename std::pair<K, V> Par;
		typedef typename std::list<Par>::iterator ListIt;

		public:
			/* Konstruktor sa zadatim kapacitetom kesa */
			LRU_kes(size_t _kapacitet) : kapacitet(_kapacitet) {}

			/* Dodaje par kljuc-vrednost u kes */
			void stavi(const K& kljuc, const V& vrednost)
			{
				// Ako par sa datim kljucem vec postoji, ukloni ga iz liste i mape
				auto it = mapa_stavki.find(kljuc);
				if (it != mapa_stavki.end()) {
					lista_stavki.erase(it->second);
					mapa_stavki.erase(it);
				}

				// Dodaj novi par na pocetak liste i u mapu
				lista_stavki.push_front(std::make_pair(kljuc, vrednost));
				mapa_stavki[kljuc] = lista_stavki.begin();

				// Ako je kapacitet kesa prekrsen, ukloni najdavnije korisceni par
				if (mapa_stavki.size() > kapacitet) {
					auto last = std::prev(lista_stavki.end());
					mapa_stavki.erase(last->first);
					lista_stavki.pop_back();
				}
			}

			/* Vraca vrednost za dati kljuc i oznacava ga kao najskorije koriscenog */
			const V& uzmi(const K& kljuc)
			{
				auto it = mapa_stavki.find(kljuc);
				if (it == mapa_stavki.end()){
					throw std::range_error("Nema trazenog kljuca u kesu");
				}

				// Premesti par na pocetak liste (oznaci ga kao najvise koriscenog)
				lista_stavki.splice(lista_stavki.begin(), lista_stavki, it->second);

				return it->second->second;
			}

			/* Proverava da li kes sadrzi dati kljuc */
			bool postoji(const K& kljuc) const
			{
				return mapa_stavki.find(kljuc) != mapa_stavki.end();
			}

		private:
			std::list<Par> lista_stavki;
			std::unordered_map<K, ListIt> mapa_stavki;
			size_t kapacitet;
	};
};

int main(void)
{
	int n; std::cin >> n;

	matf::LRU_kes<int, int> kes(n);

	char op;

	while(std::cin >> op) {
		if (op == 's') {
			int k, v; std::cin >> k >> v;
			kes.stavi(k, v);
		} else if (op == 'u') {
			int k; std::cin >> k;
			if (kes.postoji(k)) {
				int v = kes.uzmi(k);
				std::cout << k << std::endl;
			} else {
				std::cerr << "Kljuc nije u kesu" << std::endl;
			}
		}
	}

	return 0;
}