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.

Container basics
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.
Table A

Sequence containers

lists, deque, vector

Sorted associative containers

set, multiset, map, multimap

STL containers
Table B


Type newobj


Allow initialization through default constructor


Type newobj( )


Allow initialization through default constructor


Type(srcobj)


Copy constructor, Type(object) = object


Type newobj(srcobj)


Copy constructor, newobj = srcobj


obj1 == obj2


Equivalent relation, bool result


obj1 != obj2


Equivalent relation, result should equal
!(obj1 == obj2)


newobj = srcobj


Assignment operator, must return Type &


*object


Dereference element to provide access to reference


object -> member


Provide access to member of element


++object


Preincrement, returns new position


–object


Predecrement, returns new position


object++


Postincrement, returns old position


object–


Postdecrement, returns old position

Common traits of containers

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.
Table C


const_iterator


The class that implements this container’s const iterator


const_reference


Const reference to the specialization type


difference_type


Represents difference between two iterators


iterator


The class that implements this container’s iterator


reference


Reference to the specialization type


size_type


Type that represents the size of the container


value_type


Specialization type

Class abilities

In my implementation of an iterator, I also need to define a set of iterator traits, listed in Table D.
Table D


difference_type


Represents difference between two iterators


iterator_category


One of the five iterator categories


pointer


Pointer to the specialization type


reference


Reference to the specialization type


value_type


Specialization type

Iterator traits

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.

The implementation
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.
Table E


Type obj


Allows initialization through default constructor


Type newobj(srcobj)


Copies constructor, Type(object) = object


Type newobj(beg, end)


Creates container and copies elements from beg to end


obj.size( )


Returns the number of elements in object


obj.empty( )


Returns a bool stating whether container is empty


obj.max_size( )


Returns the maximum number of elements possible


obj1 == obj2


Checks all elements in containers for equality


obj1 != obj2


Equivalent to !(obj1 == obj2)


obj1 < obj2


Checks all elements in containers for predicate


obj1 > obj2


Checks all elements in containers for predicate


obj1 <= obj2


Checks all elements in containers for predicate


obj1 >= obj2


Checks all elements in containers for predicate


obj1 = obj2


Assignment of all elements in container


obj1.swap(obj2)


Swaps the data in containers obj1 with obj2


swap(obj1, obj2)


Swaps the data in containers obj1 with obj2


obj.begin( )


Returns the iterator for the first element


obj.end( )


Returns the iterator for the last element + 1

Common member functions of containers

The implementation
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.

Allocators
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.


More C++

Do you want to see more advanced C++ coverage? Tell us what you want to read or post a comment below.