c++ container allowing you to sort items by when they where last accessed?

Question

Does such a thing exist? or could anyone please recommend how I could implement such a container?

basically I have a std::map which uses a 64bit integer as its key and a custom datatype as the containing item.

I need to be able to periodically remove items that havent been accessed in a while in the most optimal way. does anyone have any suggestions for this?

cheers

Answer 1

Use a priority queue that places the least-recently-used (LRU) item at the head of the queue. When an item is accessed, remove it and re-insert it against the current timestamp. When you want to expire items, simply remove them from the head of the queue.

I should point out that you can't use the standard priority_queue, since that doesn't support random removal. You'll have to use the heap functions in conjunction with a vector.

I should also point out that updating an item on access will be expensive (O(N) to find the element to remove).

EDIT: Please disregard this answer. On rethinking, it isn't the best way to do it. (Also, see comments.)

Answer 2

Here is a sketch of how it might be done, using a list to store the most recently accessed items in order. The list is updated in constant time, so there is no significant overhead above the map access (unlike some other answers which require a linear search on each access). I've kept the interface very basic, and haven't tested it very thoroughly.

template <typename KEY, typename VALUE>
class Container
{
public:
    void Set(const KEY& key, const VALUE& value)
    {
        typename Map::iterator it = map.find(key);
        if (it == map.end())
        {
            list.push_front(it);
            it = map.insert(std::make_pair(key, std::make_pair(value, list.begin()))).first;
            list.front() = it;
        }
        else
        {
            it->second.first = value;
            Accessed(it);
        }
    }

    const VALUE* Get(const KEY& key)
    {
        typename Map::iterator it = map.find(key);
        if (it == map.end())
            return 0;

        Accessed(it);
        return &it->second.first;
    }

    void Expire(std::size_t new_size)
    {
        while (list.size() > new_size)
        {
            map.erase(list.back());
            list.pop_back();
        }
    }

private:
    // Needed to resolve the semicircular dependency on nested iterator types.
    struct MapIterator;

    typedef std::list<MapIterator> List;
    typedef std::map<KEY, std::pair<VALUE, typename List::iterator> > Map;

    struct MapIterator : Map::iterator
    {
        MapIterator(const typename Map::iterator& it) : Map::iterator(it) {}
    };

    void Accessed(typename Map::iterator it)
    {
        list.erase(it->second.second);
        list.push_front(it);
        it->second.second = list.begin();
    }

    Map map;
    List list;
};