Sloppy LUR impl

lru_sub_opt.cpp

#include <iostream>
#include <list>
#include <unordered_map>
#include <algorithm>
#include <functional>

using namespace std;

template<typename T>
struct lru {
  struct node {
    T id;
    uint32_t hitcount;
  };

  lru(initializer_list<T> l) {
      for(auto id : l)
        hit(id);
  }

  void hit(T id) {
    // O(1)
    auto target = m_index.find(id);
    if (target == m_index.end()) {
      // O(1)
      m_nodes.push_front(node{id, 1});
      // O(1)
      m_index.insert(make_pair(id, m_nodes.begin()));
    } else {
      node updated = *target->second;
      updated.hitcount++;
      m_nodes.erase(target->second);

      // O(log2(N))
      auto pos = lower_bound(m_nodes.begin(), m_nodes.end(), updated,
                             [](node const &lhs, node const &rhs) {
                               return lhs.hitcount < rhs.hitcount;
                             });
      // O(1)
      target->second = m_nodes.insert(pos, updated);
    }
  }

  uint32_t victim() const {
     auto id = m_nodes.front().id;
     // O(1)
     m_nodes.pop_front();
     // O(1)
     m_index.erase(id);
     return id;
  }

  void print() const {
    for(auto const &n : m_nodes) {
      cout << n.id << ": " << n.hitcount << "\n";
    }
  }

private:
  list<node> m_nodes;
  unordered_map<T, typename list<node>::iterator> m_index;
};

int main() {

  lru<int32_t> cache = { 4, 2, 1, 1, 2, 3, 1, 2, 4 };
  cache.print();
  return 0;
}