Broad Network


C++ Container List Synopses

Writing a C++ Container - Part 2

Forward: In the previous part of the series I gave you an overview on how to write your own C++ container.

By: Chrysanthus Date Published: 11 Oct 2012

Introduction

This is part 2 of my series, Writing a C++ Container. In the previous part of the series I gave you an overview on how to write your own C++ container. In this part of the series, I explain the synopsis (summary) of the C++ container list element, the synopsis of the container list itself, and the synopsis of the corresponding iterator. Remember, I said in the previous part of the series that I would use the C++ standard container list to explain how you can write your own C++ container. You should have read the previous part of the series before reaching here.

The synopsis of a class is a summary of the class coding. It indicates the data members (properties) and member functions (methods) of the class. For the functions, you have the prototypes in the synopsis. The synopsis is like the technical requirements for a class. It consists mainly of data member declarations and member function prototypes.

The code I give for the list container, is not really what you will find in the C++ specification; it is my own version. However, the fundamental principles are the same.

Main Components of the Container List
A list consists of elements. Each element is instantiated from the element class. The class used to instantiate the elements, is a class template. There are 3 components for the list: the element, the list itself and the corresponding iterator. The list is also instantiated from a class template. The iterator too, is instantiated from a class template. So, each of the three components is a class template. Actually, each of the three usable components is instantiated from the corresponding class template.

The Element Class Template
Remember, the element consists of three objects. The three objects are in a class template. The first object is a pointer to the previous element. The middle object has the value of interest. The third (last) object is a pointer to the next element. The list resulting from such elements is known as a doubly linked list, because of the two pointers of each element.

In the case of the first element in the list, the first object is a null pointer (null address): this means it has an integer value of zero. In the case of the last element in the list, the third object is also a null pointer (null address): this means it also has an integer value of zero. In the case of a single element in the list, the first object is a null pointer and the third object is also a null pointer. You will see the code of all these as we go on. Null pointer means, pointing to nothing.

For simplicity, consider the three element objects to lie consecutively in memory.

The element class template 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
        };

This is a template, so its parameter is T. This means it is a placeholder (generic type). T is a placeholder for the element value, the middle object. So, at one time, all the elements in the list would have values of int, at another time; they would all have the values of float; at another time, they would all have the values of a particular instantiated class, and so on. All that is because the Element code is a template, with the parameter, "class T". The class can be int now, float later, instantiated class another time, and so on.

This class template has two friends, which are TempList<T> for the list itself (see below) and TempIterator<T> for the iterator (see below).

The argument of the constructor is of type, T. It is actually a constant reference "const T &val". This means, inside the constructor body, you cannot assign any new value to val. val receives its value when the the constructor function is called, and cannot be changed inside the body (curly brackets).

Remember, an element has three objects: the first one holds the address of the previous element. The middle one holds the value of interest (val). The last one holds the address of the next element. The first one is a pointer. In the Element class template, it is called, Predecessor. The last one is also a pointer. In the Element class template, it is called, Successor. The middle element is of type, T and it holds the value of interest. In the Element class template, it is called ElementValue. ElementValue, Predecessor and Successor are data members (properties) of the Element class template. They are identifiers.

The first line in the constructor assigns the argument val, to the class template data member (property), ElementValue. ElementValue is the middle object, of the three objects for the Element. There is only one constructor in the Element class template. It creates an element without knowing which other element is in front of it or behind it, in the list. It does not have to know this. It is the work of the iterator that can move (point) from one element to the next, to determine which element is in front or behind which.

The first statement in the constructor function assigns the value val to ElementValue. The second statement assigns a null address (int of 0) to Predecessor. The third statement in the contructor also assigns a null address, but to Successor. After the object has been instantiated, the iterator will then determine the proper addresses to Predecessor and Successor. At the moment, they are null pointers (with address 0) pointing to no-where. They will seize to become null pointers when the iterator has determined their proper addresses.

Below, in the class template code, you have the ElementValue (middle object), Predecessor (first object) and Successor (third object) objects declared. The rest of the code in the Element class template, keeps the three objects together, as a unit. The name of the class template is Element.

The above code is simple. It is not really the synopsis (summary); it is the complete class. The two code samples below are actually synopses (summaries). The above code and the synopses below should be written in one header file.

The List Class Template Synopsis
A synopsis is a class summary. It consists of data members and member function prototypes. It is like a skeleton of the class. You can also look at it as the class requirements. After that you have the implementation, which has mainly the member function bodies. The implementation code is separated from the synopsis code. You can combine the synopsis code and the implementation code as one code, but that is uncommon.

The list class template synopsis is:

template<class T>
    class TempList
        {
            //friend classes
            friend class TempIterator<T>;
            public:
            //typedef convenience
            typedef TempIterator<T> iterator;
            //constructor
            TempList();
            //destructor
            ~TempList();
            //inspectors and accessors
            int size() const;
            T& front();
            const T& front() const;
            T& back();
            const T& back() const;
            //iterator facilitators
            iterator begin();
            iterator end();
            //convenience functions
            void push_back(const T &val);
            void pop_front();
            //insertion facilitator
            iterator insert(iterator p, const T &val);
            //list facilitators
            iterator erase(iterator p);
            void clear();
            //member assignment and copy constructors
            TempList<T>& operator=(const TempList &S);
            TempList(const TempList<T> &S);
            private:
            //data members
            Element<T> *Front; //pointer to first element
            Element<T> *Back; //pointer to last element
            int ListLength;  // number of elements
        };

I gave the name, "TempList" meaning, "Template List". It is not only a template, it is also a class. It has a class template friend, which is TempIterator<T>. So, at this point, you know that Element has 2 friends which are, TempList<T> and TempIterator<T>, while TempList has one friend, which is TempIterator<T>. TempList<T> is also a friend to TempIterator<T>.

The synopsis has a typedef identifier, which is "iterator", which becomes a short form (replacement) for TempIterator<T>.

It has 3 data members, which are Front, Back and ListLength. Front is a pointer that points to the first element in the list. Back is a pointer that points to the last element in the list. You will see their uses as we go along, in the other parts of the series. ListLength stores the number of elements in the list. If the programmer wants to know the number of elements in the list (size of list), this is the value that is read.

For now just glance through the member function prototypes in the synopsis. I will explain them in details in a different part of the series. The function prototypes represent the methods talked about in the previous part of the series.

TempList<T> has one normal constructor and one normal destructor. It also has an assignment constructor and a copy constructor. The assignment constructor is used to copy one object to another using the = sign. The copy constructor copies one object to another using parentheses (see illustration later).

The Iterator Synopsis
The synopsis of the iterator is:

template<class T>
    class TempIterator
        {
            friend class TempList<T>;
            public:
            //default constructor
            TempIterator();
            //specific constructor
            TempIterator(TempList<T> &L);
            //mutate to next element in list
            TempIterator<T>& operator++();    //prefix
            TempIterator<T> operator++(int);    //postfix
            //mutate to previous element in list
            TempIterator<T>& operator--();    //prefix
            TempIterator<T> operator--(int);    //postfix
            //inspector/mutator operator for an iterator
            T& operator*();
            //test for equality
            bool operator==(const TempIterator<T> &p) const;
            //test for inequality
            bool operator!=(const TempIterator<T> &p) const;
            //bool cast
            operator bool() const;
            protected:
            //specific constructor for TempList use
            TempIterator(TempList<T> *p, Element<T> *q);
            private:
            TempList<T> *ThisList;    //pointer to iterated list
            Element<T> *ElementPtr;    //pointer to current element
        };

I gave the name, TempIterator to the iterator. TempIterator means Template Iterator. The iterator has a friend, which is TempList<T>. This means TempList<T> can access (read and change) all the protected and private members of TempIterator.

Talking about the friendship above, TempList and TempIterator are friends to Element. This means they can access the protected and private members of Element. All three templates are also classes. TempIterator is a friend to TempList, so TempIterator can access all the protected and private members of TempList. TempList is a friend to TempIterator, so TempList can access all the protected and private members of TempIterator.

Which friendship is reciprocal? TempList and TempIterator are friends to one another. That is the only reciprocal friendship. TempList and TempIterator are friends to Element. Element is not a friend to any class. It does not have to. It is very simple with mainly the constructor method. It is more of a tool (element) than a partner. The TempList and TempIterator classes use it. The using is not vice-versa: it does not use TempList or TempIterator. More on this in the next parts of the series.

Back to the Iterator:  Remember, in the TempList class, TempIterator is called an iterator for short. That short form (typedef) name can be used only in TempList and not outside it.

TempIterator has two data members (properties), which are ThisList and ElementPtr. Before the above three classes can work together, each of them has to be instantiated. When all three have been instantiated properly, ThisList (data member of iterator) would be a pointer to the TempList instantiated class (i.e. it would have the start address of the TempList object). After all instantiation, ElementPtr (data member of iterator) would be a pointer to the Element instantiated class (i.e. it would have the start address of the Element object).

TempIterator has two constructor functions: the normal default constructor and a constructor function that takes a pointer to an instantiated TempList class and a pointer to an instantiated Element class, as arguments. The former constructor constructs an iterator (instantiated TempIterator class) without any association with an Element or TempList object (instantiated class). The later constructor constructs an iterator that is associated to an Element and TempList object.

For now, glance through the member function and member operator prototypes in the iterator synopsis; I will explain the details later.

In one of the series in this C++ volume titled, "Function and Operator Overloading in C++" I talked about operator overloading and single parameter (operand). I did not talk about prefix and postfix single parameters. In other words, how do you do operator overloading for single parameters. The iterator synopsis above indicates it for the ++ and -- overloaded operators. ++ is the increment operator and -- is the decrement operator.

When there is a single parameter (operand) and it is prefix, you have an empty parentheses. When the single parameter (operand) is postfix, you have the fundamental object type in the parentheses. There is more; see later

I will explain the bool cast operator later.

The Header File
The above three synopses should be typed in one header file. I will explain the details of a header file later. For now just know that a header file is used to join different C++ files together to form one large file. In the header file, before you type the synopses you have to type the following declarations first:

template <class T> class Element;
template <class T> class TempList;
template <class T> class TempIterator;

These three declarations (prototypes) are for the three synopses. Note that each of them has the name of each class template. If you do not do this, the file will never compile, and will always be issuing error messages. In C++, identifier that is used in a statement should have been declared before (higher up) in the file; if this is not done, your file will never compile. Each of the above three classes uses the name of one or two of the other classes. So the three declaration statements enable a class to use (see) the identifiers of the other classes as predeclared; otherwise the file will not compile and will always be issuing error messages in the light that "something is to be used in a synopses without being declared".

After the above three statements, the synopses can be typed in any order.

That is it, for this part of the series. We take a break here and continue in the next part of the series.

Chrys

Related Courses

C++ Course
Relational Database and Sybase
Windows User Interface
Computer Programmer – A Jack of all Trade – Poem
NEXT

Comments

Become the Writer's Fan
Send the Writer a Message