Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

16.3 Creating Your Own Containers

All of the options that build on existing C++ Standard Library containers incur a certain amount of overhead. When performance demands are critical, or the container requirements very specific, there may be no choice but to implement a container from scratch.

When building from scratch, there are three sets of design requirements that you must meet:

We'll talk about each of these in the next sections.

16.3.1 Meeting the Container Requirements

The C++ Standard Library defines general interface requirements for containers, and specific requirements for specialized containers. When you create a container, the first part of your task is making sure that the basic interface requirements for a container are met. In addition, if your container will be a sequence or an associative container, you need to provide all additional pieces specified for those categories. For anything but the simplest container, this is definitely not a task for the faint of heart.

It's very important to meet the requirements so that users of the container will know exactly what capabilities to expect without having to read the code directly. Review the sections on individual containers for information about the container requirements.

16.3.2 Meeting the Allocator Interface Requirements

A user-defined container makes use of the allocator interface for all storage management. An exception to this is a container that exists in a completely self-contained environment where there is no need for substitute allocators.

The basic interface of an allocator class consists of a set of typedefs, a pair of allocation functions, allocate() and deallocate(), and a pair of construction/destruction members, construct() and destroy(). The typedefs are used by a container to determine the look of pointers, references, sizes, and differences, where a difference means a distance between two pointers. The functions are used to do the actual management of data storage.

To use the allocator interface, a container must meet the following three requirements:

An abbreviated version of the set class appears below. The class interface shows the required typedefs and the Allocator member for this class:

Given this class interface, here's a definition of a possible constructor that uses the allocator. The numbered comments following this code briefly describe the allocator's role. For a more thorough treatment of allocators, see Chapter 15 and the Apache C++ Standard Library Reference Guide entry for allocators.

//1The allocator parameter is copied into a protected member of the container. This private copy can then be used for all subsequent storage management.
//2An initial buffer is allocated using the allocator's allocate function.
//3The contents of the buffer are initialized using the values from the iterator range supplied to the constructor by the start and finish parameters. The construct function constructs an object at a particular location. In this case the location is at an index in the container's buffer.

16.3.3 Iterator Requirements

Every container must define an iterator type. Iterators allow algorithms to iterate over the container's contents. Although iterators can range from simple to very complex, it is not the complexity but the iterator category that most affects an algorithm. The iterator category describes capabilities of the iterator, such as which direction it can traverse. Section 16.4 and the iterator entries in the Apache C++ Standard Library Reference Guide provide additional information about iterator categories.

The example in Section 16.3.2 shows the implementation of a container that uses a simple pointer. A simple pointer is actually an example of the most powerful type of iterator: the random access iterator. If an iterator supports random access, we can add to or subtract from it as easily as we can increment it.

Some iterators have much less capability. For example, consider an iterator attached to a singly-linked list. Since each node in the list has links leading forward only, a naive iterator can advance through the container in only one direction. An iterator with this limitation falls into the category of forward iterator.

Certain member functions such as begin() and end() produce iterators for a container. A container's description should always describe the category of iterator that its member functions produce. That way, a user of the container can see immediately which algorithms can operate successfully on the container.



Previous fileTop of DocumentContentsIndex pageNext file