[forrestthewoods]

I like intrusive lists. Another consideration is that a std::vector<FooPtr> is as fast to iterate over as intrusive list of Foos. The memory access pattern is the same. (Note: typed FooPtr instead of Foo Asterisk because the single asterisk italicized everything)

Another perk is that an element can remove itself from the list without actually having to know anything about the list. This makes a lot of shutdown code super easy and clean.

I do like intrusive lists to be inherited I think. That makes the interface for adding or removing objects from lists super clean. It also eliminates the extra obj pointer since the obj root address is known at compile time. Storing one object in multiple intrusive lists gets a little hairy and you need a tag parameter but that's a relatively rare need in my experience so it's fine.

One thing I don't like is lack of good debugging info in visual studio. For c++ at least their customization tools are seemingly nOT powerful enough to handle intrusive lists well. Not being able to clearly see all objects in the watch window is wildly frustrating. Things that make code harder to debug make me very, very cranky.

[repsilat]

> Another consideration is that a std::vector<FooPtr> is as fast to iterate over as intrusive list of Foos.

A "normal" linked-list of strings or vectors always makes me sad -- the reasoning goes,

- The list elements need to live on the heap because they might live forever, - The string object has to be fixed-size because objects are always (at least officially) fixed-size. - The string storage has to live on the heap, because it can be arbitrarily large.

So printing out a linked-list of strings gets two pointer dereferences per string instead of one. I guess that's the cost of abstraction, though.

(This actually fits into the C++ zero-cost-abstraction narrative pretty well, though:

- Linked-lists are not zero cost, - C++ programmers don't like non-zero-cost abstractions, - C++ programmers don't like linked lists.

:)

[sorbits]

> C++ programmers don't like non-zero-cost abstractions

I think you’re confusing zero cost with zero overhead.

What C++ programmers like is that the compiler does not add overhead, for example calling `a[10]` will read the word at address `a + 10` and return that. No bounds checks are inserted, no function call is done to lookup the element in some implementation defined sparse data structure, etc.

But C++ programmers are generally not opposed to using things that has a cost associated with it (basically everything has a cost) — for example `std::map` is quite popular and certainly not “zero cost”, though it has its running time defined, and the implementation is actually using a self-balancing search tree rather than a hash table because we can give guarantees about the running time of the former, not the latter.

[nly]

std::map is implemented using a tree and not a hash table because it's specified as an ordered data structure.

[sorbits]

I am quite sure (based on interviews I’ve read) that Alexander Stepanov’s primary concern was having a data structure with known (fixed) complexity rather than a sorted container. The latter is just a nice side-effect.

[dfkf]

In the worst case scenario the time complexity of a hash table equals that of its bucket, which doesn't have to be a list. So the only advantage of the map over the unordered_map seems to be the ease of use, it only needs a comparer.

[nly]

unordered_map pretty much has to have linked buckets due to its interface and complexity requirements.