Book Image

C++ Data Structures and Algorithm Design Principles

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

C++ Data Structures and Algorithm Design Principles

By: John Carey, 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)

std::array

std::array automates the allocation and deallocation of memory. std::array is a templatized class that takes two parameters – the type of the elements and the size of the array.

In the following example, we will declare std::array of int of size 10, set the value of any of the elements, and then print that value to make sure it works:

std::array<int, 10> arr;        // array of int of size 10

arr[0] = 1;                    // Sets the first element as 1

std::cout << "First element: " << arr[0] << std::endl;

std::array<int, 4> arr2 = {1, 2, 3, 4};

std::cout << "Elements in second array: ";

for(int i = 0; i < arr.size(); i++)

    std::cout << arr2[i] << " ";

This example would produce the following output:

First element: 1

Elements in second array: 1 2 3 4

As we can see, std::array provides operator[], which is same as the C-style array, to avoid the cost of checking whether the index is less than the size of the array. Additionally, it also provides a function called at(index), which throws an exception if the argument is not valid. In this way, we can handle the exception in an appropriate manner. So, if we have a piece of code where we will be accessing an element with a bit of uncertainty, such as an array index being dependent on user input, we can always catch the error using exception handling, as demonstrated in the following example.

try

{

    std::cout << arr.at(4);    // No error

    std::cout << arr.at(5);    // Throws exception std::out_of_range

}

catch (const std::out_of_range& ex)

{

    std::cerr << ex.what();

}

Apart from that, passing std::array to another function is similar to passing any built-in data type. We can pass it by value or reference, with or without const. Additionally, the syntax doesn't involve any pointer-related operations or referencing and de-referencing operations. Hence, the readability is much better compared to C-style arrays, even for multidimensional arrays. The following example demonstrates how to pass an array by value:

void print(std::array<int, 5> arr)

{

    for(auto ele: arr)

    {

        std::cout << ele << ", ";

    }

}

std::array<int, 5> arr = {1, 2, 3, 4, 5};

print(arr);

This example would produce the following output:

1, 2, 3, 4, 5

We can't pass an array of any other size for this function, because the size of the array is a part of the data type of the function parameter. So, for example, if we pass std::array<int, 10>, the compiler will return an error saying that it can't match the function parameter, nor can it convert from one to the other. However, if we want to have a generic function that can work with std::array of any size, we can make the size of the array templatized for that function, and it will generate code for all the required sizes of the array. So, the signature will look like the following:

template <size_t N>

void print(const std::array<int, N>& arr)

Apart from readability, while passing std::array, it copies all the elements into a new array by default. Hence, an automatic deep copy is performed. If we don't want that feature, we can always use other types, such as reference and const reference. Thus, it provides greater flexibility for programmers.

In practice, for most operations, std::array provides similar performance as a C-style array, since it is just a thin wrapper to reduce the effort of programmers and make the code safer. std::array provides two different functions to access array elements – operator[] and at(). operator[], is similar to C-style arrays, and doesn't perform any check on the index. However, the at() function provides a check on the index, and throws an exception if the index is out of range. Due to this, it is a bit slower in practice.

As mentioned earlier, iterating over an array is a very common operation. std::array provides a really nice interface with the help of a range for loops and iterators. So, the code for printing all the elements in an array looks like this:

std::array<int, 5> arr = {1, 2, 3, 4, 5};

for(auto element: arr)

{

    std::cout << element << ' ';

}

This example would show the following output:

1 2 3 4 5

In the preceding example, when we demonstrated printing out all of the elements, we iterated using an index variable, where we had to make sure that it was correctly used according to the size of the array. Hence, it is more prone to human error compared to this example.

The reason we can iterate over std::array using a range-based loop is due to iterators. std::array has member functions called begin() and end(), returning a way to access the first and last elements. To move from one element to the next element, it also provides arithmetic operators, such as the increment operator (++) and the addition operator (+). Hence, a range-based for loop starts at begin() and ends at end(), advancing step by step using the increment operator (++). The iterators provide a unified interface across all of the dynamically iterable STL containers, such as std::array, std::vector, std::map, std::set, and std::list.

Apart from iterating, all the functions for which we need to specify a position inside the container are based on iterators; for example, insertion at a specific position, deletion of elements in a range or at a specific position, and other similar functions. This makes the code more reusable, maintainable, and readable.

Note

For all functions in C++ that specify a range with the help of iterators, the start() iterator is usually inclusive, and the end() iterator is usually exclusive, unless specified otherwise.

Hence, the array::begin() function returns an iterator that points to the first element, but array::end() returns an iterator just after the last element. So, a range-based loop can be written as follows:

for(auto it = arr.begin(); it != arr.end(); it++)

{

    auto element = (*it);

    std::cout << element << ' ';

}

There are some other forms of iterators, such as const_iterator and reverse_iterator, which are also quite useful. const_iterator is a const version of the normal iterator. If the array is declared to be a const, its functions that are related to iterators, such as begin() and end(), return const_iterator.

reverse_iterator allows us to traverse the array in the reverse direction. So, its functions, such as the increment operator (++) and advance, are inverses of such operations for normal iterators.

Besides the operator[] and at() functions, std::array also provides other accessors, as shown in the following table:

Figure 1.6: Table showing some accessors for std::array

The following snippet demonstrates how these functions are used:

std::array<int, 5> arr = {1, 2, 3, 4, 5};

std::cout << arr.front() << std::endl;       // Prints 1

std::cout << arr.back() << std::endl;        // Prints 5

std::cout << *(arr.data() + 1) << std::endl; // Prints 2

Another useful functionality provided by std::array is the relational operator for deep comparison and the copy-assignment operator for deep copy. All size operators (<, >, <=, >=, ==, !=) are defined for std::array to compare two arrays, provided the same operators are also provided for the underlying type of std::array.

C-style arrays also support all the relational operators, but these operators don't actually compare the elements inside the array; in fact, they just compare the pointers. Therefore, just the address of the elements is compared as integers instead of a deep comparison of the arrays. This is also known as a shallow comparison, and it is not of much practical use. Similarly, assignment also doesn't create a copy of the assigned data. Instead, it just makes a new pointer that points to the same data.

Note

Relational operators work for std::array of the same size only. This is because the size of the array is a part of the data type itself, and it doesn't allow values of two different data types to be compared.

In the following example, we shall see how to wrap a C-style array, whose size is defined by the user.

Exercise 1: Implementing a Dynamic Sized Array

Let's write a small application to manage the student records in a school. The number of students in a class and their details will be given as an input. Write an array-like container to manage the data, which can also support dynamic sizing. We'll also implement some utility functions to merge different classes.

Perform the following steps to complete the exercise:

  1. First, include the required headers:

    #include <iostream>

    #include <sstream>

    #include <algorithm>

  2. Now, let's write a basic templated structure called dynamic_array, as well as primary data members:

    template <typename T>

    class dynamic_array

    {

        T* data;

        size_t n;

  3. Now, let's add a constructor that takes the size of the array and copies it:

    public:

    dynamic_array(int n)

    {

        this->n = n;

        data = new T[n];

    }

        dynamic_array(const dynamic_array<T>& other)

      {

        n = other.n;

        data = new T[n];

        for(int i = 0; i < n; i++)

        data[i] = other[i];

      }

  4. Now, let's add operator[] and function() in the public accessor to support the access of data directly, in a similar way to std::array:

    T& operator[](int index)

    {

        return data[index];

    }

    const T& operator[](int index) const

    {

        return data[index];

    }

    T& at(int index)

    {

        if(index < n)

        return data[index];

        throw "Index out of range";

    }

  5. Now, let's add a function called size() to return the size of the array, as well as a destructor to avoid memory leaks:

    size_t size() const

    {

        return n;

    }

    ~dynamic_array()

    {

        delete[] data;   // A destructor to prevent memory leak

    }

  6. Now, let's add iterator functions to support range-based loops to iterate over dynamic_array:

    T* begin()

    {

        return data;

    }

    const T* begin() const

    {

        return data;

    }

    T* end()

    {

        return data + n;

    }

    const T* end() const

    {

        return data + n;

    }

  7. Now, let's add a function to append one array to another using the + operator. Let's keep it as a friend function for better usability:

    friend dynamic_array<T> operator+(const dynamic_array<T>& arr1, dynamic_array<T>& arr2)

    {

        dynamic_array<T> result(arr1.size() + arr2.size());

        std::copy(arr1.begin(), arr1.end(), result.begin());

        std::copy(arr2.begin(), arr2.end(), result.begin() + arr1.size());

        return result;

    }

  8. Now, let's add a to_string function that takes a separator as a parameter with the default value as ",":

    std::string to_string(const std::string& sep = ", ")

    {

      if(n == 0)

        return "";

      std::ostringstream os;

      os << data[0];

      for(int i = 1; i < n; i++)

        os << sep << data[i];

      return os.str();

    }

    };

  9. Now, let's add a struct for students. We'll just keep the name and the standard (that is, the grade/class in which the student is studying) for simplicity, and also add operator<< to print it properly:

    struct student

    {

        std::string name;

        int standard;

    };

    std::ostream& operator<<(std::ostream& os, const student& s)

    {

        return (os << "[Name: " << s.name << ", Standard: " << s.standard << "]");

    }

  10. Now, let's add a main function to use this array:

    int main()

    {

        int nStudents;

        std::cout << "Enter number of students in class 1: ";

        std::cin >> nStudents;

    dynamic_array<student> class1(nStudents);

    for(int i = 0; i < nStudents; i++)

    {

        std::cout << "Enter name and class of student " << i + 1 << ": ";

        std::string name;

        int standard;

        std::cin >> name >> standard;

        class1[i] = student{name, standard};

    }

    // Now, let's try to access the student out of range in the array

    try

    {

        class1[nStudents] = student{"John", 8};  // No exception, undefined behavior

        std::cout << "class1 student set out of range without exception" << std::endl;

        class1.at(nStudents) = student{"John", 8};  // Will throw exception

    }

    catch(...)

    {

    std::cout << "Exception caught" << std::endl;

    }

    auto class2 = class1;  // Deep copy

        std::cout << "Second class after initialized using first array: " << class2.to_string() << std::endl;

        auto class3 = class1 + class2;

        // Combines both classes and creates a bigger one

        std::cout << "Combined class: ";

        std::cout << class3.to_string() << std::endl;

        return 0;

    }

  11. Execute the preceding code with three students – Raj(8), Rahul(10), and Viraj(6) as input. The output looks like the following in the console:

    Enter number of students in class 1 : 3

    Enter name and class of student 1: Raj 8

    Enter name and class of student 2: Rahul 10

    Enter name and class of student 3: Viraj 6

    class1 student set out of range without exception

    Exception caught

    Second class after initialized using first array : [Name: Raj, Standard: 8], [Name: Rahul, Standard: 10], [Name: Viraj, Standard: 6]

    Combined class : [Name: Raj, Standard: 8], [Name: Rahul, Standard: 10], [Name: Viraj, Standard: 6], [Name: Raj, Standard: 8], [Name: Rahul, Standard: 10], [Name: Viraj, Standard: 6]

    Most of the functions mentioned here have a similar implementation to that of std::array.

Now that we have seen various containers, we shall learn how to implement a container that can accept any kind of data and store it in a common form in the following exercise.

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

In this exercise, we will write a function that takes any number of elements of any type, which can, in turn, be converted into a common type. The function should also return a container having all the elements converted into that common type, and it should also be fast to traverse:

  1. Let's begin by including the required libraries:

    #include <iostream>

    #include <array>

    #include <type_traits>

  2. First, we'll try to build the signature of the function. Since the return type is a container that is fast to traverse, we'll go ahead with std::array. To allow any number of parameters, we'll use variadic templates:

    template<typename ... Args>

    std::array<?,?> build_array(Args&&... args)

    Considering the requirement that the container should be fast to traverse for the return type, we can choose an array or a vector. Since the number of elements is known at the compile time based on the number of parameters to the function, we can go ahead with std::array.

  3. Now, we must provide the type of the elements and the number of elements for std::array. We can use the std::common_type template to find out what the type of elements inside std::array will be. Since this is dependent on arguments, we'll provide the return type of the function as a trailing type:

    template<typename ... Args>

    auto build_array(Args&&... args) -> std::array<typename std::common_type<Args...>::type, ?>

    {

        using commonType = typename std::common_type<Args...>::type;

        // Create array

    }

  4. As shown in the preceding code, we now need to figure out two things – the number of elements, and how to create the array with commonType:

    template< typename ... Args>

    auto build_array(Args&&... args) -> std::array<typename std::common_type<Args...>::type, sizeof...(args)>

    {

        using commonType = typename std::common_type<Args...>::type;

        return {std::forward<commonType>(args)...};

    }

  5. Now, let's write the main function to see how our function works:

    int main()

    {

        auto data = build_array(1, 0u, 'a', 3.2f, false);

        for(auto i: data)

            std::cout << i << " ";

        std::cout << std::endl;

    }

  6. Running the code should give the following output:

    1 0 97 3.2 0

    As we can see, all final output is in the form of float, since everything can be converted to float.

  7. To test this further, we can add the following inside the main function and test the output:

    auto data2 = build_array(1, "Packt", 2.0);

    With this modification, we should get an error saying that all the types can't be converted to a common type. The exact error message should mention that template deduction has failed. This is because there is no single type in which we can convert both the string and number.

Builder functions, such as the one we have created in this exercise, can be used when you are not sure about the type of data, yet you need to optimize efficiency.

There are a lot of useful features and utility functions that std::array doesn't provide. One major reason for this is to maintain similar or better performance and memory requirements compared to C-style arrays.

For more advanced features and flexibility, C++ provides another structure called std::vector. We will examine how this works in the next section.