Build Lab: O(1) LRU and Frequency-Bucketed LFU Cache Engine

End-to-End State Machine of the $O(1)$ LFU Engine

Let us trace every edge case required to implement a zero-allocation, bug-free $O(1)$ LFU Cache of capacity $C$. Every cached item is represented by a Node containing {key, value, freq, prev, next}. We maintain:

• key_table: Maps key -> Node* (or arena slot index).
• freq_table: Maps freq -> DoublyLinkedList, where each list orders nodes of that exact frequency from Most Recently Used (front) to Least Recently Used (back).
• min_freq: An integer tracking the smallest frequency $f \ge 1$ such that freq_table[f] is non-empty.

Operation Complexity & Edge-Case Matrix

Visualizing Eviction + Insertion Order on Cache-Full Miss

Complete Control Flow of LFUCache::put(key, value)

Production Implementation: Zero-Allocation Intrusive O(1) LFU Cache Engine

#include <cstdint>
#include <unordered_map>
#include <vector>

class LFUCache {
  struct Node {
    int key = 0;
    int value = 0;
    int freq = 1;
    int prev = -1;
    int next = -1;
  };

  struct FreqList {
    int head = -1; // MRU front
    int tail = -1; // LRU back
    int count = 0;
  };

  int capacity_;
  int size_ = 0;
  int min_freq_ = 0;
  std::vector<Node> pool_;
  std::vector<int> free_slots_;
  std::unordered_map<int, int> key_to_slot_;
  std::unordered_map<int, FreqList> freq_lists_;

  void remove_from_list(int slot, int freq) {
    auto it = freq_lists_.find(freq);
    FreqList& list = it->second;
    const int p = pool_[slot].prev;
    const int n = pool_[slot].next;

    if (p != -1) pool_[p].next = n;
    else list.head = n;

    if (n != -1) pool_[n].prev = p;
    else list.tail = p;

    pool_[slot].prev = pool_[slot].next = -1;
    if (--list.count == 0) {
      freq_lists_.erase(it); // Prevent unbounded empty bucket memory leak!
      if (min_freq_ == freq) {
        ++min_freq_;
      }
    }
  }

  void push_front_list(int slot, int freq) {
    FreqList& list = freq_lists_[freq];
    pool_[slot].prev = -1;
    pool_[slot].next = list.head;
    if (list.head != -1) pool_[list.head].prev = slot;
    else list.tail = slot;
    list.head = slot;
    ++list.count;
  }

  void touch(int slot) {
    const int f = pool_[slot].freq;
    remove_from_list(slot, f);
    pool_[slot].freq = f + 1;
    push_front_list(slot, f + 1);
  }

public:
  explicit LFUCache(int capacity) : capacity_(capacity), pool_(capacity > 0 ? capacity : 0) {
    for (int i = capacity - 1; i >= 0; --i) {
      free_slots_.push_back(i);
    }
  }

  int get(int key) {
    auto it = key_to_slot_.find(key);
    if (it == key_to_slot_.end()) return -1;
    const int slot = it->second;
    touch(slot);
    return pool_[slot].value;
  }

  void put(int key, int value) {
    if (capacity_ <= 0) return;

    auto it = key_to_slot_.find(key);
    if (it != key_to_slot_.end()) {
      const int slot = it->second;
      pool_[slot].value = value;
      touch(slot);
      return;
    }

    int slot = -1;
    if (size_ == capacity_) {
      // Evict LRU tail of min_freq_ BEFORE resetting min_freq_ = 1!
      const int victim = freq_lists_[min_freq_].tail;
      remove_from_list(victim, min_freq_);
      key_to_slot_.erase(pool_[victim].key);
      slot = victim; // Reuse evicted slot in place!
    } else {
      slot = free_slots_.back();
      free_slots_.pop_back();
      ++size_;
    }

    pool_[slot].key = key;
    pool_[slot].value = value;
    pool_[slot].freq = 1;
    push_front_list(slot, 1);
    key_to_slot_[key] = slot;
    min_freq_ = 1;
  }
};