Skip to content
TheChatArchiveThe Chat Archive
gpt-4-0314· OpenAIHugging Face Arena Human Preference 55K

Implement LRU cache in cpp

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-1’s answer.
  1. User

    Implement LRU cache in cpp

  2. Assistant

    An LRU (Least Recently Used) cache is a cache data structure that removes the least recently used items first when the cache reaches its maximum capacity. Here's one way to implement an LRU cache in C++ using STL containers (unordered_map and list):

    #include <iostream>
    #include <list>
    #include <unordered_map>
    
    class LRUCache {
    public:
        LRUCache(int capacity): _capacity(capacity) {}
    
        int get(int key) {
            // If key is not in the cache, return -1
            if (_cache.find(key) == _cache.end()) {
                return -1;
            }
            // Move the accessed element to the front of the list
            _lru.splice(_lru.begin(), _lru, _cache[key].second);
            
            // Return the value of the key
            return _cache[key].first;
        }
    
        void put(int key, int value) {
            // If key is already in the cache, update the value and move to the front
            if (_cache.find(key) != _cache.end()) {
                _cache[key].first = value;
                _lru.splice(_lru.begin(), _lru, _cache[key].second);
                return;
            }
            // If the cache is full, remove the least recently used element
            if (_cache.size() == _capacity) {
                int lruKey = _lru.back();
                _lru.pop_back();
                _cache.erase(lruKey);
            }
            // Add the new key-value pair to the cache and the list
            _lru.push_front(key);
            _cache[key] = {value, _lru.begin()};
        }
    
    private:
        int _capacity;
        std::list<int> _lru;
        std::unordered_map<int, std::pair<int, std::list<int>::iterator>> _cache;
    };
    
    int main() {
        LRUCache cache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        std::cout << cache.get(1) << std::endl; // returns 1
        cache.put(3, 3); // evicts key 2
        std::cout << cache.get(2) << std::endl; // returns -1 (not found)
        cache.put(4, 4); // evicts key 1
        std::cout << cache.get(1) << std::endl; // returns -1 (not found)
        std::cout << cache.get(3) << std::endl; // returns 3
        std::cout << cache.get(4) << std::endl; // returns 4
    
        return 0;
    }
    

    This implementation uses an unordered_map (_cache) to store key-value pairs and their iterators to the corresponding elements in a list (_lru). The list is used to track the order of usage, with the front being the most recently used and the back being the least recently used element. When the cache reaches its capacity, the least recently used element is removed from both the unordered_map and the list.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt