c ++容器允许您按上次访问的位置对项目进行排序？

Question

这样的事情存在吗？或者有人可以建议我如何实施这样的容器？

基本上我有一个std :: map,它使用64位整数作为键,自定义数据类型作为包含项.

我需要能够以最佳方式定期删除一段时间内未访问过的项目.有没有人对此有任何建议？

干杯

Answer 1

使用优先级队列将最近最少使用(LRU)项放在队列的头部.访问项目时,将其删除并重新插入当前时间戳.如果要使项目过期,只需将它们从队列的头部删除即可.

我应该指出你不能使用标准priority_queue,因为那不支持随机删除.您必须将堆函数与向量结合使用.

我还应该指出,更新访问项目将是昂贵的(O(N)找到要删除的元素).

编辑:请忽略这个答案.重新思考,这不是最好的方法.(另外,请参阅评论.)

Answer 2

下面是一个如何完成的草图,使用列表按顺序存储最近访问的项目.该列表在固定时间内更新,因此在地图访问之上没有明显的开销(与其他需要在每次访问时进行线性搜索的其他答案不同).我保持界面非常基本,并没有彻底测试它.

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;
};

Answer 3

一个想法：维护一个std::deque，每当访问地图时，它都会将迭代器放入推到前面的地图元素中。然后，您可以轻松查看双端队列以了解最近使用过哪些元素。

一些 C++ 草图（没有错误检查，重点是演示双端队列在访问地图时更新，并且您可以稍后修剪地图）。

class MyMap {
  typedef std::map<int64_t, void *> Map;
  Map m_map;
  std::deque<Map::iterator> m_recentlyUsedItems;

public:
  void *getItem( int64_t key ) {
    Map::iterator it = m_map.find( key );
    if ( it == m_map.end() ) {
      return 0;
    }
    m_recentlyUsedItems.push_front( it );
    return it->second;
  }

  void removeAllButMostRecentlyUsedItems( int n ) {
    std::deque<Map::iterator> it = m_recentlyUsedItems.begin();
    advance( it, n );
    std::deque<Map::iterator> it2 = it;
    for ( ; it2 != m_recentlyUsedItems.end(); ++it2 ) {
      m_map.erase( *it2 );
    }
    m_recentlyUsedItems.erase( it, m_recentlyUsedItems.end() );
  }
};