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.

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.

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}