Using the C++ Container List Element
Writing a C++ Container - Part 3
Forward: In this part of the series I talk about the C++ Container List Element.
By: Chrysanthus Date Published: 11 Oct 2012
Introduction
Element Code
The complete code for the element is:
template<class T>
class Element
{
//friend classes
friend class TempList<T>;
friend class TempIterator<T>;
protected:
//default constructor
Element(const T &val)
{
ElementValue = val;
Predecessor = 0;
Successor = 0;
};
private:
//data members
T ElementValue;
Element *Predecessor; //pointer to previous element
Element *Successor; //pointer to next element
};
It is a class template with the name, Element. It is quite short. So in this series it is placed in the header file. In the previous part of the series, I described the Element content. In this part of the series I say how it is used.
Element Constitients
Each element consists mainly of three objects. The first object is the Predecessor pointer that holds the address of the previous element. The second (middle) object holds the value of interest. The third (last) object is the Successor pointer that holds the address of the following element in the list. For simplicity assume that the three objects lie next to one another, consecutively in memory.
Pointed Element
When the Predecessor or Sucessor pointer is pointing to an element, it is actually pointing to the start address of the element.
Empty List
When the list is empty its has no element. This means there is no instantiated element class for an empty instantiated List class.
For a list to have one or more elements, the List (TempList) class must have been instantiated. Any element that is part of the list must have been instantiated, as well. Remember, we have three related classes. It is the instantiated classes (objects) that work together and not the classes themselves.
If an element is alone in a list, it means it has no element in front of it and no element behind it. In this case, the values of the Predecessor and Successor pointers are each null (int of 0); meaning they point to no-where.
In this case, the only element in the list has a value of interest. This means that the ElementValue data member of the Element has been assigned a value.
Note: You cannot have an element in the list without a value of interest. You can have an empty list without any element, but you cannot have an empty element in the list. Once a list acquires an element, it acquires the element with the element's value of interest.
First Element
I look at the case here, for the first element, where a list has more than one element. In this case the Predecessor pointer of the first element is a null pointer (has null address - int of zero). The Successor pointer has the address of the next element in the list.
Last Element
I look at the case here, for the last element, where a list has more than one element. In this case the Predecessor pointer of the last element is pointing (has the address) to the previous element. The Successor pointer is a null pointer (has null address - int of zero).
I look at the case here, for element within list, where a list has at least three elements. In this case, the Predecessor pointer of the element is pointing (has the address) to the previous element. The Successor pointer has the address of (is pointing to) the next element in the list.
Behavior of the Iterator
The element (Element<T>), the list (TempList<T>) and the iterator (TempIterator<T>), work together after each has been instantiated. Everything being equal, the iterator would first point to the start of the list if it is empty or to the first element, if the list is not empty (see actual implementation later). After that the iterator can be incremented (a number of times) to point to any other element in the list.
Remember from the previous part of the series that the iterator has an overloaded dereference operator. This iterator overloaded dereference operator can be used to obtain the value of the element that the iterator is pointing to. The value obtained is actually the value of the middle object (ElementValue) of the element.
Inserting a Value in a List
When a value is inserted in a list, it is a whole element that is inserted into the list. The value (element) is inserted using the iterator. The iterator is always pointing to an element in the list. The inserted element is inserted just above the element that the iterator was pointing to. After that the iterator starts pointing to the inserted element.
Just after insertion, the Predecessor pointer of the inserted element has to be made to point to the new previous element in the list; the Successor pointer has to be made to point to the new next element in the list; the Successor pointer of the new previous element has to be updated to point to the inserted element in the list; the Predecessor pointer of the new next element has to be updated to point to the inserted element in the list.
If the inserted element becomes the first element, then its Predecessor pointer has to be given the null address. If the inserted element becomes the last element, then its Successor pointer has to be given the null address.
Erasing is the opposite of inserting. The element that the iterator is pointing to, is the one that is erased. After that the iterator points to the element that was below the erased element. The Predecessor and Successor pointers of the related elements have to be adjusted (updated).
The Sentinel
As you keep incrementing the iterator, the address it just points to at the end of the list, is called the sentinel. In good coding, precaution must be taken so that the abstract value of the sentinel is not accessed, in the name of accessing an element of the list. You will see the case of the container list in the following parts of the series.
Adding a Value
Adding a value means adding an element with its value. The element is added at the bottom of the list, increasing the size of the list by 1. Adding an element uses the insert technique, while the iterator is pointing to the sentinel. The Predecessor and Successor pointers of the related elements have to be adjusted (updated).
That is it for this part of the series. We stop here and continue in the next part with coding.
Chrys
Related Courses
C++ CourseRelational Database and Sybase
Windows User Interface
Computer Programmer – A Jack of all Trade – Poem
NEXT