[purplesyringa]

Ah yes, the most reliable solution to a wrong choice of a data structure: add data-specific hacks until it works. For the life of me I can't figure out why people never consider replacing linked lists. Even without worst-case O(n) insertion, they usually behave worse than vectors, deques, or hives.

[xigoi]

What is a hive in the context of data structures?

[purplesyringa]

I meant something close to https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p04...

Perhaps a simple way to look at it is that it's like a dynamic array, but when the capacity is exceeded, you don't reallocate the array, just just allocate a new (exponentially larger) chunk and keep the old one as-is. Then just link the chunks in a (very short) linked list, or keep a separate small list of chunks (you're never gonna need more than 48, so you can just have a fixed allocation for it), or what have you. The bonus here is that it reduces latency on pushing and has more predictable performance.

[masklinn]

I assume it's an autocorrect of heap.

[mjevans]

There's also the choice of data structure that appears to force multiple copies of the same thing rather than thin references and ideally copy on modify.