Developer

Extending the C++ STL with custom containers

The Standard Template Library (STL) helps C++ developers deliver robust code fast. Find out how you can extend customized containers--a key component of the STL.


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.

 

 

 

 

 

Editor's Picks