From mboxrd@z Thu Jan  1 00:00:00 1970
Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Newsgroups: comp.lang.ada
Subject: Re: Map iteration and modification
Date: Tue, 2 Jan 2024 21:57:35 +0100
Organization: A noiseless patient Spider
Message-ID: <un1tbv$2r6uk$1@dont-email.me>
References: <umjukd$9sp$1@rasp.pasdenom.info>
 <umjuvc$9sp$2@rasp.pasdenom.info> <umk6ds$e9hc$1@dont-email.me>
 <umldsq$na79$1@dont-email.me> <umm4r5$ppag$1@dont-email.me>
 <ummn4v$s6gr$1@dont-email.me> <ummtfl$t4uo$1@dont-email.me>
 <umv3nn$2adp0$1@dont-email.me> <umv8rg$2b4on$1@dont-email.me>
 <un1e96$2p2av$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 2 Jan 2024 20:57:35 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="4da79024fa82e70feadccf0f1b74f12b";
	logging-data="2989012"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18h7Y4w11iNauwYYyoMqLLDcm89ujzYnpU="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:U0L/aPj/YuHVN7W334hfAwL6ee4=
In-Reply-To: <un1e96$2p2av$1@dont-email.me>
Content-Language: en-US
Xref: news.eternal-september.org comp.lang.ada:65952
List-Id: <comp.lang.ada>

On 2024-01-02 17:40, G.B. wrote:
> On 01.01.24 21:55, Dmitry A. Kazakov wrote:
> 
>>> Would it not be possible to get these benefits using a different
>>> approach? I think the use case is clearly stated:
>>>
>>> First, find Cursors in map =: C*.
>>> Right after that, Delete from map all nodes referred to by C*.
>>
>> Right. Find cursors, store cursors in another container, iterate that 
>> container deleting elements of the first. Now, consider that the 
>> cursors in the second container become invalid (dangling pointers). If 
>> you wanted to delete them immediately from the second container, you 
>> would return the square one! (:-))
> 
> OK, yet if indicating nodes in a container is designed to survive
> any deletions, leaving nothing dangling i.e., doesn't this limit
> the way in which implementations can store nodes?

Unless the container keeps references to all pointers and corrects them 
as necessary. Which basically defeats the only advantage of pointers. 
They have O(1) complexity in large non-contiguous containers while 
positions without caching are likely O(log(n)).

> Seems like every "pointer" (= (Container, Position)) needs to know
> its element, and/or the container will have to equip its storage
> management with a "vacuuming" algorithm accordingly.
> 
> Transactions seem more flexible (a locking flag in a sequential
> algorithm?), a dedicated operation looks simpler than both.

For large and persistent containers. But that requires a lot of work for 
the client and it is slow and resource consuming on the container side. 
A general-purpose container must be as simple as tooth powder.

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