Don’t blindly prefer emplace_back to push_back

Re:Don’t blindly prefer emplace_back to push_back by beaconstudios on Thursday March 04, 2021 @05:53AM (#26340918)

Naively, I would assume that LLs are best used for long lists which are typically traversed incrementally, like a FILO-only job queue. That wouldn't perform better than a static array of statically-sized objects, but it could be better for eg. a list of structs with flexible array members (ie, variable-sized structs).

They might be good for traversed lists with the possibility of partway insertion too, or performing insertion sort. Hell they might even be good for traversed lists in the general case, but I'm not a low level dev so I don't know without testing it.

Fun exercise though!

I'm guessing they're taught because they're taught, in that special inertial way that education propagates. Originally, I bet they were introduced when implementing your own data structures rather than pulling a library was normal industry practice.

Of course there is tons of value in knowing about data structures and their characteristics, but probably not in knowing how to implement LLs.

[ Parent | on HN ]

Re:Don’t blindly prefer emplace_back to push_back by ywei3410 on Thursday March 04, 2021 @06:34AM (#26341155)

They're also an example of a data-structure which works pretty in a concurrent setting - you can get away with a single atomic reference for an unbounded FILO queue implemented with a linked list. Adding and removing items to it is then dirt-cheap - provided you don't go through the queue quickly and job running time > iteration time.

But with all things in computer science, it really depends on your use-case.

[ Parent | on HN ]

Re:Don’t blindly prefer emplace_back to push_back by gmueckl on Thursday March 04, 2021 @06:31AM (#26341133)

Even if linked lists and double linked lists aren't all that universally useful by themselves, they teach all the basics about taversing data structures by references / pointers that more complex trees and graphs require. A linked list is just a degenerate tree with at most one child for each parent. So I think teaching that isn't a bad decision.

[ Parent | on HN ]

Re:Don’t blindly prefer emplace_back to push_back by dmurray on Thursday March 04, 2021 @06:33AM (#26341153)

I couldn't have said it better :)

[ Parent | on HN ]

Re:Don’t blindly prefer emplace_back to push_back by beaconstudios on Thursday March 04, 2021 @06:37AM (#26341172)

good point, they may still be useful as a pedagogical tool to introduce pointer-based structures.

[ Parent | on HN ]

Re:Don’t blindly prefer emplace_back to push_back by dmurray on Thursday March 04, 2021 @06:33AM (#26341145)

Everyone would probably agree it's good to teach trees in a CS data structures class. Linked lists make a nice introduction to this: what is a linked list except a tree with max branching factor 1? So you teach LLs on day one, and introduce in the simplest useful way the idea of a recursive data structure.

[ Parent | on HN ]