Logo - springer
Slogan - springer

Computer Science - Software Engineering | Data Structure Programming - With the Standard Template Library in C++

Data Structure Programming

With the Standard Template Library in C++

Bergin, Joseph

Softcover reprint of the original 1st ed. 1998, XIV, 336 p.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-1-4612-1630-8

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-1-4612-7223-6

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

  • *Introduces data structures and the STL.
  • *Provides a carefully integrated discussion of general data structures and their implementation and use in the STL.
  • *The author teaches readers the important features of abstraction while using the STL to develop applications, and is well known in the community.
Once programmers have grasped the basics of object-oriented programming and C++, the most important tool that they have at their disposal is the Standard Template Library (STL). This provides them with a library of re-usable objects and standard data structures. It has recently been accepted by the C++ Standards Committee. This textbook is an introduction to data structures and the STL. It provides a carefully integrated discussion of general data structures and their implementation and use in the STL. In so doing, the author is able to teach readers the important features of abstraction and how to develop applications using the STL.

Content Level » Graduate

Keywords » Ada - C++ programming language - algorithms - data structure - data structures - hash function - hash table - sorting

Related subjects » Software Engineering - Theoretical Computer Science

Table of contents 

1. Data Structures and Algorithms.- 1.1 Data Abstraction and Encapsulation.- 1.2 Classes, Data Abstraction, Encapsulation, and Information Hiding.- 1.3 Derived Classes. Object Orientation.- 1.4 Templates.- 1.5 Which Data Abstractions Are Useful?.- 1.6 Abstractions Provided by the STL.- 1.7 Summary.- 1.8 Exercises.- 2. Programming with Arrays and Pointers.- 2.1 Arrays.- 2.1.1 An Example. A Guessing Game.- 2.1.2 Another Example. Array of Objects.- 2.2 Pointers and Arrays.- 2.3 Pointer Arithmetic.- 2.4 Arrays with More than One Dimension.- 2.5 Putting It Together. An Application.- 2.6 How the STL Generalizes Arrays and Pointers.- 2.7 Some Common Problems. Searching and Sorting.- 2.7.1 Linear Search in Arrays.- 2.7.2 Selection Sort.- 2.7.3 Binary Search.- 2.7.4 Quicksort.- 2.7.5 The Efficiency of These Algorithms.- 2.8 Using Arrays with the STL.- 2.9 Another Example. A Simple Database.- 2.10 Arrays That Contain Pointers.- 2.11 Another Use for Pointers—Lists.- 2.12 Summary.- 2.13 Exercises.- 3. Overview of Container Mechanisms.- 3.1 Storage Mechanisms.- 3.2 Dense Storage.- 3.3 An Extended Example Part 1: The Array Stack.- 3.4 Linked Storage.- 3.5 An Extended Example Part 2: The Linked Stack.- 3.6 Tree Storage.- 3.7 Graph Storage.- 3.8 Hashed Storage.- 3.9 Indexed Storage.- 3.10 Summary.- 3.11 Exercises.- 4. Overview of the Standard Template Library.- 4.1 Components of the STL.- 4.2 A Motivating Example: A Spell Checker.- 4.3 Containers.- 4.3.1 Sequence Containers.- 4.3.2 More on the Spell Checker.- 4.3.3 Sorted Associative Containers.- 4.3.4 Rebuilding the Spelling Dictionary as a Set.- 4.4 Iterators.- 4.4.1 Forward Iterators.- 4.4.2 Bidirectional Iterators.- 4.4.3 Random Access Iterators.- 4.4.4 Input Iterators.- 4.4.5 Output Iterators.- 4.4.6 Istream and Ostream Iterators.- 4.5 Generic Algorithms.- 4.5.1 Minimum and Maximum Algorithms.- 4.5.2 Generalized Numeric Algorithms.- 4.5.3 Nonmutating Sequence Operations.- 4.5.4 Mutating Sequence Operations.- 4.5.5 Sorting Related Operations.- 4.5.6 Set Operations on Sorted Structures.- 4.5.7 Heap Operations.- 4.5.8 Lexicographical Compare Operations.- 4.5.9 Permutation Generation Operations.- 4.5.10 Miscellaneous Additional Operations.- 4.6 Function Objects.- 4.6.1 Arithmetic Operations.- 4.6.2 Comparison Operations.- 4.6.3 Logical Operations.- 4.7 Adaptors.- 4.7.1 Function Adaptors.- 4.7.2 Container Adaptors.- 4.7.3 Iterator Adaptors.- 4.8 Allocators.- 4.9 Summary.- 4.10 Exercises.- 5. Vector Programming.- 5.1 Vectors—Expandable Arrays.- 5.2 The Indexing Problem.- 5.3 How We Can Implement Vectors.- 5.4 Memory Management.- 5.5 Adding to the Functionality of ExpandableArrays.- 5.6 Programming with Expandable Arrays.- 5.7 Building a Stack Adaptor.- 5.8 The STL vector Template.- 5.9 A Graph Implemented with STL vectors.- 5.10 Summary.- 5.11 Exercises.- 6. Dequeue Programming.- 6.1 Queues and Double-Ended Queues.- 6.2 Implementing a Dequeue.- 6.3 A Simple deque Example.- 6.4 The deque Interface.- 6.5 Efficiency of deque.- 6.6 More on Container Adaptors—The queue Adaptor.- 6.7 Priority Queues and Heaps.- 6.7.1 Heaps.- 6.7.2 Priority Queues.- 6.8 STL Generic Algorithms—Searching and Sorting.- 6.8.1 Generalized Searching.- 6.8.2 Sorting.- 6.8.3 Searching Sorted Containers.- 6.9 Median and Other Order Statistics.- 6.10 Merging.- 6.11 Summary.- 6.12 Exercises.- 7. Lists.- 7.1. Implementation Strategies of STL Lists.- 7.2. Properties of STL Lists.- 7.3 A Simple Implementation of Circular Lists.- 7.3.1 Sorting a List.- 7.3.2 Recursive List Operations.- 7.3.3 Some Difficulties with This Implementation.- 7.4 An Alternate Implementation of Lists.- 7.5 The Iterator Invalidation Problem and Its Solution.- 7.6 Techniques for STL Lists.- 7.6.1 Finding an Item in a Sorted List.- 7.6.2 Inserting into a Sorted List.- 7.6.3 Applying an Arbitrary Function to Each Element of a List.- 7.6.4 Splicing Lists.- 7.6.5 Merging Sorted Lists.- 7.6.6 Reversing a List.- 7.6.7 Building a Spelling Dictionary.- 7.6.8 A Merge Sort Suitable for Lists.- 7.7 Summary.- 7.8 Exercises.- 8. Sets, Maps, Multisets, and MultiMaps.- 8.1 Sequential Versus Sorted Containers.- 8.2 Binary Trees.- 8.3 Binary Search Trees.- 8.4 Balanced Binary Search Trees.- 8.5 2-3-4Trees.- 8.6 Red-Black Trees.- 8.7 Sets and Multisets.- 8.8 Maps and Multimaps.- 8.9 An Implementation of Red-Black Trees.- 8.10 Summary.- 8.11 Exercises.- 9. Hash Tables.- 9.1. Hashed Associative Containers and the STL.- 9.2 Simple Hashing—Separate Chaining.- 9.3 Simple Hashing—Circular Hashing.- 9.4 Variations on Simple Hashing.- 9.5 Hash Functions.- 9.6 Reorganization of a Hash Table.- 9.7 Using Hashed Structures.- 9.8 Elements of an Implementation.- 9.8.1 The Hash Table.- 9.8.2 Sets and Maps.- 9.8.3 Using the Sets and Maps.- 9.9 Design Issues.- 9.10 Extending the Standard Template Library.- 9.11 Summary.- 9.12 Exercises.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Programming Techniques.

Additional information