CareerCup

Suppose that priority function is given F(c,t), then I would answer like this: We will need four things - an array of elements 'a', a symbol table 'st' (e.g. hash map or tree map) and priority queue 'pq' and a custom mutable class Node.

Now, how to put everything together: (i) Node contains an array index 'i' and priority of an element stored at a[i]. Node is comparable, hence can be comapred with other Node via priority. (ii) The priority queue 'pq' contains these nodes, notice that node with the highest priority is alway at the head. (iii) The map 'st' contains 'key, value' pairs which are an element hash and reference to the node (or a pointer if you will).

Given new element, first check if the element is present in the chache, hence check if the key is present in the map 'st':
a) Existing element
Get corresponding Node reference from 'st' and update its priority.

b) Non-existing element
(i) Dequeue the Node with the highest priority, get index 'i', get element at a[i]
(ii) Remove key (element a[i]) from the 'st'
(iii) Replace a[i] with the new element
(iv) Add new Node with F(c,t) and 'i' into the priority queue
(v) Add element, Node pair into the symbol table 'st'

This is just a general idea but it might work. I am not going to put some code here since it would be too long and not that interesting.

Since t is time elapsed, it is constantly changing, Hence, the F(t, c) will also be ever-changing. So, every time we need to remove an element from cache, we would need to evaluate F(t, c) and get the least and remove that. That makes it O(n).

Instead if t is the timestamp when the element was added, it can be done in O(1) using Priority Queues.

As the previous comment says, timestamps should be used instead of elapsed time.
The timestamp function is strictly increasing, thus a Min Priority Queue is enough to tell us
how to remove elements in O(1).
We also need a hashtable, for storing the data and retrieving it from the outside.

A possible solution (remove() is linear in worst case):

template <typename key_type, typename value_type, uint32_t size_value>
    class CustomLruCache
    {
    public:
        typedef std::function<uint32_t(const time_t &, const uint32_t &)> tKeyFunction;
        
    public:
        CustomLruCache(const tKeyFunction &f)
        : mF(f)
        , mData()
        , mPriorities()
        , mPriorityMap()
        { }
        
        value_type & operator[] (const key_type &key)
        {
            return get(key);
        }
        
        const value_type & operator[] (const key_type &key) const
        {
            return get(key);
        }
        
        void insert(const key_type &key, const value_type &value, const uint32_t cost)
        {
            if (mData.size() == size_value)
                remove();
            
            uint32_t prio = mF(time(nullptr), cost);
            mData[key] = Element(value, cost, prio);
            mPriorities.push(prio);
            mPriorityMap[prio].insert(key);
        }
        
    private:
        struct Element
        {
            value_type value;
            uint32_t cost;
            uint32_t priority;
            
            Element()
            : value()
            , cost(0)
            , priority(0)
            { }
            
            Element(const value_type &value, const uint32_t cost, const uint32_t priority)
            : value(value)
            , cost(cost)
            , priority(priority)
            { }
        };
        
    private:
        value_type & get(const key_type &key)
        {
            auto& el = mData[key];
            mPriorityMap[el.priority].erase(key);
            if (mPriorityMap[el.priority].empty())
                mPriorityMap.erase(el.priority);
            
            el.priority = mF(time(nullptr), el.cost);
            mPriorityMap[el.priority].insert(key);
            return el.value;
        }
        
        void remove()
        {
            while (!mPriorities.empty())
            {
                uint32_t lowestPrio = mPriorities.top();
                auto& keysAtLowestPrio = mPriorityMap[lowestPrio];
                
                if (keysAtLowestPrio.empty())
                {
                    mPriorityMap.erase(lowestPrio);
                    mPriorities.pop();
                    continue;
                }
                
                auto keyIt = keysAtLowestPrio.begin();
                mData.erase(*keyIt);
                
                keysAtLowestPrio.erase(keyIt);
                if (keysAtLowestPrio.empty())
                {
                    mPriorityMap.erase(lowestPrio);
                    mPriorities.pop();
                }
                
                return;
            }
        }
        
    private:
        tKeyFunction mF;
        
        std::unordered_map<key_type, Element> mData;
        std::priority_queue<uint32_t, std::vector<uint32_t>, std::greater<uint32_t>> mPriorities;
        std::unordered_map<uint32_t, std::unordered_set<key_type>> mPriorityMap;
    };

Create a min heap using the function value for the different nodes. Create a hashmap in parallel which contains the page address as key and value as the node pointer of the heap. Whenever a page access is done, the node's function value is updated and we heapify with that node as start point. The nodes with highest value of 'f' will be at the end. During removal, remove the node at the top and insert the last node at the root location and call heapify.

Maintain a heap for each cost so you don't have to keep re-heapifying to figure out which F(t, c) to remove. You'll still have to scan through the heap tops to find the next one to remove. This obviously only works if you have cost categories. If every item has a unique cost then this becomes a list.