Principles of a Simple C++ Sequence Container
Container Library Sequences in C++ Simplified - Part 2
Forward: In this part of the series, we look at the Principles of a Simple C++ Sequence Container.
By: Chrysanthus Date Published: 24 Aug 2012
Introduction
Note: If you cannot see the code or if you think anything is missing (broken link, image absent), just contact me at forchatrans@yahoo.com. That is, contact me for the slightest problem you have about what you are reading.
Some Rules Concerning the List
I will create a simple C++ container proper, in the next part of the series. There are some rules concerning the array in the dynamic memory that you should recall or learn. We look at them for the rest of this tutorial.
Creating an Array in Dynamic Memory
The following statement, copied from the class constructor above, creates an array in dynamic memory.
T *listPtr = new T[noIniCells];
T is a placeholder for the object type if you are dealing with a template. If you were not dealing with a template, then T would be say, int or char or float, etc.
Accessing an Element
For an int array, if you want the new value of an element, say of index 3 to be 17, you would type the statement:
listPtr[3] = 17;
You use the pointer and the square brackets; you do not precede the pointer with * for the value; the square brackets take care of that. For the simple container, we shall have a slightly different way of accessing the values.
You can increase the size, one element at a time. To do this, use the pointer with the index of the expected next element to access the next element. If the above array has 5 elements initially, it means the highest index is 4. If the array is for ints, to increase the size of the array by one and give the value 26 to the new element, type the statement:
listPtr[5] = 26;
Is Dynamic Memory Available?
Dynamic memory (free store) may not be available when you want it. So you have to check if dynamic memory is available before you create the array and also check if it is available before you add a new element. The following code will check and create the initial list for the above constructor:
T *listPtr = new T[noIniCells];
if (listPtr != NULL)
{
for (int i = 0; i < noIniCells; ++i)
{
listPtr[i] = defaultObj;
}
}
else
{
cout << "Initial list could not be created in dynamic memory.";
}
If there is no dynamic memory, the request for it (new T[noIniCells]) returns NULL. So after attempting to create the list, you check if the pointer is NULL. If it is not NULL, you proceed to fill the list with the default values.
When you add an element to the list, you can check if dynamic memory was available by verifying if NULL was returned. There is a problem here: When you add an element using the square brackets and array pointer as seen above, the pointer is not incremented. You have to increment the pointer a number of times until it is pointing to the added element, before you can use it to check if the returned value is NULL. The following code illustrates this for an int dynamic array.
#include <iostream>
using namespace std;
int main()
{
int *listPtr = new int[5];
listPtr[0] = 0;
listPtr[1] = 1;
listPtr[2] = 2;
listPtr[3] = 3;
listPtr[4] = 4;
//add new element.
listPtr[5] = 5;
++listPtr;
++listPtr;
++listPtr;
++listPtr;
++listPtr;
if (listPtr == NULL)
{
cout << "Element could not be added in dynamic memory.";
}
--listPtr;
--listPtr;
--listPtr;
--listPtr;
--listPtr;
return 0;
}
There is still a problem: Assume that the new element could not be added because its pointer would point to a memory position that has already been taken by some other object unknown to us. In that case when you increment the pointer the number of times it would still point to an address that exist which is not NULL. In this case, the if-check with NULL will tell us that an address exists but the address would not have our element (and its value). This is a wrong conclusion. A better test is as follows:
if (*listPtr != 5)
{
cout << "Element could not be added in dynamic memory.";
}
In the if-condition, we dereference the pointer to the memory position of the supposed added object and we see if the returned value is the same as the value we sent for the added element. In the program above the value we sent was 5.
A pointer is the address of an object in memory. We saw a problem above that when you move the pointer of the array (array name) ahead a number of times, you have to move it behind the same number of times, otherwise the indexing will go wrong. So it is not advisable to move the pointer of the array.
You can have more than one pointer pointing to the same address in memory; that is you can have pointers of different names pointing to the same address. In the above code, we wanted the address of the last (newly added) element. To solve the above problem (index problem), it is good to have a pointer of a different name that will scan your object for you to get the address you are looking for. This address can be returned or saved somewhere in an object (identifier). In that way the pointer of the array (array name) will not change its position and the indexing using the array name will remain OK. The fear of the indexing problem will not be there. For the above code, the returned or saved address will then be used to see if dynamic memory was available.
You need a class (an object instantiated from it) that will have the scanning pointer and then return or save the address you want. Such an object can be called an iterator. In practice, iterators for the containers of the Container Library are more complex than this. We shall not go into any of such complexity here.
The following code gives the class of a simple iterator for the above problem:
class Iter
{
public:
int *retPtr;
Iter(int indx, int *ptr)
{
int *iterPtr = ptr;
for (int i=0; i<indx; ++i)
{
++iterPtr;
}
retPtr = iterPtr;
}
int *retrnPtr()
{
return retPtr;
}
};
The last statement in the constructor assigns the final incremented pointer to the property of the class. The second method in the class, returns this final incremented value. That is how our iterator works. It takes a new pointer to a position and leaves it there, and does not take it back to its start position. Practical iterators work in a similar way. With practical iterators, if you want to change the position of the iterator (pointer), you have to move it from the position it was left, and not from its start position.
#include <iostream>
using namespace std;
class Iter
{
public:
int *retPtr;
Iter(int indx, int *ptr)
{
int *iterPtr = ptr;
for (int i=0; i<indx; ++i)
{
++iterPtr;
}
retPtr = iterPtr;
}
int *retrnPtr()
{
return retPtr;
}
};
int main()
{
int *listPtr = new int[5];
listPtr[0] = 0;
listPtr[1] = 1;
listPtr[2] = 2;
listPtr[3] = 3;
listPtr[4] = 4;
//add new element.
listPtr[5] = 5;
Iter myIter(5, listPtr);
int *returnPtr = myIter.retrnPtr();
if (*returnPtr != 5)
{
cout << "Element could not be added in dynamic memory.";
}
else
{
cout << listPtr[0] << "\n";
cout << listPtr[1] << "\n";
cout << listPtr[2] << "\n";
cout << listPtr[3] << "\n";
cout << listPtr[4] << "\n";
cout << listPtr[5] << "\n";
cout << "\n";
cout << *returnPtr << "\n";
}
return 0;
}
In the next part of the series, we shall use the knowledge we have developed so far to create a simple C++ Sequence (container). Let us take a break now and then go there later.
Chrys
Related Courses
C++ CourseRelational Database and Sybase
Windows User Interface
Computer Programmer – A Jack of all Trade – Poem
NEXT