Writing your own forward_list<T> alternative
Writing a node-based container such as std::list, std::unordered_map, std:: map, and so on is an interesting exercise, but in this chapter, the fact that it is interesting will not necessarily “shine” right away. The points of interest for such classes will be more evident in Chapter 13 and Chapter 14, but we will still write a basic, simplified version here to make the side-by-side evolution of our container types clearer in the pages and chapters to come.
A forward list is an exercise in leanness. We want the type to be small and do what it does well. Some forward lists occupy the size of a single pointer in memory (a pointer to the first node in the sequence); in our implementation, we will pay the price for an additional integer (the number of elements) in order to get a constant-time complexity guarantee for the size() member function.
Representational choices for a node-based container
In our implementation...
