How to implement LFU cache using STL?

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.