It's nice to be able to have productive discussion on the internet!
We can agree on almost all points, I think.
The CS 101 bit you mention is a good point: intrusiveness matters for asymptotics in CS, and should be taught in academia, not (very small portions of) industry.
By the way, when you mention "a vector whose elements are linked list heads", a much more typical scenario is an array/vector whose elements contain one or more list heads.
You were wondering about the kinds of software I was working on that needs this stuff: high-performance storage controllers. We need to maintain a lot of concurrency, handle a lot of kinds of failures, etc. We often require the same objects (e.g: an ongoing I/O request) to be looked up in various ways, associated with failure domains, timed out, etc. So we want it organized by many different data structures, and we need the O(1) of deleting it from the various structures when an I/O request dies.
We also shun dynamic allocations, aside from relatively rare memory pools for large structures that contain the various allocations we need. Intrusive style allows us so many nice things within this style:
* Avoiding the runtime costs of dynamic allocations
* Avoiding the memory costs of extra indirections incurred by dynamic allocations and STL (non-intrusive) style
* Avoiding handling out-of-memory errors in every single code path: there are almost no allocations anywhere, almost all functions become "void" error-free functions!
* Having optimal asymptotics for our operations
* Having reusable generic data structures in C without templates (we dislike C++)
Compared to all this, the STL stuff is just horrible. STL is widely considered to be a superb library, but I find it horrid.
We can agree on almost all points, I think.
The CS 101 bit you mention is a good point: intrusiveness matters for asymptotics in CS, and should be taught in academia, not (very small portions of) industry.
By the way, when you mention "a vector whose elements are linked list heads", a much more typical scenario is an array/vector whose elements contain one or more list heads.
You were wondering about the kinds of software I was working on that needs this stuff: high-performance storage controllers. We need to maintain a lot of concurrency, handle a lot of kinds of failures, etc. We often require the same objects (e.g: an ongoing I/O request) to be looked up in various ways, associated with failure domains, timed out, etc. So we want it organized by many different data structures, and we need the O(1) of deleting it from the various structures when an I/O request dies.
We also shun dynamic allocations, aside from relatively rare memory pools for large structures that contain the various allocations we need. Intrusive style allows us so many nice things within this style:
* Avoiding the runtime costs of dynamic allocations
* Avoiding the memory costs of extra indirections incurred by dynamic allocations and STL (non-intrusive) style
* Avoiding handling out-of-memory errors in every single code path: there are almost no allocations anywhere, almost all functions become "void" error-free functions!
* Having optimal asymptotics for our operations
* Having reusable generic data structures in C without templates (we dislike C++)
Compared to all this, the STL stuff is just horrible. STL is widely considered to be a superb library, but I find it horrid.