Re:Don’t blindly prefer emplace_back to push_back
by jpcooper on Thursday March 04, 2021 @06:43AM
(#26341229)
Agreed on linked lists in Haskell if you’re doing forward iteration. You can have lazy byte strings under the bonnet while providing a ‘pure’ linked list interface. No worries about explicit iteration.
* Lazy linked lists are the same thing as iterators, a fact which is used pervasively in Haskell.
* Intrusive or otherwise inline linked lists like are used everywhere, e.g. the DOM has a doubly linked list of children for each node, simple memory pools are often implemented as free lists, and tons of resources inside kernels are members of many linked lists.
* Linked lists are guaranteed O(1) append, but dynamic arrays are only amortized O(1) append. Intrusive linked lists also never need to allocate. That makes them useful inside resource-constrained places.