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

Question

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

该映射表可能会保存数千个元素，如果我存储时间并迭代地图以检查每个元素的时间，那么它可能最终变得非常耗时。

有没有人有好主意如何在std :: map中清除旧元素？

- theAlse

---

你可能想要查看Boost多索引容器。 - PlasmaHH

老手？你需要一个明确的标准来执行一个动作，除非你定义了一个，否则问题就没有方向性。 - Alok Save

@PlasmaHH 嗯，使用 Boost 在这个项目中并非不可能，但是并不合适。 - theAlse

@Alborz：我经常听到这样的话，我想知道是否有人在使用boost... - PlasmaHH

“或者比那更有效率的东西” - 那么，基于插入时间还是其他什么？如果不是基于插入时间，我建议基于成为映射中的第一个元素，这比搜索映射更有效率 ;) - Christian Rau

Answer 1

std::map<>类型没有插入元素时的概念，它只用于保存键值对映射。它也没有插入顺序的概念，因此甚至无法提供相对类型的插入。

如果您想要做的是关联元素和它们插入的时间，那么您需要在元素和它们插入的时间之间建立关联。如果您只想要相对顺序，则可以使用与映射配对的std::queue。每次将元素插入映射中时，也将其插入std::queue中。队列前面的元素比后面的元素旧，您可以使用这个特性来确定它们的相对年龄。

- JaredPar

Answer 2

与LRU Cache相似。

Boost.MultiIndex库展示了MRU Cache（最近最常用），因此将其适应为LRU应该很容易。

基本上，想法是并行维护两个数据结构：

• 一个包含项目的map
• 一个带有对map的引用的deque

基本代码：

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

当然，如果意图是获得多线程代码，则这些结构需要同步。

- Matthieu M.

---

这不应该是 > EXPIRY 吗？ - klaus

@klaus：在我看来是这样的。这个问题已经存在了7年，哎呀！ - Matthieu M.

哈哈！顺便说一下，谢谢你的回答，它帮了我很多 (: - klaus

Answer 3

你可以使用一个队列，在对象插入到映射表时插入对象指针。队列中的下一个项目将是最旧的项目。或者，如果您还需要插入时间，可以在队列中存储一对。

- perreal

---

迭代器可能比指针更有用，但是无论哪种方式都不会受到对映射插入和删除的影响：https://dev59.com/OGw15IYBdhLWcg3wuuGn#6438087 - Mark Ransom