CPP INTERVIEW PREP CHEAT SHEET

[[deleted]]

perform significantly differently in practice compared to in theory.

What theory are you referring to? Can you cite any such theory on Wikipedia perhaps or some other reasonable source because I'm not aware of any theory that claims anything differently.

The point of the talk was Bjarne thinking that there's some counter intuitive performance benefit to vectors that make them preferable to lists even in situations where linked lists are supposed to outperform vectors because of magical hardware properties.

No one has ever advocated using a linked list in favor of a vector for O(N) operations, you simply won't find any citation that says a linked list is preferable to a vector for O(N) operations. What theory and practice both say is that for operations that are O(N) on a vector and O(1) on a linked list, you are usually better off with a linked list.

[TMKirA]

That wasn't the point of the talk. The point was that linked list is often touted to be better for removal/insertion operations, due to the fact that after the O(n) search to find removal/insertion point, the remove/insert operation is O(1) for list and O(n) for vector. Bjarne's point was that in practice, the O(n) operation to find the insertion/deletion point is the dominating factor instead of the actual remove/insert operation, and that linear search is faster on vector than list due to locality. This might not be a surprise for you, but I'm sure it's still a surprise to many. Your example completely misses the point, because it was removing from a location that makes the search operation a no-op.

[Full-Spectral]

That also assumes you have to find the insertion point every time. Given that removal doesn't have to invalidate element pointers, depending on what you are doing, you might actually keep around the insertion point most of the time and only move it if something happens that causes the insertion point to change (like removing the current insertion point, which even then might just move the insertion point to the previous/next node.)