Book Image

C++ Data Structures and Algorithm Design Principles

By : John Carey, Anil Achary, Shreyans Doshi, Payas Rajan
Book Image

C++ Data Structures and Algorithm Design Principles

By: John Carey, Anil Achary, Shreyans Doshi, Payas Rajan

Overview of this 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.
Table of Contents (11 chapters)


As we have seen that different containers have a variety of pros and cons, no one container is the perfect choice for every situation. Sometimes, multiple containers may give a similar performance on average for the given scenario. In such cases, benchmarking is our friend. This is a process of determining the better approach based on statistical data.

Consider a scenario where we want to store data in contiguous memory, access it, and operate on it using various functions. We can say that we should either use std::vector or std::deque. But we are not sure which among these will be the best. At first glance, both of them seem to give good performance for the situation. Among different operations, such as access, insertion, push_back, and modifying a specific element, some are in favor of std::vector and some of are in favor of std::deque. So, how should we proceed?

The idea is to create a small prototype of the actual model and implement it using both std::vector and std::deque. And then, measure the performance of both over the prototype. Based on the result of the performance testing, we can choose the one that gives better results overall.

The simplest way to do that is to measure the time required to perform different operations for both and compare them. However, the same operation may take different amounts of time during different runs, since there are other factors that come into the picture, such as OS scheduling, cache, and interrupts, among others. These parameters can cause our results to deviate quite heavily, because, to perform any operation once, is a matter of a few hundred nanoseconds. To overcome that, we can perform the operation multiple times (by that, we mean a few million times) until we get a considerable time difference between both the measurements.

There are some benchmarking tools that we can use, such as, which provide us with an easy way to run benchmarks. You can try running the operations mentioned earlier on vector and deque to quickly compare the performance differences.

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

In this activity, we'll simulate a queue for a shared printer in an office. In any corporate office, usually, the printer is shared across the whole floor in the printer room. All the computers in this room are connected to the same printer. But a printer can do only one printing job at any point in time, and it also takes some time to complete any job. In the meantime, some other user can send another print request. In such a case, a printer needs to store all the pending jobs somewhere so that it can take them up once its current task is done.

Perform the following steps to solve the activity:

  1. Create a class called Job (comprising an ID for the job, the name of the user who submitted it, and the number of pages).
  2. Create a class called Printer. This will provide an interface to add new jobs and process all the jobs added so far.
  3. To implement the printer class, it will need to store all the pending jobs. We'll implement a very basic strategy – first come, first served. Whoever submits the job first will be the first to get the job done.
  4. Finally, simulate a scenario where multiple people are adding jobs to the printer, and the printer is processing them one by one.


    The solution to this activity can be found on page 487.