The creators of C++ took immense care to create a library that was efficient, portable, and reusable. The Standard Template Library (STL) can be summed up into iterators, algorithms, and containers. In this article, I will concentrate on analyzing and extending the containers that STL provides.
The STL library offers a number of useful containers. STL is easily extensible by adding algorithms, and once you have enough experience with the STL, you can even add containers.
Containers are implemented with generic data structures, which have certain insertion times, removal times, and traversal times. If you want, you can implement a data structure that’s tailored for your particular application.
To extend STL, you don’t need to derive from the included classes. STL is not programmed in such a way as to be extensible via inheriting from them as base classes. Their destructor is not even virtual, which makes the decision to inherit from them quite difficult.
STL was programmed in an orthogonal manner. Each container provides a certain set of iterators, and each algorithm has a set of iterators that function in it. Let’s look at the types of containers the STL includes and the iterators each type implements. Then, I’ll implement a custom bidirectional iterator and a subset of a sequence container.
Take a step back
For some background information on STL, read the first two articles in this series:
Container categories and iterator types
The containers in the library fall into two categories, as listed in Table A. Each category has its own set of characteristics, which are outlined in Table B.
There are five types of iterators:
- Input iterators
- Output iterators
- Forward iterators
- Bidirectional iterators
- Random access iterators
In STL, all sequence containers implement random access iterators, and all associative containers implement bidirectional iterators.
The best way to see a full implementation of an iterator is to open the source file for your favorite STL container. Go to SGI’s STL Web site for a reference implementation.
Bidirectional iterator requirements
To create a bidirectional iterator, I need only to declare a class that possesses the abilities shown in Table C.
In my implementation of an iterator, I also need to define a set of iterator traits, listed in Table D.
Let’s assume that you are specializing a vector::iterator template, vector<int>::iterator. The value_type would be int, the pointer would be int *, and the reference would be int &.
Our iterator category is bidirectional_iterator_tag, and the difference_type is int.
Listing A contains the result of an implementation of a bidirectional iterator. Our container will implement the iterator using an array, so our iterator merely needs to increment and decrement pointer values. If I were to implement a heap, the mathematics involved would be more complex.
In the interests of clarity, I did not implement error checking. You will also notice that we do not declare a const version of our iterator for proper container support.
Sequence container subset
Now, I’ll implement a subset of the sequence container. In this way, I will show you how to write a simple class of iterators and a simple container class and yet still be able to use the algorithms that STL provides to manipulate your data.
Let’s assume that you are specializing a vector template, vector<int>. The value_type would be int, the pointer would be int *, and the reference would be int &.
The difference_type like in the case for the iterator is int and the size_type would be int, in bytes, for our memory model.
I have decided against implementing a const_iterator, as that would require a reproduction of Listing A with const declaratives.
Table E describes the common member functions for containers. I won’t delve into which traits are specific to sequence containers or associative containers.
Listing B is our implementation of a simple sequence container. I decided to create a bare minimum container that can take advantage of a number of algorithms to illustrate the concept of extending STL. You can easily customize your own container to implement such things as an AVL tree that would check whether the data structure was balanced on insertion, and if not, will rotate the branches accordingly.
I’ve implemented begin, end, empty, size, max_size, and a default constructor that initializes our array to zero elements. I also added a custom function, which is common in sequential containers, that allows the user to push elements back into the array. Our array is artificially limited to a maximum of 16 elements and is not dynamically resizable.
All of the STL containers in the library can change their default allocator. STL provides a default allocator that can be customized by the implementation for the current memory model.
You can also pass a default allocator to any standard STL container if you want to change the memory model. You might want to do this to detect memory leaks by inserting allocation counters. You may also opt to allocate memory using a predefined heap that is a programmer-controlled piece of memory for efficiency reasons. This is all possible with the containers in STL.
Our container doesn’t use the generic allocator class, since that would introduce undue complexity to a simple example. But it’s important to know that allocators exist and that you can take advantage of them when you write customized container code.
The resulting container
We’ve now created a simple container, which possesses a bidirectional iterator. Listing C shows the output of this container when compared against a vector. We passed our container and iterator combination through the following STL algorithms:
- A standard C++ for loop using the iterator class
- A for_each loop with a functor that prints the value
- A find looking for a specific value
- A max_element, which determines the highest value in the container
I also decided to print the results of the member functions, size, max_size, and empty as an exercise.
Listing D is the source code used to generate the output. You should be able to easily notice that the code for the vector and the custom container is virtually identical. We have successfully extended STL with a custom container. You can download the source code for the entire example here.
Do you want to see more advanced C++ coverage? Tell us what you want to read or post a comment below.