Simple lru cache cpp implementation

#include <cstdio>
#include <cassert>
#include <list>
#include <map>

class Cache {
public:
  Cache(int cap) {
    cap_ = cap;
  }
  int get(int key) {
    if(map_.find(key) != map_.end()) {
      int value = map_[key]->second;
      moveToFront(key, value);
      return value;
    }
    return -1;

  }

  void put(int key, int val) {
    if(map_.find(key) != map_.end()) {
      moveToFront(key, val);
      return;
    }
    if(items_.size() == cap_) {
      // remove the tail key from list and map
      int tail_key = items_.back().second;
      auto tail_key_iter = map_[tail_key]; 
      // does the order matter?
      map_.erase(tail_key);
      // items_.erase(tail_key_iter);
      items_.pop_back();
    }
    items_.push_front(std::make_pair(key, val));
    map_[key] = items_.begin();
  }

private:
  void moveToFront(int key, int val) {
    items_.erase(map_[key]);
    items_.push_front(std::make_pair(key, val));
    // map_.insert(std::make_pair(key, items_.begin()));
    map_[key] = items_.begin();
  }
  int cap_;
  std::list<std::pair<int, int>> items_;
  std::map<int, std::list<std::pair<int, int>>::iterator> map_;
};
int main() {
  auto cache =   Cache(3);
  cache.put(1, 1 );
  cache.put(2, 2 );
  cache.put(3, 3);
  assert(cache.get(1) == 1);
  assert(cache.get(2) == 2);
  assert(cache.get(3) == 3);

  cache.put(4, 4);
  assert(cache.get(1) == -1);

  assert(cache.get(2) == 2);
  cache.put(5, 5);
  assert(cache.get(3) == -1);
  printf("OK\n");

}

LRUCache::LRUCache(size_t capacity, int num_shard_bits,
                   bool strict_capacity_limit, double high_pri_pool_ratio,
                   double low_pri_pool_ratio,
                   std::shared_ptr<MemoryAllocator> allocator,
                   bool use_adaptive_mutex,
                   CacheMetadataChargePolicy metadata_charge_policy,
                   std::shared_ptr<SecondaryCache> _secondary_cache)
    : ShardedCache(capacity, num_shard_bits, strict_capacity_limit,
                   std::move(allocator)),
      secondary_cache_(std::move(_secondary_cache)) {
  size_t per_shard = GetPerShardCapacity();
  SecondaryCache* secondary_cache = secondary_cache_.get();
  MemoryAllocator* alloc = memory_allocator();
  InitShards([=](LRUCacheShard* cs) {
    new (cs) LRUCacheShard(
        per_shard, strict_capacity_limit, high_pri_pool_ratio,
        low_pri_pool_ratio, use_adaptive_mutex, metadata_charge_policy,
        /* max_upper_hash_bits */ 32 - num_shard_bits, alloc, secondary_cache);
  });
}

Status LRUCacheShard::Insert(const Slice& key, uint32_t hash,
                             Cache::ObjectPtr value,
                             const Cache::CacheItemHelper* helper,
                             size_t charge, LRUHandle** handle,
                             Cache::Priority priority) {
  assert(helper);

  // Allocate the memory here outside of the mutex.
  // If the cache is full, we'll have to release it.
  // It shouldn't happen very often though.
  LRUHandle* e =
      static_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));

  e->value = value;
  e->m_flags = 0;
  e->im_flags = 0;
  e->helper = helper;
  e->key_length = key.size();
  e->hash = hash;
  e->refs = 0;
  e->next = e->prev = nullptr;
  e->SetInCache(true);
  e->SetPriority(priority);
  memcpy(e->key_data, key.data(), key.size());
  e->CalcTotalCharge(charge, metadata_charge_policy_);

  // value == nullptr is reserved for indicating failure for when secondary
  // cache compatible
  assert(!(e->IsSecondaryCacheCompatible() && value == nullptr));

  return InsertItem(e, handle, /* free_handle_on_fail */ true);
}

Status LRUCacheShard::InsertItem(LRUHandle* e, LRUHandle** handle,
                                 bool free_handle_on_fail) {
  Status s = Status::OK();
  autovector<LRUHandle*> last_reference_list;

  {
    DMutexLock l(mutex_);

    // Free the space following strict LRU policy until enough space
    // is freed or the lru list is empty.
    EvictFromLRU(e->total_charge, &last_reference_list);

    if ((usage_ + e->total_charge) > capacity_ &&
        (strict_capacity_limit_ || handle == nullptr)) {
      e->SetInCache(false);
      if (handle == nullptr) {
        // Don't insert the entry but still return ok, as if the entry inserted
        // into cache and get evicted immediately.
        last_reference_list.push_back(e);
      } else {
        if (free_handle_on_fail) {
          free(e);
          *handle = nullptr;
        }
        s = Status::MemoryLimit("Insert failed due to LRU cache being full.");
      }
    } else {
      // Insert into the cache. Note that the cache might get larger than its
      // capacity if not enough space was freed up.
      LRUHandle* old = table_.Insert(e);
      usage_ += e->total_charge;
      if (old != nullptr) {
        s = Status::OkOverwritten();
        assert(old->InCache());
        old->SetInCache(false);
        if (!old->HasRefs()) {
          // old is on LRU because it's in cache and its reference count is 0.
          LRU_Remove(old);
          assert(usage_ >= old->total_charge);
          usage_ -= old->total_charge;
          last_reference_list.push_back(old);
        }
      }
      if (handle == nullptr) {
        LRU_Insert(e);
      } else {
        // If caller already holds a ref, no need to take one here.
        if (!e->HasRefs()) {
          e->Ref();
        }
        *handle = e;
      }
    }
  }

  TryInsertIntoSecondaryCache(last_reference_list);

  return s;
}