4 ms·

Standard name for this type of linked list is the "intrusive linked list". There's an implementation for it in boost for c++ and here's another article about it

by rawnlq 12y ago

Standard name for this type of linked list is the "intrusive linked list". There's an implementation for it in boost for c++ and here's another article about it: http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists http://www.codeofhonor.com/blog/avoiding-game-crashes-relate...

deathanatos 12y ago
I don't know if Boost's intrustive containers are necessarily quite the same as an internal linked list. std::list<T> is internal but not intrustive; the difference between the three is something like… external: class Node<T> { Node *next; T *item; } internal: class Node<T> { Node *next; T item; } intrusive: typedef T Node<T>; class <T> { Node *next; // members of T }; (Though I suppose you could consider intrusive a type of internal linked list, and the middle representation is then also a type of internal linked list ("non-intrusive"?).) The intrusive one allows the linked list to avoid memory allocations, and hold objects that are not copy- or move-able. The Boost page has a good table on the differences[1]. I'm actually not sure how much I agree w/ the codeofhorror article. They present the difference between a std::list holding raw pointers and an intrusive list with the title "Avoiding Game Crashes…"; if you want to avoid crashes, std::list<T> or std::list<std::unique_ptr<T>> (or even a shared_ptr, if appropriate); Of course std::list<T*> is error prone! [1]: http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.properties_of_intrusive http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/intr...
Dewie 12y ago
Is storing the elements in-place instead of with a pointer seriously all it takes to be intrusive? I'd have thought that would be par for the course in languages like C/++. Is there something else to it that I'm missing?

by rawnlq 12y ago

deathanatos 12y ago

I don't know if Boost's intrustive containers are necessarily quite the same as an internal linked list. std::list<T> is internal but not intrustive; the difference between the three is something like… external: class Node<T> { Node *next; T *item; } internal: class Node<T> { Node *next; T item; } intrusive: typedef T Node<T>; class <T> { Node *next; // members of T }; (Though I suppose you could consider intrusive a type of internal linked list, and the middle representation is then also a type of internal linked list ("non-intrusive"?).) The intrusive one allows the linked list to avoid memory allocations, and hold objects that are not copy- or move-able. The Boost page has a good table on the differences[1]. I'm actually not sure how much I agree w/ the codeofhorror article. They present the difference between a std::list holding raw pointers and an intrusive list with the title "Avoiding Game Crashes…"; if you want to avoid crashes, std::list<T> or std::list<std::unique_ptr<T>> (or even a shared_ptr, if appropriate); Of course std::list<T*> is error prone! [1]: http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/intrusive_vs_nontrusive.html#intrusive.intrusive_vs_nontrusive.properties_of_intrusive http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive/intr...

Dewie 12y ago

Is storing the elements in-place instead of with a pointer seriously all it takes to be intrusive? I'd have thought that would be par for the course in languages like C/++. Is there something else to it that I'm missing?