title: How to implement LFU cache using STL?
body: <p>I'm trying to implement LFU (Least Frequently Used) cache using pure STL (I don't want to use Boost!).</p>
  
  <p>Requirements are:</p>
  
  <ul>
  <li>Associative access to any element using a <code>Key</code> like with <code>std::map</code>.</li>
  <li>Ability to release the lowest priority item (using its <code>UsesCount</code> attribute).</li>
  <li>Ability to update priority (<code>UsesCount</code>) of any item.</li>
  </ul>
  
  <p>The problems are:</p>
  
  <ul>
  <li>If I use <code>std::vector</code> as container of items (<code>Key</code>, <code>Value</code>, <code>UsesCount</code>), <code>std::map</code> as a container of iterators to the vector for associative access and <code>std::make_heap</code>, <code>std::push_heap</code> and <code>std::pop_heap</code> as priority queue implementation within the vector, the itertors in the map are not valid after heap operations.</li>
  <li>If I use <code>std::list</code> (or <code>std::map</code>) instead of <code>std::vector</code> in the previous configuration, <code>std::make_heap</code> etc. can't be compiled becasue their iterators does not support aritmetic.</li>
  <li>If I'd like to use <code>std::priority_queue</code>, I don't have ability to update item priority.</li>
  </ul>
  
  <p>The questions are:</p>
  
  <ul>
  <li>Am I missing something obvious how this problem could be solved?</li>
  <li>Can you point me to some pure C++/STL implementation of LFU cache meeting previous requirements as an example?</li>
  </ul>
  
  <p>Thank you for your insights.</p>