C++ Data Structures with Templates From First Principles in C

The book explores the development of a series of key data structures using C and C++. The reader is taken on a graduated journey with each chapter leading to the development of a new C++ template class.The data structures are:A Linked List, including a double linked list that allows a look at list reversal and sorting.A FiFo Queue class based upon a linked list looking at the benefits and subtle challenges of sub-classing.A LiFo Stack class.An introduction to binary trees that includes tree balancing techniques including the DSW algorithm which is a nice introduction to rotations.An AVL self-balancing binary tree that maintains a near optimal balance through insertions and deletions.A Red-Black tree that is optimised for frequent insertions and deletions.A Splay tree optimised for repeated and frequent interaction with a sub-set of the tree data items.A Map class based upon a Red-Black binary tree.Hash tables - developing both the linear probing and separate chaining types.A Vector class representing an efficient resizable array.An introduction to binary heaps and the development of a priority queue based upon a heap.A set class based upon a modified AVL tree.The reader is presented with a range of iterator types and is introduced to template specialization.The book includes C++ demonstration code for each data structure. Additional code samples are supplied for programmers targeting the Arduino IDE which has some variations.