Как фильтровать элементы с std:: map?

У меня примерно следующий код. Может ли это сделать лучше или эффективнее? Возможно, используя 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);
}

Ответы

Ответ 1

Вы можете использовать erase(), но я не знаю, как 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;
}

Ответ 2

Вариант алгоритма Mark Ransom, но без необходимости временного.

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

Ответ 3

Если идея состоит в том, чтобы удалить истекшие элементы, почему бы не использовать map:: erase? Таким образом вам нужно только удалить элементы, которые вам больше не нужны, а не перестраивать всю копию со всеми элементами, которые вы хотите сохранить.

То, как вы это сделаете, - это сохранить итераторы, указывающие на элементы, которые вы хотите удалить, и затем удалить их после окончания итерации.

Или вы можете сэкономить элемент, который вы посетили, перейти к следующему элементу и затем удалить временный. Границы цикла перепутаны в вашем случае, так что вы должны точно настроить итерацию самостоятельно.

В зависимости от того, как истек срок действия(), могут быть и другие способы. Например, если вы отслеживаете временную метку в качестве ключа к карте (как указано в expired()?), Вы можете сделать upper_bound в текущей временной отметке, и все элементы в диапазоне [begin(), upper_bound()) нуждаются в для обработки и стирания.

Ответ 4

Что-то, о чем никто никогда не узнает, - это то, что erase возвращает новый, гарантированный к действию итератор при использовании в любом контейнере.

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

Сохранение actions.end(), вероятно, не является хорошим планом в этом случае, так как стабильность итератора не гарантируется, я считаю.