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

From: "M. Mueller (bhu5nji)" <[email-masked]>
Date: Tue, 12 Feb 2002 06:21:18 -0500

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.

---

From: Tanner Lovelace <[email-masked]>
Date: 12 Feb 2002 16:10:36 -0500

> then the loop must be forcefully aborted.  This is a practical rule only.

Hmm... the Josuttis book says this about erase:

"For vectors and deques, this operation might invalidate iterators and 
reference to other elements."  

Which seems to suggest that iterators of other containers shouldn't
be invalidated.  I wonder if the spec changed this at the last minute?

Hmm... actually looking at the implementation gives some insight,
though.  Apparently, associative containers are implemented using
red-black trees.  RB trees, being balanced, will tend to shift
quite a bit whenever something is inserted or deleted.  That's the
most likely reason why erase invalidates the iterators.

> exercise for the reader.  This reader could use a little help, however.

See above.  For a non-associative container, however, it's a little
bit different.  Lists should have no problem.  iterators should still
work (try it out, if you're curious).  For vectors, however, because
the memory allocation is dynamic, if an insert or erase triggers
an allocation/deallocation in memory, the container could be moved
to a different location, and therefore have all it's iterators
invalidated.

Tanner
-- 
Tanner Lovelace | [email-masked] | http://wtl.wayfarer.org/
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
GPG Fingerprint = A66C 8660 924F 5F8C 71DA  BDD0 CE09 4F8E DE76 39D4
GPG Key can be found at http://wtl.wayfarer.org/lovelace.gpg.asc
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
 Those who are willing to sacrifice essential liberties for a little 
 order, will lose both and deserve neither.  --  Benjamin Franklin 

 History teaches that grave threats to liberty often come in times
 of urgency, when constitutional rights seem too extravagant to 
 endure.  --  Justice Thurgood Marshall, 1989