Curious C++ Lambda Examples: Recursion, constexpr, Containers C++23 included
cppstories.com
cppstories.com
The most amazing thing about it is how it manages to be so entertaining to read (the last thing I expected from a C++ textbook and a thing that made getting through it way easier)!
>I'm not sure if there's an even more recent edition that covers C++17 and C++20
Sadly, there is not. Scott for-the-most-part retired in 2015: https://scottmeyers.blogspot.com/2015/12/good-to-go.html
https://www.stroustrup.com/tour2.html
which might fit the bill. It doesn't go very far in depth, though. 240 pages.
auto factorial23 = [] fact_recur (int n) {
if (n <= 1)
return 1;
return n * fact_recur(n - 1);
};
class Awesome {
// ...
foo& my_method() { /* ... */ }
const foo& my_method() const { /* ... */ }
};
Also many sets of people are disjoint.
So much developer thought and mental energy expended to do something as simple as recursion.
`this` can be captured, like
[this](int x) { return x + this->x; }
int factorial (int n) { return (n > 1) ? n * factorial(n - 1) : 1; }
* Recursion in an anonymous function. Are you sure this is so simple in other languages?
* Compile-time recursion with anonymous functions. Which other languages even have this to begin with?
Both of these cases are rarely used in practice. The C++23 addition which facilitates them is actually due to another issue entirely, which is avoiding code duplication when you want to specialize methods according to features of the object they're running for (const/non-const, lvalue/rvalue). See:
What it can do in practice is use (configurable) hard limits on the depth and on the amount of time for evaluating constexpr expressions. That way it doesn't overflow its own stack/buffers, nor will it hang on such evaluations. This is good enough, since the purpose of this feature is not perform heavy computations using the compiler, but rather preventing not-so-heavy computations from being performed repeatedly at run-time (and to be able to use their results in template instantiation etc.)
Compile time recursive functions are likewise available in common lisp via recursive macros. Some schemes have them, too. And the syntax is much more elegant.
I used to write C++ for a few years, and the mental burden is real, you just stop noticing it. Having come back to C++ for an old project a few months ago, and writing it felt like a chore. Maybe I just never liked it without realising, and it's only just surfaced, though!
In OCaml, for example, you can't do recursion for the same reason without the special "let rec" construct.
If you do, you can just make an embedded domain specific language, since it supports that too.
The syntax examples here is what makes C++ hard to read: scores of special symbols hiding rather simple underlying mechanism.
This is the sort of thing that’s interesting to know from an intellectual perspective to see how far can you bend and twist a language to do certain things, but you’re setting yourself up for a world of maintenance pain if you use this sort of stuff in your code base.
There probably is a language and an application where recursion makes sense but C++ isn't one of those languages. Certainly a factorial is a horrible example because iterative is strictly better.
Obviously in a non-functional language, you can do these things without recursion by using your own stack rather than the runtime function-call stack. But sometimes it's nice to have the stack provided for you. That also plays well with C++ runtime exception propagation.
Given in most languages you can't enforce tail call optimisation, it's risky to use unbounded recursion.
The last time I worked on a project with that rule was about 23 years ago, and that was on a 32-bit system.
As for linked lists, obviously it's true that the cases where they should be used are much more limited than they used to be. But still, they're a very simple data structure that's easy to reason about and which software engineers are very likely to occasionally encounter in practice. I don't think there's much to be gained by eliminating them from students' education.
You should measure this!
In Python, the issue is the easily reachable max recursion depth. Tail recursion isn't optimized.
In Erlang, you use recursion even just to iterate through a list. It's fine, the language is made for that.
The linked list is a peculiar data structure which makes a lot of sense in the 1970s because all memory reads cost the same and addresses are small, but is terrible in most cases in 2022 because we have huge addresses and very fast local cache. There still are good uses for the linked list, but they're now pretty esoteric.
Using the list concept with recursion is great, but fast implementations of languages in 2022 do not lean on the linked list. Java's ArrayList, and the terribly named C++ std::vector, are more appropriate structures for a lot of cases where a 1970s algorithms book says "list".
Linked lists aren’t very common in desktop application programming, if they ever were, and non-intrusive linked lists as container classes do seem particularly prone to having better alternatives, especially naïve implementations that allocate the list nodes and node content separately. One of the best reasons to reach for a linked list is to avoid all calls to new or malloc or free, so doubling up on them is especially silly.
I don’t think this is really a 70s thing though. Linked lists might have been used slightly more often in the past, but I think they’ve always been used far less than arrays, and my old algorithms books that predate std::vector just use arrays. Maybe the main utility of linked lists is to teach about pointers and algorithm complexity. They do make good examples of pointer management and of algorithms with different big-O than arrays, hashes, trees, etc. I maybe used linked lists a couple of times in games programming, but have rarely ever used them, while they were covered thoroughly in school.
In embedded my guess would be that you see linked lists because lots of embedded programmers are C programmers and that's what they learned to do, not because it's actually a good choice. I reckon if you look at C programs I wrote in the 1990s there are a lot of linked lists, and I can't defend any of those as the right solution.