[beder]

There's plenty of discussion relating to the article he references at http://news.ycombinator.com/item?id=4455225, and much of the same applies here.

1. He's not comparing apples-to-apples between `std::list` and his intrusive linked list; the proper analogue would be to unlink a node from its iterator, for which the running time is still O(1).

2. The main (only?) reason to use intrusive lists is for the single indirection (which helps both memory and speed). In his example for how using std::list would crash his server because of the O(N) node removal, he's just not storing the right data for each connection (again, use an iterator).

3. He looked at boost's intrusive list, but I'm guessing he didn't actually try it out. The examples are pretty good, and it's much easier than it "looks". (That is, boost libraries can look intimidating when you first look at them because they're so template-heavy.)

4. It may even be that a vector, plus an auxiliary data structure for lookup, may be faster.

[shrughes]

1. Yes.

2. Also the safety. You can include assertions that the object is not a member of a linked list, when you add it to the linked list.

3. A general rule of thumb when using C++ is that you shouldn't use Boost. Boost is a source of major headaches -- even in innocuous looking parts like smart pointers. There are many reasons to avoid it in general, the most important one being compile times, because boost developers are terrible at avoiding creating long compile times. You can reimplement a boost header (for example, for uuid, shared_ptr, intrusive_ptr, and so on) and get a significant compile time speed-up. The other problem with boost libraries is that they lack assertions that are appropriate for software development. For example, with a scoped_ptr, it is better to have an init(T *) method that asserts the object has not been initialized, not just a general reset method, because with most uses of scoped_ptr<T>::reset() (in code that I've worked with) you're expecting it to currently be empty.

(Edit: Also, boost libraries are intimidating because the documentation is bad.)

4. Maybe.

[quotemstr]

> A general rule of thumb when using C++ is that you shouldn't use Boost.

That's not a rule of thumb. It may be something you do, and a reason I'd never work with you. Boost is a wonderful library that IME solves far more problems than it creates. Compile times aren't a problem with modern compilers, and your scoped_ptr example is nonsense.

[shrughes]

Um, compile times are still a problem with modern compilers.

And regarding scoped_ptrs: you want what, fewer assertions? Okay... that's very counterproductive of you.

[omnigoat]

I don't get your reasoning (mainly because all you've provided none). I wrote games, we used Boost heavily, on the PC, Xbox360, DS, Wii and PSP. I mean really heavily. Boost.Thread, Boost.SmartPtr, Boost.Bind, Boost.Function, Boost.MultiSet, Boost.Array, Boost.PreProcessor, Boost.LexicalCast... (more)...

We turned off exceptions (BOOST_NO_EXCEPTION) because the Wii and the DS didn't support exceptions. That was it. We never had a problem with spurious assertions, nor with unexpected behaviour from a lack of assertions. Compile times were about 5 to 7 minutes for partial builds. A full build was longer (I forget), something like 15. This is a huge code base, remember.

I honestly have no idea what you're talking about. It's certainly not a "general rule of thumb".

[shrughes]

The fact that there are people who use boost heavily is not news to me. So if you're confused by my assertion that everybody avoids boost as a general rule, well, I'm confused as to why you believe I made such an assertion.

(Note that I don't completely avoid Boost either. The thing is, the parts that are nice to use are simple enough to reimplement more situation-appropriately, and the other parts, I'll use, but I'll use them with trepidation, and if I don't feel like thinking about whether they might be useful, avoid them. For example, it's better to write a recursive descent parser than it is to use Spirit, and it's better to write your own serialization stuff than to use Boost Serialization (if only for compile times, but also, there's some disturbing complexity hidden in that library). I don't exactly know how you use LexicalCast without exceptions turned on, but if you're going in the int->string direction I generally use a printf-like function that returns a std::string.)

[huhtenberg]

THE reason to use "intrusive" containers is to let a piece of data to sit in multiple containers, none of which is primary. I'll give you an skbuff and you show me how to put it on several linked lists and a couple of hashmaps with STL-style containers.

[shrughes]

That's not the only reason. Another is simplicity.

[morsch]

Store multiple pointers to the same datum?

[gsg]

Then for deletion you need to traverse every data structure in which you store said pointers.