C++11 LRU Cache

lru.cc

#include <list>
#include <unordered_map>

class LRUCache {
 public:
  LRUCache(int capacity) : capacity_(capacity) {}

  int get(int key) {
    auto it = used_.find(key);
    if (it == used_.end()) {
      return -1;
    }

    least_.splice(least_.begin(), least_, it->second);
    return it->second->second;
  }

  void put(int key, int value) {
    auto it = used_.find(key);
    if (it != used_.end()) {
      least_.splice(least_.begin(), least_, it->second);
      it->second->second = value;
    } else {
      least_.push_front(std::make_pair(key, value));
      used_[key] = least_.begin();
      if (used_.size() > capacity_) {
        used_.erase(least_.back().first);
        least_.pop_back();
      }
    }
  }

 private:
  int capacity_;
  std::list<std::pair<int, int>> least_;
  std::unordered_map<int, decltype(least_)::iterator> used_;
};

int main() {
  LRUCache cache(2);

  cache.put(1, 1);
  cache.put(2, 2);
  cache.get(1);     // returns 1
  cache.put(3, 3);  // evicts key 2
  cache.get(2);     // returns -1 (not found)
  cache.put(4, 4);  // evicts key 1
  cache.get(1);     // returns -1 (not found)
  cache.get(3);     // returns 3
  cache.get(4);     // returns 4
}