29

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); }
Improve this question
0

4 Answers 4

Reset to default
53

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

for(Actions::iterator it = _actions.begin();it != _actions.end();) { if (expired(*it)) { bar(*it); it = _actions.erase(it); } else { ++it; // Use Pre-Increment here as it is more efficient // Because no copy of it is required. } }
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Nicely done. Too bad it took me 2 1/2 years to see this refinement.
@Mark Ransom: That's OK. We can still call it the Mark Ransom technique :-)
Thanks @Mark Ransom and @Martin. So much info in that code. I always wondered why Stroustrup preferred ++i.
As the author of this excellent answer, Loki, said, coppro's answer is correct now.
31

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; }
Improve this answer

2 Comments

Please do not use the solution presented in this (outdated) answer. Its behaviour is container dependent. Since C++11 there is a much better solution: erase returns a new iterator to the element following the erased element. for(auto it = container.begin(); it != container.end(); ) if (to_delete(it)) it = container.erase(it); else ++it;
Correct here: stackoverflow.com/a/263958/14065
8

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.

Improve this answer

9 Comments

According to the documentation I linked in my response, erase returns void, and your code sample won't compile.
This is an extension in VC++, I think
This is not true for any Container, only those that are models of Sequence. For containers that are a model of Associative Container, erase has a return type of void.
Looks like map::erase() will have to return iterator too: open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2728.html#130
With the advent of C++11 this answer is now correct. +1
|
1

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.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.