Re: Map iteration and modification

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

On 2023-12-29 16:03, G.B. wrote:
> On 29.12.23 10:51, Dmitry A. Kazakov wrote:
>> 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.
> 
> Suppose that there is a way of orderly proceeding from one item to the 
> next.
> It is probably known to the implementation of map. Do single steps
> guarantee transitivity, though, so that an algorithm can assume the
> order to be invariable?

An insane implementation can expose random orders each time.

> At the start of the algorithm, the assumption of order of items implies
> an ordered sequence of all the keys.

You do not need ordered keys to enumerate pairs. For example, consider a 
2D array. As a map it has keys (row, column) which are unordered.

> Someone might want to use this known
> order for a cache of "index values". It might be the implementation
> that does so.

If not exposed through an interface the order cannot be known. The 
question is whether there must be such interface or not. In my view a 
good container library must provide position->pair interface, no OOP's 
cursors/iterators and no functional stuff like Foreach.

> Insane? Or just tampering? (Randy Brukardt's example demonstrates
> the mitigation using Cursor, I think.)

Unless removing element invalidates all cursors. Look, insanity has no 
bounds. Cursors AKA pointers are as volatile as positions in certain 
implementations. Consider a garbage collector running after removing a 
pair and shuffling remaining pairs in memory.

> Maybe the bulk operations of some DBMS' programming
> interfaces work just like this, for practical reasons.
> Ada 202x' Ordered_Maps might want to add a feature ;-)
> 
>       procedure Delete (Container : in out Map;
>                         From      : in out Cursor;
>                         To        : in out Cursor);

Here you assume that cursors are ordered and the order is preserved from 
call to call. Even if From and To are stable the range From..To can 
include random pairs in between.

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