3 ms·
I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only a
by DSMan195276 6y ago
I think your typical template-based list is actually a bad example :P Maybe there's something about C++ I don't know, but typically those implementations only allow for adding one list node (via the template wrapping), and also they can't usually take an element from one list and then attach it to another one. Where-as intrusive implementations like the Linux Kernel's allow for any number of list nodes or other data structures to be placed alongside the data, and the elements can be moved onto any list you want without any allocations necessary.
- gpderetta 6y agostd::list has splice to move nodes between lists. boost.intrusive does, among other things, provide true intrusive lists and, for example, can insert the same node on multiple containers (not just lists) at the same time. But really, no need for boost.intrusive, writing a templated intrusive list is not hard.
- DSMan195276 6y agoOnce you do that though (use a "true" intrusive implementation), you typically lose the "keep the list structure out of your data" aspect. std::list allows you to avoid that, but carries its own limitations that embedding the list structures into the data does not. Don't get me wrong, I'm not saying one is better or worse, just that containers like std::list aren't better for every use-case you might have compared to an intrusive implementation. Perhaps I just misunderstood your "have your cake in eat it too" remark though.