Difference between revisions of "cpp/container/queue"

Latest revision as of 23:51, 2 August 2024

Defined in header `<queue>`
template< class T, class Container = std::deque<T> > class queue;

The std::queue class template is a container adaptor that gives the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.

The class template acts as a wrapper to the underlying container - only a specific set of functions is provided. The queue pushes the elements on the back of the underlying container and pops them from the front.

(constructor)	constructs the `queue` (public member function) [edit]
(destructor)	destructs the `queue` (public member function) [edit]
operator=	assigns values to the container adaptor (public member function) [edit]
Element access
front	access the first element (public member function) [edit]
back	access the last element (public member function) [edit]
Capacity
empty	checks whether the container adaptor is empty (public member function) [edit]
size	returns the number of elements (public member function) [edit]
Modifiers
push	inserts element at the end (public member function) [edit]
push_range (C++23)	inserts a range of elements at the end (public member function) [edit]
emplace (C++11)	constructs element in-place at the end (public member function) [edit]
pop	removes the first element (public member function) [edit]
swap (C++11)	swaps the contents (public member function) [edit]

[edit] Non-member functions

operator==operator!=operator<operator<=operator>operator>=operator<=> (C++20)	lexicographically compares the values of two `queue`s (function template) [edit]
std::swap(std::queue) (C++11)	specializes the std::swap algorithm (function template) [edit]

[edit] Helper classes

std::uses_allocator<std::queue> (C++11)	specializes the std::uses_allocator type trait (class template specialization) [edit]
std::formatter<std::queue> (C++23)	formatting support for `std::queue` (class template specialization) [edit]

Deduction guides

(since C++17)

[edit] Notes

Feature-test macro	Value	Std	Feature
`__cpp_lib_containers_ranges`	202202L	(C++23)	Ranges construction and insertion for containers

[edit] Example

Run this code

#include <cassert>
#include <iostream>
#include <queue>
 
int main()
{
    std::queue<int> q;
 
    q.push(0); // back pushes 0
    q.push(1); // q = 0 1
    q.push(2); // q = 0 1 2
    q.push(3); // q = 0 1 2 3
 
    assert(q.front() == 0);
    assert(q.back() == 3);
    assert(q.size() == 4);
 
    q.pop(); // removes the front element, 0
    assert(q.size() == 3);
 
    // Print and remove all elements. Note that std::queue does not
    // support begin()/end(), so a range-for-loop cannot be used.
    std::cout << "q: ";
    for (; !q.empty(); q.pop())
        std::cout << q.front() << ' ';
    std::cout << '\n';
    assert(q.size() == 0);
}

Output:

q: 1 2 3

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 307	C++98	`std::queue` did not support containers using proxy reference types^[1] in place of (`const`) `value_type&`	supported
LWG 2566	C++98	Missing the requirement for `Container::value_type`	ill-formed if `T` is not the same type as `Container::value_type`

↑ Such as containers similar to std::vector<bool> with additional support of pop_front(). The resolution of this DR
added support of std::vector<bool> for std::stack and std::priority_queue. The changes involving std::queue
are for maintaining consistency.

[edit] See also

priority_queue	adapts a container to provide priority queue (class template) [edit]
deque	double-ended queue (class template) [edit]
list	doubly-linked list (class template) [edit]

[1] Such as containers similar to std::vector<bool> with additional support of pop_front(). The resolution of this DR
added support of std::vector<bool> for std::stack and std::priority_queue. The changes involving std::queue
are for maintaining consistency.

[1]

@@ Line 1: / Line 1: @@
 {{cpp/title|queue}}
 {{cpp/container/queue/navbar}}
-{{ddcl | header=queue |
+{{ddcl|header=queue|1=
 template<
      class T,
-     class Container {{=}} std::deque<T>
+     class Container = std::deque<T>
 > class queue;
 }}
-The {{tt|std::queue}} class is a container adapter that gives the programmer the functionality of a queue - specifically, a FIFO (first-in, first-out) data structure.
+The {{tt|std::queue}} class template is a [[cpp/container#Container adaptors|container adaptor]] that gives the functionality of a {{enwiki|Queue (abstract data type)|queue}} - specifically, a FIFO (first-in, first-out) data structure.
 The class template acts as a wrapper to the underlying container - only a specific set of functions is provided. The queue pushes the elements on the back of the underlying container and pops them from the front.
@@ Line 14: / Line 14: @@
 ===Template parameters===
 {{par begin}}
-{{par | T | The type of the stored elements. {{rev inl|since=c++17|The behavior is undefined if {{tt|T}} is not the same type as {{tt|Container::value_type}}.}} }}
+{{par|T|The type of the stored elements. The program is ill-formed if {{tt|T}} is not the same type as {{tt|Container::value_type}}.}}
-{{par | Container | The type of the underlying container to use to store the elements. The container must satisfy the requirements of {{named req|SequenceContainer}}. Additionally, it must provide the following functions with the usual semantics:
+{{par|Container|The type of the underlying container to use to store the elements. The container must satisfy the requirements of {{named req|SequenceContainer}}. Additionally, it must provide the following functions with the [[cpp/named req/SequenceContainer#Optional operations|usual semantics]]:
+* {{tt|back()}}, e.g., {{lc|std::deque::back()}},
+* {{tt|front()}}, e.g. {{lc|std::list::front()}},
+* {{tt|push_back()}}, e.g., {{lc|std::deque::push_back()}},
+* {{tt|pop_front()}}, e.g., {{lc|std::list::pop_front()}}.
-* {{tt|back()}}
+The standard containers {{lc|std::deque}} and {{lc|std::list}} satisfy these requirements.
-* {{tt|front()}}
-* {{tt|push_back()}}
-* {{tt|pop_front()}}
-The standard containers {{lc|std::deque}} and {{lc|std::list}} satisfy these requirements.
 }}{{par end}}
 ===Member types===
 {{dsc begin}}
-{{dsc hitem | Member type | Definition}}
+{{dsc hitem|Member type|Definition}}
-{{dsc inc | cpp/container/dsc container_type | queue}}
+{{dsc inc|cpp/container/dsc container_type|queue}}
-{{dsc inc | cpp/container/dsc value_type | queue}}
+{{dsc inc|cpp/container/dsc value_type|queue}}
-{{dsc inc | cpp/container/dsc size_type | queue}}
+{{dsc inc|cpp/container/dsc size_type|queue}}
-{{dsc inc | cpp/container/dsc reference | queue}}
+{{dsc inc|cpp/container/dsc reference|queue}}
-{{dsc inc | cpp/container/dsc const_reference | queue}}
+{{dsc inc|cpp/container/dsc const_reference|queue}}
+{{dsc end}}
+===Member objects===
+{{dsc begin}}
+{{dsc hitem|Member name|Definition}}
+{{dsc inc|cpp/container/dsc c|queue}}
 {{dsc end}}
 ===Member functions===
 {{dsc begin}}
-{{dsc inc | cpp/container/dsc constructor | queue}}
+{{dsc inc|cpp/container/dsc constructor|queue}}
-{{dsc inc | cpp/container/dsc destructor | queue}}
+{{dsc inc|cpp/container/dsc destructor|queue}}
-{{dsc inc | cpp/container/dsc operator{{=}} | queue}}
+{{dsc inc|cpp/container/dsc operator{{=}}|queue}}
-{{dsc h2 | Element access}}
+{{dsc h2|Element access}}
-{{dsc inc | cpp/container/dsc front | queue}}
+{{dsc inc|cpp/container/dsc front|queue}}
-{{dsc inc | cpp/container/dsc back | queue}}
+{{dsc inc|cpp/container/dsc back|queue}}
-{{dsc h2 | Capacity}}
+{{dsc h2|Capacity}}
-{{dsc inc | cpp/container/dsc empty | queue}}
+{{dsc inc|cpp/container/dsc empty|queue}}
-{{dsc inc | cpp/container/dsc size | queue}}
+{{dsc inc|cpp/container/dsc size|queue}}
-{{dsc h2 | Modifiers}}
+{{dsc h2|Modifiers}}
-{{dsc inc | cpp/container/dsc push | queue}}
+{{dsc inc|cpp/container/dsc push|queue}}
-{{dsc inc | cpp/container/dsc emplace | queue}}
+{{dsc inc|cpp/container/dsc push_range|queue}}
-{{dsc inc | cpp/container/dsc pop | queue}}
+{{dsc inc|cpp/container/dsc emplace|queue}}
-{{dsc inc | cpp/container/dsc swap | queue}}
+{{dsc inc|cpp/container/dsc pop|queue}}
+{{dsc inc|cpp/container/dsc swap|queue}}
-{{dsc h1 | Member objects}}
-{{dsc inc | cpp/container/dsc c | queue}}
 {{dsc end}}
 ===Non-member functions===
 {{dsc begin}}
-{{dsc inc | cpp/container/dsc operator_cmp | queue}}
+{{dsc inc|cpp/container/dsc operator_cmp|queue}}
-{{dsc inc | cpp/container/dsc swap2 | queue}}
+{{dsc inc|cpp/container/dsc swap2|queue}}
 {{dsc end}}
 ===Helper classes===
 {{dsc begin}}
-{{dsc inc | cpp/container/dsc uses_allocator | queue}}
+{{dsc inc|cpp/container/dsc uses_allocator|queue}}
+{{dsc inc|cpp/container/dsc adaptor_formatter|queue}}
 {{dsc end}}
-===[[cpp/container/queue/deduction_guides|Deduction guides]]{{mark since c++17}}===
+{{rrev|since=c++17|
+==={{rl|deduction guides|Deduction guides}}===
+}}
+===Notes===
+{{ftm begin|std=1|comment=1}}
+{{ftm|__cpp_lib_containers_ranges|value=202202L|std=C++23|Ranges construction and insertion for containers}}
+{{ftm end}}
+===Example===
+{{example
+|code=
+#include <cassert>
+#include <iostream>
+#include <queue>
+int main()
+{
+    std::queue<int> q;
+    q.push(0); // back pushes 0
+    q.push(1); // q = 0 1
+    q.push(2); // q = 0 1 2
+    q.push(3); // q = 0 1 2 3
+    assert(q.front() == 0);
+    assert(q.back() == 3);
+    assert(q.size() == 4);
+    q.pop(); // removes the front element, 0
+    assert(q.size() == 3);
+    // Print and remove all elements. Note that std::queue does not
+    // support begin()/end(), so a range-for-loop cannot be used.
+    std::cout << "q: ";
+    for (; !q.empty(); q.pop())
+        std::cout << q.front() << ' ';
+    std::cout << '\n';
+    assert(q.size() == 0);
+}
+|output=
+q: 1 2 3
+}}
+===Defect reports===
+{{dr list begin}}
+{{dr list item|wg=lwg|dr=307|std=C++98|before={{tt|std::queue}} did not support containers using proxy<br>reference types<ref>Such as containers similar to {{ltt|cpp/container/vector bool|std::vector<bool>}} with additional support of {{tt|pop_front()}}. The resolution of this DR<br>added support of {{ltt|cpp/container/vector bool|std::vector<bool>}} for {{lc|std::stack}} and {{lc|std::priority_queue}}. The changes involving {{tt|std::queue}}<br>are for maintaining consistency.</ref> in place of ({{tt|const}}) {{tt|value_type&}}|after=supported}}
+{{dr list item|wg=lwg|dr=2566|std=C++98|before=Missing the requirement for {{tt|Container::value_type}} |after=ill-formed if {{tt|T}} is not the same type as {{tt|Container::value_type}}}}
+{{dr list end}}
+<references/>
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/container/dsc deque}}
+{{dsc inc|cpp/container/dsc priority_queue}}
+{{dsc inc|cpp/container/dsc deque}}
+{{dsc inc|cpp/container/dsc list}}
 {{dsc end}}
 {{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}}

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

Sequence
array (C++11)
vector
vector<bool>
inplace_vector (C++26)
deque
forward_list (C++11)
list
Associative
set
multiset
map
multimap
Unordered associative
unordered_set (C++11)
unordered_multiset (C++11)
unordered_map (C++11)
unordered_multimap (C++11)
Adaptors
stack
queue
priority_queue
flat_set (C++23)
flat_multiset (C++23)
flat_map (C++23)
flat_multimap (C++23)
Views
span (C++20)
mdspan (C++23)
Tables
Iterator invalidation
Member function table
Non-member function table

Member functions
queue::queue
queue::~queue
queue::operator=
Element access
queue::front
queue::back
Capacity
queue::empty
queue::size
Modifiers
queue::push
queue::push_range (C++23)
queue::emplace (C++11)
queue::pop
queue::swap (C++11)
Non-member functions
swap(std::queue) (C++11)
operator==operator!=operator<operator>operator<=operator>=operator<=> (C++20)
Helper classes
uses_allocator<std::queue> (C++11)
formatter<std::queue> (C++23)
Deduction guides(C++17)

Member type	Definition
`container_type`	`Container`[edit]
`value_type`	`Container::value_type`[edit]
`size_type`	Container::size_type[edit]
`reference`	`Container::reference`[edit]
`const_reference`	`Container::const_reference`[edit]

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/container/queue"

Latest revision as of 23:51, 2 August 2024

Contents

[edit] Template parameters

[edit] Member types

[edit] Member objects

[edit] Member functions

Element access

Capacity

Modifiers