Comment by repsilat | Hacker News Reader

Comment by repsilat | Hacker News Reader

Parent Full thread

> 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.

:)

> 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.

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

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.

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.

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

Reply on news.ycombinator.com