C++ Data Structures and Algorithm Design Principles E-Book

John Carey

• Herausgeber: Packt Publishing
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 575

Veröffentlichungsjahr: 2019

Beschreibung

Get started with C++ programming by learning how to build applications using its data structures and algorithms

Key Features

• Explore data structures such as arrays, stacks, and graphs with real-world examples
  
  


• Study the trade-offs between algorithms and data structures and discover what works and what doesn't
  
  


• Discover how techniques such as bloom filters and multi-way heaps boost real-world applications

Book Description

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++.

This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book.

By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.

What you will learn

• Build applications using hash tables, dictionaries, and sets
  
  


• Explore how modern hardware affects the actual run-time performance of programs
  
  


• Apply common algorithms such as heapsort and merge sort for string data types
  
  


• Use C++ template metaprogramming to write code libraries
  
  


• Implement a URL shortening service using a bloom filter
  
  


• Use appropriate modern C++ idioms such as std:: array instead of C-style arrays

Who this book is for

This book is for developers or students who want to revisit basic data structures and algorithm design techniques. Although no mathematical background is required, basic knowledge of complexity classes and Big O notation along with a qualification in an algorithms course will help you get the most out of this book. Familiarity with C++ 14 standard is assumed.

Leseprobe

C++ Data Structures and Algorithm Design Principles

Leverage the power of modern C++ to build robust and scalable applications

John Carey

Shreyans Doshi

Payas Rajan

C++ Data Structures and Algorithm Design Principles

Copyright © 2019 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the authors, nor Packt Publishing, and its dealers and distributors will be held liable for any damages caused or alleged to be caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.

Authors: John Carey, Shreyans Doshi, and Payas Rajan

Technical Reviewer: Shubham Srivastava

Managing Editor: Aniket Shedge

Acquisitions Editors: Kunal Sawant and Sneha Shinde

Production Editor: Shantanu Zagade

Editorial Board: Shubhopriya Banerjee, Bharat Botle, Ewan Buckingham, Mahesh Dhyani, Manasa Kumar, Alex Mazonowicz, Bridget Neale, Dominic Pereira, Shiny Poojary, Abhisekh Rane, Erol Staveley, Ankita Thakur, Nitesh Thakur, and Jonathan Wray.

First Published: October 2019

Production Reference: 1311019

ISBN: 978-1-83882-884-4

Published by Packt Publishing Ltd.

Livery Place, 35 Livery Street

Birmingham B3 2PB, UK

Table of Contents

Preface   i

1. Lists, Stacks, and Queues   1

Introduction   2

Contiguous Versus Linked Data Structures   2

Contiguous Data Structures   3

Linked Data Structures   4

Comparison   6

Limitations of C-style Arrays   7

std::array   7

Exercise 1: Implementing a Dynamic Sized Array   12

Exercise 2: A General-Purpose and Fast Data Storage Container Builder   17

std::vector   19

std::vector – Variable Length Array   19

Allocators for std::vector   23

std::forward_list   24

Inserting and Deleting Elements in forward_list   24

Other Operations on forward_list   26

Exercise 3: Conditional Removal of Elements from a Linked List Using remove_if    27

Iterators   31

Exercise 4: Exploring Different Types of Iterators   32

Exercise 5: Building a Basic Custom Container   34

Activity 1: Implementing a Song Playlist   39

std::list   40

Common Functions for std::list   40

Exercise 6: Insertion and Deletion Functions for std::list   41

Bidirectional Iterators   43

Iterator Invalidation for Different Containers   43

Activity 2: Simulating a Card Game   44

std::deque – Special Version of std::vector   45

The Structure of Deque   45

Container Adaptors   48

std::stack   49

std::queue   50

std::priority_queue   51

Iterators for Adaptors   51

Benchmarking   51

Activity 3: Simulating a Queue for a Shared Printer in an Office   52

Summary   53

2. Trees, Heaps, and Graphs   55

Introduction   56

Non-Linear Problems   56

Hierarchical Problems   57

Cyclic Dependencies   58

Tree – It's Upside Down!   59

Exercise 7: Creating an Organizational Structure   59

Traversing Trees   63

Exercise 8: Demonstrating Level Order Traversal   65

Variants of Trees   66

Binary Search Tree   67

Time Complexities of Operations on a Tree   71

Exercise 9: Implementing a Binary Search Tree   71

Balanced Tree   76

N-ary Tree   79

Activity 4: Create a Data Structure for a Filesystem   80

Heaps   81

Heap Operations   82

Exercise 10: Streaming Median   85

Activity 5: K-Way Merge Using Heaps   88

Graphs   89

Representing a Graph as an Adjacency Matrix   90

Exercise 11: Implementing a Graph and Representing it as an Adjacency Matrix   91

Representing a Graph as an Adjacency List   94

Exercise 12: Implementing a Graph and Representing it as an Adjacency List   94

Summary   98

3. Hash Tables and Bloom Filters   101

Introduction   102

Hash Tables   102

Hashing   103

Exercise 13: Basic Dictionary for Integers   104

Collisions in Hash Tables   108

Close Addressing – Chaining   108

Exercise 14: Hash Table with Chaining   109

Open Addressing   114

Perfect Hashing – Cuckoo Hashing   116

Exercise 15: Cuckoo Hashing   118

C++ Hash Tables   126

Exercise 16: Hash Tables Provided by STL   128

Activity 6: Mapping Long URLs to Short URLs   133

Bloom Filters   134

Exercise 17: Creating Bloom Filters   136

Activity 7: Email Address Validator   140

Summary   140

4. Divide and Conquer   143

Introduction   144

Binary Search   146

Exercise 18: Binary Search Benchmarks   148

Activity 8: Vaccinations   152

Understanding the Divide-and-Conquer Approach   154

Sorting Using Divide and Conquer   155

Merge Sort   156

Exercise 19: Merge Sort   157

Quicksort   160

Exercise 20: Quicksort   162

Activity 9: Partial Sorting   166

Linear Time Selection   168

Exercise 21: Linear Time Selection   170

C++ Standard Library Tools for Divide and Conquer   176

Dividing and Conquering at a Higher Abstraction Level – MapReduce   178

The Map and Reduce Abstractions   179

Exercise 22: Map and Reduce in the C++ Standard Library   180

Integrating the Parts – Using a MapReduce Framework   183

Exercise 23: Checking Primes Using MapReduce   184

Activity 10: Implementing WordCount in MapReduce    189

Summary   193

5. Greedy Algorithms   195

Introduction   196

Basic Greedy Algorithms   197

Shortest-Job-First Scheduling   197

Exercise 24: Shortest-Job-First Scheduling   198

The Knapsack Problem(s)   201

The Knapsack Problem   201

The Fractional Knapsack Problem   202

Exercise 25: Fractional Knapsack Problem   203

Activity 11: The Interval Scheduling Problem   207

Requirements for Greedy Algorithms   210

The Minimum Spanning Tree (MST) Problem   210

Disjoint-Set (or Union-Find) Data Structures   214

Exercise 26: Kruskal's MST Algorithm   220

The Vertex Coloring Problem   228

Exercise 27: Greedy Graph Coloring   229

Activity 12: The Welsh-Powell Algorithm   236

Summary   240

6. Graph Algorithms I   243

Introduction   244

The Graph Traversal Problem   246

Breadth-First Search   247

Exercise 28: Implementing BFS   249

Depth-First Search   256

Exercise 29: Implementing DFS   259

Activity 13: Finding out Whether a Graph is Bipartite Using DFS   266

Prim's MST Algorithm   270

Exercise 30: Prim's Algorithm   273

Dijkstra's Shortest Path Algorithm   280

Exercise 31: Implementing Dijkstra's Algorithm   283

Activity 14: Shortest Path in New York   290

Summary   291

7. Graph Algorithms II   293

Introduction   294

Revisiting the Shortest Path Problem   294

The Bellman-Ford Algorithm   296

Exercise 32: Implementing the Bellman-Ford Algorithm (Part I)   296

The Bellman-Ford Algorithm (Part II) – Negative Weight Cycles   300

Exercise 33: Implementing the Bellman-Ford Algorithm (Part II)   301

Activity 15: Greedy Robot   304

Johnson's Algorithm   311

Exercise 34: Implementing Johnson's Algorithm   314

Activity 16: Randomized Graph Statistics   322

Strongly Connected Components   325

Connectivity in Directed and Undirected Graphs   326

Kosaraju's Algorithm   329

Exercise 35: Implementing Kosaraju's Algorithm   330

Activity 17: Maze-Teleportation Game   335

Choosing the Right Approach   344

Summary   346

8. Dynamic Programming I   349

Introduction   350

What Is Dynamic Programming?   350

Memoization – The Top-Down Approach   353

Tabulation – the Bottom-Up Approach   355

Subset Sum Problem   356

Solving the Subset Sum Problem – Step 1: Evaluating the Need for DP   358

Step 2 – Defining the States and the Base Cases   360

Step 2.a: Brute Force   360

Exercise 36: Solving the Subset Sum Problem by Using the Brute-Force Approach   361

Step 2.b: Optimizing Our Approach – Backtracking   364

Exercise 37: Solving the Subset Sum Problem by Using Backtracking   369

Step 3: Memoization   373

Devising a Caching Scheme   373

Exercise 38: Solving the Subset Sum Problem by Using Memoization   375

Step 4: Tabulation   377

Exercise 39: Solving the Subset Sum Problem by Using Tabulation   381

Activity 18: Travel Itinerary   385

Dynamic Programming on Strings and Sequences   390

The Longest Common Subsequence Problem   391

Exercise 40: Finding the Longest Common Subsequence by Using the Brute-Force Approach   398

First Steps Toward Optimization – Finding the Optimal Substructure   402

Activity 19: Finding the Longest Common Subsequence by Using Memoization   403

From Top-Down to Bottom-Up – Converting the Memoized Approach into a Tabulated Approach   405

Activity 20: Finding the Longest Common Subsequence Using Tabulation   407

Activity 21: Melodic Permutations   408

Summary   413

9. Dynamic Programming II   415

Introduction   416

An Overview of P versus NP   416

Reconsidering the Subset Sum Problem   421

The Knapsack Problem   422

0-1 Knapsack – Extending the Subset Sum Algorithm   424

Exercise 41: 0-1 Knapsack Problem   426

Unbounded Knapsack   428

State Space Reduction   431

Exercise 42: Unbounded Knapsack   441

Activity 22: Maximizing Profit   444

Graphs and Dynamic Programming   447

Reconsidering the Bellman-Ford Algorithm   448

Approaching the Shortest Path Problem as a DP Problem   452

Exercise 43: Single-Source Shortest Paths (Memoization)   455

All-Pairs Shortest Path   460

The Floyd-Warshall Algorithm   460

Exercise 44: Implementing the Floyd-Warshall Algorithm   462

Activity 23: Residential Roads   468

Summary   473

Appendix   475

Preface

About

This section briefly introduces the authors, the coverage of this book, the technical skills you'll need to get started, and the hardware and software requirements required to complete all of the included activities and exercises.

About the Book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++.

This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book.

By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.

About the Authors

John Carey

A composer and pianist, John Carey's formal education is almost exclusively based within the musical realm. Having used computers and other forms of technology extensively in his artistic endeavors, he invested years of self-study in the subjects of programming and mathematics and now works professionally as a software engineer. He believes his unusual background provides him with a unique and relatively non-academic perspective on the topic of software development. He currently works for Hydratec Industries, a company that primarily develops CAD software for fire sprinkler system designers that is used to perform hydraulic calculations on proposed designs so as to determine their efficacy and legality.

Shreyans Doshi

Shreyans graduated with a Bachelor of Technology degree in Computer Engineering from Nirma University, Ahmedabad. After graduation, he joined the finance industry to work on ultra-low latency trading systems using cutting-edge C++ applications. For the past three years, he has been designing trading infrastructure in C++.

Payas Rajan

Payas graduated with a Bachelor of Technology degree in Computer Science from NIT Allahabad. Later, he joined Samsung Research India, where he helped develop the multimedia framework for Tizen devices. Currently working as a teaching and research assistant while pursuing a PhD specializing in geospatial databases and route planning algorithms at the University of California Riverside, he has been creating applications using C++ for a decade.

Learning Objectives

By the end of this book, you will be able to:

Build applications using hash tables, dictionaries, and setsImplement a URL shortening service using a bloom filterApply common algorithms such as heapsort and merge-sort for string data typesUse C++ template metaprogramming to write code librariesExplore how modern hardware affects the actual runtime performance of programsUse appropriate modern C++ idioms such as std::array, instead of C-style arrays

Audience

This book is intended for developers or students who want to revisit basic data structures and algorithm design techniques. Although no mathematical background is required, some basic knowledge of complexity classes and Big O notation, along with a qualification in an algorithms course, will help you get the most out of this book. Familiarity with the C++ 14 standard is assumed.

Approach

This book uses a practical and hands-on approach to explain various concepts. Through exercises, the book shows that different data structures that theoretically should perform similarly actually perform quite differently on modern computers. The book does not delve into any theoretical analyses and instead focuses on benchmarking and practical results.

Hardware Requirements

For the optimal student experience, we recommend the following hardware configuration:

Any entry-level PC/Mac with Windows, Linux, or macOS is sufficientProcessor: Intel Core 2 Duo, Athlon X2, or betterMemory: 4 GB RAMStorage: 10 GB available space

Software Requirements

You'll also need the following software installed in advance:

Operating system: Windows 7 SP1 32/64-bit, Windows 8.1 32/64-bit, or Windows 10 32/64-bit, Ubuntu 14.04 or later, or macOS Sierra or laterBrowser: Google Chrome or Mozilla FirefoxAny modern compiler and IDE (optional) that supports the C++ 14 standard.

Installation and Setup

Before you embark on this book, install the following libraries used in this book. You will find the steps to install these here:

Installing Boost libraries:

Some exercises and activities in the book require the Boost C++ libraries. You can find the libraries, as well as the installation instructions, on the following links:

Windows: https://www.boost.org/doc/libs/1_71_0/more/getting_started/windows.html

Linux/macOS: https://www.boost.org/doc/libs/1_71_0/more/getting_started/unix-variants.html

Installing the Code Bundle

Copy the code bundle for the class to the C:/Code folder.

Additional Resources

The code bundle for this book is also hosted on GitHub at https://github.com/TrainingByPackt/CPP-Data-Structures-and-Algorithm-Design-Principles.

We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

1. Lists, Stacks, and Queues

Learning Objectives

By the end of this chapter, you will be able to:

Describe the importance of using the right data structure in any applicationImplement various built-in data structures, depending on the problem, to make application development easierImplement a custom linear data structure suited for given situations if the ones provided by C++ are not good enough for the use caseAnalyze real-life problems where different types of linear data structures are helpful and decide which one will be the most suitable for a given use case

This chapter describes the importance of using the right data structures in any application. We will learn how to use some of the most common data structures in C++, as well as built-in and custom containers, using these structures.