README.md

How to run this:

• Put lru.hpp in the include folder of a project (e.g. the sample exam)
• Put lru_client.cpp in the source folder of a project (e.g. the sample exam)
• Edit the source/CMakeLists.txt file to include

cxx_executable(
    TARGET "lru_client"
    FILENAME "lru_client.cpp"
)

That should work I guess

lru.hpp

#include <cstddef>
#include <ostream>
#include <stdexcept>
#include <utility>

namespace lru {
	class cache_error : public std::runtime_error {
		cache_error()
		: std::runtime_error("LRU cache error") {}
	};

	template<typename K, typename V>
	class cache {
	public:
		// TODO: make this initialise a LRU cache with default capacity 10
		cache() = default;

		// TODO: make this initialise a LRU cache with given capacity
		cache(std::size_t const capacity) {
			(void)capacity;
		}

		// TODO: make this return whether the cache is empty or not
		auto empty() -> bool {
			return false;
		}

		// TODO: make this return whether the cache is full or not
		auto full() -> bool {
			return false;
		}

		// TODO: make this get the value associated with the requested key, in amortised O(1) time
		// this should make that key the most recently used one upon successful lookup
		// throw cache_error if the key does not exist
		auto get(K const& key) -> V {
			(void)key;
			return V{};
		}

		// TODO: make this add the appropriate key-value pair to the cache, in amortised O(1) time
		// naturally, this should be the least recently-used pair
		// replace the value if the key already exists
		// if the key does not already exist, evict the least recently-used element to make room if
		// the cache is already full
		auto push(K const& key, V const& val) -> void {
			(void)key;
			(void)val;
		}

		// TODO (troll): implement a push() function that takes an arbitrary number of key-value
		// pairs to add to the cache
		//
		// part of the exercise is deciding how to declare this function, but it should be usable like
		//   c.push(std::make_pair(k1, v1));
		//   c.push(std::make_pair(k1, v1), std::make_pair(k2, v2));
		//   c.push(std::make_pair(k1, v1), std::make_pair(k2, v2), std::make_pair(k3, v3));
		// etc.

		// TODO: make this evict the least recently-used item from the cache, and return it
		// throw cache_error if the cache is empty
		auto evict() -> std::pair<K, V> {
			return std::make_pair(K{}, V{});
		}

		// TODO: make this print the cache in usage history order (most to least recently used)
		//
		// print nothing if the cache is empty
		// no trailing comma if the cache only has 1 element
		//
		// as an example, if the key-value pairs in the cache are, in order,
		//   - ("hello", 2)   <-- most recently used
		//   - ("there", 1)
		//   - ("friendo", 3) <-- least recently used
		// the output should be ("hello", 2), ("there", 1), ("friendo", 3)
		friend auto operator<<(std::ostream& os, cache& c) -> std::ostream& {
			(void)c;
			return os;
		}

	private:
		// your impl. details here
	};

} // namespace lru

lru_client.cpp

#include "lru.hpp"

#include <iostream>
#include <utility>

auto main() -> int {
	auto c = lru::cache<int, int>(3);

	// should print 1 and 0 respectively
	std::cout << c.empty() << "\n";
	std::cout << c.full() << "\n";

	// if you get pushing with an arbitrary number of pairs at once you should be able to just do
	// c.push(std::make_pair(1, 3), std::make_pair(2, 2), std::make_pair(3, 1));
	c.push(1, 3);
	c.push(2, 2);
	c.push(3, 1);

	// should print (3, 1), (2, 2), (1, 3)
	std::cout << c << "\n";

	// should print 2
	auto const v2 = c.get(2);
	std::cout << v2 << "\n";

	// should print (2, 2), (3, 1), (1, 3)
	std::cout << c << "\n";

	// should print (1, 3)
	auto const p = c.evict();
	std::cout << "(" << p.first << ", " << p.second << ")\n";

	// should print (2, 2), (3, 1)
	std::cout << c << "\n";
}