STL Containers

A container is an STL template class that manages a sequence of elements. Such elements can be of any object type that supplies a copy constructor, a destructor, and an assignment operator (all with sensible behavior, of course). The destructor may not throw an exception. This document describes the properties required of all such containers, in terms of a generic template class Container. An actual container template class may have additional template parameters. It will certainly have additional member functions.

The STL template container classes are:

    deque
    forward_list
    list
    map
    multimap
    multiset
    set
    unordered_map
    unordered_multimap
    unordered_multiset
    unordered_set
    vector

namespace std {
template<class Ty>
    class Container;

        // TEMPLATE FUNCTIONS
template<class Ty>
    bool operator==(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    bool operator!=(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    bool operator<(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    bool operator>(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    bool operator<=(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    bool operator>=(
        const Container<Ty>& left,
        const Container<Ty>& right);
template<class Ty>
    void swap(
        Container<Ty>& left,
        Container<Ty>& right);
}  // namespace std

Container

· allocator_type · begin · cbegin · cend · const_pointer · const_void_pointer · clear · const_iterator · const_reference · const_reverse_iterator · crbegin · crend · difference_type · empty · end · get_allocator · erase · iterator · max_size · pointer · rbegin · reference · rend · reverse_iterator · size · size_type · swap · value_type · void_pointer

template<class Ty,
    class Alloc>
    class Container {
public:
    typedef Ty value_type;
    typedef Alloc allocator_type;

    typedef T1 pointer;
    typedef T2 const_pointer;
    typedef T3 void_pointer;
    typedef T4 const_void_pointer;

    typedef Ty& reference;
    typedef const Ty& const_reference;

    typedef T5 size_type;
    typedef T6 difference_type;

    typedef T7 iterator;
    typedef T8 const_iterator;
    typedef T9 reverse_iterator;
    typedef T10 const_reverse_iterator;

    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator rend();
    const_reverse_iterator rend() const;

    const_iterator cbegin() const; [added with C++11]
    const_iterator cend() const; [added with C++11]
    const_reverse_iterator crbegin() const; [added with C++11]
    const_reverse_iterator crend() const; [added with C++11]

    allocator_type get_allocator() const;
    size_type size() const;
    size_type max_size() const;
    bool empty() const;
    iterator erase(iterator where);
    iterator erase(iterator first, iterator last);
    void clear() noexcept;
    void swap(Container& right);
    };

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

A container constructor or member function may find occasion to call the copy constructor Ty(const Ty&), the move constructor Ty(Ty&&), the copy assign function Ty::operator=(const Ty&) or the move assign function Ty::operator=(Ty&&). If such a call throws an exception, the container object is obliged to maintain its integrity, and to rethrow any exception it catches. You can safely swap, assign to, erase, or destroy a container object after it throws one of these exceptions. In general, however, you cannot otherwise predict the state of the sequence controlled by the container object.

A few additional caveats:

• If the expression ~Ty() throws an exception, the resulting state of the container object is undefined.
• If the stored allocator object al throws an exception, other than as a result of a call to al.allocate, the resulting state of the container object is undefined.
• If the container stores a function object comp, to determine how to order the controlled sequence, and comp throws an exception of any kind, the resulting state of the container object is undefined.

The container classes defined by STL satisfy several additional requirements, as described in the following paragraphs.

Container template class list provides deterministic, and useful, behavior even in the presence of the exceptions described above. For example, if an exception is thrown during the insertion of one or more elements, the container is left unaltered and the exception is rethrown.

For all the container classes defined by STL, if an exception is thrown during calls to the following member functions:

insert // single element inserted at end
push_back
push_front

the container is left unaltered and the exception is rethrown.

For all the container classes defined by STL, no exception is thrown during calls to the following member functions:

pop_back
pop_front

The member function erase throws an exception only if a copy operation (assignment or copy construction) throws an exception.

Moreover, no exception is thrown while copying an iterator returned by a member function.

The member function swap makes additional promises for all container classes defined by STL:

• The member function throws an exception only if the container stores an allocator object al, and al throws an exception when copied, or if the container stores a function object comp, to determine how to order the controlled sequence, and comp throws an exception when copied.
• Unless otherwise specified, references, pointers, and iterators that designate elements of the controlled sequences being swapped remain valid.

An object of a container class defined by STL allocates and frees storage for the sequence it controls through a stored object of type Alloc, which is typically a template parameter. Such an allocator object must have the same external interface as an object of class allocator<Ty>. In particular, Alloc must be the same type as Alloc::rebind<value_type>::other

For all container classes defined by STL, the member function:

Alloc get_allocator() const;

returns a copy of the stored allocator object.

Beginning with C++11, an allocator can contain additional member types and functions. Moreover, an allocator can omit many of the member types and functions supplied by template class allocator. Containers are expected to mediate nearly all accesses to allocators through the class allocator_traits<Alloc>.

Note that the stored allocator object is not necessarily copied when the container object is assigned. All constructors initialize the value stored in allocator, to Alloc() if the constructor contains no allocator parameter.

A container class defined by STL can assume that:

• All objects of class Alloc need not compare equal. (You can maintain multiple pools of storage.)
• Type Alloc::const_pointer need not be the same as const Ty *, and type Alloc::pointer need not be the same as Ty *. (A pointer can be a class.)
• Alloc::allocate and Alloc::deallocate traffic in Alloc::pointer objects.
• You can convert an Alloc::pointer object to a Ty * object (and you must do so to construct or destroy an object)
• You cannot necessarily convert a Ty * object to an Alloc::pointer object.

Container::allocator_type

typedef Alloc allocator_type;

The type is a synonym for Alloc.

Container::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).

Container::cbegin

const_iterator cbegin() const; [added with C++11]

The member functions return a random-access iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

Container::cend

const_reference cend() const; [added with C++11]

The member functions return a random-access iterator that points just beyond the end of the sequence.

Container::clear

void clear() noexcept;

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

Container::const_iterator

typedef T8 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 T8.

Container::const_pointer

typedef T2 const_pointer;

The type describes an object that can serve as a pointer to constant allocated storage. It is described here as a synonym for the unspecified type T2.

Container::const_reference

typedef const Ty& const_reference;

The type describes a constant reference to an element of the controlled sequence.

Container::const_reverse_iterator

typedef T10 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 T10 (typically reverse_iterator <const_iterator>).

Container::const_void_pointer

typedef T4 const_void_pointer;

The type describes an object that can serve as a generic pointer to constant allocated storage. It is described here as a synonym for the unspecified type T4.

Container::crbegin

const_reverse_iterator crbegin() const; [added with C++11]

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

Container::crend

const_reverse_iterator crend() const; [added with C++11]

The member functions return 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.

Container::difference_type

typedef T6 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 T6 (typically Alloc::difference_type).

Container::empty

bool empty() const;

The member function returns true for an empty controlled sequence.

Container::end

const_iterator end() const;
iterator end();

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

Container::erase

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

The first member function removes the element of the controlled sequence pointed to by where. 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.

The member functions throw an exception only if a copy operation throws an exception.

Container::get_allocator

allocator_type get_allocator() const;

The member function returns a copy of the stored allocator object.

Container::iterator

typedef T7 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 T7. An object of type iterator can be cast to an object of type const_iterator.

Container::max_size

size_type max_size() const;

The member function returns the length of the longest sequence that the object can control, in constant time regardless of the length of the controlled sequence.

Container::pointer

typedef T1 pointer;

The type describes an object that can serve as a pointer to allocated storage. It is described here as a synonym for the unspecified type T1.

Container::rbegin

const_reverse_iterator rbegin() const;
reverse_iterator rbegin();

The member function returns a reverse iterator that designates the last element of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

Container::reference

typedef Ty& reference;

The type describes a reference to an element of the controlled sequence.

Container::rend

const_reverse_iterator rend() const;
reverse_iterator rend();

The member function returns a reverse iterator that designates the (fictitious) element before the first element of the controlled sequence. Hence, it points just beyond the end of the reverse sequence.

Container::reverse_iterator

typedef T10 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 T10 (typically reverse_iterator <iterator>).

Container::size

size_type size() const;

The member function returns the length of the controlled sequence, in constant time regardless of the length of the controlled sequence.

Container::size_type

typedef T5 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 T5 (typically Alloc::size_type).

Container::swap

void swap(Container& right);

The member function swaps the controlled sequences between *this and right. If get_allocator() == right.get_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.

Container::value_type

typedef T4 value_type;

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

Container::void_pointer

typedef T3 void_pointer;

The type describes an object that can serve as a generic pointer to allocated storage. It is described here as a synonym for the unspecified type T3.

operator!=

template<class Ty>
    bool operator!=(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function returns !(left == right).

operator==

template<class Ty>
    bool operator==(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function overloads operator== to compare two objects of template class Container. The function returns left.size() == right.size() && equal(left. begin(), left. end(), right.begin()).

operator<

template<class Ty>
    bool operator<(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function overloads operator< to compare two objects of template class Container. The function returns lexicographical_compare(left. begin(), left. end(), right.begin(), right.end()).

operator<=

template<class Ty>
    bool operator<=(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function returns !(right < left).

operator>

template<class Ty>
    bool operator>(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function returns right < left.

operator>=

template<class Ty>
    bool operator>=(
        const Container <Ty>& left,
        const Container <Ty>& right);

The template function returns !(left < right).

swap

template<class Ty>
    void swap(
        Container <Ty>& left,
        Container <Ty>& right);

The template function executes left.swap(right).

See also the Table of Contents and the Index.

Copyright © 1992-2013 by P.J. Plauger. Portions derived from work copyright © 1994 by Hewlett-Packard Company. All rights reserved.