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:
container interface requirements
allocator interface requirements
iterator requirements.
We'll talk about each of these in the next sections.
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.
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:
A container needs to have a set of typedefs that look like the following:
typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef implementation_defined iterator;
typedef implementation_defined iterator;
A container also needs to have an Allocator member that contains a copy of the allocator argument provided by the constructors:
protected:
Allocator the_allocator;
A container needs to use that Allocator member for all storage management. For instance, our set container might have a naive implementation that simply allocates a large buffer and then constructs values on that buffer. Note that this not a very efficient mechanism, but it serves as a simple example. We're also going to avoid the issue of Allocator::allocate() throwing an exception, in the interest of brevity.
An abbreviated version of the set class appears below. The class interface shows the required typedefs and the Allocator member for this class:
#include <memory>
namespace my_namespace {
template <class T, class Allocator = std::allocator<T> >
class set
{
public:
// typedefs and allocator member as above
typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type
difference_type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference
const_reference;
// Our iterator will be a simple pointer
typedef Allocator::pointer iterator;
typedef Allocator::const_pointer iterator;
protected:
Allocator the_allocator; // copy of the allocator
private:
size_type buffer_size;
iterator buffer_start;
iterator current_end;
iterator end_of_buffer;
public:
// A constructor that initializes the set using a range
// from some other container or array
template <class Iterator>
set(Iterator start, Iterator finish,
Allocator alloc = Allocator());
iterator begin() { return buffer_start; }
iterator end() { return current_end; }
};
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.
template <class T, class Allocator>
template <class Iterator>
set<T,Allocator>::set(Iterator start, Iterator finish,
Allocator alloc)
: buffer_size(finish-start + DEFAULT_CUSHION),
buffer_start(0),
current_end(0), end_of_buffer(0)
{
// Copy the argument to our internal object
the_allocator = alloc; // 1
// Create an initial buffer
buffer_start = the_allocator.allocate(buffer_size); // 2
end_of_buffer = buffer_start + buffer_size;
// Construct new values from iterator range on the buffer
for (current_end = buffer_start;
start != finish;
current_end++, start++)
the_allocator.construct(current_end,*start); // 3
// Now let's remove duplicates using a standard algorithm
std::unique(begin(),end());
}
} // End of my_namespace
| //1 | The allocator parameter is copied into a protected member of the container. This private copy can then be used for all subsequent storage management. |
| //2 | An initial buffer is allocated using the allocator's allocate function. |
| //3 | The 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. |
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.