Re: Map iteration and modification

["Randy Brukardt" <randy@rrsoftware.com>]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:umk6ds$e9hc$1@dont-email.me...
...
> Provided a sane implementation of map.
>
> 1. It is safe to loop over the map items in the *reverse* order of, 
> deleting whatever items.

A sane implementation of a map does not have/require an ordering of keys. So 
the idea of "reverse" or "forward" does not make sense for a general map. 
(There are, of course, special cases where the keys have an order that 
matters to the map; the standard ordered map is like that.) Assuming an 
ordering is exposing the implementation unnecessarily.

You always complain about mixing implementation with interface, but you are 
clearly doing that here. That technique really only works if the data 
structure is implemented with an underlying array. If you have separately 
allocated nodes, deletion might completely destroy a node that the iterator 
is holding onto. Avoiding that takes significant efforts that sap 
performance when you don't intend to modify the container you're iterating 
(which is the usual case).

My longstanding objection to the entire concept of arrays is that they are 
not a data structure, but rather a building block for making data 
structures. One wants indexed sequences sometimes, cheap maps othertimes, 
but arrays have all of the operations needed for both, along with other 
capabilities not really related to data structures at all. It's way better 
to declare what you need and get no more (visibly, at least). That makes it 
way easier to swap implementations if that becomes necessary - you're not 
stuck with a large array that really should be managed piecemeal.

                   Randy.