I have been asked by a colleague about good teaching references (preferrrably books) for teaching basic implementation of data structures in C++.
Any recommendations?
(Spoiler: I have no recommendations.)
FWIW, I think there's two ways to interpret this topic. Are you asking for material on learning data structures that just happens to use C++ as the implementation language? Or are you asking for material on learning how to implement data structures in C++?
For "learning data structures," you'll end up using C++ as an "only slightly better C" or a "weirder-looking Pascal." You can assume that the payload type is something trivial like `int`, so you don't have to explain the difference between "allocating space for an element" and "constructing an element." You'll still use raw pointers, because after all the point of the class is to teach how to implement data structures — you can't teach linked lists without pointers, or splay trees without pointers. You won't care about the C++ allocator model. You might care about C++ destructors, in that you do want to teach how to tear down a data structure and free its memory properly after the fact, and (with C++ as the implementation language) the idiomatic way to spell that is with a "~". (Whereas in C you'd just write a function named `linkedlist_free` or whatever.)
I can see how a book from the '90s or '00s that used C++ as its implementation language would have deficiencies from a modern programmer's point of view. Small ones, but annoying ones that the instructor would have to patch "by hand" and that would be icky. For example, your SplayTree class should `=delete` its special members, instead of making-them-private or doing-nothing-about-them. For example, if there's anyplace that returns a class type, it should just return it by value, rather than by out-parameter as most '90s textbooks would have done. Etc.
For "learning C++ implementation of data structures (e.g. STL containers)," you'd care to focus much more on:
- Template programming. Making your container a class template. Documenting requirements on T.
- The difference between allocating memory, versus constructing a payload.
- The C++ allocator model.
- The iterator model. Providing const and reverse iterators.
- The proper idiom for making iterator convertible to const_iterator but not vice versa.
- Copy construction and assignment.
- Move semantics.
- That `size()` must be O(1), or omitted.
- Specific non-STL idioms for non-STL-style containers such as tries and slot-maps.
- Proxy references.
etc. etc.
Which is a vastly different question, and also vastly more difficult material to collect and organize.
–Arthur