Table of Contents

C++ Containers library

https://en.cppreference.com/w/cpp/container

The Containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like queues, lists and stacks. There are three classes of containers – sequence containers, associative containers, and unordered associative containers – each of which is designed to support a different set of operations.

The container manages the storage space that is allocated for its elements and provides member functions to access them, either directly or through iterators (objects with properties similar to pointers).

Most containers have at least several member functions in common, and share functionalities. Which container is the best for the particular application depends not only on the offered functionality, but also on its efficiency for different workloads.

Sequence containers

Sequence containers implement data structures which can be accessed sequentially.

Associative containers

Associative containers implement sorted data structures that can be quickly searched (

complexity).

Unordered associative containers

Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (

amortized,

worst-case complexity).

Container adaptors

Container adaptors provide a different interface for sequential containers.

{{tt|span}}

A

is a non-owning view over a contiguous sequence of objects, the storage of which is owned by some other object.

Iterator invalidation

Read-only methods never invalidate iterators or references. Methods which modify the contents of a container may invalidate iterators and/or references, as summarized in this table.

Category Container After insertion, are… After erasure, are… Conditionally
iterators valid? references valid? iterators valid? references valid?
<!– –> Sequence containers

colspan=“2”

colspan=“2”

colspan=“2”

colspan=“2”

Insertion changed capacity
colspan=“2”

colspan=“2”

Before modified element(s)
colspan=“2”

colspan=“2”

At or after modified element(s)

rowspan=“2”

colspan=“2”

Modified first or last element

colspan=“2”

Modified middle only

colspan=“2”

colspan=“2”

colspan=“2”

colspan=“2”

<!– –> Associative containers

<br/><!– –>

<br/><!– –>

<br/><!– –>

colspan=“2”

colspan=“2”

<!– –> Unordered associative containers

<br/><!– –>

<br/><!– –>

<br/><!– –>

rowspan=“2”

colspan=“2”

<!–N/A due to incompatibility between the condition “Insertion caused rehash” and this column's topic (“After erasure…”).

–>

 Insertion caused rehash

colspan=“2”

No rehash

Here, insertion refers to any method which adds one or more elements to the container and erasure refers to any method which removes one or more elements from the container.

The past-the-end iterator deserves particular mention. In general this iterator is invalidated as though it were a normal iterator to a non-erased element. So

is never invalidated,

is invalidated only on rehash,

is always invalidated (since it is always after the modified elements), and so on.

There is one exception: an erasure which deletes the last element of a

does invalidate the past-the-end iterator, even though it is not an erased element of the container (or an element at all). Combined with the general rules for

iterators, the net result is that the only modifying operation which does not invalidate

is an erasure which deletes the first element, but not the last.

member functions can be called concurrently by different threads on the same container. In addition, the member functions

,

,

,

,

,

,

,

,

,

,

,

, and, except in associative containers,

, behave as

for the purposes of thread safety (that is, they can also be called concurrently by different threads on the same container). More generally, the C++ standard library functions do not modify objects unless those objects are accessible, directly or indirectly, via the function's non-const arguments, including the this pointer.

  1. Different elements in the same container can be modified concurrently by different threads, except for the elements of

    (for example, a vector of

    objects can be receiving values from multiple threads).

  2. Iterator operations (e.g. incrementing an iterator) read, but do not modify the underlying container, and may be executed concurrently with operations on other iterators on the same container, with the const member functions, or reads from the elements. Container operations that invalidate any iterators modify the container and cannot be executed concurrently with any operations on existing iterators even if those iterators are not invalidated.
  3. Elements of the same container can be modified concurrently with those member functions that are not specified to access these elements. More generally, the C++ standard library functions do not read objects indirectly accessible through their arguments (including other elements of a container) except when required by its specification.
  4. In any case, container operations (as well as algorithms, or any other C++ standard library functions) may be parallelized internally as long as this does not change the user-visible results (e.g.

    may be parallelized, but not

    which is specified to visit each element of a sequence in order)

}}

Member function table

- functions present in C++03
- functions present since C++11
- functions present since C++17
- functions present since C++20

Sequence containers Associative containers Unordered associative containers Container adaptors
Header

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}
Container

<!– —>

<!– –>

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}

}}
<!– –>

Iterators

<!– –>

<!– –>

<!– –>

Element <br> access

<!– –>

<!– –>

<!– –>

<!– –>

Capacity

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

Modifiers

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

List operations

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

Lookup

<!– –>

<!– –>

<!– –>

<!– –>

<!– –>

Observers

<!– –>

<!– –>

<!– –>

Allocator

Container

Sequence containers Associative containers Unordered associative containers Container adaptors

See also