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

> Now you can guess the next step?

Rewrite the commands to püthon?

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

> Now the kids are forced to write down such stuff in German Pseudocode - with Umlauts.

That's the classical way to check examinations and written homework, it's not practical to have a whole class sitting in front of hardware.

Pseudocode is good to demonstrate the algorithmic understanding while not worrying about syntax errors.

The other extreme is googled "homework" code.

This might be passing passing the syntax check and is somehow producing the required result because of a lot of try and error.

But will often not demonstrate any understanding.

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

Pseudocode is good to demonstrate the algorithmic understanding while not worrying about syntax errors

I know someone who agrees with you on that (Verzeihung, Australisch rühren wieder :).

No. «Fünf hinein!» as my old teacher said.

It should be:

mische(victor)
sortiere(victor)
[download]

Now describe what a Übersetzer and a Bindelader is. In German as we are in Germany. You got one minute as we are in a hurry 🤪 Then write a class StandardChorobaBibliotkekDoppeltVerketteteListe. Don‘t google. Don’t read any man page. As real programmers never make it so. You got 5 minutes. Else you are durchgefallen.

«The Crux of the Biscuit is the Apostrophe»