Jeremy

queue

std::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.

All member functions of std::queue are constexpr: it is possible to create and use std::queue objects in the evaluation of a constant expression. However, std::queue objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression. // C++26

  • Template parameters

    • T: The type of the stored elements. The program is ill-formed if T is not the same type as Container::value_type.
    • Container: The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics:
      • back(), e.g. std::deque::back(),
      • front(), e.g. std::list::front(),
      • push_back(), e.g. std::deque::push_back(),
      • pop_front(), e.g. std::list::pop_front(). The standard containers std::deque and std::list satisfy these requirements.

  • Member types

Member type Definition
container_type Container
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference
  • Member objects
Member name Definition
container C the underlying container
  • Member functions
Function Definition
(constructor) constructs the queue
(destructor) destructs the queue
operator= assigns values to the container adaptor
front access the first element
back access the last element
empty checks whether the container adaptor is empty
size returns the number of elements
push inserts element at the end
push_range (C++23) nserts a range of elements at the end
emplate (C++11) constructs element in-place at the end
pop removes the first element
swap (C++11) swaps the contents
  • Non-member functions
Non-member function Definition
operator== lexicographically compares the values of two queues
operator!= lexicographically compares the values of two queues
operator< lexicographically compares the values of two queues
operator<= lexicographically compares the values of two queues
operator> lexicographically compares the values of two queues
operator>= lexicographically compares the values of two queues
operator<=> (C++20) lexicographically compares the values of two queues
std::swap(C++11) specializes the std::swap algorithm
  • Example
#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
 */

std::priority_queue

template<
  class T,
  class Container = std::vector<T>
  class Compare = std::less<typename Container::value_type>
> class priority_queue

The priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

  • Parameters

    • T: The type of the stored elements. The program is ill-formed if T is not the same type as Container::value_type.
    • Container: The type of the underlying container to use to store the elements. Additionally, it must provide the following functions with the usual semantics:
      • front()
      • push_back()
      • pop_back()
    • Compare: A Compare type providing a strict weak ordering. Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that “come before” are actually output last. That is, the front of the queue contains the “last” element according to the weak ordering imposed by Compare.

  • Member Types

Member type Definition
container_type Container
value_compare Compare
value_type Container::value_type
size_type Container::size_type
reference Container::reference
const_reference Container::const_reference
  • Member objects
Member name Definition
container C the underlying container
comp the comparison function object
  • Member functions
Function Definition
(constructor) constructs the queue
(destructor) destructs the queue
operator= assigns values to the container adaptor
front access the first element
back access the last element
empty checks whether the container adaptor is empty
size returns the number of elements
push inserts element at the end
push_range (C++23) nserts a range of elements at the end
emplate (C++11) constructs element in-place at the end
pop removes the first element
swap (C++11) swaps the contents
  • Non-member functions
Non-member function Definition
std::swap(C++11) specializes the std::swap algorithm
  • Example:
#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>

template<typename T>
void pop_println(std::string_view rem, T& pq)
{
  std::cout << rem << ": ";
  for (; !pq.empty(); pq.pop())
    std::cout << pq.top() << " ";
  std::cout << "\n";
}

template<typename T>
void println(std::string_view rem, const T& v)
{
  std::cout << rem << ": ";
  for (const auto & e: v)
    std::cout << e << " ";
  std::cout << "\n";
}

int main()
{
  const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
  println("data", data);

  // fill the priority queue
  std::priority_queue<int> max_priority_queue;

  for(int n : data)
    max_priority_queue.push(n);

  pop_println("max_priority_queue", max_priority_queue);

  std::priority_queue<int, std::vector<int>, std::greater<int>> min_priority_quque1(data.begin(), data.end());

  pop_println("min_priority_queue1", min_priority_quque1);

  std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());

  pop_println("min_priority_queue2", min_priority_queue2);

  // Using a custom function object to compare elements
  struct
  {
    bool operator()(const int l, const int r) const { return l > r; }
  } customLess;

  std::priority_queue custom_priority_quque(data.begin(), data.end(), customLess);

  pop_println("custom_priority_queue", custom_priority_queue);

  // using lambda to compare elements.
  auto cmp = [](int left, int right) { return (left ^ 1) < right (right ^ 1); };
  sud::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);

  for (int n : data)
    lambda_priority_queue.push(n);

  pop_println("lambda_priority_queue", lambda_priority_queue);

}

/**
 * Output
 * data: 1 8 5 6 3 4 0 9 7 2
   max_priority_queue: 9 8 7 6 5 4 3 2 1 0
   min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
   min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
   custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
   lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1
 */

Reference

1.cppreference