Implementing the C++ Container List Class Template
Writing a C++ Container - Part 4
Forward: In this part of the series I explain the implementation code of the C++ Container List Class Template.
By: Chrysanthus Date Published: 11 Oct 2012
Introduction
Content of Implementation Code
The data members are not repeated (retyped) in the implementation code. The implementation code consists of member function definitions. There is no start tag or end tag for the assembly of the implementation code. You just define all the functions in a group, making use of the scope resolution operator and the class template name with return type, for each function. You should type the group in one file. For the rest of this part of the series, for each function, I give the name, code and explanation. The different function prototypes are in the synopsis in one of the previous parts of the series. Remember, the name of the list is, TempList.
The TempList Default Constructor
The definition of the default constructor is:
template<class T>
TempList<T>::TempList()
{
ListLength = 0;
Front = 0;
Back = 0;
}
This is a constructor and so it has no return type. It begins in the classical member function class template definition way. Note the position of the scope resolution operator. Remember, the TempList class template has data members, ListLength, Front and Back. ListLength is an int object type that holds the number of elements in the list. Front is a pointer that points to the first element in the list. Back is also a pointer, but it points to the last element (not the sentinel) in the list.
The first statement in the block assigns zero to the int object, ListLength. The TempList constructor creates (instantiates) an empty list, so its length is zero. That is why the first statement assigns zero to ListLength. The list is empty and has no element. So the second statement makes Front a null pointer (assigns null address, int zero). This means that when the empty list is just created, Front points to nowhere. For the same reason, the third statement makes Back a null pointer.
The TempList Destructor
The destructor is the opposite of constructor. It removes the instantiated class from memory. The function definition is:
template<class T>
TempList<T>::~TempList()
{
clear();
}
The body of the function calls the clear() function. The clear() function removes all the dynamic objects (elements) from free store. C++ automatically removes the remaining empty list. C++ will not automatically remove the dynamic objects for you; that is why you need the clear function. I give the details of the clear function later.
Remember, all the functions in this part of the series are member functions of the TempList class template.
The size() Function
This function returns the number of elements in the list. The definition is:
template<class T>
int TempList<T>::size() const
{
return ListLength;
}
The function body has just one line, which returns the number of elements in the list. ListLength is a data member in the list that holds the number of elements of the list. The return type of the function is int; note its position in the declaration. The specifier, const, at the end of the second line makes sure that the body of the function does not change the value of any TempList data member.
This function returns the first element value in the list. The definition is:
template<class T>
T& TempList<T>::front()
{
if (size() = 0)
{
//error message
cout << "List is empty so there is no first element.";
}
else
{
return Front->ElementValue;
}
}
The body is an if-construct. The if-construct checks if the size is zero. If it is zero it issues an error message saying that the list is empty and there is no first element. If the list is not empty, it returns Front->ElementValue, which I explain:
T& in front of the function means you have to return the identifier of a reference (&identifier). Now, Front is a data member of the list. It is a pointer to the first element. The first element (or any other element in the list) is an instantiated class. When you have a pointer to an instantiated class, to obtain the value of its data member, you have to use the arrow, -> operator. "Front->ElementValue" is equivalent (forced) to the the identifier of a reference. Remember, the reference or pointer is used when you want economy of memory.
The front() const Function
This is an overloaded front() function. You can overload a function by adding "const" at the end of the signature line of the function. This means the body of the function cannot change the value of any data member of the class. In such a case, the function is a member of a class. The function definition is:
template<class T>
const T& TempList<T>::front() const
{
if (size() = 0)
{
//error message
cout << "List is empty so there is no first element.";
}
else
{
return Front->ElementValue;
}
}
The main difference between this function and the previous one is the const at the end of the signature line. The const in front makes the value of the effecttive identifier, "Front->ElementValue" constant, so far as "Front->ElementValue" is concerned.
The back() Function
This function returns the last element value in the list. The definition is:
template<class T>
T& TempList<T>::back()
{
if (size() = 0)
{
//error message
cout << "List is empty so there is no first element.";
}
else
{
return Back->ElementValue;
}
}
The explanation is the same as for front(), but this time it is the last element value that is returned. Do not confuse between the last element and the sentinel. The sentinel is just beyond the last element.
The back() const Function
This is an overloaded form of back(). Its definition is:
template<class T>
const T& TempList<T>::back() const
{
if (size() = 0)
{
//error message
cout << "List is empty so there is no first element.";
}
else
{
return Back->ElementValue;
}
}
The explanation is the same as for "front() const", but this time it is the last element value that is returned.
This function instantiates and returns an iterator that points to the first element of the list. The definition is:
template<class T>
TempIterator<T> TempList<T>::begin()
{
return TempIterator<T>(this, Front);
}
The return type is TempIterator<T>, meaning an iterator. The return statement instantiates and returns the iterator, using the iterator constructor function, "TempIterator(TempList<T> *p, Element<T> *q)". In order to instantiate a class template, you need to type the angle backets just after the constructor call. The T all over, is determined when the list class is instantiated; it may be int, float, etc. The arguments for the instantiating iterator are "this" and "Front". "this" is a pointer to the list object in question. "Front" is a pointer to the first element in the list.
The end() Function
This function instantiates and returns an iterator that points to the end of the list. The end of the list is not the last element, it is just beyond the last element. It is the sentinel. The definition is:
template<class T>
TempIterator<T> TempList<T>::end()
{
return TempIterator<T>(this, 0);
}
The explanation is the same as for the begin() function, but this time, the returned iterator is pointing to the end of the list. The sentinel for the list has a null address (int of 0 in argument above); I will explain why and how it is so, later.
The push_back() Function
This function adds an element with its value at the end of the list. It takes the value (or identifier of the value) as argument. It then forms the whole element with the value and adds. The definition is:
template<class T>
void TempList<T>::push_back(const T &val)
{
insert(end(), val);
}
The return type of the function is, void. The specifier "const" means you cannot change the value of val in the function body using the identifier, val. The only statement in the function body is a call to the insert() function. I explain the insert() function below. The insert function takes, end() and val as arguments. end() is a function that returns an iterator that points to the sentinel; the returned value of end() becomes the first argument of insert() above.
After the execution of the push_back() function, the number of elements in the list is increased by 1.
The pop_front() Function
This function removes the first element of the list completely. After that, the number of elements in the list is reduced by 1. The definition is:
template<class T>
void TempList<T>::pop_front()
{
erase(begin());
}
The return type is void. It takes no argument. The only statement in the function body, is a call to the erase() function (see below). The argument to the erase function is the function, begin(). begin() results (returns) in an iterator that points to the first element of the list. In this case the returned (resulting) iterator becomes the real argument to the erase() function.
The insert() Function
This function takes an iterator and value as arguments to insert an element (with the value) into the list. The iterator needs to have been associated with the list(see how later). The function forms the element with the value before inserting. It inserts the new element to displace the element, the iterator was just pointing to. The displaced element moves one position downward within the list. This movement is done by adjusting the values of the Predecessor and Successor pointers of the relevant elements.
The new element can be inserted in front of the list, at the end of the list or within other elements of the list. It can also be inserted into an empty list. After inserting, the Predecessor and Successor pointers of the relevant elements are adjusted. I explain that without code in one of the previous parts of the series. Here, emphasis in the explanation will be more on the code.
The function definition is:
template<class T>
TempIterator<T> TempList<T>::insert(TempIterator<T> p, const T &val)
{
//make sure the iterator is associated with the list before taking decision
if (!(p.ThisList == this))
{
cout << "List and iterator are not yet associated.";
}
else
{
//create the new element with val
Element<T> *curr = new Element<T>(val);
//check if element was actually created before you continue
if (!(curr))
{
cout << "New Element could not be created.";
}
else
{
if (p.ElementPtr != 0)
{ //new element is not the last
//determine successor and predecessor of new element
Element<T> *succ = p.ElementPtr;
Element<T> *pred = succ->Predecessor;
//adjust links to relect the changes to the list
curr->Successor= succ;
curr->Predecessor = pred;
succ->Predecessor = curr;
//determine if new element has become the first in the list
if (succ == Front)
{//yes it is
Front = curr;
}
else
{//no it is not
pred->Successor = curr;
}
}
else
{//iterator p does not point to a list element
if (size() == 0)
{//new element is to become the only element
Front = Back = curr;
}
else
{//curr is to become the last in the list
curr->Predecessor = Back;
Back->Successor = curr;
Back = curr;
}
}
//having added element, add 1 to the number of elements
++ListLength;
//prepare and return an iterator pointing to the new element
p.ElementPtr = curr;
return p;
}
}
}
The content of the whole block is an if-construct, with smaller if-constructs. The main if-construct has to first make sure that the existing iterator and the existing list are already associated (I explain how this association is done later). If not, an error message is issued and the else part of the block to insert the value (and its element) is not executed.
If the existing iterator and existing list are already associated together, then the else part is executed. We now look at what is in the else part. The first thing is that a new element with the value is created in free store. Remember, you do not insert the value alone. You insert the value within an element. The element is created with the new value as follows:
Element<T> *curr = new Element<T>(val);
The right hand expression of the assignment operator creates the element in free store (dynamic memory). This expression is an example of how you call the constructor of a class template. Remember, the constructor of interest (of the element) takes just one argument. The expression returns an address of the element. This address (pointer) is assigned to the new identifier, curr, of type, Element<T> *. This means, curr is a pointer of type Element<T> * and points to an Element<T> element. curr means current (actually 'new' in this case) and it is the pointer that will be used for the rest of the function code to refer to the newly instantiated element in free store.
Before the code continues, it has to be determined if the element was acutually instantiated (created). Remember, free store may not be available. If free store is not available, the element would not be created. The whole code goes now into an if-construct. The construct first checks if curr does not exist (had not been created). If it does not exist, it issues an error message and the else part does not execute. If the else part does not execute, it means the insert() function does not continue; and should not continue if curr (the new element) was not created.
The else part has an if-construct, but this if-construct is not all the rest of the code. The condition of the if-construct checks if the list is not empty and the new element is not the last element. If it is not empty and the new element is not the last elementg it handles the situation. If the list is empty the else part of this if-construct handles the situation. If the list is not empty, the address of the iterator data member, ElementPtr will not be null. I will explain why this is so later. "Not empty" here means the list has at least one element and the new element is not to be the last element. It is the feature, "pointer not null" that is used in the if-condition as follows:
p.ElementPtr != 0
Remember, null address is integer, zero (0).
The if-block begins by determining the successor and predecessor of the new element, with the following statements:
Element<T> *succ = p.ElementPtr;
Element<T> *pred = succ->Predecessor;
The successor is the element the new one has come to replace. The iterator is currently pointing to the successor (element). The address of the successor is currently being held by the data member (property), ElementPtr of the iterator. The address (pointer) is assigned to the new pointer, succ. The predecessor is currently the predecessor of the element to be displaced. The second line here takes care of this and assigns the address (pointer) to the new pointer, pred.
At this point the successor and predecessor pointers have not yet been given to the new element. They are still with the identifiers, succ and pred. The next code segment from the function body gives this for the new element and the new successor element:
curr->Successor= succ;
curr->Predecessor = pred;
succ->Predecessor = curr;
The first two lines here are for the new element with the pointer, curr. The third line is for the new successor element that the new element displaces. We are dealing with the case where the list had at least one element before the new one was introduced. At this point the new element has been given its Successor and Predecessor pointers (address); the new successor element has also been given its predecessor pointer, which has the address of the new element.
In this case the list has at list one element. The new element can be the first element or within the elements of the list. If it is the first element, then the Front data member pointer of the list has to point to it. If it is not, then the Successor pointer of the element now above the new element, has to point to the new element. The next inner if-construct in the code handles this. The inner if-construct is:
if (succ == Front)
{//yes it is
Front = curr;
}
else
{//no it is not
pred->Successor = curr;
}
If before the new element is created (instantiated) the list is empty or the new element is to become the last element, the iterator, through "p.ElementPtr", would be a null pointer (have a null address). If the list were empty, the null address would have been assigned to "p.ElementPtr" (see later). If the new element were to become the last element, then "p.ElementPtr" would be pointing to the sentinel, which has a null address (see later).
There are two possibilities here: if the list is empty, the list member function of size() would return zero. In that case the new element would be the first and the last element. Its pointer (address) has to be assigned to the list data member, Back and to the list data member, Front. That can be done in one of the following ways:
Back = curr;
Front = curr;
or
Front = Back = curr;
For the other possibility, the new element becomes the last element, so the predecessor pointer of the new element has to receive the address (pointer) of the former Back data member; the successor pointer of the former Back (last) element has to receive the address (pointer) of the new element; and the Back data member has to receive the address (pointer) of the new element.
After the element has been inserted, the number of list elements stored in the ListLength data member has to be increased by 1; the iterator through "p.ElementPtr" has to point to the new element; the iterator with the new pointer address, has to be returned. The following code segment from the insert() function code above, does the trick.
++ListLength;
p.ElementPtr = curr;
return p;
At this point some people instantiates a new iterator and return.
This function removes an element completely from the list and then it adjusts the successor and predecessor pointers of the predecessor and successor elements respectively. The member function code is:
template<class T>
TempIterator<T> TempList<T>::erase(TempIterator<T> p)
{
//make sure the iterator is associated with the list before taking decision
if (!(p.ThisList == this))
{
cout << "List and iterator are not yet associated.";
}
else
{
//make sure the iterator is pointing to an element
if (!(p.ElementPtr))
{
cout << "Element does not exist.";
}
else
{
//identify element and its neighbors (if any)
Element<T> *curr = p.ElementPtr;
Element<T> *pred = curr->Predecessor;
Element<T> *succ = curr->Successor;
//determine whether element heads list
if (curr == Front)
{//yes it does
//Successor (if any) now heads the list
Front = succ;
}
else
{//no it does not
//the predecessor should point to its sucessor (if any)
pred->Successor = succ;
}
//determine whether element ends the list
if (curr == Back)
{//yes it does
//predecessor (if any) now ends the list
Back = pred;
}
else
{//it does not
//successor should point to its predecessor (if any)
succ->Predecessor = pred;
}
//the element can now be deleted since its neighborhood is updated
delete curr;
//show in data member ListLength that the element has been removed
--ListLength;
//retrun an iterator that points to the next element (if any)
++p;
return p;
}
}
}
It is a template member function. It has only one parameter, which is an iterator. The function begins by checking if the list and the iterator sent are associated (see how later) in an if-construct. If there is no association, then an error message is sent and the else part which includes the rest of the code is not executed. If the association is there, then the else part is executed. In the else part, there is another big if-construct. This if-construct checks if the iterator is actually pointing to an existing element in the list. The if-condition for this is:
p.ElementPtr
The value of ElementPtr can only be null if the iterator is pointing to the sentinel. In this case the list is empty. The sentinel is a theoretical element just beyond the list. The sentinel has a null address. If this condition is null, no element can be removed, because the list is empty. In this case an error message is issued. Since the else part of this code has the rest of the code, the rest of the code is not executed.
If any element exists, the else part is executed. It begins by creating three pointers: curr, which holds the address of the element to be removed; pred, which holds the address of the predecessor of the element to be removed; and succ, which holds the address of the successor of the element to be removed.
The code then goes on to check if the element to be removed is the first element of the list. If it is the first element, then succ is assigned to Front, which is the data member of the List that holds the address of the first element. If it is not the first element, then succ is assigned to the successor pointer of the predecessor of the element to be removed. That conditioning and assignment is taken care of by an if-construct.
The code then goes on to check if the element to be removed is the last element of the list. If it is the last element, then pred is assigned to Back, which is the data member of the list that holds the address of the last element. If it is not the last element, then pred is assigned to the predecessor pointer of the successor of the element to be removed. That conditioning and assignment is taken care of by an if-construct.
At this point, the pointers of the new predecessor and successor elements have been adjusted. So the element to be removed is redundant. Remember, the complete element and its value is removed. The next statement in the code removes the element off free store as follows:
delete curr;
After the element has been erased, the number of list elements stored in the ListLength data member has to be decreased by 1; the iterator through "p.ElementPtr" has to point to the element that was next; the iterator with the new pointer address, has to be returned. The following code segment from the erase() function code above, does the trick.
--ListLength;
p.ElementPtr = succ;
return p;
If there is no next element, the iterator points to the sentinel, which has a null address.
At this point some people instantiates a new iterator and return.
This member function removes all the elements (including their values) from the list. It is:
template<class T>
void TempList<T>::clear()
{
Element<T> *Ptr = Front;
while (Ptr)
{
Element<T> *Next = Ptr->Successor;
delete Ptr;
Ptr = Next;
};
ListLength = 0;
Front = Back = 0;
}
The function has no parameter. It first declares a pointer, Ptr, and assigns the address of the first element to it. After that you have a while-construct. While the declared pointer is not null, the successor address of the current element is assigned to a new pointer called Next. The current element is deleted off free store. Next is assigned to Ptr; until Ptr becomes null by pointing to the sentinel.
Outside the while loop you set the data members, ListLength, Front and Back, to null.
List Assignment Operator for Instantiation
The prototype of the list assignment operator is:
TempList& operator=(const TempList &S);
This is an assignment constructor, meaning you can use an already instantiated class to instantiate a new object of the same class by copying with the assignment operator. The function definition is:
template<class T>
TempList<T>& TempList<T>::operator=(const TempList<T> &S)
{
TempList<T> &A = S;
return A;
}
Note how the first line of the operator (function) signature has been coded. Inside the function, a reference identifier is created of the class template type (note the use and position of &). The identifier of the reference is returned. I will show you this assignment operator in use in one of the following parts of the series.
The Copy Contructor
This is a constructor function which does the same thing as the above assignment operator but without the assignment operator. In other words, this time, the constructor function has as an argument an already instantiated object, to produce a new object of the same class. The function is:
template<class T>
TempList<T>::TempList(const TempList<T> &S)
{
ListLength = S.ListLength;
Front = S.Front;
Back = S.Back;
}
There is no return type here; that is OK. So, in the function block, the values of the data members of the already instantiated object are copied to those of the object being instantiated.
We have made a long ride for this part of the series. We take a break here, and continue in the next part.
Chrys
Related Courses
C++ CourseRelational Database and Sybase
Windows User Interface
Computer Programmer – A Jack of all Trade – Poem
NEXT