[Dev] Pruning elements from sorted associative sequence containers (set, multiset, map, multimap)

[M. Mueller (bhu5nji)]

By trial and error and head banging I learned that pruning elements from 
sequence containers needs extra care.

My application (as before) is to keep transaction state information in a map 
where the key is the transaction ID and the entry is a struct with 
transaction related information, including a field called xState (transaction 
state).

It belongs to a system that is a single process daemon that manages multiple 
concurrent transactions from many clients.  It has three independent stages: 
transaction origination, transaction operation, transaction completion.

The transaction map is filled by origination and emptied by completion.  To 
operations, the map is a todo list.  The rate of growth, both positive and 
negative, in origination and completion are independent from a design 
perspective.  I can have 1 origination and 2 completions in a single main 
loop iteration.

In the completion stage the map is examined, element-by-element, looking for 
xState == XS_COMPLETE.  When such an element is found, the element is 
removed, or pruned, from the map.  This is where the learning occurred.

What I learned was tested on a map but I suspect the lesson applies to all of 
the sorted associative sequence containers (set, multiset, map, multimap).

Flawed code

{
	map<uint32_t, t_xAct>::iterator i;
	for (i = xMap.begin(); i != xMap.end(); i++) // endless loop
	{
		if (i->second.xState == XS_COMPLETE)
		{
			// completion duties
			xMap.erase(i); // disturbs loop guard
		}
	}
}

Code that appears to work:

{
	map<uint32_t, t_xAct>::iterator i;
TOP:
	for (i = xMap.begin(); i != xMap.end(); i++)
	{
		if (i->second.xState == XS_COMPLETE)
		{
			// completion duties
			xMap.erase(i); // disturbs loop guard
			goto TOP: // start search over again
		}
	}
}

I am not concerned about the "goto".  I could work around not using it.  It 
provides a concise way to demonstrate what I learned.

What I learned is that a container size must remain constant when an iterator 
is being used in a loop guard condition.  If this rule cannot be followed, 
then the loop must be forcefully aborted.  This is a practical rule only.

The Musser 2nd Ed. book has no example AFAIK showing the potential flaw and a 
work around.  The only hint is in Section 21.1.5 Sorted Associative Container 
Requirements on page 326 where it states,

"Finally, an *iterator* of a sorted associative container is bidirectional. 
The *insert* operations do not affect the validity of the iterators and 
references to the container, and *erase* operations invalidate only iterators 
and references to the erased elements."

It appears that the reason that *erase* invalidates iterators is left as an 
exercise for the reader.  This reader could use a little help, however.

----------------------

What seems to be missing from my library is a book filled with non-trivial 
examples from mixed applications - IT, communications, control, math, etc.  I 
am going to make it a point to read every single Josutiss example.  Then I'm 
going to the local bookeries to have another look at what's available.

So far, STL has been a bit of a struggle.  First I had the *for_each* 
questions then the *a.erase(i)* difficulties.  I believe the struggle is  
worthwhile.

Thanks for all the help.

Mike M.