How to filter items from a std::map?

Question

I have roughly the following code. Could this be made nicer or more efficient? Perhaps using std::remove_if? Can you remove items from the map while traversing it? Can we avoid using the temporary map?

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

Solution 1

You could use erase(), but I don't know how BOOST_FOREACH will handle the invalidated iterator. The documentation for map::erase states that only the erased iterator will be invalidated, the others should be OK. Here's how I would restructure the inner loop:

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

Solution 2

A variation of Mark Ransom algorithm but without the need for a temporary.

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

Solution 3

Something that no one ever seems to know is that erase returns a new, guaranteed-to-be-valid iterator, when used on any container.

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

Storing actions.end() is probably not a good plan in this case since iterator stability is not guaranteed, I believe.

Solution 4

If the idea is to remove expired items, why not use map::erase? This way you only have to remove elements you don't need anymore, not rebuild an entire copy with all the elements that you want to keep.

The way you would do this is to save off the iterators pointing to the elements you want to erase, then erase them all after the iteration is over.

Or, you can save off the element that you visited, move to the next element, and then erase the temporary. The loop bounds get messed up in your case though, so you have to fine tune the iteration yourself.

Depending on how expired() is implemented, there may be other better ways. For example if you are keeping track of a timestamp as the key to the map (as expired() implies?), you can do upper_bound on the current timestamp, and all elements in the range [ begin(), upper_bound() ) need to be processed and erased.

View more solutions