根据插入时间从std :: map中删除元素

我需要根据插入时间（或其他更有效的方式）从std :: map中删除元素。根据插入时间从std :: map中删除元素

该地图可能会包含数千个元素，如果我存储时间并迭代地图以检查每个元素的时间，它可能最终会相当耗时。

有没有人有任何好主意，当他们变老时如何从std :: map中擦除元素？

来源

2012-03-15 theAlse

你可能想看看boost多索引容器 – PlasmaHH 2012-03-15 14:46:44

旧吗？你需要一个明确的标准来执行一个动作，除非你定义了一个动作，Q几乎没有方向性。 – 2012-03-15 14:47:01

@PlasmaHH耶提高本来不会但不可能在这个项目中使用 – theAlse 2012-03-15 14:56:14

std::map<>类型没有插入元素的概念。它仅用于保存键/值对映射。它也没有插入顺序的概念，所以它甚至不能提供相对的插入类型。

要做你想做的事情，你需要在元素和插入时间之间添加一个关联。如果你想要的只是相对的顺序，那么你可以使用与地图配对的std::queue。每当您插入到地图中时，也会插入std::queue。队列前面的元素比后面的元素老，您可以使用相对年龄的元素

来源

2012-03-15 14:47:54 JaredPar

您可以使用队列，并插入指向插入到地图中的对象的指针。队列中的下一个项目将是最早的一个。或者，如果您还需要插入时间，则可以将一对存储在队列中。

来源

2012-03-15 14:47:27 perreal

迭代器可能比指针更有用，但它们都不会受插入和擦除地图的影响： http://stackoverflow.com/a/6438087/5987 – 2012-03-15 16:39:42

非常接近LRU Cache。

Boost.MultiIndex库显示了MRU Cache（最近使用）的示例，因此将其适配为LRU应该是微不足道的。

基本上想法是保持两个并联的数据结构：

一个map与物品
一个deque与引用到地图

Basic代码：

static double const EXPIRY = 3600; // seconds 

std::map<Key, Value> map; 
std::deque<std::pair<std::map<Key, Value>::iterator, time_t>> deque; 

bool insert(Key const& k, Value const& v) { 
    std::pair<std::map<Key, Value>::iterator, bool> result = 
    map.insert(std::make_pair(k, v)); 

    if (result.second) { 
    deque.push_back(std::make_pair(result.first, time())); 
    } 

    return result.second; 
} 

// to be launched periodically 
void clean() { 
    while (not deque.empty() and difftime(time(), deque.front().second) < EXPIRY) { 
    map.erase(deque.front().first); 
    deque.pop_front(); 
    } 
}

当然，那些结构需要b如果意图获取多线程代码，则进行同步。

来源

2012-03-15 15:59:00

非常感谢，我会尝试一个非常好的IDE。 – theAlse 2012-03-16 12:57:32

根据插入时间从std :: map中删除元素

回答

相关问题