On: Malloc broke Serenity's JPGLoader, or: how to win ...

[layer8]

> How do you preserve insertion order in a hash map?

You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely critical in practice. It can be made more efficient if the hash map doesn’t need to support deletion.

[Sesse__ → layer8]

> The overhead is rarely critical in practice.

Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.

[layer8 → Sesse__]

I repeat: This is rarely critical in practice. Of course there are cases where it becomes critical, but it’s a perfectly good default.

[thinkharderdev → layer8]

Ah yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)