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" Newsgroups: comp.lang.ada Subject: Re: Map iteration and modification Date: Fri, 29 Dec 2023 17:52:07 +0100 Organization: A noiseless patient Spider Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 29 Dec 2023 16:52:05 -0000 (UTC) Injection-Info: dont-email.me; posting-host="311365a112cb887017aa9196999f4eee"; logging-data="955352"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/LhccrYWjDsndD3Ml+HnXJEi73Kh0J6ks=" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:Aq+1uAhX56Pvo3keu/97VKXHZHY= Content-Language: en-US In-Reply-To: Xref: news.eternal-september.org comp.lang.ada:65943 List-Id: 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" 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