3 ms·
>I'd love to know how many different implementations of a linked list in C++ exist in the wild today. Why isn't the STL linked list enough?
by andrepd 11y ago
>I'd love to know how many different implementations of a linked list in C++ exist in the wild today.
Why isn't the STL linked list enough?
- AnimalMuppet 11y agoNIH syndrome. Some company thinks that they can do better than the STL, or that it doesn't meet their needs, or that they have a bunch of legacy code that was written before the STL and they have to maintain compatibility, or that they're a bunch of special snowflakes that deserve to have their own, or whatever. So they write their own, even though the STL is just fine.
- amyjess 11y agoBecause a lot of C++ code predates the STL (or at least the STL being made available for whatever compiler they use).
- deleted 11y ago[deleted]
- bkjelden 11y agoA combination of code that predates the STL and a fear in taking a dependency on things you can't change. (Both should be irrelevant in a new code base, but most large C++ codebases are pretty old)
- ludamad 11y agoSometimes intrusive linked lists are more efficient and require less cleanup
- nly 11y agoWith an intrusive linked list you pay the memory cost of having node pointers all the time. If you're you're going to do that, then you may as well keep all your nodes in a list all the time, and use splice() to move them around. There are practically no performance advantages to using intrusive linked-lists in this case.
- comex 11y agoThere is a usability advantage, though: with a STL list, you need an iterator corresponding to an element to move it between lists, not just a pointer to the value. So all functions taking a reference to an object, if they might want to move it around at some point, need to take an iterator, and in particular, object methods cannot do so, unless the class contains a wasteful iterator-to-self field. Intrusive lists also allow an object to be in multiple lists at the same time (usually ones with different purposes) by having multiple sets of prev/next pointers.
- nly 11y agoBoost multi_index solves both of these problems. To simulate multiple lists you can simply add more than one sequenced index to the container type. The sequenced index interface provides an iterator_to() method which takes a reference and returns an iterator, and the container interface allows you to project one index to another. It's incredibly powerful. http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/seq_indices.html http://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/re... As a bonus the ownership semantics are clear and memory management remains trivial. Intrusive lists are useful, i'll grant you, but they'll always be a last resort for me. Especially if you're implementing them yourself.