Re: Map iteration and modification

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On 2023-12-29 04:20, Randy Brukardt wrote:
> "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.

Yes, but iterating a map requires ordering regardless properties of the 
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.

It always does sense *IF* enumeration (needed for iteration) is 
provided. Enumeration of pairs (<key>, <value>) is not same as ordering 
values by the keys.

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

No. First, it is two different interfaces. A view of a map as:

1. An ordered set of pairs (<key>, <value>)

2. A mapping <key> -> <value>

Second, the point is that both are array interfaces. The first has 
position as the index, the second has the key as the index.

Both are invariant to removal a pair and any *sane* implementation must 
be OK with that.

The problem is not whether you allocate pairs individually or not. The 
insanity begins with things unrelated to the map:

1. OOP iterator object.

2. FP iteration function.

Both are bad ideas imposed by poor programming paradigms on 
implementation of a clear mathematical concept. That comes with 
constraints, assumptions and limitation array interface do not have.

    for Index in reverse Map'Range loop
       Map.Delete (Index);
    end loop;

would always work. OOP/FP anti-patterns, who knows?

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

Arrays have interface and implementation. The array interface is a 
mapping key -> value, the most fundamental thing in programming. An 
array implementation as a contiguous block of values indexed by a linear 
function is a basic data structure that supports the interface.

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

Let me help (:-))

    One wants array interface without a built-in array implementation.

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

Sure. The problem with Ada is that it does not separate array interface 
from its built-in array implementation and does not separate record 
interface and implementation either.

Both are mappings. BTW in many cases people could prefer record 
interface of a map to array interface:

    Map.Key

instead of

    Map (Key)

Now, tell me that you have a longstanding objection to the entire 
concept of records... (:-))

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de