7. Algorithm, Data Structure, Collection Framework and Standard Template Library (STL)
Algorithm is expressed as a set of steps. By describing the actions at each step we instruct the computer do something. Usually we can use any natural language to describe the actions to perform at each step.
Consider this simple description.
1 1. Enter one integer
2 2. Enter another integer
3 3. Compare both integers and return the maximum value
4 4. Compare both integers and return the minimum value
In C++ programming language, on one hand, we can create generic functions to find the maximum or minimum value; and, on the other, we can take help from the ‘algorithm’ template library to find the same values.
Every high level language comes with its own algorithm library. They do so for one reason. Any system of counting or calculation by means of a device like computer involves following a steps or directions. Computer scientists use the word ‘algorithm’ to describe such as ‘set of directions’.
In some cases, these directions could be simple as described above. In most cases, it is much more complex. For complex cases, we need the help of ‘algorithm’ library. Otherwise, we have to do the low-level plumbing, which is much more time consuming and that takes us away from building other important parts of any application. Historically, the derivation of this word has some interesting facts.
At the beginning of ninth century a mathematician wrote a book called ‘Kitab al jabr w’al muqabala’ (Rules of Restoration and Reduction). The word ‘algebra’ comes from the title of the book. This textbook introduced the use of Hindu numerals and included a systematic discussion of fundamental operations on integers.
The word ‘algorithm’ comes from the name of the mathematician, Abu Ja’far Mohammed ibn Musa al-Khowarizmi.
One of the most famous and well known algorithms is of course Euclid’s Algorithm. It is a process for calculating the greatest common divisor (GCD) of two integers.
We can illustrate this algorithm in the following way.
1 1. Take two integers x and y
2 2. Divide y by x and get the remainder as r
3 3. Now replace the value of x with the value of r and replace the value of y with th\
4 e value of x
5 4. Again divide y by x
6 5. This process will continue until we get r = 0
7 6. Once we get r = 0, stop the calculation, x is the GCD
Notice that the algorithm is expressed as a set of steps. Each step describes some action to take. The important thing is to describe the actions to be performed clearly and unambiguously.
Let us summarize this introductory part on algorithm in one sentence.
Data go inside the computer as inputs, algorithm takes charge, processing the data and after that the data as outputs come out.
By the way, people often mistake the word ‘data’ as singular; but, it is actually a plural form of the Latin word ‘datum’. Since we have used this word too often in our discourse, and will use in future, therefore, for the curious readers I opened up the Oxford dictionary and searched for the word: datum.
Oxford dictionary defines datum as “A thing given or granted; a thing known or assumed as a fact, and made the basis of reasoning or calculation; a fixed starting-point for a series of measurements etc.” It has also made it clear that the plural form of ‘datum’ is ‘data’.
For instance, in Java we have Collection class and in C++ we have containers that manage this data structure part.
We are going to find out how they are related to algorithm.
Introducing Algorithm Library
Now, we have an idea about how algorithm works. For a computer, it is ‘set of steps, or directions, or instructions’. For a chef it is a recipe.
Is not it?
In real world, when somebody asks directions to go to a certain place, we always try to help by giving that person a set of directions.
Right?
In the Google map, same thing happens, but in a different way.
There are trillions of algorithms working worldwide, may be more. As time passes by, it will increase. Quite naturally; because the volume of data increases; we need to structure those data in a more organized way. So we need things like ‘container classes’ in C++ or Collection framework in language like Java. We will discuss them in great detail in this chapter, along with algorithm, and discrete mathematics.
Moreover, it is clear that to avoid low-level plumbing for a huge volume of data we need algorithm libraries. For a small set of data we can manage it by manually, but for a IT product company, it needs very specialized algorithms, to put it eloquently, very complex algorithms that will deliver their complex products successfully.
Let us see two code snippets in C++ to understand why we need algorithm library. It is a component of Standard Template Library (STL). It provides many generic versions of standard algorithms that replace our low-level plumbing.
The first example shows us a simple program where we take two integers from the users and gives the output of the maximum and minimum values.
1 // code 7.1
2 #include <iostream>
3 #include <string>
4 using namespace std;
5
6 int Maximum(int a, int b){
7 if(a < b){
8 return b;
9 } else {
10 return a;
11 }
12 }
13
14 int Minimum(int a, int b){
15 if(a > b){
16 return b;
17 } else {
18 return a;
19 }
20 }
21
22 int EnterAndGet(){
23 std::cout << "Please enter a number (integer): " << '\n';
24 int Recieve;
25 std::cin >> Recieve;
26 return Recieve;
27 }
28
29 int main(int argc, char const *argv[]) {
30 /* code */
31 int valueOne = EnterAndGet();
32 int valueTwo = EnterAndGet();
33 std::cout << "Maximum value: " << Maximum(valueOne, valueTwo) << '\n';
34 std::cout << "Minimum value: " << Minimum(valueOne, valueTwo) << '\n';
35 return 0;
36 }
Running the program prompts us to give two integers. We enter two integers, and we get the maximum and the minimum values.
However, we could have tackled the same problem with less lines of code, if we used the C++ algorithms libraries. Let us see the next code snippets.
1 // code 7.2
2 #include <iostream>
3 #include <string>
4 #include <algorithm>
5 using namespace std;
6
7 int EnterAndGet(){
8 std::cout << "Please enter a number (integer): " << '\n';
9 int Recieve;
10 std::cin >> Recieve;
11 return Recieve;
12 }
13
14 int main(int argc, char const *argv[]) {
15 /* code */
16 int valueOne = EnterAndGet();
17 int valueTwo = EnterAndGet();
18 std::cout << "Maximum value: " << max(valueOne, valueTwo) << '\n';
19 std::cout << "Minimum value: " << min(valueOne, valueTwo) << '\n';
20 return 0;
21 }
Adding the algorithm header file on the top of our code makes all the difference. Now we can use the max() and min() methods; the libraries take all the load of low-level plumbing. With the less lines of code we get the same result.
In this particular point of our discourse, we need to understand one key concept. Every high level language tries to solve the same problem in their own way using their own framework or libraries.
There are some common algorithmic terms, such as ‘sort’, ‘shuffle’, or ‘search’.
In Java, the algorithms come from the Collection class and the great majority of the algorithms provided by the Java platform operate on List instances. A few of them also operate on arbitrarily chosen Collection instances.
Let us see one example where we sort a list of alphabets in ascending order.
1 // code 7.3
2 //Java
3 package fun.sanjibsinha.chapter7;
4
5 import java.util.Arrays;
6 import java.util.Collections;
7 import java.util.List;
8
9 public class SortExampleOne {
10
11 public static void main(String[] args) {
12
13 List<String> list = Arrays.asList("x", "n", "y", "a", "s", "j");
14 Collections.sort(list);
15 System.out.println(list);
16 }
17 }
The algorithm described above takes the form of static methods whose first argument is the collection on which the operation is to be performed. Running the above code gives us the following output:
1 //output of 7.3
2
3 [a, j, n, s, x, y]
When the volume of the list is small, we can do the low-level plumbing, although it is wise to take help from the Algorithm Library in case of a very large volume of data.
Watch the following code snippets:
1 // code 7.4
2 package fun.sanjibsinha.chapter7;
3
4 import java.util.Arrays;
5
6 public class SortExampleTwo {
7
8 public static void main(String[] args) {
9
10 int[] anyArray = {210, 45, 258, 326, -12, 0, 89, 4, 9};
11 System.out.println("Before Sorting : ");
12 System.out.println(Arrays.toString(anyArray));
13 System.out.println("After Sorting : ");
14 for (int i = 0; i < anyArray.length; i++){
15 int index = i;
16 for (int j = i + 1; j < anyArray.length; j++)
17 if (anyArray[j] < anyArray[index])
18 index = j;
19
20 int smallerNumber = anyArray[index];
21 anyArray[index] = anyArray[i];
22 anyArray[i] = smallerNumber;
23 System.out.println(anyArray[i]);
24 }
25 }
26 }
Here goes the output with the elements in ascending order.
1 //output of 7.4
2 Before Sorting :
3 [210, 45, 258, 326, -12, 0, 89, 4, 9]
4 After Sorting :
5 -12
6 0
7 4
8 9
9 45
10 89
11 210
12 258
13 326
The above program shows us reordering a List so that its elements are in ascending order according to an ordering relationship. However, to do that we need to hard code from the scratch. It is not necessary. We could have used Java Collection framework and manage to do the same operations by the following code snippets.
1 // code 7.5
2 package fun.sanjibsinha.chapter7;
3 import java.util.Arrays;
4 import java.util.Collections;
5 import java.util.List;
6 public class SortExampleThree {
7
8 public static void main(String[] args) {
9
10 List<Integer> list = Arrays.asList(210, 45, 258, 326, -12, 0, 89, 4, 9);
11 Collections.sort(list);
12 System.out.println(list);
13 }
14
15 }
16
17 //output of 7.5
18 [-12, 0, 4, 9, 45, 89, 210, 258, 326]
We can do the same thing in C++ programming language. C++ Standard Template Library stands between algorithm and containers (data structure) and manages them wisely. We will discuss them in great detail in this chapter. At the same time we will dig deep into the Collection Framework of Java; as Java does the same thing in its own way.
Comparing these two great programming languages we will have a better understanding of how algorithm and data structures are related.
Let us see the same code snippets in C++.
1 // code 7.6
2 #include <algorithm>
3 #include <array>
4 #include <iostream>
5
6 int main()
7 {
8 std::array<int, 9> standardArray = {210, 45, 258, 326, -12, 0, 89, 4, 9}
9
10 // sort using the default operator
11 std::sort(standardArray.begin(), standardArray.end());
12 for (auto autoVariable : standardArray) {
13 std::cout << autoVariable << " ";
14 }
15 std::cout << '\n';
16
17 // sort using a standard library compare function object
18 std::sort(standardArray.begin(), standardArray.end(), std::greater<int>());
19 for (auto autoVariable : standardArray) {
20 std::cout << autoVariable << " ";
21 }
22 std::cout << '\n';
23 }
As you see in the above code snippets, the std::sort() method by default takes two arguments-the beginning point and the end point. After that, it puts the list in ascending order. We do not have to reinvent the wheel as we did in the Java code snippets (code 7.4). Besides putting a collection of integers in ascending order, we may turn the order inside out. C++ Standard Template Library lets us do that by passing another argument.
1 std::sort(standardArray.begin(), standardArray.end(), std::greater<int>());
Therefore, we get the following output, where the unordered list is ordered in ascending and descending orders both.
1 //output of 7.6
2 -12, 0, 4, 9, 45, 89, 210, 258, 326
3 326, 258, 210, 89, 45, 9, 4, 0, -12
Hopefully we have understood the basic conceptions regarding the algorithm libraries. In this section we have also learned how algorithm and data structures are related.
We will learn more about this in the coming sections.
Different types of Algorithms
There are many types of algorithm; as intermediate learners of computer science, you may have heard about them, and probably used some of them. In this section, we are neither going to learn them by heart, nor we will discuss them one after another.
We simply cannot do that. Even we could do that, we would not even try to do that because most of the examples are available in open source, and they are all over there in the internet.
In my opinion, the best thing we should do is to understand the core conceptions of different types of algorithms, and after that we can try to apply them to solve different types of problems.
We are not going to define algorithm again, we have already learned that ‘set of directions’ or ‘set of steps’ is called algorithm. It is true for everything; as long as algorithm is concerned, humans and computers look utterly alike. They all need directions to do something meaningful.
Some of the better known algorithms are Recursive algorithms, dynamic programming algorithms, Brute Force algorithms, etc.
There is no eternal endpoint for learning algorithm; therefore, especially for basic cognitive process to pick up algorithm, the learning curve is really steep. A steep learning curve will always try to shed you from its roof, just like a steep roof sheds snow; if you want to go the top, and want to master the art of writing your own algorithm, you need to work hard to solve different types of problems.
Recursive Algorithm
Semantically, when we say that a function calls itself directly or indirectly, it is called recursion. However, if we want to put it in an algorithmic way, we should write that ‘it is a set of directions by which we want to divide a problem and conquer’. We can put it in more eloquent way, ‘decrease the problem and conquer’.
We use one function to call itself, and the corresponding functions are known as recursive functions. But there is a drawback or difficulty that is not evident.
First of all, when a function calls itself, it will call itself endlessly if we do not stop it. Therefore, there should be a mechanism to stop it. Otherwise, it might make things look like eternal looping and cause run time error. We need a base case, so that the mechanism called ‘calling itself’ should progress towards the base case.
The second most important things are ‘space, speed and time’. When a function calls itself again and again, it takes place in the stack. The final code or program might end up as a slow program. We will discuss the pros and cons after we get our head around the recursive algorithm a little bit. Let us try to understand how it works, first.
Suppose using a function we want to print 2 and 1. We can do that two ways-one is iterative way, using loop construct. The another way is the recursive way, allowing the the function to call itself. Consider the code snippet below.
1 //code 7.7
2 void printNumber(int n){
3 if (n == 0) { //this is the base case towards which the method proceeds
4 return;
5 }
6 System.out.println(n);
7 printNumber(n - 1);
8 }
If we call the method “printNumber(2)”, what is going to happen? Let us try to understand the core conception of recursion. When we call the above method, passing the integer parameter 2, three clones are made. The original call should give us 2 as output. But it has made a recursive call creating a clone of the function as the value of ‘n’ is now equal to 1. This call should give us 1 as output. After that, it makes another recursive call and makes the value of ‘n’ equal to 0.
However, that is our base case, and we are making progress towards that base case where we have made a condition so that it goes away and stops calling the function. When we reach the base case, that is the output of ‘n’ is equal to 0, the ‘if’ condition is true and it just returns. If there were no ‘base case’, the stacks would be overflowed. There would be a run time error. The ‘if’ condition or the base case prevents the recursive call from being made again and again.
In our following code snippets we will see some simple examples of recursive functions; then we will move towards the lesser known world of recursion to the unknown world of recursion, solving more complex problems.
The first C++ code snippet will give us a glimpse of recursion in its simplest version. We will move forward to the base case from a given number, and at the same time, we will rearrange the order.
1 //code 7.8
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <algorithm>
13
14 void factorialExampleOne(int n){
15 if(n < 1){
16 return;
17 } else {
18 std::cout << n << "\n";
19 factorialExampleOne(n - 1);
20 std::cout << n << "\n";
21 }
22 }
23
24 int main(int argc, char const *argv[]) {
25
26 std::cout << "Hello World." << "\n";
27 factorialExampleOne(3);
28 return 0;
29 }
We will move from 3 to 1 and vice versa. Here is the output:
1 //output of 7.8
2 Hello World.
3 3
4 2
5 1
6
7 1
8 2
9 3
In the next code snippet, we will manipulate the output by squaring the numbers; it is a test case, it shows that you can do many types of manipulations for your own advantage.
1 //code 7.9
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <algorithm>
13
14 using namespace std;
15
16 void factorialExampleTwo(int n){
17 if(n < 1){
18 return;
19 } else {
20 //pass any integer and get the squared value in descending order
21 cout << n * n << "\n";
22 factorialExampleTwo(n - 1);
23 //reversing the order of the squared integers
24 cout << n * n << "\n";
25 }
26 }
27
28 int main(int argc, char const *argv[]) {
29
30 int n = 4;
31 cout << "Hello World." << "\n";
32 factorialExampleTwo(n);
33 return 0;
34
35 }
The output is quite expected. We have the squared values of the output.
1 //output of 7.9
2 Hello World.
3 16
4 9
5 4
6 1
7
8 1
9 4
10 9
11 16
The manipulation of integers could cause run time error and make the stack overflow if your base case is wrong. Therefore, that should be the most important part when you call a function recursively.
We can call a recursive function indirectly, too. The next code snippet in C++ shows you a simple example.
1 //code 7.10
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <algorithm>
13
14 using namespace std;
15
16 void factorialExampleThree(int n){
17 //cout << "Calling recursion. \n";
18 if(n < 1){
19 return;
20 }else{
21 cout << n << "\n";
22 cout << "Calling recursion. \n";
23 factorialExampleThree(n - 1);
24 //cout << "Calling recursion. \n";
25 }
26 //cout << "Calling recursion. \n";
27 }
28
29 void AnotherRecursion(){
30 cout << "Enter a positive even integer to see more recursion. \n";
31 int a = 0;
32 cin >> a;
33 if(a % 2 == 0){
34 factorialExampleThree(a);
35 } else {
36 cout << "Wrong input!";
37 }
38 }
39
40 int main(int argc, char const *argv[]) {
41
42 int n = 4;
43 cout << "Hello Recursive functions." << "\n";
44 factorialExampleThree(n);
45 cout << "Hello Another Recursive functions." << "\n";
46 AnotherRecursion();
47 return 0;
48
49 }
While calling another recursion, we can test whether that integer is even or odd. Based on that, we can make some more recursive calls.
1 //output of 7.10
2 Hello Recursive functions.
3 4
4 Calling recursion.
5 3
6 Calling recursion.
7 2
8 Calling recursion.
9 1
10 Calling recursion.
11 Hello Another Recursive functions.
12 Enter a positive even integer to see more recursion.
13 8
14 8
15 Calling recursion.
16 7
17 Calling recursion.
18 6
19 Calling recursion.
20 5
21 Calling recursion.
22 4
23 Calling recursion.
24 3
25 Calling recursion.
26 2
27 Calling recursion.
28 1
29 Calling recursion.
Probably you have already noticed that the fee levied for the use of stack memory is enormous. It happens for the memory allocation and re-allocation. When any function is called from main(), the memory is usually allocated to it on the stack, for the recursive calls different copy of local variables or clone is created for each function call. This process continues till the process reaches the base case.
When the same problem is solved using the iterative methods, it consumes less memory, but usually the length of code is bigger than the recursive one. However, for a small problem like finding factors, we cannot even feel the difference.
1 //code 7.11
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <algorithm>
13
14 using namespace std;
15
16 static int i;
17
18 void findFactors(int n, int i){
19 // Checking if the number is less than the input
20 if (i <= n) {
21 if (n % i == 0) {
22 cout << i << " ";
23 }
24 findFactors(n, i + 1);
25 }
26 }
27
28 void findidngFactors(int f){
29 for(i = 1; i <= f; i++){
30 if(f % i == 0){
31 cout << i << "\n";
32 }
33 }
34 }
35
36 int main(int argc, char const *argv[]) {
37
38 cout << "Enter any integer to check factors. \n";
39 int p = 0;
40 cin >> p;
41 findidngFactors(p);
42 cout << "*****";
43 cout << "\n";
44 findFactors(p, 1);
45
46 return 0;
47
48 }
Both the functions give us the same output. Whatever number you pass through the functions, it will give you the same output. There is only one difference. The same thing does not take place in the memory region.
1 //output of 7.11
2 Enter any integer to check factors.
3 119
4 *****
5 1
6 7
7 17
8 119
9 *****
10 1 7 17 119
Some problems, such as tree traversals, or Tower of Hanoi is inherently recursive. Of course the same problems can be solved iterative way with the help of data structures. If you compare the lines of code then recursion takes less and looks cleaner.
In the next problem, we will find the prime factors of any integer. Usually any prime number has only two factors-1, and the number itself. For that reason, they are called prime numbers. Other integers has more than one factors.
Consider a number-6; it has factors, such as 1, 2, 3, and 6. The integer 6 is divisible by all those factors. In this list, not all factors are prime. Only 2 and 3 are prime factors.
In the next code snippet, we will find only the prime factors of any integer, using recursion.
1 //code 7.12
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <algorithm>
13
14 using namespace std;
15
16 void findPrimeFactors(int x)
17 {
18 int a;
19 for(a = 2; a <= x; a++)
20 {
21 if(x % a == 0){
22 cout << a << " ";
23 findPrimeFactors(x / a);
24 break;
25 }
26 }
27 }
28
29 int main(int argc, char const *argv[]) {
30 int number;
31 cout << "\n" << "Enter a number: " << "\n";
32 cin >> number;
33 findPrimeFactors(number);
34 cout << "\n\n";
35
36 return 0;
37
38 }
We have used a loop counter to call the function recursively. We could have written the same code in shorter space if we did not use the loop counter. Instead we could have pass another parameter through the same function.
1 //output of 7.12
2 Enter a number:
3 81
4 3 3 3 3
5 Enter a number:
6 564
7 2 2 3 47
8 Enter a number:
9 45689
10 7 61 107
As you have noticed, to prevent the infinite recursion, we always provide a condition, or base case. The next code snippet, in Java, will give us factorials of any integer.
By using comments, we have pointed out the termination call.
1 //code 7.13
2 package fun.sanjibsinha.recursive;
3
4 public class AlgoRecursiveOne {
5
6 static int getFactorial(int f) {
7 if (f != 0) // termination condition, base case
8 return f * getFactorial(f - 1); // recursive call
9 else
10 return 1;
11 }
12
13 public static void main(String[] args) {
14
15 int number = 4, result;
16 result = getFactorial(number);
17 System.out.println(number + " factorial = " + result);
18
19 }
20
21 }
22 //output of 7.13
23 4 factorial = 24
To get the factorial of 4 we do not have to write a long line of code. It has been managed in a shorter space. However, as the number gets bigger, the output acts like a beggar. The ‘int’ data type has a limit. It is overflowed.
In that case, we can use the ‘long’, the bigger version of ‘int’ data type.
1 //code 7.14
2 package fun.sanjibsinha.recursive;
3
4 import java.util.Scanner;
5
6 public class AlgoRecursiveOne {
7
8 static long i;
9
10 static long getFactorial(long f) {
11 if (f != 0) // termination condition, base case
12 return f * getFactorial(f - 1); // recursive call
13 else
14 return 1;
15 }
16
17 public static void main(String[] args) {
18
19 Scanner sc = new Scanner(System.in);
20 System.out.printf("Enter any positive integer to know its factorial: ");
21 i = sc.nextLong();
22 long result;
23 result = getFactorial(i);
24 System.out.println(i + " factorial = " + result);
25
26 }
27
28 }
29
30
31 //output of 7.14
32 12 factorial = 479001600
33 20 factorial = 2432902008176640000
With the help of recursion, we can solve such problems quite easily. Moreover, we need to write less line of code than we write when we solve the same problems iterative way.
We need to understand one key concept here. Whenever we call a function an active record is maintained. The active record of each call includes spaces in the stack for many further operations. Remember, between calling a function and returning the value, there are several moments; parameters of methods, local variables, returned addresses;so many things are there. And they all want spaces in the stack. When a function is called, its active record is pushed into the stack, but after that, many things happen.
When a function calls recursively, the stacks get busy with many such operations. This overhead of many operations in the stack, makes any recursion slow. It also uses more memory. Keeping all these barriers that impede free movement of memory, we still need recursion.
Why? We will see in a minute.
We are going to compare two code snippets one after another. In the first one, we get the factorials using iterative way.
1 //code 7.15
2 package fun.sanjibsinha.recursive;
3
4 public class AlgoRecursiveTwo {
5
6 static int getFactorial(int f) {
7 if (f == 0){
8 return 1;
9 }
10 int tmp = f;
11 for (int k = f-1; k>=1; k--){
12 tmp = tmp * k;
13 }
14 return (tmp);
15 }
16
17 public static void main(String[] args) {
18 int newNumber = 4, result;
19 result = getFactorial(newNumber);
20 System.out.printf("Factorial of " + newNumber + " = " + result);
21 System.out.printf("");
22 }
23 }
24
25
26 //output of 7.15
27 Factorial of 4 = 24
Now take a look at the same code, written in recursive way.
1 //code 7.16
2 package fun.sanjibsinha.recursive;
3
4 public class AlgoRecursiveThree {
5
6 static int getFactorial(int f) {
7 if (f == 0){
8 return 1;
9 } else {
10 return (f * getFactorial(f - 1));
11 }
12 }
13
14
15 public static void main(String[] args) {
16 int newNumber = 4, result;
17 result = getFactorial(newNumber);
18 System.out.printf("Factorial of " + newNumber + " = " + result);
19 System.out.printf("");
20
21 }
22 }
23
24
25 //output of 7.16
26 Factorial of 4 = 24
The advantage of using recursion is its shortness, cleanliness, and moreover, it is closer to our discrete mathematical definitions. If you think and model your code keeping the mathematical conceptions in your mind, then recursion is close to your definition.
It is more evident when we use recursion in finding the Fibonacci series. Mathematically, the Fibonacci is defined as the following:
1 Fibonacci of 1 or 2 is 1
2 Fibonacci of F (for F > 2) is Fibonacci of (F - 1) + Fibonacci of (F – 2)
If we want to find the Fibonacci series using recursion, it is not only the simplest version, but also mathematically similar.
Watch the next line of code snippet.
1 //code 7.17
2 package fun.sanjibsinha.recursive;
3
4 public class AlgoFibTwo {
5
6 static int getFibonacci(int f) {
7 if ((f == 1) || (f == 2)){
8 return 1;
9 } else {
10 return (getFibonacci(f - 1) + getFibonacci(f - 2));
11 }
12 }
13
14 public static void main(String[] args) {
15
16 int newNumber = 6, result;
17 result = getFibonacci(newNumber);
18 System.out.printf("Fibonacci series of " + newNumber + " = " + result);
19 System.out.printf("");
20 System.out.printf("");
21 }
22
23 }
24
25
26 //output of 7.17
27
28 Fibonacci series of 6 = 8
We can do the same thing using iterative way, but it does not reflect the mathematical conception as the recursion does. The next code snippet shows us the same thing.
1 //code 7.18
2 package fun.sanjibsinha.recursive;
3
4 public class AlgoFibOne {
5
6 static int getFibinacci(int f) {
7 int k1, k2, k3;
8 k1 = k2 = k3 = 1;
9 for (int j = 3; j <= f; j++) {
10 k3 = k1 + k2;
11 k1 = k2;
12 k2 = k3;
13 }
14 return k3;
15 }
16
17 public static void main(String[] args) {
18
19 int newNumber = 6, result;
20 result = getFibinacci(newNumber);
21 System.out.printf("Fibonacci series of " + newNumber + " = " + result);
22 System.out.printf("");
23 System.out.printf("");
24 }
25 }
26
27
28 //output of 7.18
29 Fibonacci series of 6 = 8
Ability to simulate the mathematical models cannot always give the moral support to the recursions. Because there are many other factors while we program, we need to keep them in our mind.
Maintaining that the recursive versions are slower than the iterative versions, we may still want to adopt it for some reasons. When the code is heavy in iterative versions,it is much simpler to adopt the recursions, it also easier to debug and maintain. Whatever our reasons to adopt the recursions, slowing down the program may cost at the end. We cannot save the memory space, we cannot speed up the execution; yet, in some cases, recursions are essential.
As we progress, we will find that later.
Binary Tree and Data Structure
Binary tree is a specialized representation of data structure. Our main purposes of studying data structure is to organize data in the most efficient manner. Binary tree is used for data storage purposes. A tree is represented by nodes that are connected by edges or pointers.
A binary tree has a special condition, which has also made it very special among other data storage mechanisms. A node of binary tree can have maximum two children. When it has one or two children, we call it a sub-tree. Therefore, each node of a sub-tree might have more sub-trees.
When a node of a tree or a sub-tree does not have any children, it is called leaf node.
While traversing a tree, we always take the leaf node as our end point, or base case for recursion. We can search a binary tree as an ordered array. Besides, we can insert and delete data in any binary tree just like a LinkedList.
As we have just said, a tree and its sub-tree always create a sequence of nodes; this sequence is known as path. This path starts from the top of the node, which is referred as root. Always there is only one root and one path to the other node. It has no duplicate path.
The nodes that are placed below, are called children; and, these children nodes always have nodes above them, which are known as parent nodes.
If we consider a root node as the parent node, then it is said that this node is on the level one. The node just below is placed at level two.
Finally, a tree can be traversed in various manners; they are pre-order, post-order and in-order.
There are different algorithms for each kind of tree traversal. In this section, we will take a brief look at those algorithms of tree traversal.
Tree Traversal Algorithm
As we have just learned, in some cases, recursions are essential. Especially when most of the tree based algorithms are concerned, they can be easily implemented using recursion because a binary tree is a recursive data structure. Although it is wise to learn solving the same problems using without recursion; you can solve the tree based algorithms using iteration, also.
In this section, we will learn tree traversals using recursion and using iteration, both. As the tool of our learning, we have chosen Java as programming language. In the following sections, we will take a brief look at other algorithms as well.
A hierarchical tree structure usually represents a set of linked nodes. We can associate an ADT or abstract data type as it simulates the tree structure. It has a root value and the sub-tree of children may be connected with the parent node.
First of all, let us think about an image of tree structure to understand the concept. We will use this image in the following code snippets also.
1 * input:
2 * 1
3 * / \
4 * 2 5
5 * / \ \
6 * 3 4 6
7 *
8 * output: 1 2 3 4 5 6
In the above input section, the collection of nodes start with the root node. Each node is connected with a list of references to children nodes.
This tree structure can be defined recursively; because each node is a data structure consisting of a value that generates the list of references to children nodes.
Although there are other methods to do the binary tree traversal, but the most popular ways to traverse the trees in Java are the pre-order, post-order, and in-order traversal. In this section, we will take a detailed look at each of the traversal methods.
Generally, when you traverse a tree you have three choices-root, left sub-tree, and right sub-tree. In which order you will traverse the tree decides the nature of the algorithm associated with it.
By default a binary tree is a recursive data structure; firstly, it has similarities with LinkedList, which is also a recursive data structure; secondly, if you remove a node, rest of the structure is also a binary tree like left and right binary tree. For that reason, when a function calls itself, it is easier to traverse from one node to the other.
In this section we will limit our discussion to three types of binary tree traversal algorithms; they are pre-order, post-order and in-order.
A tree can be traversed by our algorithm in several ways. In pre-order traversal, it goes this way: root, left and right. In post-order traversal, it goes this way: left, right and root. The in-order traversal traverses the nodes this way: left, root and right.
We have seen how LinkedList works, therefore creating nodes is not difficult. We can start visiting the root node first, then we can move towards the left sub-tree and after that we can proceed towards the right sub-tree.
We should start with the Node class, because a tree has nodes. After that we might use recursion to generate more nodes. The advantage of node is it has left or right pointers that point either to the left side or right side.
To do the pre-order tree traversal, we can use a method like ‘preOrder()’ that will call itself by passing the node object; you can give it any name.
Pre Order Traversal
Let us start with a pre-order tree traversal code snippet, which will give us a clear picture how we can implement our algorithm. By dissecting that code, we will learn how pre-order tree traversal algorithm works. In the first code snippet, we will see how we can traverse the tree without using recursion. We start traversing the tree with the root node, after that we visit the left sub-tree and next, we visit the right sub-tree.
Each sub-tree is also visited pre-order way. That means it starts from the root of the sub-tree, then it goes to the left sub-tree and the above process continues until we reach a leaf node.
The pattern of traversal tells us one thing very clearly; this tree traversal is a good candidate for recursion. After visiting the root node, we can recursively visit the left sub-tree and then, we can visit the right sub-tree recursively again.
Still recursion is not the only way. We can do the traversal using iteration also. The following code snippet shows that example.
1 //code 7.19
2
3 package fun.sanjibsinha.chapter7.binarytree.preordertraversal;
4
5 // we need to use the Stack Collection framework
6 import java.util.Stack;
7
8 public class BinaryTreeWithoutRecursion {
9
10 static class TreeNodeClass {
11 String data;
12 BinaryTreeWithoutRecursion.TreeNodeClass left, right;
13
14 TreeNodeClass(String value) {
15 this.data = value;
16 left = right = null;
17 }
18
19 boolean isLeaf() {
20 return left == null ? right == null : false;
21 }
22
23 }
24
25 // root of the binary tree from where we start our journey
26 BinaryTreeWithoutRecursion.TreeNodeClass root;
27
28 /**
29 * this method will visit tree nodes without recursion.
30 */
31 public void VisitTreeWithoutRecursion() {
32 Stack<BinaryTreeWithoutRecursion.TreeNodeClass> nodes = new Stack<>();
33 nodes.push(root);
34
35 while (!nodes.isEmpty()) {
36 BinaryTreeWithoutRecursion.TreeNodeClass current = nodes.pop();
37 System.out.printf("%s ", current.data);
38
39 if (current.right != null) {
40 nodes.push(current.right);
41 }
42 if (current.left != null) {
43 nodes.push(current.left);
44 }
45 }
46 }
47
48 }
49
50 package fun.sanjibsinha.chapter7.binarytree.preordertraversal;
51
52 /**
53 * In our example: A B C D E F
54 A
55 / \
56 B E
57 / \ \
58 C D F
59
60 */
61
62 public class PreOrderTreeTraversalWithoutRecursion {
63
64 public static void main(String[] args) {
65
66 // construct the binaryTree object to traverse without recursion
67 BinaryTreeWithoutRecursion binaryTree = new BinaryTreeWithoutRecursion();
68 BinaryTreeWithoutRecursion.TreeNodeClass root = new BinaryTreeWithoutRecursi\
69 on.TreeNodeClass("A");
70 binaryTree.root = root;
71 binaryTree.root.left = new BinaryTreeWithoutRecursion.TreeNodeClass("B");
72 binaryTree.root.left.left = new BinaryTreeWithoutRecursion.TreeNodeClass("C"\
73 );
74
75 binaryTree.root.left.right = new BinaryTreeWithoutRecursion.TreeNodeClass("D\
76 ");
77 binaryTree.root.right = new BinaryTreeWithoutRecursion.TreeNodeClass("E");
78 binaryTree.root.right.right = new BinaryTreeWithoutRecursion.TreeNodeClass("\
79 F");
80
81 // the binaryTree object will traverse the tree without recursion
82 binaryTree.VisitTreeWithoutRecursion();
83 System.out.println();
84
85
86 }
87 }
The output is quite expected here, in the comments section we have declared how it will look like.
1 //output of 7.19
2
3 A B C D E F
4
5 Process finished with exit code 0
In general, recursion implicitly uses a Stack data structure. In recursion when we reach the base point, it starts unwinding. For that reason, in the above code, we have used the Stack data structure to traverse the tree without using recursion.
In a tree, the leaf node is the base point. Reaching that point node becomes null, and we reach the base point. To simulate the recursion we need to apply Stack explicitly, instead of implicitly. Let us watch the above code snippets to understand what happens inside.
First, this part where we have defined and declared the static ‘TreeNodeClass’:
1 static class TreeNodeClass {
2 String data;
3 BinaryTreeWithoutRecursion.TreeNodeClass left, right;
4
5 TreeNodeClass(String value) {
6 this.data = value;
7 left = right = null;
8 }
9
10 boolean isLeaf() {
11 return left == null ? right == null : false;
12 }
13
14 }
15
16 // root of the binary tree from where we start our journey
17 BinaryTreeWithoutRecursion.TreeNodeClass root;
We want three ‘node’ objects, and we name them as ‘left’, ‘right’, and ‘root’. We also need a ‘String’ data type variable to store our values. The advantage of making the class static is it will run the program faster.
The only problem of using iteration lies in its length of code. We cannot make it as concise and readable as we can do using recursion.
Let us try to do the same pre-order tree traversal in recursive way. Comparing these two code snippets will give us a good idea about why binary tree traversal is usually done recursively.
1 //code 7.20
2
3 package fun.sanjibsinha.chapter7.binarytree.preordertraversal;
4
5 public class BinaryTreeWithRecursion {
6
7 static class TreeNodeClass {
8 String data;
9 TreeNodeClass left;
10 TreeNodeClass right;
11
12 TreeNodeClass(String value) {
13 this.data = value;
14 left = right = null;
15 }
16
17 boolean isLeaf() {
18 return left == null ? right == null : false;
19 }
20
21 }
22
23 // root of the binary tree from where we start our journey
24 BinaryTreeWithRecursion.TreeNodeClass root;
25
26 /**
27 * the public method to traverse and display the nodes
28 * by calling the recursive function
29 */
30 public void traversingPreOrderByCallingItself() {
31 traversingPreOrderByCallingItself(root);
32 }
33
34 /**
35 * traversing the binary tree by calling itself
36 */
37 private void traversingPreOrderByCallingItself(BinaryTreeWithRecursion.TreeNodeC\
38 lass node) {
39 if (node == null) {
40 return;
41 }
42 System.out.printf("%s ", node.data);
43 traversingPreOrderByCallingItself(node.left);
44 traversingPreOrderByCallingItself(node.right);
45 }
46
47 }
48
49
50 package fun.sanjibsinha.chapter7.binarytree.preordertraversal;
51
52 /**
53 * In our example: A B C D E F
54 A
55 / \
56 B E
57 / \ \
58 C D F
59
60 */
61
62 public class PreOrderTreeWithRecursion {
63
64 public static void main(String[] args) {
65
66 // construct the binaryTree object to traverse without recursion
67 BinaryTreeWithRecursion binaryTree = new BinaryTreeWithRecursion();
68 BinaryTreeWithRecursion.TreeNodeClass root = new BinaryTreeWithRecursion.Tre\
69 eNodeClass("A");
70 binaryTree.root = root;
71 binaryTree.root.left = new BinaryTreeWithRecursion.TreeNodeClass("B");
72 binaryTree.root.left.left = new BinaryTreeWithRecursion.TreeNodeClass("C");
73
74 binaryTree.root.left.right = new BinaryTreeWithRecursion.TreeNodeClass("D");
75 binaryTree.root.right = new BinaryTreeWithRecursion.TreeNodeClass("E");
76 binaryTree.root.right.right = new BinaryTreeWithRecursion.TreeNodeClass("F");
77
78 System.out.println();
79 binaryTree.traversingPreOrderByCallingItself();
80 System.out.println();
81
82 }
83 }
If you are a Java developer, you have probably guessed why we have used the pritf() method:
1 System.out.printf("%s ", node.data);
We want to store the data to build the structure. Until we reach the base case or leaf node, the function traversingPreOrderByCallingItself() calls itself and keeps adding the value to the node tree. Therefore, the output will be same as before.
1 //output of 7.20
2
3 A B C D E F
4
5 Process finished with exit code 0
Now what are the main differences between the iteration and recursion? For the pre-order tree traversal algorithm, things were a little bit complicated. We needed a Stack of node first, then we pushed the tree root in the Stack. After doing that we keep pushing the right child and left child; at the same time we pop all nodes one by one for each node.
But in recursion the recursive method takes a Node in parameter and and calls itself to add left child and right child. The code snippet, not only looks concise, but it is also more readable.
Post Order Traversal
To visit all the nodes and print their values are known as tree traversal. Just like LinkedList, in pre-order traversal, we start from the root or head node and then we move until we reach the leaf node.
The post-order tree traversal represents just the opposite. Here the root node is visited last. We start from the left sub-tree; then we visit the right sub-tree, and after that we reach the root node.
Therefore, we should use recursion to visit the left sub-tree; then visiting right sub-tree recursively leads us to our final destination-the root node. The post-order tree traversal follows this algorithm.
Let us see the post-order tree traversal using iteration as we have done in the previous case of pre-order traversal.
1 //code 7.21
2
3 package fun.sanjibsinha.chapter7.binarytree.postordertraversal;
4
5 import java.util.Stack;
6
7 public class BinaryTreeNotRecursive {
8
9 static class TreeNodeClass {
10 String data;
11 BinaryTreeNotRecursive.TreeNodeClass left, right;
12
13 TreeNodeClass(String value) {
14 this.data = value;
15 left = right = null;
16 }
17
18 boolean isLeaf() {
19 return left == null ? right == null : false;
20 }
21
22 }
23
24 // root of the binary tree from where we start our journey
25 BinaryTreeNotRecursive.TreeNodeClass root;
26
27 public void postOrderWithoutRecursion() {
28 Stack<BinaryTreeNotRecursive.TreeNodeClass> nodes = new Stack<>();
29 nodes.push(root);
30
31 while (!nodes.isEmpty()) {
32 BinaryTreeNotRecursive.TreeNodeClass current = nodes.peek();
33
34 if (current.isLeaf()) {
35 BinaryTreeNotRecursive.TreeNodeClass node = nodes.pop();
36 System.out.printf("%s ", node.data);
37 } else {
38
39 if(current.right != null){
40 nodes.push(current.right);
41 current.right = null;
42 }
43
44 if(current.left != null){
45 nodes.push(current.left);
46 current.left = null;
47 }
48 }
49
50 }
51 }
52 }
53
54 package fun.sanjibsinha.chapter7.binarytree.postordertraversal;
55
56 /** The binary tree traversal will take place as the following structure
57 * With the following output
58 A
59 * / \
60 * B F
61 * / \ \
62 * C E G
63 * / / \
64 * D H I
65 *
66 * output: D C E B H I G F A
67 */
68
69 public class DisplayPostOrderTraversal {
70
71 public static void main(String[] args) {
72
73 BinaryTreeNotRecursive tree = new BinaryTreeNotRecursive();
74 BinaryTreeNotRecursive.TreeNodeClass root = new BinaryTreeNotRecursive.TreeN\
75 odeClass("A");
76 tree.root = root;
77 tree.root.left = new BinaryTreeNotRecursive.TreeNodeClass("B");
78 tree.root.left.left = new BinaryTreeNotRecursive.TreeNodeClass("C");
79 tree.root.left.left.left = new BinaryTreeNotRecursive.TreeNodeClass("D");
80
81 tree.root.left.right = new BinaryTreeNotRecursive.TreeNodeClass("E");
82 tree.root.right = new BinaryTreeNotRecursive.TreeNodeClass("F");
83 tree.root.right.right = new BinaryTreeNotRecursive.TreeNodeClass("G");
84 tree.root.right.right.left = new BinaryTreeNotRecursive.TreeNodeClass("H");
85 tree.root.right.right.right = new BinaryTreeNotRecursive.TreeNodeClass("I");
86
87 System.out.println();
88 // post order traversal without recursion
89 System.out.println("The nodes of binary tree on post order iterative way..."\
90 );
91 tree.postOrderWithoutRecursion();
92
93 System.out.println(); // insert new line
94
95
96 }
97 }
We have mentioned the output in our comments section. The same output waits to greet us below.
1 //output of 7.21
2
3 The nodes of binary tree on post order iterative way...
4 D C E B H I G F A
5
6 Process finished with exit code 0
As always, this type of tree traversal can be managed in a better way using recursion. Visiting the left sub-tree leads us to more recursion of right sub-tree, and finally we reach the root node.
The next code snippet shows us how we can do the same operation in a more concise way using recursion.
1 //code 7.22
2
3 package fun.sanjibsinha.chapter7.binarytree.postordertraversal;
4
5 public class BinaryTreeRecursive {
6
7 static class TreeNodeClass {
8 String data;
9 BinaryTreeRecursive.TreeNodeClass left, right;
10
11 TreeNodeClass(String value) {
12 this.data = value;
13 left = right = null;
14 }
15
16 boolean isLeaf() {
17 return left == null ? right == null : false;
18 }
19
20 }
21
22 // root of the binary tree from where we start our journey
23 BinaryTreeRecursive.TreeNodeClass root;
24
25 /**
26 * the public method to traverse and display the nodes
27 * by calling the recursive function
28 */
29 public void postOrder() {
30 postOrder(root);
31 }
32
33 /**
34 * traversing the binary tree by calling itself
35 */
36 private void postOrder(BinaryTreeRecursive.TreeNodeClass node) {
37 if (node == null) {
38 return;
39 }
40
41 postOrder(node.left);
42 postOrder(node.right);
43 System.out.printf("%s ", node.data);
44 }
45
46
47 }
48
49
50 package fun.sanjibsinha.chapter7.binarytree.postordertraversal;
51
52 /** The binary tree traversal will take place as the following structure
53 * With the following output
54 A
55 * / \
56 * B F
57 * / \ \
58 * C E G
59 * / / \
60 * D H I
61 *
62 * output: D C E B H I G F A
63 */
64
65 public class DisplayingPostOrderTraversal {
66
67 public static void main(String[] args) {
68
69 BinaryTreeRecursive tree = new BinaryTreeRecursive();
70 BinaryTreeRecursive.TreeNodeClass root = new BinaryTreeRecursive.TreeNodeCla\
71 ss("A");
72 tree.root = root;
73 tree.root.left = new BinaryTreeRecursive.TreeNodeClass("B");
74 tree.root.left.left = new BinaryTreeRecursive.TreeNodeClass("C");
75 tree.root.left.left.left = new BinaryTreeRecursive.TreeNodeClass("D");
76
77 tree.root.left.right = new BinaryTreeRecursive.TreeNodeClass("E");
78 tree.root.right = new BinaryTreeRecursive.TreeNodeClass("F");
79 tree.root.right.right = new BinaryTreeRecursive.TreeNodeClass("G");
80 tree.root.right.right.left = new BinaryTreeRecursive.TreeNodeClass("H");
81 tree.root.right.right.right = new BinaryTreeRecursive.TreeNodeClass("I");
82
83 System.out.println();
84
85 // post order traversal recursive way
86 System.out.println("The nodes of binary tree on post order recursive way..."\
87 );
88
89 tree.postOrder();
90
91 System.out.println();
92
93
94 }
95 }
Now we can compare the code snippets where we have once used iteration and after that we have used recursion. Still the output is same.
1 //output of 7.22
2
3 The nodes of binary tree on post order recursive way...
4 D C E B H I G F A
5
6 Process finished with exit code 0
Whenever we use pre-order traversal, the displayed data are different than case when we use post-order traversal. Moreover, it depends on how we want to visit our nodes.
In this section, finally we will use in-order tree traversal, which is different than the previous two cases of tree traversals.
In Order Tree Traversal
When we use in-order tree traversal, we start visiting left sub-tree recursively first. After that, we visit the root and then the right sub-tree. Each node stores a value and we know them as key. In the in-order tree traversal, the output produces sorted key values in an ascending order.
Just like the previous two cases, we will do the in-order tree traversal using iteration first. After that, we will use the recursion.
1 //code 7.23
2
3 package fun.sanjibsinha.chapter7.binarytree.inorder;
4
5 import java.util.Stack;
6
7 public class InOrderBinaryTreeNotRecursive {
8
9 static class TreeNodeClass {
10 String data;
11 InOrderBinaryTreeNotRecursive.TreeNodeClass left, right;
12
13 TreeNodeClass(String value) {
14 this.data = value;
15 left = right = null;
16 }
17
18 boolean isLeaf() {
19 return left == null ? right == null : false;
20 }
21
22 }
23
24 // root of the binary tree from where we start our journey
25 InOrderBinaryTreeNotRecursive.TreeNodeClass root;
26
27 public void inOrderWithoutRecursion() {
28 Stack<InOrderBinaryTreeNotRecursive.TreeNodeClass> nodes = new Stack<>();
29 InOrderBinaryTreeNotRecursive.TreeNodeClass current = root;
30
31 while (!nodes.isEmpty() || current != null) {
32
33 if (current != null) {
34 nodes.push(current);
35 current = current.left;
36 } else {
37 InOrderBinaryTreeNotRecursive.TreeNodeClass node = nodes.pop();
38 System.out.printf("%s ", node.data);
39 current = node.right;
40 }
41
42 }
43 }
44
45
46 }
47
48 package fun.sanjibsinha.chapter7.binarytree.inorder;
49
50 /*
51 *
52 *
53 * input:
54 * D
55 * / \
56 * B E
57 * / \ \
58 * A C F
59 *
60 * output: A B C D E F
61 */
62
63 public class PrintingInOrderTraversal {
64
65 public static void main(String[] args) {
66
67 InOrderBinaryTreeNotRecursive tree = new InOrderBinaryTreeNotRecursive();
68 InOrderBinaryTreeNotRecursive.TreeNodeClass root = new InOrderBinaryTreeNotR\
69 ecursive.TreeNodeClass("D");
70 tree.root = root;
71 tree.root.left = new InOrderBinaryTreeNotRecursive.TreeNodeClass("B");
72 tree.root.left.left = new InOrderBinaryTreeNotRecursive.TreeNodeClass("A");
73
74 tree.root.left.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("C");
75 tree.root.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("E");
76 tree.root.right.right = new InOrderBinaryTreeNotRecursive.TreeNodeClass("F");
77
78 System.out.println();
79
80 tree.inOrderWithoutRecursion();
81
82 System.out.println();
83
84 }
85 }
The inner mechanism of in-order tree traversal is not evident in the output. As we have mentioned earlier the output will be presented in an ascending order.
1 //output of 7.23
2
3 A B C D E F
4
5 Process finished with exit code 0
The main disadvantages of using iteration include the lack of conciseness. For a huge binary tree the lines of code could be too long. Maintaining such huge data could be an issue, yet it is faster than using recursion.
The next code snippet will show how we can use recursion to make the same code look more concise.
1 //code 7.24
2
3 package fun.sanjibsinha.chapter7.binarytree.inorder;
4
5 public class InOrderBinaryTreeRecursive {
6
7 static class TreeNodeClass {
8 String data;
9 InOrderBinaryTreeRecursive.TreeNodeClass left, right;
10
11 TreeNodeClass(String value) {
12 this.data = value;
13 left = right = null;
14 }
15
16 boolean isLeaf() {
17 return left == null ? right == null : false;
18 }
19
20 }
21
22 // root of the binary tree from where we start our journey
23 InOrderBinaryTreeRecursive.TreeNodeClass root;
24
25 /**
26 * the public method to traverse and display the nodes
27 * by calling the recursive function
28 */
29 public void inOrder() {
30
31 inOrder(root);
32 }
33
34 /**
35 * traversing the binary tree by calling itself
36 */
37 private void inOrder(InOrderBinaryTreeRecursive.TreeNodeClass node) {
38 if (node == null) {
39 return;
40 }
41
42 inOrder(node.left);
43 System.out.printf("%s ", node.data);
44 inOrder(node.right);
45 }
46
47
48 }
49
50
51 package fun.sanjibsinha.chapter7.binarytree.inorder;
52
53 /*
54 *
55 *
56 * input:
57 * D
58 * / \
59 * B E
60 * / \ \
61 * A C F
62 *
63 * output: A B C D E F
64 */
65
66 public class PrintInOrderTraversal {
67
68 public static void main(String[] args) {
69
70 InOrderBinaryTreeRecursive tree = new InOrderBinaryTreeRecursive();
71 InOrderBinaryTreeRecursive.TreeNodeClass root = new InOrderBinaryTreeRecursi\
72 ve.TreeNodeClass("D");
73 tree.root = root;
74 tree.root.left = new InOrderBinaryTreeRecursive.TreeNodeClass("B");
75 tree.root.left.left = new InOrderBinaryTreeRecursive.TreeNodeClass("A");
76
77 tree.root.left.right = new InOrderBinaryTreeRecursive.TreeNodeClass("C");
78 tree.root.right = new InOrderBinaryTreeRecursive.TreeNodeClass("E");
79 tree.root.right.right = new InOrderBinaryTreeRecursive.TreeNodeClass("F");
80
81 System.out.println();
82
83 tree.inOrder();
84
85 System.out.println();
86 }
87 }
If we take a close look at this part of the above code it will give us more insights into the algorithm of recursion.
1 /**
2 * the public method to traverse and display the nodes
3 * by calling the recursive function
4 */
5 public void inOrder() {
6
7 inOrder(root);
8 }
9
10 /**
11 * traversing the binary tree by calling itself
12 */
13 private void inOrder(InOrderBinaryTreeRecursive.TreeNodeClass node) {
14 if (node == null) {
15 return;
16 }
17
18 inOrder(node.left);
19 System.out.printf("%s ", node.data);
20 inOrder(node.right);
21 }
In the in-order tree traversal, we have recursion this way. However, the post-order algorithm of recursion was different. Let us the same part in the post-order recursive tree traversal.
1 /**
2 * the public method to traverse and display the nodes
3 * by calling the recursive function
4 */
5 public void postOrder() {
6 postOrder(root);
7 }
8
9 /**
10 * traversing the binary tree by calling itself
11 */
12 private void postOrder(BinaryTreeRecursive.TreeNodeClass node) {
13 if (node == null) {
14 return;
15 }
16
17 postOrder(node.left);
18 postOrder(node.right);
19 System.out.printf("%s ", node.data);
20 }
Finally, we will take a look at the pre-order recursive tree traversal algorithm. The position of calling the function itself changes with each recursive tree traversal style.
1 /**
2 * the public method to traverse and display the nodes
3 * by calling the recursive function
4 */
5 public void traversingPreOrderByCallingItself() {
6 traversingPreOrderByCallingItself(root);
7 }
8
9 /**
10 * traversing the binary tree by calling itself
11 */
12 private void traversingPreOrderByCallingItself(BinaryTreeWithRecursion.TreeNodeC\
13 lass node) {
14 if (node == null) {
15 return;
16 }
17 System.out.printf("%s ", node.data);
18 traversingPreOrderByCallingItself(node.left);
19 traversingPreOrderByCallingItself(node.right);
20 }
How we use our recursive algorithm is extremely important. Although recursion has many advantages and disadvantages, we need to use this algorithm wisely. We need to understand how it works, we need to keep in our mind one key conception regarding recursive algorithm, which is there must be a base case. Recursive algorithm should have a base case, and in the above examples, we have seen the how we proceed towards the base case where we have a condition to stop the recursion.
The condition checks whether the root is null or not. That was our base case when we had been traversing the tree. Whatever be the style of tree traversal; pre-order, post-order or in-order. We have to maintain the same logic when we use recursion.
We have seen and discussed a small part of algorithm; it is as much as a teaspoon holds. In the coming section we will get more insights about data structure.
Collection Framework in Java
We have already learned that Java Collection Framework has three key components that work together. First one is Interface.
The second one is Implementations; classes that implement interfaces. We get objects from those classes on which algorithmic operations are performed.
The third and the final one is Algorithm. This is the final goal; because algorithms in Java Collection framework are methods that perform useful computations, such as sorting, searching, shuffling, etc. Algorithms are polymorphic; it means, the same method can be used by an Iterator object, and as well as an ListIterator object. We will see those examples in a minute.
We have just said polymorphic algorithm methods. Let us see how add() methods work on different Collection objects.
1 //code 7.25
2
3 package fun.sanjibsinha.chapter7.collection;
4
5 /**
6 * in this code snippets we take a brief look at the
7 * Collection framework of Java
8 */
9
10 import java.util.*;
11
12 public class CollectionOverall {
13
14 public static void main(String[] args) {
15
16 // ArrayList Examples where we add elements
17 List arrayList = new ArrayList();
18 arrayList.add("Sanjib");
19 arrayList.add("Json");
20 arrayList.add("John");
21 arrayList.add(10);
22 System.out.println(" ArrayList Elements in tabular format: ");
23 System.out.print("\t" + arrayList);
24
25 // LinkedList Examples where we add elements
26 List linkedList = new LinkedList();
27 linkedList.add("Sanjib");
28 linkedList.add("Json");
29 linkedList.add("John");
30 linkedList.add(10);
31 System.out.println();
32 System.out.println(" LinkedList Elements in tabular format: ");
33 System.out.print("\t" + linkedList);
34
35 // HashSet Examples where we add elements
36 Set hashSet = new HashSet();
37 hashSet.add("Sanjib");
38 hashSet.add("Json");
39 hashSet.add("John");
40 hashSet.add(10);
41 System.out.println();
42 System.out.println(" Set Elements in tabular format: ");
43 System.out.print("\t" + hashSet);
44
45 // HashMap Examples where we add elements
46 Map hashMap = new HashMap();
47 hashMap.put("Sanjib", "55");
48 hashMap.put("Json", "45");
49 hashMap.put("John", "35");
50 System.out.println();
51 System.out.println(" Map Elements in tabular format: ");
52 System.out.print("\t" + hashMap);
53 System.out.println();
54 }
55
56 }
The above code snippets give us the following output; furthermore, from this output, we understand that we can do the same computation using different types of collection objects.
1 //output of 7.25
2 ArrayList Elements in tabular format:
3 [Sanjib, Json, John, 10]
4 LinkedList Elements in tabular format:
5 [Sanjib, Json, John, 10]
6 Set Elements in tabular format:
7 [John, 10, Json, Sanjib]
8 Map Elements in tabular format:
9 {John=35, Json=45, Sanjib=55}
As we progress, we will learn more about data structure and algorithm through Java Collection framework. We will also find how Java Collection framework unifies its implementations using many discrete mathematical abstractions.
Discrete Mathematical Abstractions and Implementation through Java Collection
We have not forgotten the key discourse of this book. Discrete Mathematics, data structure and algorithm are inter-connected. It is evident when Java Collection Framework introduces Set collection. The Set Collection in Java does not allow duplicate elements, just like mathematical Set abstraction does in the same way. Moreover, Java Set models on discrete mathematical set abstraction.
Let us see an example:
1 //code 7.26
2 package fun.sanjibsinha.chapter7.collection;
3
4 import java.util.HashSet;
5 import java.util.Set;
6 import java.util.TreeSet;
7
8 public class SetSortingAlgorithm {
9
10 static int count;
11
12 public static void main(String[] args) {
13
14 int countingDisparateIntegers[] = {100, 256, 18, 605, 78, 5};
15
16 /**
17 * The Set Collection implements discrete mathematical Set abstraction
18 * it does not allow duplicate value like the following list
19 * int countingDisparateIntegers[] = {100, 256, 100, 605, 78, 5};
20 */
21
22 /**
23 * the organization of data can start here
24 * we can use HashSet for displaying the list
25 */
26
27 Set<Integer> hashSet = new HashSet<Integer>();
28 try {
29 for(count = 0; count < 5; count++) {
30 hashSet.add(countingDisparateIntegers[count]);
31 }
32 System.out.println("Displaying the list of the array elements : ");
33 System.out.println(hashSet);
34
35 /**
36 * we can use TreeSet for sorting algorithm
37 */
38
39 TreeSet setAfterSorting = new TreeSet<Integer>(hashSet);
40 System.out.println("The list after sorting looks like this: ");
41 System.out.println(setAfterSorting);
42
43 /**
44 * we can easily pick up the first or last element
45 * after the sorting is over
46 */
47
48 System.out.println("The First element of the generated list is: " +
49 (Integer)setAfterSorting.first());
50 System.out.println("The last element of the generated list is: " +
51 (Integer)setAfterSorting.last());
52 }
53
54 catch(Exception e) {
55 e.getMessage();
56 }
57 }
58 }
We have used sorting algorithm in the above Set Collection. After sorting is over, we have easily picked up the first and the last element.
1 //output of 7.26
2 Displaying the list of the array elements :
3 [256, 18, 100, 605, 78]
4 The list after sorting looks like this:
5 [18, 78, 100, 256, 605]
6 The First element of the generated list is: 18
7 The last element of the generated list is: 605
We have said earlier that the Set Collection implements discrete mathematical Set abstraction. Let us check it by changing this line of the above code.
1 From
2 int countingDisparateIntegers[] = {100, 256, 18, 605, 78, 5};
3 To
4 int countingDisparateIntegers[] = {100, 256, 100, 605, 78, 5};
Run the code and you will get the following output, where one ‘100’ is missing.
1 Displaying the list of the array elements :
2 [256, 100, 605, 78]
3 The list after sorting looks like this:
4 [78, 100, 256, 605]
5 The First element of the generated list is: 78
6 The last element of the generated list is: 605
In many cases, discrete mathematical abstractions are implemented in data structure and algorithm. In future code snippets, we will see more examples like above, where same things happen, in like manner.
There are more mathematical abstractions wait for us. Map Collection models mathematical abstraction, such as ‘function’. Let us see how it works in Map Collection.
1 // code 7.27
2
3 package fun.sanjibsinha.chapter7.collection;
4
5 import java.util.HashMap;
6 import java.util.Iterator;
7 import java.util.Map;
8 import java.util.Set;
9
10 /**
11 * Map.Entry is an interface that is implemented by HashMap and Set
12 * We need Iterator interface also to be implemented to work together
13 */
14
15 public class MapEntryAndIteratorInterfaceTogether {
16
17 static int age;
18
19 public static void main(String[] args) {
20
21 // we need to create a HasMap object first
22 HashMap hashMap = new HashMap();
23
24 // adding some key value pairs that represent corresponding ages
25 hashMap.put("Json", 45);
26 hashMap.put("Sanjib", 55);
27 hashMap.put("John", 35);
28
29 // now we need a Set object to implement Map.Entry interface
30 Set setObject = hashMap.entrySet();
31
32 // we need an Iterator object to implement Iterator interface
33 Iterator iteratorObject = setObject.iterator();
34
35 /**
36 * now we want to iterate the key value pair with the help
37 * of iterator object and display them one after another
38 * in the ascending order after sorting is over
39 */
40
41 System.out.printf("The age of each person in ascending order: ");
42 System.out.println();
43
44 while(iteratorObject.hasNext()) {
45 Map.Entry mapEntryObject = (Map.Entry)iteratorObject.next();
46 System.out.print(mapEntryObject.getKey() + " : ");
47 System.out.println(mapEntryObject.getValue());
48 }
49 System.out.println();
50
51 /**
52 * now we can change the value of any key with the
53 * help of HashMap object
54 */
55
56 age = ((Integer)hashMap.get("John")).intValue();
57 hashMap.put("John", age + 1);
58 System.out.println("John turned " + hashMap.get("John") + " today!");
59
60 }
61 }
It gives us the following output, where the key and value pairs work together.
1 // output of 7.27
2
3 The age of each person in ascending order:
4 John : 35
5 Json : 45
6 Sanjib : 55
7
8 John turned 36 today!
Actually, the Map interface provides a small nested interface called Map.Entry. You have seen in the above code snippets. It is a part of the Collection view methods. The Map interface includes methods or algorithm for all type of basic operations on data structures, such as put, get, remove, etc. Map interface provides bulk operations, such as putAll or clear. There are Collection view algorithms also, keySet, entrySet, and values are among them.
Comparator, Comparable and Iterator
Java Collection framework provides three major interfaces, which have all the qualities of being important and worthy of note. Comparison plays a great role in sorting or shuffling algorithm. In the like manner, iteration is also very important.
We are going to see a few code snippets where these three interfaces ( Comparator, Comparable and Iterator ) are implemented.
To get elements in sorted order, we can use TreeSet and TreeMap from Java Collection Framework; but, it is the Comparator or the Comparable interface that precisely defines what sorted order means.
Implementing the Comparator and Comparable interfaces, we can have objects that encapsulate ordering. Watch the next code snippet:
1 // code 7.29
2
3 package fun.sanjibsinha.chapter7.collection;
4
5 /**
6 * How Comparator and Comparable interfaces are implemented by a class
7 * to sort String and Integer data types provided by List and
8 * ArrayList data structures
9 */
10
11 import java.util.ArrayList;
12 import java.util.Collections;
13 import java.util.Comparator;
14 import java.util.List;
15
16 class Account implements Comparator<Account>, Comparable<Account> {
17
18 private String accountHoldersName;
19 private int accountNumber;
20
21 Account() {
22 }
23
24 Account(String name, int number) {
25 accountHoldersName = name;
26 accountNumber = number;
27 }
28
29 public void setAccountHoldersName(String accountHoldersName) {
30 this.accountHoldersName = accountHoldersName;
31 }
32
33 public String getAccountHoldersName() {
34 return accountHoldersName;
35 }
36
37 public void setAccountNumber(int accountNumber) {
38 this.accountNumber = accountNumber;
39 }
40
41 public int getAccountNumber() {
42 return accountNumber;
43 }
44
45 /**
46 * overriding the compareTo() method to sort the name
47 * @param account
48 * @return
49 */
50 public int compareTo(Account account) {
51 return (this.accountHoldersName).compareTo(account.accountHoldersName);
52 }
53
54 /**
55 * overriding the compare() method to sort the account number
56 * @param account
57 * @param anotherAccount
58 * @return
59 */
60 public int compare(Account account, Account anotherAccount) {
61 return account.accountNumber - anotherAccount.accountNumber;
62 }
63 }
64
65 public class ComparatorInterfaceExample {
66
67 public static void main(String[] args) {
68
69 // list of account object
70 List<Account> listOfAccounts = new ArrayList<Account>();
71
72 listOfAccounts.add(new Account("Sanjib", 203));
73 listOfAccounts.add(new Account("Json", 205));
74 listOfAccounts.add(new Account("John", 201));
75 listOfAccounts.add(new Account("Hicky", 204));
76 listOfAccounts.add(new Account("Amubrata", 202));
77
78
79 // sorting the ArrayList
80 Collections.sort(listOfAccounts);
81
82 /**
83 * printing the sorted names
84 */
85 System.out.println("Printing the sorted names of account holders: ");
86 for(Account account: listOfAccounts){
87 System.out.print(account.getAccountHoldersName() + ", ");
88 }
89
90 /**
91 * sorting the ArrayList with the help of comparator
92 */
93 Collections.sort(listOfAccounts, new Account());
94 System.out.println(" ");
95
96 /**
97 * sorting based on account numbers
98 */
99 System.out.println("Printing the names of account holders based on sorted ac\
100 count" +
101 " numbers in ascending numbers: ");
102 for(Account account: listOfAccounts)
103 System.out.print(account.getAccountHoldersName() + " : "
104 + account.getAccountNumber() + ", ");
105 }
106 }
First of all, we have sorted the names of the account holders; in similar fashion, we have printed the names of account holders based on sorted account numbers in ascending numbers.
1 // output of 7.29
2
3 Printing the sorted names of account holders:
4 Amubrata, Hicky, John, Json, Sanjib,
5 Printing the names of account holders based on sorted account numbers in ascending n\
6 umbers:
7 John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
8 Process finished with exit code 0
What will happen if inadvertently someone adds a negative account number? Therefore, for the second part of the code where we have implemented Comparator interface method compare(), we should write the logic in this way.
1 // code 7.30
2
3 public int compare(Account account, Account anotherAccount) {
4 /**
5 * Don't do it unless you're absolutely
6 * sure no one will ever have a negative account number!
7 */
8 //return account.accountNumber - anotherAccount.accountNumber;
9 /**
10 * this is more logical approach
11 */
12 return (account.accountNumber < anotherAccount.accountNumber ? -1 :
13 (account.accountNumber == anotherAccount.accountNumber ? 0 : 1));
14 }
15
16 // output of 7.30
17 Printing the sorted names of account holders:
18 Amubrata, Hicky, John, Json, Sanjib,
19 Printing the names of account holders based on sorted account numbers in ascending n\
20 umbers:
21 John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
22 Process finished with exit code 0
Now, our code is more protected. Why we need to take such protections? It is little bit theoretical and this book is not about only Java Collection Framework. Yet, it is good to know that if an integer is a large positive integer and another integer is a large negative integer, then their subtraction will return a negative integer. To represent the difference of two arbitrary signed integers, a signed integer type is not big enough.
When we implement Comparable or Comparator interfaces, we need to maintain the technical restrictions.
If we want to compare two elements, especially for that type of algorithm, implementing the Comparable interface is always the better choice.
1 // code 7.31
2 package fun.sanjibsinha.chapter7.collection;
3
4 import java.util.ArrayList;
5 import java.util.Arrays;
6 import java.util.Collections;
7 import java.util.List;
8
9 class City implements Comparable<City>{
10
11 private String name;
12
13 City(String name){
14 if (name == null){
15 throw new NullPointerException();
16 }
17 this.name = name;
18 }
19
20 public String displayName(){
21 return name;
22 }
23
24 public String toString(){
25 return name;
26 }
27
28
29 @Override
30 public int compareTo(City city) {
31 int lastCompare = name.compareTo(city.name);
32 return (lastCompare != 0 ? lastCompare : name.compareTo(city.name));
33 }
34 }
35
36 public class ComparableInterfaceExample {
37
38 public static void main(String[] args) {
39
40 City cityNames[] = {
41 new City("Berlin"),
42 new City("Kolkata"),
43 new City("Munich"),
44 new City("Paris"),
45 new City("Mew York"),
46 };
47
48 List<City> names = Arrays.asList(cityNames);
49
50 Collections.sort(names);
51
52 System.out.println("The city names in ascending order: ");
53
54 System.out.println(names.toString());
55
56 }
57 }
We can get the city names in ascending order. For the algorithm that is related to sorting and comparing, it is a good choice in Java Collection framework.
1 // output of 7.31
2 The city names in ascending order:
3 [Berlin, Kolkata, Mew York, Munich, Paris]
4
5 Process finished with exit code 0
Finally we will curtain the Java Collection framework with iteration. It is also a very important part of algorithm and data structure. Java Collection framework handles it quite well by implementing the Iterator interface.
1 // code 7.32
2 package fun.sanjibsinha.chapter7.collection;
3
4 import java.util.ArrayList;
5 import java.util.Iterator;
6 import java.util.ListIterator;
7
8 /**
9 * An Iterator is an object that enables you to traverse through a collection
10 * public interface Iterator<E> {
11 * boolean hasNext();
12 * E next();
13 * void remove(); //optional
14 * }
15 * An Iterator object implements either Iterator, or ListIterator interface
16 */
17
18 public class IteratorInterfaceExample {
19
20 public static void main(String[] args) {
21
22 /**
23 * creating an ArrayList that will use iterator object
24 */
25
26 ArrayList arrayList = new ArrayList();
27
28 /**
29 * adding some city names to the array list
30 */
31 arrayList.add("Calcutta");
32 arrayList.add("Allahabad");
33 arrayList.add("Edinburgh");
34 arrayList.add("Berlin");
35 arrayList.add("Detroit");
36 arrayList.add("Fujiyama");
37
38 /**
39 * we can use iterator to display all the city names now
40 */
41
42 System.out.print("The city names as entered in the list : ");
43 Iterator itratorObject = arrayList.iterator();
44
45 while(itratorObject.hasNext()) {
46 Object element = itratorObject.next();
47 System.out.print(element + ", ");
48 }
49 System.out.println();
50
51 /**
52 * ListIterator object can implement the ListIterator interface
53 */
54 ListIterator listIterator = arrayList.listIterator();
55
56 System.out.print("Now we can cycle through the city names forward through li\
57 stIterator : ");
58 System.out.println();
59 while(listIterator.hasNext()) {
60 Object element = listIterator.next();
61 listIterator.set(element);
62 System.out.println(element);
63 }
64
65 System.out.print("Now we can cycle through the city names forward through it\
66 erator : ");
67 itratorObject = arrayList.iterator();
68
69 while(itratorObject.hasNext()) {
70 Object element = itratorObject.next();
71 System.out.print(element + ", ");
72 }
73 System.out.println();
74
75 System.out.print("Now we can cycle through the city names forward through li\
76 stIterator : ");
77
78 while(listIterator.hasPrevious()) {
79 Object element = listIterator.previous();
80 System.out.print(element + ", ");
81 }
82 System.out.println();
83 }
84 }
To traverse through a collection of elements, we need iteration; and, to do that we need an iterator object that implements the Iterator interface.
1 // output of 7.32
2 The city names as entered in the list : Calcutta, Allahabad, Edinburgh, Berlin, Detr\
3 oit, Fujiyama,
4
5 Now we can cycle through the city names forward through listIterator :
6 Calcutta
7 Allahabad
8 Edinburgh
9 Berlin
10 Detroit
11 Fujiyama
12
13 Now we can cycle through the city names forward through iterator : Calcutta, Allahab\
14 ad, Edinburgh, Berlin, Detroit, Fujiyama,
15 Now we can cycle through the city names forward through listIterator : Fujiyama, Det\
16 roit, Berlin, Edinburgh, Allahabad, Calcutta,
17
18 Process finished with exit code 0
When we want to iterate through the elements in a collection, and display each element, the easiest way is shown above. Employing an iterator object is the best solution to such algorithmic problems. The iterator object either implements the Iterator interface, or implements ListIterator interface.
We have learned some key concepts about data structure and algorithm; moreover, we have also seen how they model the discrete mathematical abstractions.
In the next section, we will find some more interesting facts about data structure and algorithm through C++ Standard Template Library.
Standard Template Library in C++
We should avoid the practice of being unjust to C++ Standard Template Library, in short, STL. It is a very big topic that we cannot discuss, entirely, in a small section. We can only compare it with Java Collection framework.
C++ STL mainly deals with three main components. They are, Container, Algorithm, and Iterator. However, before moving to the STL, we will try to understand what templates are. In C++, we use templates to create generalized functions and classes.
Why we need generalized functions and classes? For many reasons, of course. But, the foremost among them is through generalized functions and classes, we can use any data types, such as integer, floating point values, characters, etc. The list is not finished yet, we can use also some user defined data.
Theoretically, templates are foundations of generic programming. You can write code in a way, which is independent of any particular type.
Using template we can create a generic class or function. The C++ STL containers, iterators, and algorithms are ideal examples of generic programming. C++ Standard Template Library has been developed using template concept.
For that reason, let us try to understand first, how these template concepts work.
1 // code 7.33
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12
13 using namespace std;
14
15 template <typename T>
16 inline T const& FindMax (T const& c1, T const& c2) {
17 return c1 < c2 ? c2 : c1;
18 }
19
20 int main(){
21
22 /**
23 * We can use two different data types to compare which is maximum
24 */
25
26 int num1 = 20;
27 int num2 = 10;
28
29 cout << "Find the maximum comparing two values : " << FindMax(num1, num2) << end\
30 l;
31
32 double d1 = 20.12;
33 double d2 = 10.35;
34
35 cout << "Find the maximum comparing two values : " << FindMax(d1, d2) << endl;
36
37 return 0;
38 }
In the above code, we have created a general template method ‘FindMax()’. It helps us to find the maximum number. We can pass integers as well as floating point values.
1 // output of 7.33
2
3 Find the maximum comparing two values : 20
4 Find the maximum comparing two values : 20.12
We can use templates to create not only generalized functions, we can create generalized classes. Now using generalized classes, we can apply any data type, such as int, float, char, etc. In some cases, we can use the template specialization that helps us to use any particular type of data, like char. By this template generalization we can apply special template function for specialization. We will come to that point in a minute, before that let us see how generalization of template classes is used.
1 // code 7.34
2 #include <iostream>
3 #include <string>
4 #include <cmath>
5 #include <cstdlib>
6 #include <sstream>
7 #include <numeric>
8 #include <string>
9 #include <vector>
10 #include <cstddef>
11 #include <limits>
12 #include <stdexcept>
13
14 using namespace std;
15
16 /**
17 * We will define class Stack<> and implement generic methods
18 * to push and pop the elements from the stack
19 */
20
21 template <class T>
22
23 class Stack {
24 private:
25 vector<T> elementsToPushAndPop;
26
27 public:
28 void push(T const&);
29 void pop();
30 T top() const;
31
32 bool empty() const {
33 return elementsToPushAndPop.empty();
34 }
35 };
36
37 template <class T>
38 void Stack<T>::push (T const& elem) {
39 // we can append the copy of the element that we passed
40 elementsToPushAndPop.push_back(elem);
41 }
42
43 template <class T>
44 void Stack<T>::pop () {
45 // if the stack is empty, we can throw an exception
46 if (elementsToPushAndPop.empty()) {
47 throw out_of_range("Stack<>::pop(): empty stack");
48 }
49
50 // then we can remove the last element
51 elementsToPushAndPop.pop_back();
52 }
53
54 template <class T>
55 T Stack<T>::top () const {
56 // if the stack is empty, we can throw an exception
57 if (elementsToPushAndPop.empty()) {
58 throw out_of_range("Stack<>::top(): empty stack");
59 }
60
61 // then we can return copy of last element
62 return elementsToPushAndPop.back();
63 }
64
65 int main(){
66
67 // let us create a stack of integer elements
68 Stack<int> stackIntegers;
69
70 // now we can keep adding the stack
71 stackIntegers.push(500);
72 stackIntegers.push(501);
73
74 cout << stackIntegers.top() << endl;
75 if(stackIntegers.empty()){
76 cout << "The stack is empty." << endl;
77 } else {
78 cout << "The stack is not empty." << endl;
79 }
80
81
82 return 0;
83 }
We have created a general template class of Stack data structure that organizes data by adding value on the top of the table. It can also remove that data as well. A boolean method to create whether the stack is empty or not, is also checked.
1 // output of 7.34
2 501
3 The stack is not empty.
Now we can add more functionalities to this general template Stack class. It will give you an idea how STL in C++ works behind the scene.
1 // code 7.35
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * We will define class Stack<> and implement generic methods
19 * to push and pop the elements from the stack
20 */
21
22 template <class T>
23
24 class Stack {
25 private:
26 vector<T> elementsToPushAndPop;
27
28 public:
29 void push(T const&);
30 void pop();
31 T top() const;
32
33 bool empty() const {
34 return elementsToPushAndPop.empty();
35 }
36 };
37
38 template <class T>
39 void Stack<T>::push (T const& elem) {
40 // we can append the copy of the element that we passed
41 elementsToPushAndPop.push_back(elem);
42 }
43
44 template <class T>
45 void Stack<T>::pop () {
46 // if the stack is empty, we can throw an exception
47 if (elementsToPushAndPop.empty()) {
48 throw out_of_range("Stack<>::pop(): empty stack");
49 }
50
51 // then we can remove the last element
52 elementsToPushAndPop.pop_back();
53 }
54
55 template <class T>
56 T Stack<T>::top () const {
57 // if the stack is empty, we can throw an exception
58 if (elementsToPushAndPop.empty()) {
59 throw out_of_range("Stack<>::top(): empty stack");
60 }
61
62 // then we can return copy of last element
63 return elementsToPushAndPop.back();
64 }
65
66 int main(){
67
68 // let us create a stack of integer elements
69 Stack<int> stackIntegers;
70
71 // now we can keep adding the stack
72 stackIntegers.push(500);
73 stackIntegers.push(501);
74
75 cout << stackIntegers.top() << endl;
76 if(stackIntegers.empty()){
77 cout << "The stack is empty." << endl;
78 } else {
79 cout << "The stack is not empty." << endl;
80 }
81
82 // let us remove one element from our stack
83 stackIntegers.pop();
84
85 // and see the output
86 cout << stackIntegers.top() << endl;
87
88 // after that we can check whether the stack is empty or not
89 if(stackIntegers.empty()){
90 cout << "The stack is empty." << endl;
91 } else {
92 cout << "The stack is not empty." << endl;
93 }
94
95 return 0;
96 }
Because we have created generic methods, we can now create Stack object of int data type that will implement a few key algorithms, such as adding, removing, etc.
1 // output of 7.35
2
3 501
4 The stack is not empty.
5 500
6 The stack is not empty.
The above code snippets give us an idea how STL provides common data structures, such as lists, stacks, arrays, etc. To understand STL properly, we need to learn how to create template classes are created.
The next code snippet gives us a more robust flavor of stack data structure where we have removed all the elements and caught the exception.
1 // code 7.36
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * We will define class Stack<> and implement generic methods
19 * to push and pop the elements from the stack
20 */
21
22 template <class T>
23
24 class Stack {
25 private:
26 vector<T> elementsToPushAndPop;
27
28 public:
29 void push(T const&);
30 void pop();
31 T top() const;
32
33 bool empty() const {
34 return elementsToPushAndPop.empty();
35 }
36 };
37
38 template <class T>
39 void Stack<T>::push (T const& elem) {
40 // we can append the copy of the element that we passed
41 elementsToPushAndPop.push_back(elem);
42 }
43
44 template <class T>
45 void Stack<T>::pop () {
46 // if the stack is empty, we can throw an exception
47 if (elementsToPushAndPop.empty()) {
48 throw out_of_range("Stack<>::pop(): empty stack");
49 }
50
51 // then we can remove the last element
52 elementsToPushAndPop.pop_back();
53 }
54
55 template <class T>
56 T Stack<T>::top () const {
57 // if the stack is empty, we can throw an exception
58 if (elementsToPushAndPop.empty()) {
59 throw out_of_range("Stack<>::top(): empty stack");
60 }
61
62 // then we can return copy of last element
63 return elementsToPushAndPop.back();
64 }
65
66 int main(){
67
68 // let us create a stack of integer elements
69 Stack<int> stackIntegers;
70
71 // now we can keep adding the stack
72 stackIntegers.push(500);
73 stackIntegers.push(501);
74
75 cout << stackIntegers.top() << endl;
76 if(stackIntegers.empty()){
77 cout << "The stack is empty." << endl;
78 } else {
79 cout << "The stack is not empty." << endl;
80 }
81
82 // let us remove one element from our stack
83 stackIntegers.pop();
84
85 // and see the output
86 cout << stackIntegers.top() << endl;
87
88 // after that we can check whether the stack is empty or not
89 if(stackIntegers.empty()){
90 cout << "The stack is empty." << endl;
91 } else {
92 cout << "The stack is not empty." << endl;
93 }
94
95 // and see the output
96 cout << stackIntegers.top() << endl;
97
98 // let us keep removing the stack elements
99 try {
100 // this removes 500
101 stackIntegers.pop();
102 // if we try to remove element again, it will throw an exception
103 // that we can now catch
104 stackIntegers.pop();
105 } catch (exception const& excep) {
106 cerr << "Exception: " << excep.what() << endl;
107 return -1;
108 }
109
110 return 0;
111 }
Let us see the output first. After that, we will see why we needed such working experience of creating general template classes and generic methods.
1 // output of 7.36
2
3 501
4 The stack is not empty.
5 500
6 The stack is not empty.
7 500
8 Exception: Stack<>::pop(): empty stack
Now, one thing is clear. The Standard Template Library (STL) is a set of C++ template classes that provide common programming data structures and functions, such as lists, stacks, etc. The three major components, container classes,algorithms and iterators work at tandem. In the above examples, we have seen how the components are parameterized.
You approach to understand STL whatever way, in our view, this is the best way. Try to gain the working experience of creating your own general template functions and classes.
Therefore, we will devote more time to understand this conception, after that, we will see a couple of STL examples.
Let us create a simple general template function, as well as a specialized template function.
1 // code 7.37
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * we can use any general template function to pass
19 * any kind of data type as a parameter
20 * we can also use any specialized function that will pass
21 * a certain kind of data type as a parameter
22 */
23
24 // a general template function
25 template<typename T>
26 void templateFucntion(T t) {
27 cout << "A general template function where we can pass any data type : " << t << end\
28 l ;
29 }
30
31 // a specialized template function where we can pass only string as parameter
32 template<>
33 void templateFucntion(char s) {
34 cout << "A specialized template function where we cannot pass any data type except c\
35 har : " << s << endl ;
36 }
37
38 int main(){
39 templateFucntion(10);
40 templateFucntion(10.14);
41 templateFucntion('A');
42 templateFucntion("A string value....");
43
44 return 0;
45 }
The above code snippet is fairly simple. Through the general template function, we can pass any data, like int, float, char, string, even user defined data. However, using specialization makes a key difference. We can now only pass char data.
1 // output of 7.37
2
3 A general template function where we can pass any data type : 10
4 A general template function where we can pass any data type : 10.14
5 A specialized template function where we cannot pass any data type except char : A
6 A general template function where we can pass any data type : A string value.…
In the same way, we can create general template class and method that will allow to pass any data of our choice.
1 // code 7.38
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * we can use any general template class to use
19 * any data type
20 */
21
22 template<typename T>
23 class GeneralClass {
24 public:
25 // this is constructor
26 GeneralClass() {
27 cout << "This is constructor of a general class " << endl;
28 }
29 // a general method through which we can pass any data type
30 void generalMethod(T t){
31 cout << "A general template function where we can pass any data type : " << \
32 t << endl;
33 }
34 };
35
36 int main(){
37 // let us create a few different types of objects
38 GeneralClass<int> integerObject;
39 cout << "Let us call the general method to pass an integer value" << endl;
40 integerObject.generalMethod(10);
41 GeneralClass<float> floatObject;
42 cout << "Let us call the general method to pass a float value" << endl;
43 floatObject.generalMethod(10.11);
44 GeneralClass<char> charObject;
45 cout << "Let us call the general method to pass a char value" << endl;
46 charObject.generalMethod('C');
47 GeneralClass<string> strObject;
48 cout << "Let us call the general method to pass a string value" << endl;
49 strObject.generalMethod("Hello World, I an a string!");
50
51
52 return 0;
53 }
It appears in the above code, our choice has no limitations. Now we can create an object and call the same method again and again to pass any data.
1 // output of 7.38
2
3 This is constructor of a general class
4 Let us call the general method to pass an integer value
5 A general template function where we can pass any data type : 10
6 This is constructor of a general class
7 Let us call the general method to pass a float value
8 A general template function where we can pass any data type : 10.11
9 This is constructor of a general class
10 Let us call the general method to pass a char value
11 A general template function where we can pass any data type : C
12 This is constructor of a general class
13 Let us call the general method to pass a string value
14 A general template function where we can pass any data type : Hello World, I an a st\
15 ring!
In like manner we can also create a specialized template class and method that will allow a certain type of data to be passed.
1 // code 7.39
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * we can use any general template class to use
19 * any data type, but this is special case
20 */
21 template<typename t>
22 class SpecialClass {};
23
24 template<>
25 class SpecialClass<int> {
26 public:
27 // this is constructor
28 SpecialClass() {
29 cout << "This is constructor of a special class for only integer type. " << \
30 endl;
31 }
32 // a general method through which we can pass any data type
33 void specialMethod(int num){
34 cout << "A special template function where we can pass only integer data typ\
35 e : " << num << endl;
36 }
37 };
38
39 int main(){
40 // let us create a few different types of objects
41 cout << "Let us call the constructor of the special template class, by creating \
42 an object." << endl;
43 SpecialClass<int> integerObject;
44 cout << "Let us call the special method to pass an integer value, we have passed\
45 10" << endl;
46 integerObject.specialMethod(10);
47
48 try {
49 // let us try to pass any other data type
50 cout << "If we pass char, it will give us the ASCII code of that particular \
51 character A." << endl;
52 integerObject.specialMethod('A');
53 cout << "If we pass float, it will change it to the whole number." << endl;
54 integerObject.specialMethod(10.95);
55 /*
56 Details:10.15
57 Default:10.15
58 Decimal:10
59 Hex:0xa
60 Binary:1010
61 Octal:012
62 */
63
64 } catch (exception const& excep) {
65 cerr << "Exception: " << excep.what() << endl;
66 return -1;
67 }
68
69
70 return 0;
71 }
A specialized template class that allows only int data type. If you pass a character, it will convert that value to its ASCII equivalent. Watch the output:
1 // output of 7.39
2
3 Let us call the constructor of the special template class, by creating an object.
4 This is constructor of a special class for only integer type.
5 Let us call the special method to pass an integer value, we have passed 10
6 A special template function where we can pass only integer data type : 10
7 If we pass char, it will give us the ASCII code of that particular character A.
8 A special template function where we can pass only integer data type : 65
9 If we pass float, it will change it to the whole number.
10 A special template function where we can pass only integer data type : 10
We have had enough working experience with the general template classes and functions. Now we can taste of STL. Before using STL, we need to know that container classes mainly manage the data structures part.
Basically, containers store user defined data and primitive data. There are several standard container classes, header files, etc.
In such a small section we cannot elaborate them. We can have a brief look at how they are used. There are sequence containers that implement a special type data structures. The specialty is it can be accessed in sequential manner. It includes vector, list, array, etc. With the new version of C++, something new will be added in the future. Therefore, the list is incomplete.
There are also associative containers that implement a certain type of data structures. Associative containers have set or map; they implement sorted data structures that can be structured in a key and value pair. We will a few examples.
Let us start with ‘list’. We will also check different types of STL algorithms that are associated with ‘list’.
1 // code 7.40
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <list>
8 #include <iterator>
9 #include <stdexcept>
10
11 using namespace std;
12
13 /**
14 * we want a function to print the elements
15 * that belong to the list
16 */
17
18 void printList(list <int> l)
19 {
20 list <int> :: iterator itr;
21 for(itr = l.begin(); itr != l.end(); ++itr)
22 cout << *itr << ", ";
23 cout << endl;
24 }
25
26 int main()
27 {
28 cout << "Different types of STL Algorithms using List: " << endl;
29 cout << endl;
30
31 list <int> list1, list2;
32
33 // we can apply STL algorithm o print out
34 // in ascending and descending order
35 for (int i = 0; i < 10; ++i)
36 {
37 // place the values in ascending order
38 list1.push_back(i);
39 // place the values in descending order
40 list2.push_front(i);
41 }
42 cout << "First print the list1, in ascending order: " << endl;
43 printList(list1);
44 cout << endl;
45
46 cout << "Then print the list2, in descending order: " << endl;
47 printList(list2);
48 cout << endl;
49
50 // let us print the first value
51 cout << "The first value of list one: ";
52 cout << list1.front() << endl;
53 // let us print the last value
54 cout << "The last value of list one: ";
55 cout << list1.back() << endl;
56
57 // let us print the first value
58 cout << "The first value of list two: ";
59 cout << list2.front() << endl;
60 // let us print the last value
61 cout << "The last value of list two: ";
62 cout << list2.back() << endl;
63
64 cout << "Let us remove the first element 0 of list one: " << endl;
65 list1.pop_front();
66 printList(list1);
67 cout << endl;
68
69 cout << "Let us remove the last element 0 of list two: " << endl;
70 list2.pop_back();
71 printList(list2);
72 cout << endl;
73
74 cout << "We can reverse the list one making it equal to list two: " << endl;
75 list1.reverse();
76 printList(list1);
77 cout << endl;
78
79 cout << "We can sort the list two making it equal to list one: " << endl;
80 list2.sort();
81 printList(list2);
82
83 return 0;
84
85 }
We have implemented a couple of algorithms that show general functionalities, such as sorting, searching, adding, removing, or copying.
1 // output of 7.40
2
3 Different types of STL Algorithms using List:
4
5 First print the list1, in ascending order:
6 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
7
8 Then print the list2, in descending order:
9 9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
10
11 The first value of list one: 0
12 The last value of list one: 9
13 The first value of list two: 9
14 The last value of list two: 0
15 Let us remove the first element 0 of list one:
16 1, 2, 3, 4, 5, 6, 7, 8, 9,
17
18 Let us remove the last element 0 of list two:
19 9, 8, 7, 6, 5, 4, 3, 2, 1,
20
21 We can reverse the list one making it equal to list two:
22 9, 8, 7, 6, 5, 4, 3, 2, 1,
23
24 We can sort the list two making it equal to list one:
25 1, 2, 3, 4, 5, 6, 7, 8, 9,
Hopefully, comments will guide us how STL data structures and algorithms work clasping each other’s hands.
Another good sequential container class is ‘vector’. It is better than array in one sense. It can automatically adjust its storage capabilities. The following example will show us how it works.
1 // code 7.41
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <vector>
8 #include <iterator>
9 #include <stdexcept>
10
11 using namespace std;
12
13 /**
14 * vector container is similar to an array
15 * except that it automatically handles the
16 * storage requirements
17 */
18
19 int main(){
20
21 // let us create a vector to store some names
22 vector<string> vecOne;
23 vector<int> vecTwo;
24 int i;
25 int j;
26
27 // first display the original size of the first container
28 cout << "The vector container size : " << vecOne.size() << endl;
29
30 // then display the original size of the second container
31 cout << "The vector container size : " << vecTwo.size() << endl;
32
33 // let us add a few names into the vector one
34 for (j = 0; j < 5; j++){
35 vecOne.push_back("John");
36 vecOne.push_back("JSON");
37 vecOne.push_back("Smith");
38 vecOne.push_back("Web");
39 vecOne.push_back("Trace");
40 }
41
42 // let us add a few names into the vector two
43 for (i = 0; i < 5; i++){
44 vecTwo.push_back(i);
45 }
46
47 // display extended size of vector container one
48 cout << "The extended vector size = " << vecOne.size() << endl;
49
50 // display extended size of vector container two
51 cout << "The extended vector size = " << vecTwo.size() << endl;
52
53 // let us access 5 values from the vector one
54 for(j = 0; j < 5; j++) {
55 cout << "The value of vector container one " << j << " = " << vecOne[j] << e\
56 ndl;
57 }
58
59 // let us access 5 values from the vector one
60 for(i = 0; i < 5; i++) {
61 cout << "The value of vector container two " << i << " = " << vecTwo[i] << e\
62 ndl;
63 }
64
65 return 0;
66 }
With the help of ‘vector’ we can definitely solve certain type of problems. The only advantage is with array, we need to do the lower level plumbing. We can avoid them by implementing vector data structures and associated algorithms.
1 // output of 7.41
2
3 The vector container size : 0
4 The vector container size : 0
5 The extended vector size = 25
6 The extended vector size = 5
7 The value of vector container one 0 = John
8 The value of vector container one 1 = JSON
9 The value of vector container one 2 = Smith
10 The value of vector container one 3 = Web
11 The value of vector container one 4 = Trace
12 The value of vector container two 0 = 0
13 The value of vector container two 1 = 1
14 The value of vector container two 2 = 2
15 The value of vector container two 3 = 3
16 The value of vector container two 4 = 4
Whatever data structures we implement, or whatever algorithms we use, we need to keep one thing in our mind. Time-complexity is a big factor. In the next example, we will see ‘set’, and after that ‘map’. Both belong to the Associative Container classes. There is an advantage. Because it implements sorted data structures, the search operation takes less time.
In the next chapter we will try to understand how time-complexity works, and why it is necessary in programming.
Before that, in the next examples, let us see how the ‘set’ data structures from STL sets in with its key algorithms.
1 // code 7.42
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <set>
8 #include <iterator>
9 #include <stdexcept>
10
11 using namespace std;
12
13 /**
14 * we will see a lot of set algorithms in this example
15 */
16
17 int main()
18 {
19 // first we need an empty set container
20 set <int, greater <int> > setOne;
21
22 // now we can insert elements in random order
23 // however the numbers are unique
24 setOne.insert(55);
25 setOne.insert(89);
26 setOne.insert(1);
27 setOne.insert(41);
28 setOne.insert(74);
29 setOne.insert(23);
30 setOne.insert(32);
31
32 // to print the set one we need an iterator
33 set <int, greater <int> > :: iterator itr;
34 cout << "The iterator automatically orders the arrangement." << endl;
35 cout << "The set one is in now descending order : ";
36 for (itr = setOne.begin(); itr != setOne.end(); ++itr)
37 {
38 cout << *itr << ", ";
39 }
40 cout << endl;
41
42 // we can use a special algorithm to reverse the order
43 // to do that we need to assign the values of set one
44 // to another set called set two
45 set <int> setTwo(setOne.begin(), setOne.end());
46 cout << endl;
47
48 // now we can display the value of set two
49 cout << "The set two is in now ascending order : ";
50 for (itr = setTwo.begin(); itr != setTwo.end(); ++itr)
51 {
52 cout << *itr << ", ";
53 }
54 cout << endl;
55
56 // we can remove elements below 41 from set two
57 cout << "Removing values below 41 from set two: " << endl;
58 cout << "Now set two will start from 41: " << endl;
59 cout << "Now set two looks like this: " << endl;
60 setTwo.erase(setTwo.begin(), setTwo.find(41));
61 for (itr = setTwo.begin(); itr != setTwo.end(); ++itr)
62 {
63 cout << *itr << ", ";
64 }
65 cout << endl;
66
67 // we can remove any particular element whose value is 41 in set two
68 setTwo.erase (41);
69 cout << "Erasing 41 from set two" << endl;
70 cout << "Now set two will start from the value after 41 : " << endl;
71 cout << "Now set two looks like this: " << endl;
72 for (itr = setTwo.begin(); itr != setTwo.end(); ++itr)
73 {
74 cout << *itr << ", ";
75 }
76
77 cout << endl;
78
79 cout << "All the algorithms applied on set two have not affected set one : " << \
80 endl;
81 cout << "Set one remains same, it looks like this: " << endl;
82 for (itr = setOne.begin(); itr != setOne.end(); ++itr)
83 {
84 cout << *itr << ", ";
85 }
86 cout << endl;
87
88 return 0;
89
90 }
As we have seen in the above code, there are lots of different types of algorithms applied in ‘set’. Moreover, it is implemented as sorted data structures. But we can always change that order, quite easily.
1 // output of 7.42
2
3 The iterator automatically orders the arrangement.
4 The set one is in now descending order : 89, 74, 55, 41, 32, 23, 1,
5
6 The set two is in now ascending order : 1, 23, 32, 41, 55, 74, 89,
7 Removing values below 41 from set two:
8 Now set two will start from 41:
9 Now set two looks like this:
10 41, 55, 74, 89,
11 Erasing 41 from set two
12 Now set two will start from the value after 41 :
13 Now set two looks like this:
14 55, 74, 89,
15 All the algorithms applied on set two have not affected set one :
16 Set one remains same, it looks like this:
17 89, 74, 55, 41, 32, 23, 1,
As an associative container class, ‘map’ has also many advantages; with the help of STL algorithms, we can operate on any value through keys.
1 // code 7.43
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <map>
8 #include <iterator>
9 #include <stdexcept>
10
11 using namespace std;
12
13 /**
14 * we will see a few map algorithms from STL
15 * map belongs to the associative containers section
16 * it has key, value pairs
17 */
18
19 int main()
20 {
21 // first we will create an empty map container
22 map<int, int> mapOne;
23
24 // let us insert elements in random order keeping the key in ascending order
25 mapOne.insert(pair<int, int>(1, 56));
26 mapOne.insert(pair<int, int>(2, 89));
27 mapOne.insert(pair<int, int>(3, 2));
28 mapOne.insert(pair<int, int>(4, 64));
29 mapOne.insert(pair<int, int>(5, 14));
30 mapOne.insert(pair<int, int>(6, 35));
31 mapOne.insert(pair<int, int>(7, 75));
32
33 // to display all elements of map one we need iterator
34 map<int, int>::iterator itr;
35 cout << endl;
36 cout << " The map one's key=>value pairs are displayed in tabular form : \n";
37 cout << "\tKEY\tELEMENT\n";
38 for (itr = mapOne.begin(); itr != mapOne.end(); ++itr) {
39 cout << '\t' << itr->first
40 << '\t' << itr->second << '\n';
41 }
42 cout << endl;
43
44 // assigning the elements from mapOne to mapTwo
45 map<int, int> mapTwo(mapOne.begin(), mapOne.end());
46 cout << endl;
47
48 // now we can print all elements of the mapTwo
49 cout << "The map two after having values copied from map one in tabular form : "\
50 << endl;
51 cout << "\tKEY\tELEMENT\n";
52 for (itr = mapTwo.begin(); itr != mapTwo.end(); ++itr) {
53 cout << '\t' << itr->first
54 << '\t' << itr->second << endl;
55 }
56 cout << endl;
57
58 // we can apply the removal algorithm based on key
59 // let us remove all elements below key=>3
60 cout << endl;
61 cout << "The values of map two in tabular form after removal of elements less th\
62 an key=3 : " << endl;
63 cout << "\tKEY\tELEMENT\n";
64 mapTwo.erase(mapTwo.begin(), mapTwo.find(3));
65 for (itr = mapTwo.begin(); itr != mapTwo.end(); ++itr) {
66 cout << '\t' << itr->first
67 << '\t' << itr->second << '\n';
68 }
69
70 return 0;
71 }
To show the key, value pair properly, we have to use the tabular format. Although we have not use many algorithms, yet hopefully it will give us an idea about how ‘map’ works.
1 // output of 7.43
2
3 The map one's key=>value pairs are displayed in tabular form :
4 KEY ELEMENT
5 1 56
6 2 89
7 3 2
8 4 64
9 5 14
10 6 35
11 7 75
12
13
14 The map two after having values copied from map one in tabular form :
15 KEY ELEMENT
16 1 56
17 2 89
18 3 2
19 4 64
20 5 14
21 6 35
22 7 75
23
24
25 The values of map two in tabular form after removal of elements less than key=3 :
26 KEY ELEMENT
27 3 2
28 4 64
29 5 14
30 6 35
31 7 75
So far, we have taken a very brief look at the C++ STL, and before that, we have also seen Java Collection framework in action.
In the next chapter we will try to understand another key concept, time-complexity.
I write regularly on Algorithm and Data Structure in
QUIZZ on Chapter Seven
Question 1: Every high level language comes with its own algorithm library.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 2: Semantically, when we say that a function calls itself directly or indirectly, it is called recursion.
Option 1: The above statement does not make any sense.
Option 2: Based on this statement the recursive algorithm is formed.
Option 3: The recursion has its own limitations if we cannot stop it.
Option 4: Recursive algorithm is the fastest among all.
Answer: Option 2 and 3. Both are true in this case.
========================
Question 3: To prevent the infinite recursion, we always provide a condition, or base case.
Option 1: True
Option 2: False
Answer: Option 1
=======================
Question 4: The ‘container classes’ in C++ and Collection framework in language like Java play the same role.
Option 1: False
Option 2: True
Answer: Option 2
=======================
Question 5: For a huge binary tree using iteration could be too long as long as code lines are concerned. But it is faster than using recursion.
Option 1: The above statement is false.
Option 2: Iteration is always slower than recursion.
Option 3: Although the code could be too long, it faster than recursion.
Option 4: Recursion is faster than Iteration
Answer: Option 3
Challenge 1 : Standard Template Library (STL) provides many generic versions of standard algorithms that replace our low-level plumbing. Can you show the difference by writing code.
Solution to Challenge 1:
Language Used: C++
1 // code
2
3
4 #include <iostream>
5 #include <string>
6 using namespace std;
7
8 int Maximum(int a, int b){
9 if(a < b){
10 return b;
11 } else {
12 return a;
13 }
14 }
15
16 int Minimum(int a, int b){
17 if(a > b){
18 return b;
19 } else {
20 return a;
21 }
22 }
23
24 int EnterAndGet(){
25 std::cout << "Please enter a number (integer): " << '\n';
26 int Recieve;
27 std::cin >> Recieve;
28 return Recieve;
29 }
30
31 int main(int argc, char const *argv[]) {
32 /* code */
33 int valueOne = EnterAndGet();
34 int valueTwo = EnterAndGet();
35 std::cout << "Maximum value: " << Maximum(valueOne, valueTwo) << '\n';
36 std::cout << "Minimum value: " << Minimum(valueOne, valueTwo) << '\n';
37 return 0;
38 }
39
40 // if user enters 20 and 10, it will evaluate the corerct value.
41
42 // We can reduce the code lines with the help of STL
43
44 // code
45
46 #include <iostream>
47 #include <string>
48 #include <algorithm>
49 using namespace std;
50
51 int EnterAndGet(){
52 std::cout << "Please enter a number (integer): " << '\n';
53 int Recieve;
54 std::cin >> Recieve;
55 return Recieve;
56 }
57
58 int main(int argc, char const *argv[]) {
59 /* code */
60 int valueOne = EnterAndGet();
61 int valueTwo = EnterAndGet();
62 std::cout << "Maximum value: " << max(valueOne, valueTwo) << '\n';
63 std::cout << "Minimum value: " << min(valueOne, valueTwo) << '\n';
64 return 0;
65 }
66
67 // in the above code, we have added #include <algorithm> as header file. This STL ma\
68 kes the difference.
Challenge 2 : Can you prove with an example how the STL makes a difference when we want to sort a list of data.
Solution to Challenge 2:
Language Used: Java
1 // in the first code snippet we will do the low-level plumbing by writing the algori\
2 thm.
3
4 // code
5
6 package fun.sanjibsinha.chapter7;
7
8 import java.util.Arrays;
9
10 public class SortExampleTwo {
11
12 public static void main(String[] args) {
13
14 int[] anyArray = {210, 45, 258, 326, -12, 0, 89, 4, 9};
15 System.out.println("Before Sorting : ");
16 System.out.println(Arrays.toString(anyArray));
17 System.out.println("After Sorting : ");
18 for (int i = 0; i < anyArray.length; i++){
19 int index = i;
20 for (int j = i + 1; j < anyArray.length; j++)
21 if (anyArray[j] < anyArray[index])
22 index = j;
23
24 int smallerNumber = anyArray[index];
25 anyArray[index] = anyArray[i];
26 anyArray[i] = smallerNumber;
27 System.out.println(anyArray[i]);
28 }
29 }
30 }
// Here goes the output with the elements in ascending order.
1 //output
2
3 Before Sorting :
4 [210, 45, 258, 326, -12, 0, 89, 4, 9]
5
6 After Sorting :
7 -12
8 0
9 4
10 9
11 45
12 89
13 210
14 258
15 326
16
17
18 // Now we are going to use the STL of Java
19
20 // code
21
22 package fun.sanjibsinha.chapter7;
23 import java.util.Arrays;
24 import java.util.Collections;
25 import java.util.List;
26 public class SortExampleThree {
27
28 public static void main(String[] args) {
29
30 List<Integer> list = Arrays.asList(210, 45, 258, 326, -12, 0, 89, 4, 9);
31 Collections.sort(list);
32 System.out.println(list);
33 }
34
35 }
36
37 //output
38 // after sorting
39
40 [-12, 0, 4, 9, 45, 89, 210, 258, 326]
’’’’’’'’Conclusion’’’’’’’’’’’’
In any high-level language, the name of the Standard Template Library may differ, but it drastically reduces the code size.
Challenge 3 : Using recursion in programing is closer to our discrete mathematical definitions. Can you prove it?
Solution to Challenge 3:
Language Used: Java
Mathematically, the Fibonacci is defined as the following:
1 Fibonacci of 1 or 2 is 1
2 Fibonacci of F (for F > 2) is Fibonacci of (F - 1) + Fibonacci of (F – 2)
3
4 // Therefore we can transport this Mathematical function to programming.
5
6 //code
7
8 package fun.sanjibsinha.recursive;
9
10 public class AlgoFibonacci {
11
12 static int getFibonacci(int f) {
13 if ((f == 1) || (f == 2)){
14 return 1;
15 } else {
16 return (getFibonacci(f - 1) + getFibonacci(f - 2));
17 }
18 }
19
20 public static void main(String[] args) {
21
22 int newNumber = 6, result;
23 result = getFibonacci(newNumber);
24 System.out.printf("Fibonacci series of " + newNumber + " = " + result);
25 System.out.printf("");
26 System.out.printf("");
27 }
28
29 }
30
31
32 //output
33
34 Fibonacci series of 6 = 8
Challenge 4 : Recursive algorithm should have a base case. Write a program where we can proceed towards the base case and a condition to stop the recursion.
Solution to Challenge 4:
Language Used: Java
1 //code
2
3 package fun.sanjibsinha.chapter7.binarytree.inorder;
4
5 public class InOrderBinaryTreeRecursive {
6
7 static class TreeNodeClass {
8 String data;
9 InOrderBinaryTreeRecursive.TreeNodeClass left, right;
10
11 TreeNodeClass(String value) {
12 this.data = value;
13 left = right = null;
14 }
15
16 boolean isLeaf() {
17 return left == null ? right == null : false;
18 }
19
20 }
21
22 // root of the binary tree from where we start our journey
23 InOrderBinaryTreeRecursive.TreeNodeClass root;
24
25 /**
26 * the public method to traverse and display the nodes
27 * by calling the recursive function
28 */
29 public void inOrder() {
30
31 inOrder(root);
32 }
33
34 /**
35 * traversing the binary tree by calling itself
36 */
37 private void inOrder(InOrderBinaryTreeRecursive.TreeNodeClass node) {
38 if (node == null) {
39 return;
40 }
41
42 inOrder(node.left);
43 System.out.printf("%s ", node.data);
44 inOrder(node.right);
45 }
46
47
48 }
49
50
51 package fun.sanjibsinha.chapter7.binarytree.inorder;
52
53 /*
54 *
55 *
56 * input:
57 * D
58 * / \
59 * B E
60 * / \ \
61 * A C F
62 *
63 *
64 */
65
66 public class PrintInOrderTraversal {
67
68 public static void main(String[] args) {
69
70 InOrderBinaryTreeRecursive tree = new InOrderBinaryTreeRecursive();
71 InOrderBinaryTreeRecursive.TreeNodeClass root = new InOrderBinaryTreeRecursi\
72 ve.TreeNodeClass("D");
73 tree.root = root;
74 tree.root.left = new InOrderBinaryTreeRecursive.TreeNodeClass("B");
75 tree.root.left.left = new InOrderBinaryTreeRecursive.TreeNodeClass("A");
76
77 tree.root.left.right = new InOrderBinaryTreeRecursive.TreeNodeClass("C");
78 tree.root.right = new InOrderBinaryTreeRecursive.TreeNodeClass("E");
79 tree.root.right.right = new InOrderBinaryTreeRecursive.TreeNodeClass("F");
80
81 System.out.println();
82
83 tree.inOrder();
84
85 System.out.println();
86 }
87 }
88
89 // output:
90
91 A B C D E F
Challenge 5 : Can you prove that Discrete Mathematics, data structure and algorithm are inter-connected?
Solution to Challenge 5:
Language Used: Java
1 //code
2
3 package fun.sanjibsinha.chapter7.collection;
4
5 import java.util.HashSet;
6 import java.util.Set;
7 import java.util.TreeSet;
8
9 public class SetSortingAlgorithm {
10
11 static int count;
12
13 public static void main(String[] args) {
14
15 int countingDisparateIntegers[] = {100, 256, 18, 605, 78, 5};
16
17 /**
18 * The Set Collection implements discrete mathematical Set abstraction
19 * it does not allow duplicate value like the following list
20 * int countingDisparateIntegers[] = {100, 256, 100, 605, 78, 5};
21 */
22
23 /**
24 * the organization of data can start here
25 * we can use HashSet for displaying the list
26 */
27
28 Set<Integer> hashSet = new HashSet<Integer>();
29 try {
30 for(count = 0; count < 5; count++) {
31 hashSet.add(countingDisparateIntegers[count]);
32 }
33 System.out.println("Displaying the list of the array elements : ");
34 System.out.println(hashSet);
35
36 /**
37 * we can use TreeSet for sorting algorithm
38 */
39
40 TreeSet setAfterSorting = new TreeSet<Integer>(hashSet);
41 System.out.println("The list after sorting looks like this: ");
42 System.out.println(setAfterSorting);
43
44 /**
45 * we can easily pick up the first or last element
46 * after the sorting is over
47 */
48
49 System.out.println("The First element of the generated list is: " +
50 (Integer)setAfterSorting.first());
51 System.out.println("The last element of the generated list is: " +
52 (Integer)setAfterSorting.last());
53 }
54
55 catch(Exception e) {
56 e.getMessage();
57 }
58 }
59 }
60
61
62 // We have used sorting algorithm in the above Set Collection. After sorting is over\
63 , we have easily picked up the first and the last element.
64
65
66 //output
67
68 Displaying the list of the array elements :
69 [256, 18, 100, 605, 78]
70 The list after sorting looks like this:
71 [18, 78, 100, 256, 605]
72 The First element of the generated list is: 18
73 The last element of the generated list is: 605
’’’’’’’’’’’’'’CONCLUSION’’’’’’’’’’’’’’’’
The Set Collection in Java does not allow duplicate elements, just like mathematical Set abstraction does in the same way. Moreover, Java Set models on discrete mathematical set abstraction.
’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’
Challenge 6 : Can you create a general template class and method that will allow to pass any data of your choice.
Solution to Challenge 6:
Language Used: C++
1 // code
2
3 #include <iostream>
4 #include <string>
5 #include <cmath>
6 #include <cstdlib>
7 #include <sstream>
8 #include <numeric>
9 #include <string>
10 #include <vector>
11 #include <cstddef>
12 #include <limits>
13 #include <stdexcept>
14
15 using namespace std;
16
17 /**
18 * we can use any general template class to use
19 * any data type
20 */
21
22 template<typename T>
23 class GeneralClass {
24 public:
25 // this is constructor
26 GeneralClass() {
27 cout << "This is constructor of a general class " << endl;
28 }
29 // a general method through which we can pass any data type
30 void generalMethod(T t){
31 cout << "A general template function where we can pass any data type : " << \
32 t << endl;
33 }
34 };
35
36 int main(){
37 // let us create a few different types of objects
38 GeneralClass<int> integerObject;
39 cout << "Let us call the general method to pass an integer value" << endl;
40 integerObject.generalMethod(10);
41 GeneralClass<float> floatObject;
42 cout << "Let us call the general method to pass a float value" << endl;
43 floatObject.generalMethod(10.11);
44 GeneralClass<char> charObject;
45 cout << "Let us call the general method to pass a char value" << endl;
46 charObject.generalMethod('C');
47 GeneralClass<string> strObject;
48 cout << "Let us call the general method to pass a string value" << endl;
49 strObject.generalMethod("Hello World, I an a string!");
50
51
52 return 0;
53 }
54
55 // It appears in the above code, our choice has no limitations.
56 // Now we can create an object and call the same method again and again to pass any \
57 data.
58
59
60 // output
61
62 This is constructor of a general class
63 Let us call the general method to pass an integer value
64 A general template function where we can pass any data type : 10
65 This is constructor of a general class
66 Let us call the general method to pass a float value
67 A general template function where we can pass any data type : 10.11
68 This is constructor of a general class
69 Let us call the general method to pass a char value
70 A general template function where we can pass any data type : C
71 This is constructor of a general class
72 Let us call the general method to pass a string value
73 A general template function where we can pass any data type : Hello World, I an a st\
74 ring!