4 ms·
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 peop
by purplesyringa 2y ago
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.
- mjevans 2y agoThere'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.
- xigoi 2y agoWhat is a hive in the context of data structures?
- masklinn 2y agoI assume it's an autocorrect of heap.
- purplesyringa 2y agoI meant something close to https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r15.html 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.