STL Containers

The Standard Template Library (STL) provides several containers for storing collections of related objects. The containers are all template classes, allowing you to specify what objects are allowed in the containers. This topic provides an overview of the STL containers to help you decide which container is best for your needs.

There are two STL libraries to choose from: native STL and STL/CLR. For more information on STL/CLR, see STL/CLR Library Reference.

Containers in STL can be divided into three categories, sequence containers, associative containers, and container adapters. These categories, and the collections that belong to each category, are summarized here. More detailed information can be found in the reference documentation for the containers.

Sequence Containers

Sequence containers maintain the original ordering of inserted elements. This allows you to specify where to insert the element in the container.

The deque (double-ended queue) container allows for fast insertions and deletions at the beginning and end of the container. You can also randomly access any element quickly.

The list container allows for fast insertions and deletions anywhere in the container, but you cannot randomly access an element in the container.

The vector container behaves like an array, but will automatically grow as required.

For more information on the sequence containers, consult the following table:

Container

Native STL

STL/CLR

deque

deque Class

deque (STL/CLR)

list

list Class

list (STL/CLR)

vector

vector Class

vector (STL/CLR)

Associative Containers

The defining characteristic of associative containers is that elements are inserted in a pre-defined order, such as sorted ascending.

The associative containers can be grouped into two subsets: maps and sets. A map, sometimes referred to as a dictionary, consists of a key/value pair. The key is used to order the sequence, and the value is somehow associated with that key. For example, a map might contain keys representing every unique word in a text and values representing the number of times that word appears in the text. A set is simply an ascending container of unique elements.

Both map and set only allow one instance of a key or element to be inserted into the container. If multiple instances of elements are required, use multimap or multiset.

Both maps and sets support bidirectional iterators. For more information on iterators, see Iterators.

While not officially part of the STL standard, hash_map and hash_set are commonly used to improve searching times. These containers store their elements as a hash table, with each table entry containing a bidirectional linked list of elements. To ensure the fastest search times, make sure that the hashing algorithm for your elements returns evenly distributed hash values.

For more information on the associative containers, consult the following table:

Container

Native STL

STL/CLR

hash_map

hash_map Class

hash_map (STL/CLR)

hash_multimap

hash_multimap Class

hash_multimap (STL/CLR)

hash_multiset

hash_multiset Class

hash_multiset (STL/CLR)

hash_set

hash_set Class

hash_set (STL/CLR)

map

map Class

map (STL/CLR)

multimap

multimap Class

multimap (STL/CLR)

multiset

multiset Class

multiset (STL/CLR)

set

set Class

set (STL/CLR)

Container Adapters

The container adapters are simply variations of the above containers. The container adapters do not support iterators.

The priority_queue container organized such that the element with the highest value is always first in the queue.

The queue container follows FIFO (first in, first out) semantics. The first element inserted (pushed) into the queue is the first to be removed (popped).

The stack container follows LIFO (last in, first out) semantics. The last element to be inserted (pushed) on the stack is the first element to be removed (popped).

Since container adapters do not support iterators, they cannot be used with the STL algorithms. For more information on algorithms, see Algorithms.

For more information on the container adapters, consult the following table:

Container

Native STL

STL/CLR

priority_queue

priority_queue Class

priority_queue (STL/CLR)

queue

queue Class

queue (STL/CLR)

stack

stack Class

stack (STL/CLR)

Requirements for Container Elements

Elements inserted into an STL container can be of any object type that supplies a public copy constructor, a public destructor, and a public assignment operator. The destructor may not throw an exception. Furthermore, associative containers such as set and map must have a public comparison operator defined, which is operator< by default. Some operations on containers might also require a public default constructor and a public equivalence operator.

Accessing Container Elements

The elements of containers are accessed using iterators. For more information, see Iterators.

Note

You can also use for each, in to iterate over STL collections. For more information, see How to: Iterate Over STL Collection with for each.

See Also

Reference

Standard Template Library

<sample container>