> And I’m aware of how important they are

Actually, linked lists have recently become completely unimportant! :) ... due to the mind-bogglingly high cost of cache misses on modern memory architectures. Linked lists tend to maximize cache misses, at least compared to the much more compact vectors.

This is analysed in more detail in The 10**21 Problem (Part 3) where Stroustrup noted that on modern memory architectures, C++ linked lists are typically 50 to 100 times slower than vectors.

Update: Much later I remembered Re: Data structures in Perl. A C programmer's perspective. (vector vs linked list performance).

> Actually, linked lists have recently become completely unimportant!

For how long?

Things which were relevant in the 90s became unimportant because of hardware a dozen years later to reappear as relevant after the same time span again.

Example:

• Multiplication on the Motorola 68000 was so slow (~74 cycles IIRC) that Mandelbrot sets were best implemented by precalculating a big lookup table in RAM (~8 cycles)
• Later using lookup tables became obsolete by the speed difference between CPU calculations compared to RAM access.
• Later caches became so big that big tables could fit again easily

Lessons:

• Efficiency of algorithms are effected by hardware
• You can't always predict how hardware evolves.

All this doesn't justify not to study linked lists:

• they can be used in many contexts
• with many advantages
• are easily implemented (see LISP)
• and performance is not always an issue.
Now what exactly do you mean with a vector?

If you mean something with equidistant entries, how would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Sorry LanX, I confess I was indulging in the traditional Aussie pastime of stirring when I claimed that linked lists have become completely unimportant. :) You've made some excellent valid points in defence of linked lists. To answer your last question more seriously:

How would you implement an array of strings of varying length without links? And how are these string-links less likely to cause cache misses?

I'd try using the standard library: std::vector<std::string> ... hoping/trusting/assuming that this common case has already been optimized ... and googling indicates that most implementations of the C++ standard library do in fact use some form of Short/Small String Optimization (SSO) so that smallish strings are not stored on the heap, vastly improving locality of reference:

A std::string typically stores the string as a pointer to the free store ("the heap"), which gives similar performance characteristics as if you were to call new char [size]. This prevents a stack overflow for very large strings, but it can be slower, especially with copy operations. As an optimization, many implementations of std::string create a small automatic array, something like char [20]. If you have a string that is 20 characters or smaller (given this example, the actual size varies), it stores it directly in that array. This avoids the need to call new at all, which speeds things up a bit...

If I get time later, I may try to do some sort of benchmark of your interesting use case in both Perl and C++.

I guess the point is what they think a vector is. I guess they think it like this (in R):

v<-c(1:3)

typeof(v)
length(v)

min(v)
max(v)
median(v)
mean(v)
append(v, 4)

# shuffle(v)
# sort (v)
[download]

This yields in an interactive R session:

[1] "integer"
[1] 3
[1] 1
[1] 3
[1] 2
[1] 2
[1] 1 2 3 4
[download]

Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts. As we are in Germany. No kidding. Plus some UML diagrams. Just to come back to the roots. Or the original question. Now you can guess the next step? Best regards, Karl.

Regards, Karl

«The Crux of the Biscuit is the Apostrophe»

I think that Stroustrup's concept as referenced, is completely out of context. Searching a "short" array or traversing a "short" linked list sequentially will always be relevant! A vector to a short linked list (like a hash table) is very efficient.

Sorry, I don't understand the point you are trying to make. Are you suggesting that C++ vector is faster than linked list only for "small" containers? Note that Stroustrup measured up to half a million nodes, as confirmed in this talk by Herb Sutter (two years later). Herb likewise exhorts C++ programmers to prefer vector to linked list. Update: see also.

As a journeyman C++ programmer, I greatly admire both Bjarne Stroustrup and Herb Sutter for their many contributions to C++ over so many years, especially their work on language standardisation. When they both exhort you to use std::vector (and std::map) as your default containers, I pay attention. ... which BTW has a nice synergy with Perl. At least, I've always enjoyed using Perl's analogous default containers (built-in arrays and hashes) ... and never felt the urge to write my own linked list class in Perl. :)