Data structure programming. With the standard template library in C++
Knowledge of the most common data structures and efficient algorithms for the most often recurring basic problems was always considered to be a core of programmer's knowledge and skills. Nowadays, however we must add also mastering of fundamentals of data abstraction. The book addresses both these topics. Its aim is to introduce basic data structures, their programming as well as respective data abstractions. The book, however, emphasizes practical approach to these themas by using C++ and its standard template library (STL) to illustrate ideas presented there. The book consists of nine chapters and one appendix. Chapter 1 introduces the reader into the basics of data abstraction, encapsulation, and information hiding. After that templates are introduced as important means to provide abstractions in C++, followed by a short survey of abstraction provided by the STL. In Chapter 2 programming with arrays and pointers is explained. Sections devoted to pointer arithmetic and arrays with more than one dimension are then followed by short explanation of the way STL deals with arrays and pointers. Then, various searching and sorting algorithms are outlined and their efficiency analyzed. Finally, the use of arrays is illustrated by an example of a simple database. Chapter 3 provides an overview of container mechanisms. Notions of dense storage and linked storage are explained with array stack and linked stack examples respectively. In the rest of the chapter notions of tree storage, graph storage, hashed storage and indexed storage are briefly explained. In Chapter 4 overview of the STL is presented. First, components of the STL divided into six categories (containers, iterators, generic algorithms, function objects, adaptors, and allocators) are enumerated and followed by a simple spell-checker example. Then, all six categories and their respective subcategories are described and where possible illustrated by extending the simple spell-checker example. Chapter 5 deals with expandable arrays (vectors). First the indexing problem is discussed. Then the implementation of vectors is explored and the memory management problem is discussed. The rest of the chapter deals with programming with vectors. Chapter 6 is devoted to queues and double-ended queues (dequeues). First the implementation and interface issues related to queues are discussed. Then the priority queues and heaps and STL generic algorithms, searching and sorting as well as order statistics and the merging problem, are dealt with. The last three chapters address more advanced topics, namely lists (Chapter 7), maps, multisets and multimaps (Chapter 8) and hash tables (Chapter 9). In Chapter 7 properties and implementation of lists in STL are introduced followed by techniques for STL lists like finding an item in a sorted list, inserting into a sorted list or splicing, merging and inverting lists. Chapter 8 contains sections devoted mainly to variants of tree data structures (binary trees, (balanced) binary search trees, 2-3-4 trees or red-black trees). Chapter 9 is devoted to hashing even if STL does not currently have hashed data structures. Instead of that two known separate implementations are used there. Separate chaining hashing as well as circular hashing are both covered followed by discussion of using hashed structures and implementation issues. In the Appendix STL summary is presented in three parts -- algorithm prototypes, containers and adaptors. The book is written in a concise yet readable style. Each chapter ends = with a brief summary and a number of exercises. It is a useful textbook for undergraduate courses on data structures and their implementation in C++.
- Extending STL with efficient data structures
- scientific article; zbMATH DE number 108391 (Why is no real title available?)
- scientific article; zbMATH DE number 578145 (Why is no real title available?)
- scientific article; zbMATH DE number 1051938 (Why is no real title available?)
- Using the STL. The C++ standard template library
- scientific article; zbMATH DE number 2011479 (Why is no real title available?)
- scientific article; zbMATH DE number 839546 (Why is no real title available?)
- Lists revisited, cache-conscious STL lists
This page was built for publication: Data structure programming. With the standard template library in C++
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3838083)
