Hacker News Reader

Comment by nly | Hacker News Reader

There isn't one. std::list<T> has the same space requirements, memory locality and capabilities of an intrusive list. Period.

The naivety of an 'intrusive' list, where all your objects are always 'list ready', is that it allows the insertion and removal of elements without copying them, which is beneficial if your lists experience a lot of churn. The thing is, you can achieve this without intrusion anyway by keeping all your 'not in a list' items... well, in a list. You then get memory management for free and can use splice()[0] to efficiently move nodes around.

My philosophy on lists is: if you've never used or needed to splice then you probably don't really need a linked list. Splicing is what linked lists are all about.

[0] http://en.cppreference.com/w/cpp/container/list/splice

View on HN

What about modifying the elements while keeping them on multiple lists?

With intrusive list you need only modify any element on a single place (A bullet location as an example).

How could you achieve this with std::list?

I don't know what you mean. How do you keep an object on multiple lists with only one pair of pointers?

That's the point of intrusive lists. You add a pair of pointers for every list the object is in. So when you do your physics pass using the "moving objects" list the value of the bullet is automatically updated in the "renderable objects" list without having to go trough renderable objects separately.

It was explained in the original article "If you want your structure to be in two lists at the same time, you have to add another field: " with an example.

For games and other micro-optimised uses yeah... super-fine control over where you put your pointer pairs with respect to other data members and cache lines could be warranted. If you're optimising at that level then fine, I'd do it (with Boost Intrusive). Otherwise I'd pick up Boost Multi_Index with a couple of 'sequenced' (linked node) or random_access (vector of pointers) indices. This is non-intrusive and has the construction and overhead you want.

I just wanted to spell out that in most use cases intrusion is a sucky trade-off with no benefit.

If you're storing pointers to elements in the list, you only have to change the pointed object.

Then "Less Dereferencing" is not achieved as there are 2 pointer dereferences per access to an element instead of just one, and that goes against the claim "std::list<T> has the same space requirements, memory locality and capabilities of an intrusive list. Period."

I have no idea how to implement something that has same memory locality and capabilities as intrusive list with std::list and that's why I'm asking how it's done. Storing a pointer does not have same memory locality.

OK, then.

I'll give you a pointer to an element and you remove it from all containers that it is currently on, in O(1).

The only way to do that is to keep a bunch of iterators in the item itself, which is virtually identical to the intrusive container model except it involves more pointers, more heap allocations and introduces an extra invariant into the data model (the iterator stored in the item must point at a list that actually contains said item). And the only benefit you get for all this pain and suffering is that you don't have to do any "funny" casting via container_of() contraptions.

Point being is that once data items sit in more than one container, intrusive container model generally results in a simpler code that is also more efficient.

Doesn't std::list<T> generate different code for each type T, at least naively? The generated code could end up taking up more space even if the data structures on which it operates look the same in memory.

Reply on news.ycombinator.com