C++: reference to unordered_map entry for deletion

C++: reference to unordered_map entry for deletion

I want to write a Cache with O(1) insert, O(1) retrieve which sets an
upper limit on the number of entries. The least recently accessed entry
shall be discarded before an insertion when the upper limit was already
reached.
My idea was to implement this based on an unordered map. To set an upper
limit on the number of cache entries, the entries will be intrusively
doubly linked inside the unordered map (the most recently linked at the
end of the list).
template<typename V>
struct CacheEntry {
V val;
CacheEntry<V> *prev
CacheEntry<V> *next;
HandleType h; // to be explained
}
template<typename K, typename V, ...>
struct Cache {
unordered_map<K, CacheEntry<V>, ...> umap_;
CacheEntry *first;
CacheEntry *last;
public:
interface similar to implement unordered_map + cache management
}
When I insert a new item into a full cache, the least recently used item
(referenced by the first pointer) shall be discarded from the cache. This
means I need to get a handle to the item which can be used to delete the
item from the map (HandleType above).
It seems to me that there a basically two things HandleType could be:
The original key, but this is potentially a waste of space or computing
cycles.
An iterator, but those are invalidated when the table is rehashed.
Possible amendment 1: Is it possible to obtain a cheaper representation of
the key (a reference to the Key stored in the implementation of the
unordered_map. Or a tuple (key reference, key hash))?
Possible amendment 2: Does the standard guarantee that there won't be
rehashes if I manually limit the size of the unordered_map to a fixed
number N, do a reserve(N) and a max_load_factor(1.0)?
Any other suggestions for implementing a cache?