4 ms·
100% agree. It almost feels insulting to say that C++ programmer will only use std::list and a C programmer will only use a hand made doubly linked list. This
by icefox 14y ago
100% agree. It almost feels insulting to say that C++ programmer will only use std::list and a C programmer will only use a hand made doubly linked list. This almost feels like an interview question:
> Which is faster and uses less memory? A generic double linked list or a hand made double linked list?
This is a data structure, optimization, software development problem. The reason we use any 3rd party generic (in C OR C++) doubly linked list is because it helps code the problem faster. Any time you use a component you need to be aware of its overhead. After profiling my C++ code if I found that the std::list was taking up all my memory and all my cpu time I would then evaluate the algorithms I am using and pick the data structure that best fits that be that a custom link list or something else such as the above mentioned boost library.
You even have to nitpick the example about erase being expensive. When using std::list why isn't the code passing around the iterators rather than the person object? And for the memory of std::list overhead why didn't he use std::list<person>?
There is no problem using a hand made C style doubly link list in your C++ code for the core part of your application for performance reasons. Being a C++ program doesn't mean you can't use C style code or even have asm snippets. Following the same logic as the blog ZeroMQ should have been written in ASM and not C because it could have been faster, or the reverse it should have been written in Ruby because it would have been coded in a quarter of the time (but at the trade of slower runtime)
As for the conclusion I would say that the inefficiency is still in ZeroMQ code as the author doesn't fully understand C++.
- rumcajz 14y agoWhy not pass iterators? Consider the case where the object is contained in two lists. You would have to pass a pair of iterators. What if it is in 3 lists? Etc.
- icefox 14y agoAgreed, but for the example the object only needs to live in one list (as shown by the fact that it could have been a C struct that contained the next/prev pointers) so passing iterator would have been sufficient and would have solved the O(n) problem(s?) he was having.
- dkersten 14y agoExactly, the C example could not be contained in more than one list at a time, so if this is a concern, the C solution wouldn't work either.