[Basic C++] 11 - Double Pointer in C++

In this post, I am going to talk about the definition of a double pointer and how to use it in real C++ programming. It is a very hard topic to understand for people who do not understand memory, array, and pointer in C++, thus I highly recommend you to read the previous posts first well.

---

 

Table of Contents

1. Definition of double pointer
2. How to use double pointer in n-dimensional array

3. How to use double pointer in list structure

---

 

1. Definition of double pointer

 

As you might have already read at the end of the previous post. A double pointer is a pointer that points to another pointer. A pointer stores the address of a variable, likewise a double pointer stores the address of a pointer (Figure 1).

 

Figure 1 A pointer and double pointer storing the memory address

 

 

See code example 1 to understand how a double pointer works in real C++ code. There are four int variables; an int variable, an int pointer, an int double pointer, and an int triple pointer. They store the address of the previous variable as a chain of events.

 

Code example 1

#include <iostream>

int main()

{

       int* ptr; // pointer to a

       int** dptr; // double pointer to pointer

       int*** tptr; // triple pointer to double pointer

       int a = 10;

       ptr = &a;

       dptr = &ptr;

       tptr = &dptr;

       std::cout << " The value of a = " <<a<< std::endl;

       std::cout << " The address of a = " <<&a<< std::endl;

       std::cout << " ------------------------------ " << std::endl;

       std::cout << " The value of the pointer ptr = " <<ptr << std::endl;

       std::cout << " The address of the pointer ptr = " << &ptr<< std::endl;

       std::cout << " ------------------------------ " << std::endl;

       std::cout << " The value of the double pointer dptr = "<<dptr <<  std::endl;

       std::cout << " The address of the double pointer dptr " << &dptr <<  std::endl;

       std::cout << " ------------------------------ " << std::endl;

       std::cout << " The value of the triple pointer tptr = " << tptr <<  std::endl;

       std::cout << " The address of the triple pointer tptr " << &tptr <<  std::endl;

}

 

Figure 2 result of code example 1

 

From the result, you can clearly see that each pointer stores the address of the previous pointer. It can be interpreted that they have a sort of hierarchy encompassing each other. It becomes clearer when it comes to array pointers since an array pointer is the address of its first element and the other elements are placed in a consecutive manner.

 

 

2. How to use double pointer in n-th dimension array

 

An N-dimensional array is one of the most adequate examples you can take advantage of a double pointer. Let's recap how an array works in memory. 

 

• First of all, an array is a series of data created collectively as a group. When you declare an array, the C++ compiler finds an empty memory space large enough to allocate an array and then create a series of data side by side. The address of an array is the address of its first element.
• Second of all, the size of an array must be constant in the stack memory. If you want to create an array with dynamic size, it must be declared in the heap memory with the "new" keyword. Furthermore, once an array is created, it is not allowed to change the size of the array unless you make a new copy of it.
• Third of all, it is not allowed to pass an array to a function as a copy, but its address is passed.
• Finally, a multidimensional array is not really multidimensional in the stack memory, but just a block of memory. On the other hand, such an array in the heap memory is a group of discretely located values connected by pointers. This is very complicated but the next examples and figures will clear your confusion a bit.

 

Code example 2 - Two-dimensional array in the stack memory

#include <iostream>

int main()
{
    int A[] = { 1,2,3,4,5 };
    int B[2][2] = { {1,2} ,{3,4} };
    for (int i = 0; i < 5; ++i)
    {
        std::cout << &A[i]<<" : "<<A[i] << std::endl;
    }

    std::cout << "---------------------------------\n";

    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            std::cout << &B[i][j] <<" : " << B[i][j] << std::endl;
        }
    }
}

Figure 3 Result of code example 2

Code example 2 and the result show that one and two-dimensional arrays on the stack memory. You can easily declare them on the stack with no error and the elements are created consecutively on the memory. What's interesting is that the two-dimensional array is not really "Two-dimensional". It is a block of memory just like the one-dimensional array (Figure 4).

 

 

Figure 4 Stack memory allocation for arrays.

 

Then what happens if you declare an array on the heap memory?. Figure 5 shows the compilation error when trying to declare a one-dimensional array, which works completely fine, and a two-dimensional, which arises a compilation error. You can not declare a multi-dimensional array on the heap in C++.

 

Figure 5 Compilation error when trying to declare a two-dimensional array on the heap

 

Figure 5 shows how to declare arrays on the heap memory. A one-dimensional array is allocated on the heap memory consecutively juts like the stack, however, a two-dimensional array needs a different method. There are two ways to allocate a multi-dimensional array on the heap and one of them is to use a double pointer, although it's not a nice way to make an effective program.

 

Figure 6 Heap allocation of nD arrays with a double point

Let suppose you want to create a 2x2 array on the heap with the elements {1, 2, 3, 4}. First of all a pointer to an 8-byte array with two elements allocated on the heap. Each 4-byte space means the row of the array and stores the address of the column arrays. Figure 6 shows the heap allocation of nD arrays with a double point.

 

 

Code example 3

#include <iostream>

int main()
{
	// nD array stack allocation
	int S_1D[] = { 1,2,3,4 };
	int S_2D[2][2] = { {1,2},{3,4} };
	
	// nD array heap allocation
	int B_1D[] = { 1,2,3,4 };
	int** B_2D = new int* [2];
	B_2D[0] = new int[2]{ 1, 2 };
	B_2D[1] = new int[2]{ 3, 4 };

	std::cout << "---S_1D:1D array on the stack---" << std::endl;
	for (int i = 0; i < 4;++i)
	{
		std::cout << &S_1D[i] << " - " << S_1D[i] << std::endl;
	}
	std::cout << "---S_2D:2D array on the stack---" << std::endl;
	for (int i = 0; i < 2;++i)
	{
		for (int j = 0; j < 2 ;++j)
		{
			std::cout << &S_2D[i][j] << " - " << S_2D[i][j] << std::endl;
		}
	}
	std::cout << "---B_1D:1D array on the heap---" << std::endl;
	for (int i = 0; i < 4;++i)
	{
		std::cout << &B_1D[i] << " - " << B_1D[i] << std::endl;
	}
	std::cout << "---B_2D:2D array on the heap------" << std::endl;
	for (int i = 0; i < 2;++i)
	{
		std::cout << "Address: " << &B_2D[i] << ", Value: " << B_2D[i] << std::endl;

		for (int j = 0; j < 2;++j)
		{
			std::cout << &B_2D[i][j] << " - " << B_2D[i][j] << std::endl;
		}
	}
}

Figure 7 Result of code example 3

 

Code example 3 shows how exactly nD array allocation works on the stack and heap. Four nD arrays, 1D stack array, 2D stack array, 1D heap array, 2D heap array, were created and their contents were printed on the console.

 

[1] 1D stack array : The elements are consecutively allocated on the stack.

[2] 2D stack array : The elements are consecutively allocated on the stack as a block of memory even though it's 2D.

[3] 1D heap array : The elements are consecutively allocated on the heap.

[4] 2D heap array : The elements are discretely allocated on the heap. The double pointer points to the row array (8 bytes) which stores the address of the column arrays. the row array points to the column arrays which are allocated two different spaces on the heap.