Editing Standard Template Library (section)

=== Containers ===
The STL contains sequence [[Container (data structure)|containers]] and associative containers. The containers are objects that store data. The standard [[List (computing)|sequence containers]] include {{Cpp|vector}}, {{Cpp|deque}}, and {{Cpp|list}}. The standard [[associative array|associative containers]] are {{Cpp|set}}, {{Cpp|multiset}}, {{Cpp|map}}, {{Cpp|multimap}}, {{Cpp|hash_set}}, {{Cpp|hash_map}}, {{Cpp|hash_multiset}} and {{Cpp|hash_multimap}}. There are also ''container adaptors'' {{Cpp|queue}}, {{Cpp|priority_queue}}, and {{Cpp|stack}}, that are containers with specific interface, using other containers as implementation.

{| class="wikitable"
|-
! Container
! Description
|-
! colspan="2" | Simple containers
|-
! pair
| The pair container is a simple associative container consisting of a 2-[[tuple]] of data elements or objects, called 'first' and 'second', in that fixed order. The STL 'pair' can be assigned, copied and compared. The array of objects allocated in a map or hash_map (described below) are of type 'pair' by default, where all the 'first' elements act as the unique keys, each associated with their 'second' value objects.
|-
! colspan=2| [[List (computing)|Sequences]] (arrays/[[linked list]]s): ordered collections
|-
! [[vector (STL)|vector]]
| a [[dynamic array]], like [[C (programming language)|C]] array (i.e., capable of [[random access]]) with the ability to resize itself automatically when inserting or erasing an object. Inserting an element to the back of the vector at the end takes [[amortized constant time]]. Removing the last element takes only constant time, because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.
A optimization for type [[Boolean data type|bool]] exists, which can optimize for space by grouping bool values together.<ref>{{cite web |title=[vector.bool] |url=https://eel.is/c++draft/vector.bool |website=Eelis |access-date=22 December 2024}}</ref>
|-
! list
| a [[doubly linked list]]; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time).
|-
! slist<br />
| a [[Linked list|singly linked list]]; elements are not stored in contiguous memory. Opposite performance from a vector. Slow lookup and access (linear time), but once a position has been found, quick insertion and deletion (constant time). It has slightly more efficient insertion and deletion, and uses less memory than a doubly linked list, but can only be iterated forwards. It is implemented in the C++ standard library as {{Cpp|forward_list}}.
|-
! [[deque]] (''double-ended [[Queue (data structure)|queue]]'')
|a vector with insertion/erase at the beginning or end in [[amortized constant time]], however lacking some guarantees on iterator validity after altering the deque.
|-
! colspan=2| Container adaptors
|-
! [[Queue (data structure)|queue]]
| Provides [[FIFO (computing and electronics)|FIFO]] [[Queue (data structure)|queue]] interface in terms of {{Cpp|push}}/{{Cpp|pop}}/{{Cpp|front}}/{{Cpp|back}} operations.
Any sequence supporting operations {{Cpp|front()}}, {{Cpp|back()}}, {{Cpp|push_back()}}, and {{Cpp|pop_front()}} can be used to instantiate queue (e.g. {{Cpp|list}} and {{Cpp|deque}}).
|-
! [[priority queue]]
| Provides [[priority queue]] interface in terms of {{Cpp|push/pop/top}} operations (the element with the highest priority is on top).
Any [[random-access]] sequence supporting operations {{Cpp|front()}}, {{Cpp|push_back()}}, and {{Cpp|pop_back()}} can be used to instantiate priority_queue (e.g. {{Cpp|vector}} and {{Cpp|deque}}). It is implemented using a [[Heap (data structure)|heap]].

Elements should additionally support comparison (to determine which element has a higher priority and should be popped first).
|-
! [[stack (data structure)|stack]]
| Provides [[LIFO (computing)|LIFO]] [[stack (data structure)|stack]] interface in terms of {{Cpp|push/pop/top}} operations (the last-inserted element is on top).
Any sequence supporting operations {{Cpp|back()}}, {{Cpp|push_back()}}, and {{Cpp|pop_back()}} can be used to instantiate stack (e.g. {{Cpp|vector}}, {{Cpp|list}}, and {{Cpp|deque}}).
|-
! colspan=2| [[Associative containers (C++)|Associative containers]]: unordered collections
|-
! [[set (computer science)|set]]
| a mathematical [[set (computer science)|set]]; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations [[union (set theory)|union]], [[intersection (set theory)|intersection]], [[set difference|difference]], [[symmetric difference]] and test of inclusion. Type of data must implement comparison operator {{Cpp|<}} or custom comparator function must be specified; such comparison operator or comparator function must guarantee [[strict weak ordering]], otherwise behavior is undefined. Typically implemented using a [[self-balancing binary search tree]].
|-
! multiset
| same as a set, but allows duplicate elements (mathematical [[multiset]]).
|-
! [[Map (C++)|map]]
| an [[associative array]]; allows mapping from one data item (a key) to another (a value). Type of key must implement comparison operator {{Cpp|<}} or custom comparator function must be specified; such comparison operator or comparator function must guarantee [[strict weak ordering]], otherwise behavior is undefined. Typically implemented using a self-balancing binary search tree.
|-
! multimap
| same as a map, but allows duplicate keys.
|-
! hash_set<br />hash_multiset<br />[[Hash map (C++)|hash_map]]<br />hash_multimap
| similar to a set, multiset, map, or multimap, respectively, but implemented using a [[hash table]]; keys are not ordered, but a [[hash function]] must exist for the key type. These types were left out of the C++ standard; similar containers were standardized in [[C++11]], but with different names ({{Cpp|unordered_set}} and {{Cpp|unordered_map}}).
|-
! colspan=2| Other types of containers
|-
! bitset
| stores series of bits similar to a fixed-sized vector of bools. Implements bitwise operations and lacks iterators. Not a sequence. Provides random access.
|-
! valarray
| Another array data type, intended for numerical use (especially to represent [[vector (mathematics)|vectors]] and [[matrix (mathematics)|matrices]]); the C++ standard allows specific optimizations for this intended purpose. According to Josuttis, {{mono|valarray}} was badly designed, by people "who left the [C++ standard] committee a long time before the standard was finished", and [[expression templates|expression template]] libraries are to be preferred.<ref>{{cite book |first=Nicolai M. |last=Josuttis |publisher=Addison-Wesley Professional  |year=1999 |title=The C++ Standard Library: A Tutorial and Handbook |url=https://archive.org/details/cstandardlibrary00josu |url-access=registration |page=[https://archive.org/details/cstandardlibrary00josu/page/547 547]|isbn=9780201379266 }}</ref> A proposed rewrite of the {{mono|valarray}} part of the standard in this vein was rejected, instead becoming a permission to implement it using expression template.<ref>{{cite book |last1=Vandevoorde |first1=David |last2=Josuttis |first2=Nicolai M. |title=C++ Templates: The Complete Guide |publisher=[[Addison Wesley]] |year=2002 |isbn=0-201-73484-2}}
</ref>
|}