←back to thread

Don’t blindly prefer emplace_back to push_back

(quuxplusone.github.io)
178 points todsacerdoti | 1 comments | 04 Mar 21 08:02 UTC | HN request time: 0.001s | source
Show context
jokoon ◴[04 Mar 21 10:40 UTC] No.26340841[source]▶
Thanks for the article, there should be a huge list of those type of classic C++ misconceptions/FAQ style.

One of my favorite is "you don't need a linked list".

Although I'm still genuinely interested when a linked list is best suited. I'm also curious why they were invented and why they're taught, maybe just for teaching purposes...

replies(12): >>26340881 #>>26340918 #>>26340936 #>>26341086 #>>26341090 #>>26341157 #>>26341167 #>>26341203 #>>26341240 #>>26341290 #>>26341787 #>>26347246 #
beaconstudios ◴[04 Mar 21 10:53 UTC] No.26340918[source]▶
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.

replies(3): >>26341133 #>>26341145 #>>26341155 #
1. ywei3410 ◴[04 Mar 21 11:34 UTC] No.26341155[source]▶
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.