Re^4: Hashes do preserve insertion order after all

memory and time: What I had in mind was the solution of an array in tandem with a hashtable. The array receives items as they are created, and so it keeps the order of insertion. And the hashtable stores data with key to facilitate search-by-key. However deleting by key is not efficient as it needs to search the array too. Introducing more values to the hash (e.g. the corresponding array index) increases memory. Inserting also needs updating 2 data structures.

10 min edit: also deleting from middle of array is inefficient.

Comment on Re^4: Hashes do preserve insertion order after all

Replies are listed 'Best First'.
Re^5: Hashes do preserve insertion order after all by swl (Prior) on Aug 01, 2019 at 08:06 UTC
This is pretty much what Hash::Ordered does, but with tombstoning to reduce the overheads when deleting. See its POD (and code) for details, as well as its benchmarking results.	[reply]
Re^6: Hashes do preserve insertion order after all by LanX (Saint) on Aug 01, 2019 at 11:11 UTC
What a great and deep work. The author didn't only list a bunch of alternatives, but also provided a benchmark module to compare them. I was going to lament that the OO handling breaks with normal hash interface, but he also later added an alternative tie mechanism plus a backdoor with `tied` to access the methods directly! +++ Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply] [d/l]
Re^7: Hashes do preserve insertion order after all by swl (Prior) on Aug 02, 2019 at 00:19 UTC
Yes, his modules are usually pretty good and with thorough documentation. The exceptions tend to be clearly flagged as experimental.	[reply]
Re^5: Hashes do preserve insertion order after all by LanX (Saint) on Aug 01, 2019 at 02:37 UTC
You will always need to update two data structures if you reuse Perl structures. The OP suggested using sort, so how efficient is that without caching the result? Maybe `B-Trees` are better suited here, though this certainly depends on the use case. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]