如何从 std::map 过滤项目？

Question

我大致有以下代码。 这可以做得更好或更有效吗？ 也许使用 std::remove_if ？ 您可以在遍历地图时从地图上删除项目吗？ 我们可以避免使用临时地图吗？

typedef std::map<Action, What> Actions;
static Actions _actions;

bool expired(const Actions::value_type &action)
{
  return <something>;
}

void bar(const Actions::value_type &action)
{
  // do some stuff
}

void foo()
{
  // loop the actions finding expired items
  Actions actions;
  BOOST_FOREACH(Actions::value_type &action, _actions)
  {
    if (expired(action))
      bar(action);
    else
      actions[action.first]=action.second;
    }
  }
  actions.swap(_actions);
}

Answer 1

马克勒索算法的变体，但不需要临时。

for(Actions::iterator it = _actions.begin();it != _actions.end();)
{
    if (expired(*it))
    {
        bar(*it);
        _actions.erase(it++);  // Note the post increment here.
                               // This increments 'it' and returns a copy of
                               // the original 'it' to be used by erase()
    }
    else
    {
        ++it;  // Use Pre-Increment here as it is more effecient
               // Because no copy of it is required.
    }
}

Answer 2

您可以使用擦除（），但我不知道 BOOST_FOREACH 将如何处理无效的迭代器。 map::erase 的文档 指出只有被擦除的迭代器才会被失效了，其他应该没问题。 以下是我如何重构内部循环：

Actions::iterator it = _actions.begin();
while (it != _actions.end())
{
  if (expired(*it))
  {
    bar(*it);
    Actions::iterator toerase = it;
    ++it;
    _actions.erase(toerase);
  }
  else
    ++it;
}

Answer 3

似乎没有人知道的一件事是，当在任何容器上使用时，擦除都会返回一个新的、保证有效的迭代器。

Actions::iterator it = _actions.begin();
while (it != _actions.end())
{
  if (expired(*it))
  {
    bar(*it);
    it = _actions::erase(it);
  }
  else
    ++it;
}

在这种情况下，存储 actions.end() 可能不是一个好的计划，因为我相信迭代器的稳定性无法得到保证。

Answer 4

如果想法是删除过期的项目，为什么不使用 map::erase? 这样，您只需删除不再需要的元素，而不必使用您想要保留的所有元素重建整个副本。

执行此操作的方法是保存指向要擦除的元素的迭代器，然后在迭代结束后将它们全部擦除。

或者，您可以保存访问过的元素，移至下一个元素，然后删除临时元素。 不过，在您的情况下，循环边界会变得混乱，因此您必须自己微调迭代。

根据expired()的实现方式，可能还有其他更好的方法。 例如，如果您正在跟踪时间戳作为映射的键（正如expired()暗示的那样？），您可以对当前时间戳执行upper_bound，并且范围[begin(), upper_bound())中的所有元素都需要进行处理和擦除。