priority queue and map

Question

I do LRU cache in my programm. I have:

class DiadocCache : public IDiadocCache<K,T>
        {
        private:
             std::map<K, CacheEntry<T>> values_;
             std::priority_queue<?> timeQueue_;
        }

priority - it is the number of hits on a key in my case.

I put items in the std::map as follows: values_.insert (std :: make_pair (key, CacheEntry (value)));

How i can add elements in priority_queue? And what types must be specified when creating a priority queue? std::priority_queue<?>

Answer 1

LRU can not be implemented with your current DS. you should be using DLL with hashing of each element. you can use list with unordered_hash or map. as in current implementation you can not update the data of priority_queue.