Add seminar 10 and 11

1 files changed, 45 insertions, 0 deletions

diff --git a/Seminar10/src/lru-cache.cpp b/Seminar10/src/lru-cache.cpp
new file mode 100644
index 0000000..d199eb1
--- /dev/null
+++ b/Seminar10/src/lru-cache.cpp
@@ -0,0 +1,45 @@
+#include <list>
+#include <unordered_map>
+#include <stdexcept>
+
+class LRUCache
+{
+    size_t capacity;
+    std::list<std::pair<int, int>> data;
+    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> dataMap;
+
+public:
+    LRUCache(size_t capacity) : capacity(capacity) { }
+
+    int get(int key)
+    {
+        if (dataMap.find(key) == dataMap.end())
+        {
+            throw std::runtime_error("Data not in cache");
+        }
+
+        auto it = dataMap[key];
+
+        // Transfers elements from one list to another. 
+        // No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.
+        data.splice(data.begin(), data, it);
+        return it->second;
+    }
+
+    void put(int key, int value)
+    {
+        if (dataMap.find(key) != dataMap.end())
+        {
+            auto it = dataMap[key];
+            data.erase(it);
+        }
+
+        data.push_front({ key, value });
+        dataMap[key] = data.begin();
+        if (data.size() > capacity)
+        {
+            dataMap.erase(data.back().first);
+            data.pop_back();
+        }
+    }
+};
\ No newline at end of file