Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel