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.