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

• Verlag: Packt Publishing
• Jahr: 2019
• ISBN:
  9781838827915
• Auflage: 1
• Thema: Informatik
• Thema: Programmierung in C++

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.

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 application
• Implement various built-in data structures, depending on the problem, to make application development easier
• Implement a custom linear data structure suited for given situations if the ones provided by C++ are not good enough for the use case
• Analyze 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.

Introduction

The management of data is one of the most important considerations to bear in mind while designing any application. The purpose of any application is to get some data as input, process or operate on it, and then provide suitable data as output. For example, let's consider a hospital management system. Here, we could have data about different doctors, patients, and archival records, among other things. The hospital management system should allow us to perform various operations, such as admit patients, and update the joining and leaving of doctors of different specialties. While the user-facing interface would present information in a format that is relevant to the hospital administrators, internally, the system would manage different records and lists of items.

A programmer has at their disposal several structures to hold any data in the memory. The choice of the right structure for holding data, also known as a data structure, is crucial for ensuring reliability, performance, and enabling the required functionalities in the application. Besides the right data structures, the right choice of algorithms to access and manipulate the data is also necessary for the optimal behavior of the application. This book shall equip you with the ability to implement the right data structures and algorithms for your application design, in order to enable you to develop well-optimized and scalable applications.

This chapter introduces basic and commonly used linear data structures provided in C++. We will look at their individual designs, pros, and cons. We will also implement said structures with the help of exercises. Understanding these data structures will help you to manage data in any application in a more performant, standardized, readable, and maintainable way.

Linear data structures can be broadly categorized as contiguous or linked structures. Let's understand the differences between the two.

Contiguous Versus Linked Data Structures

Before processing the data in any application, we must decide how we want to store data. The answer to that question depends on what kind of operations we want to perform on the data and the frequency of the operations. We should choose the implementation that gives us the best performance in terms of latency, memory, or any other parameter, without affecting the correctness of the application.

A useful metric for determining the type of data structure to be used is algorithmic complexity, also called time complexity. Time complexity indicates the relative amount of time required, in proportion to the size of the data, to perform a certain operation. Thus, time complexity shows how the time will vary if we change the size of the dataset. The time complexity of different operations on any data type is dependent on how the data is stored inside it.

Data structures can be divided into two types: contiguous and linked data structures. We shall take a closer look at both of them in the following sections.

Contiguous Data Structures

As mentioned earlier, contiguous data structures store all the elements in a single chunk of memory. The following diagram shows how data is stored in contiguous data structures:

Figure 1.1: Diagrammatic representation of contiguous data structures

In the preceding diagram, consider the larger rectangle to be the single memory chunk in which all the elements are stored, while the smaller rectangles represent the memory allocated for each element. An important thing to note here is that all the elements are of the same type. Hence, all of them require the same amount of memory, which is indicated by sizeof(type). The address of the first element is also known as the Base Address (BA). Since all of them are of the same type, the next element is present in the BA + sizeof(type) location, and the one after that is present in BA + 2 * sizeof(type), and so on. Therefore, to access any element at index i, we can get it with the generic formula: BA + i * sizeof(type).

In this case, we can always access any element using the formula instantly, regardless of the size of the array. Hence, the access time is always constant. This is indicated by O(1) in the Big-O notation.

The two main types of arrays are static and dynamic. A static array has a lifetime only inside its declaration block, but a dynamic array provides better flexibility since the programmer can determine when it should be allocated and when it should be deallocated. We can choose either of them depending on the requirement. Both have the same performance for different operations. Since this array was introduced in C, it is also known as a C-style array. Here is how these arrays are declared:

• A static array is declared as int arr[size];.
• A dynamic array in C is declared as int* arr = (int*)malloc(size * sizeof(int));.
• A dynamic array is declared in C++ as int* arr = new int[size];.

A static array is aggregated, which means that it is allocated on the stack, and hence gets deallocated when the flow goes out of the function. On the other hand, a dynamic array is allocated on a heap and stays there until the memory is freed manually.

Since all the elements are present next to each other, when one of the elements is accessed, a few elements next to it are also brought into the cache. Hence, if you want to access those elements, it is a very fast operation as the data is already present in the cache. This property is also known as cache locality. Although it doesn't affect the asymptotic time complexity of any operations, while traversing an array, it can give an impressive advantage for contiguous data in practice. Since traversing requires going through all the elements sequentially, after fetching the first element, the next few elements can be retrieved directly from the cache. Hence, the array is said to have good cache locality.

Linked Data Structures

Linked data structures hold the data in multiple chunks of memory, also known as nodes, which may be placed at different places in the memory. The following diagram shows how data is stored in linked data structures:

Figure 1.2: Linked data structures

In the basic structure of a linked list, each node contains the data to be stored in that node and a pointer to the next node. The last node contains a NULL pointer to indicate the end of the list. To reach any element, we must start from the beginning of the linked list, that is, the head, and then follow the next pointer until we reach the intended element. So, to reach the element present at index i, we need to traverse through the linked list and iterate i times. Hence, we can say that the complexity of accessing elements is O(n); that is, the time varies proportionally with the number of nodes.

If we want to insert or delete any element, and if we have a pointer to that element, the operation is really small and quite fast for a linked list compared to arrays. Let's take a look at how the insertion of an element works in a linked list. The following diagram illustrates a case where we are inserting an element between two elements in a linked list:

Figure 1.3: Inserting an element into a linked list

For insertion, once we've constructed the new node to be inserted, we just need to rearrange the links so that the next pointer of the preceding element (i = 1) points to the new element (i = 2) instead of its current element (i = 3), ...