Back to TOC Columns

Standard C/C++

P. J. Plauger

Containers

Managing collections of objects has long been an essential but tedious part of programming. Finally, Standard C++ promises relief from the drudgery. Here's another thing a long time coming: the 100th installment of this column!

Prolog

This column is a milestone for both me and for C/C++ Users Journal. It is the hundredth consecutive column that I have written for CUJ. And, since this column has been in every issue of the magazine, it is the hundredth issue of CUJ. I am mildly astonished that I have never missed a deadline, particularly given my penchant for shaving things fine at times. I am less astonished to see CUJ as a whole going strong after all these years. Its strength is rooted deeply in the excellent staff in Lawrence, Kansas that turns it out once a month -- and in the contributions of so many practicing programmers among our readership. I'm happy to be here, in such good company.

Much less happily, I write these words the day after my father died. He meant many things to me, like any father, but I particularly remember a pivotal moment from a third of a century ago. I was a nerdy, clueless college sophomore, and I had just been bruised by Princeton's "Bicker'' system -- a particularly nasty variant of fraternity rush week. I wanted to sign up with a certain club, but was passed over. My father said, simply, "It's not what book you write in, but what you write in the books.''

I wrote my first computer program just a few months later. Since then, I've published over a dozen books, several hundred articles, a modicum of science fiction, and more reference manuals than I can count. My father's encouragement, at that dark moment, really paid off. So Dad, this one's for you, just like all the others.

Introduction

My long running series on the Standard Template Library (STL) now enters its third and final phase. I began, about a year ago, by describing iterators. An iterator is a generalization of a pointer, used throughout STL to access the elements of a sequence. The past few columns have described the numerous algorithms that manipulate sequences. Now it is time to study the various containers that STL provides. This installment begins the process with a general overview of STL containers.

A container is a class that manages a sequence. Member functions let you insert new elements in the sequence, erase (delete) existing elements, and locate them. The functions return iterators to designate elements in the sequence, so you can apply the various algorithms to part or all of the controlled sequence.

Managing a sequence involves tradeoffs. If you plan to make frequent insertions and/or erasures throughout a sequence, for example, you might prefer a container that performs such actions in constant time -- the time to perform an insertion or erasure does not increase with N, the number of elements in the sequence. Such a container is not likely to help you locate a given element in constant time as well, however. You have to decide which operations have more influence on overall program performance, then choose a suitable container type.

For this particular tradeoff, you can also compromise. It is possible for a container to support insertions, erasures, and locates all in time proportional to the logarithm of N (written log N). The logarithm increases with N, but much more slowly than N, so such time complexity may be quite satisfactory all the way around. But you then pay the price in a different dimension.

To support logarithmic behavior such as this, a container must represent its controlled sequence as some sort of ordered tree data structure. A tree stores three pointers along with the value of each element, to designate the parent element and two children. If the element value itself requires a large amount of storage, the additional overhead may be unimportant. But if the element value requires little storage, and the program allocates numerous elements, the extra overhead for a tree may prove to be prohibitive. In that case, one of the simpler container types will supply a better tradeoff. It will require fewer pointers per element, perhaps even none, at the cost of worse time complexity for certain operations on the controlled sequence.

STL thus provides an assortment of different container template classes for you to choose among. In all cases, one of the template parameters is the type of elements you wish to store in the controlled sequence. You can specialize these classes for elements of any object type that meets just a few minimum requirements:

The STL container template classes are:

Table 1 summarizes the time complexity of operations on each of these template container classes. It also shows the number of additional pointers required for each element of the controlled sequence. The Standard Template Library also defines several container adapters. These are containers that are implemented in terms of other containers. They intentionally restrict how you can access elements:

I save these container adapters for last.

I describe here the properties required of all containers in terms of a generic template class Cont. An actual container template class may have additional template parameters. It will certainly have additional member functions.

Template Class Cont


template<class T,
        p class A = allocator<T> >
    class Cont {
public:
    typedef A allocator_type;
    typedef T0 size_type;
    typedef T1 difference_type;
    typedef T2 reference;
    typedef T3 const_reference;
    typedef T4 value_type;
    typedef T5 iterator;
    typedef T6 const_iterator;
    typedef T7 reverse_iterator;
    typedef T8 const_reverse_iterator;
    iterator begin();
    const_iterator begin() const;
    iterator end();
    iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator
        rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator
        rend() const;
    size_type size() const;
    size_type max_size() const;
    bool empty() const;
    A get_allocator() const;
    iterator erase(iterator it);
    iterator erase(iterator first,
                   iterator last);
    void clear();
    void swap(Cont x);
protected:
    A allocator;
    };


The template class describes an object that controls a varying-length sequence of elements, typically of type T. The sequence is stored in different ways, depending on the actual container.

The object allocates and frees storage for the sequence it controls through a protected object named allocator, of class A. (See "Standard C/C++: Allocators,'' CUJ, June 1996.) Such an allocator object must have the same external interface as an object of template class allocator. Note that allocator is not copied when the object is assigned. All constructors store an allocator argument (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence.

What follows is a description, in alphabetical order by name, of the members of the generic template class Cont.

Member Type Cont::allocator_type

typedef A allocator_type;


The type is a synonym for the template parameter A.

Member Function Cont::begin

const_iterator begin() const;
iterator begin();


The member function returns an iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

Member Function Cont::clear

void clear() const;


The member function calls erase(begin(), end()).

Member Type Cont::const_iterator

typedef T6 const_iterator;


The type describes an object that can serve as a constant iterator for the controlled sequence. It is described here as a synonym for the unspecified type T6.

Member Type Cont::const_reference

typedef T3 const_reference;


The type describes an object that can serve as a constant reference to an element of the controlled sequence. It is described here as a synonym for the unspecified type T3 (typically A::const_reference).

Member Type Cont::const_reverse_iterator

typedef T8 const_reverse_iterator;


The type describes an object that can serve as a constant reverse iterator for the controlled sequence. It is described here as a synonym for the unspecified type T8 (typically reverse_iterator or reverse_bidirectional_iterator).

Member Type Cont::difference_type

typedef T1 difference_type;


The signed integer type describes an object that can represent the difference between the addresses of any two elements in the controlled sequence. It is described here as a synonym for the unspecified type T1 (typically A::difference_type).

Member Function Cont::empty

bool empty() const;

The member function returns true for an empty controlled sequence.
Member Function Cont::end

const_iterator end() const;
iterator end();


The member function returns an iterator that points just beyond the end of the sequence.

Member Function Cont::erase

iterator erase(iterator it);
iterator erase(iterator first,
               iterator last);


The first member function removes the element of the controlled sequence pointed to by it. The second member function removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

Member Function Cont::get_allocator

A get_allocator() const;


The member function returns allocator.

Member Type Cont::iterator

typedef T5 iterator;


The type describes an object that can serve as an iterator for the controlled sequence. It is described here as a synonym for the unspecified type T5.

Member Function Cont::max_size

size_type max_size() const;


The member function returns the length of the longest sequence that the object can control.

Member Function Cont::rbegin

const_reverse_iterator rbegin() const;
reverse_iterator rbegin();


The member function returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

Member Type Cont::reference

typedef T2 reference;


The type describes an object that can serve as a reference to an element of the controlled sequence. It is described here as a synonym for the unspecified type T2 (typically A::reference).

Member Function Cont::rend

const_reverse_iterator rend() const;
reverse_iterator rend();


The member function returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

Member Type Cont::reverse_iterator

typedef T7 reverse_iterator;


The type describes an object that can serve as a reverse iterator for the controlled sequence. It is described here as a synonym for the unspecified type T7 (typically reverse_iterator or reverse_bidirectional_iterator).

Member Function Cont::size

size_type size() const;


The member function returns the length of the controlled sequence.

Member Type Cont::size_type

typedef T0 size_type;


The unsigned integer type describes an object that can represent the length of any controlled sequence. It is described here as a synonym for the unspecified type T0 (typically A::size_type).

Member Function Cont::swap

void swap(Cont& str);


The member function swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

Member Type Cont::value_type

typedef T4 value_type;


The type is a synonym for the template parameter T. It is described here as a synonym for the unspecified type T4 (typically A::value_type).

Template Functions

Each STL container also defines, outside the template class, several template functions that let you test and manipulate container objects.

Function operator==

template<class T, class A>
    bool operator==(
        const Cont <T, A>& lhs,
        const Cont <T, A>& rhs);


The template function overloads operator== to compare two objects of template class Cont. The function returns lhs.size() == rhs.size() && equal(lhs. begin(), lhs. end(), rhs.begin()).

Function operator<

template<class T, class A>
    bool operator<(
        const Cont <T, A>& lhs,
        const Cont <T, A>& rhs);


The template function overloads
operator< to compare two objects of template class Cont. The function returns
lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()).

Function swap

template<class T, class A>
    void swap(
        const Cont <T, A>& lhs,
        const Cont <T, A>& rhs);


The template function executes lhs.swap(rhs).

Using Containers

Let's review the rather dry description above from the standpoint of a practical user. To make use of any of the STL containers or container adapters, include the header that defines its template class:

In Subsequent installments, I describe each of these headers in detail.

Each of the STL containers has a number of unique properties, as you might expect. How you construct a container object, how you insert elements into it, and how you subsequently locate those elements varies considerable among containers. But the container template classes also have a number of common properties, which I describe here. For example, each defines a number of member types that supply useful information about the container:

Several member functions return iterators. The member function erase( iterator), for example, returns an iterator that designates the (remaining) element just beyond the one removed by the function. If you want to access the entire controlled sequence directly, however, you typically call:

Given an iterator, or a range of iterators, you can erase one or more elements of the controlled sequence by calling erase. Or you can remove all elements by calling clear.

You can determine the number of elements in the controlled sequence by calling the member function size. If you merely want to determine whether any elements are present, call empty. The member function max_size provides a hint as to how long a sequence the container can control. Note, however, that available memory might impose much more severe limits than the size reported by this function.

It is not likely that you will have occasion to work directly with the allocator object stored in a container object. But if you do, you can obtain a copy of the allocator object by calling the member function get_allocator. Alternatively, you can derive a class from the specialized container template class. Member functions of the derived class can then directly access the member object allocator.

Finally, each container template class supplies an override for the (algorithm) template function swap. If the two container objects to be swapped store allocator objects that compare equal, the overriding function swaps the two controlled sequences just by manipulating the stored control information. That approach can be dramatically faster than the brute-force approach that must otherwise be employed. o

P.J. Plauger is senior editor of C/C++ Users Journal. He is the author of the Standard C++ Library shipped with Microsoft's Visual C++, v4.2. For eight years, he served as convener of the ISO C standards committee, WG14. He remains active on the C++ committee, WG21. His latest books are The Draft Standard C++ Library, Programming on Purpose (three volumes), and Standard C (with Jim Brodie), all published by Prentice-Hall. You can reach him at pjp@plauger.com.