Как отфильтровать элементы из 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);
}
Ответы 4
Если идея состоит в том, чтобы удалить просроченные элементы, почему бы не использовать карта :: стереть? Таким образом, вам нужно только удалить элементы, которые вам больше не нужны, а не перестраивать всю копию со всеми элементами, которые вы хотите сохранить.
То, как вы это сделаете, - это сохранить итераторы, указывающие на элементы, которые вы хотите удалить, а затем стереть их все после завершения итерации.
Или вы можете сохранить элемент, который вы посетили, перейти к следующему элементу, а затем стереть временный. Однако в вашем случае границы цикла запутались, поэтому вам нужно самостоятельно настроить итерацию.
В зависимости от того, как реализован expired (), могут быть другие лучшие способы. Например, если вы отслеживаете метку времени в качестве ключа к карте (как подразумевает expired ()?), Вы можете сделать upper_bound для текущей метки времени, и все элементы в диапазоне [begin (), upper_bound ()) должны для обработки и стирания.
Вы можете использовать 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;
}
Кажется, никто никогда не знает, что erase возвращает новый, гарантированно действующий итератор при использовании в любом контейнере.
Actions::iterator it = _actions.begin();
while (it != _actions.end())
{
if (expired(*it))
{
bar(*it);
it = _actions::erase(it);
}
else
++it;
}
Хранение actions.end (), вероятно, не является хорошим планом в этом случае, поскольку я считаю, что стабильность итератора не гарантируется.
Согласно документации, которую я привел в своем ответе, erase возвращает void, и ваш образец кода не компилируется.
Думаю, это расширение на VC++.
Это не верно для любого Контейнера, только для тех, которые являются моделями Последовательности. Для контейнеров, которые являются моделью ассоциативного контейнера, тип возврата erase имеет значение void.
Как насчет this vector :: erase doc? Он четко говорит, что у него есть итератор возврата erase (). Ничего не говорится о том, что это расширение MS.
@Marcin, стирание std :: vector возвращает итератор. Но это обсуждение std :: map. У которого есть стирание, которое возвращает пустоту.
Похоже, map :: erase () тоже должен вернуть итератор: open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2728.html#130
VC2013 std :: map :: erase возвращает итератор ..
С появлением C++ 11 этот ответ теперь верен. +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.
}
}
Отлично сделано. Жаль, что мне потребовалось два с половиной года, чтобы увидеть это усовершенствование.
@Mark Ransom: Ничего страшного. Мы все еще можем назвать его Mark Ransom technique :-)
Спасибо @Mark Ransom и @Martin. Так много информации в этом коде. Мне всегда было интересно, почему Страуструп предпочитает ++ i.
Пожалуйста, не используйте решение, представленное в этом (устаревшем) ответе. Его поведение зависит от контейнера. Начиная с C++ 11 существует гораздо лучшее решение: erase возвращает новый итератор элементу, следующему за удаленным элементом.
for(auto it = container.begin(); it != container.end(); ) if (to_delete(it)) it = container.erase(it); else ++it;