Как фильтровать элементы с 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

Вы можете использовать erase(), но я не знаю, как BOOST_FOREACH будет обрабатывать недействительный итератор. В documentation for 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 2

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

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

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

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

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

Вариант алгоритма 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. 
    } 
}