Standard containers

From Cppwiki

C++ provides several standard containers: classes which store instances of objects for retrieval. The containers differ in how the objects are stored; the simplest, std::vector, simply stores contiguous objects, like an array, whereas std::map provides storage of key/value pairs with fast lookup (often implemented using a red/black tree).

The standard containers are:

vector 

simple contiguous array. provides dynamic resizing with efficient memory management, and can be treated as a (const) array

list 

linked list. provides relaxed iterator invalidation; elements can be added, removed, and moved between lists without invalidation and in O(1) time, with splice

deque 

similar to vector, but provides efficient insertion of elements at both ends without reallocating the entire storage. This is the container of choice for queues

map, multimap 

stores key/value pairs with efficient lookup based on key. multimap is the same but allows multiple elements for a single key

set, multiset 

stores a set of values with efficient lookup. often used for testing whether something has been "seen" before. multiset allows multiple equal elements.

bitset 

provides a storage-efficient bit-field of unlimited size

queue 

a container adapter implementing a queue

stack 

a container adapter implementing a stack

Contents 1 Container adapters 2 Iterators 2.1 Acquiring iterators 2.2 Using iterators 2.3 The "end" iterators 2.4 Iterators and algorithms

Container adapters

A container adapter (such as queue and stack) is a special type of container. It is not a container itself, but "wraps" another container, providing a restricted subset of functionality and/or additional functions. For example, the queue adapter wraps another container, typically deque (but list can also be used) to provide a FIFO queue interface.

Iterators

All containers provide a common interface to access elements, called iteration. An iterator is a type (often, but not always, a class) which provides a consistent interface to access and manipulate a container's members. For any container C<T>, its iterator type is C<T>::iterator and its const iterator type is C<T>::const_iterator. (A const_iterator is the same as an iterator, but it cannot be used to modify the container or its elements).

Acquiring iterators

Every container provides two basic methods to acquire iterators: begin() and end(). These return iterators to the first element in the container, and an iterator pointing to one past the last element. Note that these methods do not return the actual object, only an iterator representing it.

Most containers also provide speciailised methods to find objects. For example, map provide the find() member to lookup a value by its key; this returns an iterator.

Using iterators

An iterator provides a similar interface to a pointer to an array. (In fact, std::vector's iterator often is a pointer). The simplest use of an iterator is accessing the object it refers to; this is done by dereferencing the iterator:

 vector<int> v;
 v.push_back(42);
 vector<int>::iterator i = v.begin(); // the iterator i now refers to the first element in the vector 
 cout << *i; // prints 42

To access the elements preceeding and following the iterator, use -- and ++:

 vector<int> v;
 v.push_back(42);
 v.push_back(43);
 vector<int>::iterator i = v.begin(); // the iterator i now refers to the first element in the vector 
 ++i; // now i refers to the second element
 cout << *i; // prints 43

The "end" iterators

All containers also have a special iterator, returned by the end() member. This iterator points one past the last element in a container; which is to say, if an iterator pointing to the last element in the container is incremented, it becomes equal to the end iterator. Incrementing the iterator again, or trying to dereference the end iterator, causes undefined behaviour.

The end iterator is usually used when iterator through an entire container:

 vector<int> v;
 /* populate v with items... */
 vector<int>::iterator begin = v.begin(), end = v.end();
 for (; it != end; ++it)
   cout << *it << '\n'; // prints all elements in the vector

The end iterator is also returned by find() and related functions to indicate that no element was found.

Iterators and algorithms

The iterator interface is not restricted to containers; the concept is used throughout standard C++. See Iterators and Algorithms for a more general overview of iterators.