C++ Container Overview
Writing a C++ Container - Part 1
Forward: In this part of the series I give you an overview on how to write your own C++ container.
By: Chrysanthus Date Published: 11 Oct 2012
Introduction
In this series, I will re-create the list, using my own body code. So it is like we (you and me) shall carry out a project, to create a C++ list container. I will be explaining as we go along. I hope you will understand and appreciate everything.
Remember, there are two main types of containers in C++: Sequence and Associative Containers. The list is a sequence container.
Prerequisite
This series is part of my C++ course volume. You should click the "C++ Course" link below to see the position in which the series fits into the volume and what you should have studied.
The C++ Array
You should know how to create and use the C++ array already. The C++ array has its limitations and that is why the containers were developed (invented). The content of an array is a series of values. Each value may be a fundamental object type or an instantiated class (object).
An Array Element
The element of an array is one of its values and its surrounding coding.
A Container
A container is a more flexible array with properties and methods. A container is bigger in overall code (coding) than an array. A container is a class.
The element of a container is much bigger than that of an array. In fact each element of a container has at least 3 objects. So, if a container has 5 elements, it means it has at least 15 (3 X 5) objects. The list (one of the standard C++ containers) in particular, has 3 objects per element. Of course, the coding of the objects that form the element, is part of the element.
For simplicity, assume that the objects of a container element lie in consecutive areas (one next to the other) in memory. In the case of a list, the first object of an element is a pointer to the previous element in the list. The middle object has the value of interest. The third (last) object is a pointer to the next element in the list.
Iterator
An iterator is an elaborated pointer. You increment a pointer to move from one array element to the next. You cannot do this with a container. That is, you cannot increment a pointer to move from one container element to the next. As you can see from above, one container element has more than one object, so incrementing a pointer might take you from one object to the next within the element. That is not what you want. So an iterator comes into play.
An iterator is actually an object instantiated from a class. It is always pointing to an element in the container. The iterator is an entity separated from the container. If you increment (++) an iterator it points to the next container element. If you decrement (--) an iterator it points to the prevous container element.
The secret of iterator behavior lies in the fact that an element of a container has the pointers to the next and previous elements. An iterator uses these pointers of the element to move from one element in the list (container) to the next or previous.
It should be possible to use the dereference operator in fromt of an iterator to obtain the value pointed to, in the list. Remember, the list and the iterator are two different entities; but the iterator is always pointing to an element in the list (contianer).
You will see more about the iterator for the list as we go along (in the other parts of the series).
A container has a generalized name. The generalized name is the class name. From the generalized name a specific name is written for the specific container at instantiation. C++ has a predefined container whose generalized name is, vector. From a vector you can instantiate a particular vector with a specific name.
A container may have a property (data member) that holds its initial number of elements. It may also have another property that holds the initial value for each element in the container. Such properties (values) are given during instantiation, as parameters of the container constructor function. A container can have other properties (data members).
It should be possible to add a new element to a container, delete an element or change the value (middle object content) of an element.
A container also has methods (member functions) to manipulate the container (to add, delete elements, etc.).
Container Technology
A container is actually a class template. Because it is a templete it can take different types of values. So, in a program, at one point, all the values may be ints; at another point all the values may be float; yet at another point down below in the program, all the values may be instatiated objects of a particular class. It is the template feature that gives it the possibility to have different data types at different times, in one program.
The different elements of a list are accessed by pointers (memory addresses). The elements are usually in free store (dynamic memory). So, in theory, the length of a container is limited by the size of free store.
The rest of this series will concentrate on the C++ standard container called, list. As said above, the code is mine. For the list container, the Element, List itself and the Iterator are three entities. The list itself consists of the elements. The iterator works with the list, and is separated from the list. Each element is part of the list. Below are the method (member function) names of the list:
size(): returns the number of elements in the list.
front() const : returns the first element in the list in an rvalue fashion.
front() : returns the first element in the list.
back() const: returns the last element in the list in an rvalue fashion.
back() : returns the last element in the list.
begin() const: returns a constant iterator pointing to the first element in the list.
begin(): returns an iterator pointing to the first element in the list.
end() const: returns a constant iterator pointing to a sentinel immediately beyond the last element in the list. If you continue to increment an iterator, as soon as it goes past the list, what it points to is called a sentinel.
end(): returns an iterator pointing to a sentinel immediately beyond the last element of the list.
push_back(const T &val): to add a value of interest at the end of the list, making the list to increase by one element.
pop_front(): to remove the first element (value and code) from the list, making the list to reduce in size by one element.
insert(iterator p, const T &val): inserts a value of interest into the list immediately in front of the element to which iterator p points. The function returns an iterator that points to the new element.
clear(); removes all elements from the list, giving the list a size of zero (the list will still continue to exist).
erase(iterator p): removes the element from the list to which iterator p points. The function returns an iterator that points to the next element that previously followed the removed element.
That is it for this part of the series. In the next part of the series, I will present the requirement phase of a container list. See you there.
Chrys
Related Courses
C++ CourseRelational Database and Sybase
Windows User Interface
Computer Programmer – A Jack of all Trade – Poem
NEXT