[mahouse]

I am somewhat confused by this article since to me it sounds like the writer has wanted the reader to think intrusive lists are "trickier and weird", when they have been my bread and butter during all my C work... And I guess I am not alone.

[magoghm]

You're not alone. I spent almost 20 years programming with intrusive lists before I ever heard about non-intrusive lists. Of course, they weren't known as "intrusive lists", everybody called them "linked lists".

[simias]

They are trickier though because you either have to create a new type for each list and all all accompanying functions to work on that type (the PointListNode in the article) or you can make it more generic by discarding type safety and using tricks like "container_of" (that's actually my preferred approach when writing C, at least it lets me use the linux kernel's list.h and I don't have to reinvent the wheel).

In C you don't have much of a choice to make a generic container but in C++ the templated std::list is much safer.

I'm a bit wary of that article to be honest, it's interesting but it oversells the intrusive list a bit IMO and I can definitely imagine inexperienced C++ coders deciding to use intrusive lists instead of the STL because of it. But at any rate that would be very premature optimization in my book. Even if intrusive lists happen to be faster in a certain use case (and I'd like to see benchmarks before I believe it) I'd feel much more comfortable using std::list while developing/debugging.

[dietrichepp]

The problem with std::list is that it's almost always worse than the alternatives. I would recommend using std::vector as the "default" container, and then use another container if the performance of std::vector is not good enough. Or, put another way, I think std::list is a premature optimization, because you are saying that insertions and deletions are frequent enough that you need them to be O(1), even at the expense of extra memory usage and tons of cache misses for simple traversal.

The std::vector container will outperform std::list surprisingly often. Just think of std::vector as your default container.

[bane]

Yeah, I was expecting some secret magic and it was just a basic linked-list like was used to weed out incoming freshman at my university who couldn't understand pointers.

[dbattaglia]

I think they are more likely to feel "tricky and weird" when coming from a higher level language like c++ or Java that has linked list data structures in their standard library.

[thechao]

Higher- or lower- level domains, I feel, would be more accurate; when I code my c-with-templates embedded code there's no STL, so I'm quite aware of intrusive containers, even though I rarely code straight-C. My favorite variant is multiply-included linked lists---which I've seen in a number of one-off embedded JITs.