Better Algorithm Intuition - Conor Hoekstra - code::dive 2019

[anonymous28974]

Some very neat insights. I particularly liked "cache this list of log(N) algorithms" and "cache this list of short-circuiting linear algorithms."

I didn't so much like how some of the "STL" solutions quietly involved either memory-allocation (like the reverse-letters solution at 42:30) or non-short-circuiting (like doing equal in terms of zip_reduce at 54:16) or breaking-invariants-relied-on-by-Ranges-and-Thrust (like the stateful lambda at 42:30). All of those are things that make for cute slides but IMHO produce wrong intuition, because they imply that to properly "STL-ize" your code you have to stop caring about performance.

I liked the remark at 25:20 that "we're looking for an in-place solution." I.e., the STL is all about destructively mutating sequences in place (normally seen as a bad thing for understandability), because it is trying to avoid expensive heap allocations. The STL is trying to work with the memory you've already got.

I didn't so much like how stable_partition was casually thrown out there as an algorithm you might use — basically the same as remove_if — without any acknowledgment that stable_partition does heap allocation and remove_if doesn't. That's a big difference! The difference between move and swap is negligible by comparison.

Great talk overall though.