On Sun, May 24, 2026 at 3:35 PM JOSE DANIEL GARCIA SANCHEZ via SG20 <
sg20_at_[hidden]> wrote:

>
> 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