std::priori...iority_queue(3)

💅 std::priority_queue::priority_queue 💅

okay bestie, welcome to the C++ Standard Library manual page for the std::priority_queue::priority_queue constructor. Yes, the constructor has its own page, and yes, there are twenty-two overloads in this part. We are so back. 🫶

---

✨ NAME ✨

std::priority_queue::priority_queue — std::priority_queue::priority_queue

---

🌸 Synopsis 🌸

Constructs a new underlying container of the container adaptor from a variety of data sources. Literally a constructor buffet, no cap.

priority_queue() : priority_queue(Compare(), Container()) {}  (1) (since C++11)
explicit priority_queue( const Compare& compare )
    : priority_queue(compare, Container()) {}                 (2) (since C++11)
explicit priority_queue( const Compare& compare = Compare(),
                         const Container& cont = Container() ); (3) (until C++11)
priority_queue( const Compare& compare, const Container& cont ); (3) (since C++11)
priority_queue( const Compare& compare, Container&& cont );       (4) (since C++11)
priority_queue( const priority_queue& other );                    (5)
priority_queue( priority_queue&& other );                         (6) (since C++11)

template< class InputIt >
priority_queue( InputIt first, InputIt last,
                const Compare& compare = Compare() );  (7) (since C++11)
template< class InputIt >
priority_queue( InputIt first, InputIt last,
                const Compare& compare = Compare(),
                const Container& cont = Container() ); (8) (until C++11)
template< class InputIt >
priority_queue( InputIt first, InputIt last,
                const Compare& compare, const Container& cont ); (8) (since C++11)
template< class InputIt >
priority_queue( InputIt first, InputIt last,
                const Compare& compare, Container&& cont ); (9) (since C++11)

template< class Alloc >
explicit priority_queue( const Alloc& alloc );  (10) (since C++11)
template< class Alloc >
priority_queue( const Compare& compare, const Alloc& alloc );  (11) (since C++11)
template< class Alloc >
priority_queue( const Compare& compare, const Container& cont,
                const Alloc& alloc );  (12) (since C++11)
template< class Alloc >
priority_queue( const Compare& compare, Container&& cont,
                const Alloc& alloc );  (13) (since C++11)
template< class Alloc >
priority_queue( const priority_queue& other, const Alloc& alloc );  (14) (since C++11)
template< class Alloc >
priority_queue( priority_queue&& other, const Alloc& alloc );  (15) (since C++11)

template< class InputIt, class Alloc >
priority_queue( InputIt first, InputIt last, const Alloc& alloc );  (16) (since C++11)
template< class InputIt, class Alloc >
priority_queue( InputIt first, InputIt last, const Compare& compare,
                const Alloc& alloc );  (17) (since C++11)
template< class InputIt, class Alloc >
priority_queue( InputIt first, InputIt last, const Compare& compare,
                const Container& cont, const Alloc& alloc );  (18) (since C++11)
template< class InputIt, class Alloc >
priority_queue( InputIt first, InputIt last, const Compare& compare,
                Container&& cont, const Alloc& alloc );  (19) (since C++11)

template< container-compatible-range<T> R >
priority_queue( std::from_range_t, R&& rg,
                const Compare& compare = Compare() );  (20) (since C++23)
template< container-compatible-range<T> R, class Alloc >
priority_queue( std::from_range_t, R&& rg,
                const Compare& compare, const Alloc& alloc );  (21) (since C++23)
template< container-compatible-range<T> R, class Alloc >
priority_queue( std::from_range_t, R&& rg, const Alloc& alloc );  (22) (since C++23)

Now the lore, overload by overload:

1. Default constructor. Value-initializes the comparator and the underlying container.
2. Copy-constructs the comparison functor comp with the contents of compare. Value-initializes the underlying container c.
3. Copy-constructs the underlying container c with the contents of cont. Copy-constructs the comparison functor comp with the contents of compare. Calls std::make_heap(c.begin(), c.end(), comp). This is also the default constructor. (until C++11)
4. Move-constructs the underlying container c with std::move(cont). Copy-constructs the comparison functor comp with compare. Calls std::make_heap(c.begin(), c.end(), comp).
5. Copy constructor. The underlying container is copy-constructed with other.c. The comparison functor is copy-constructed with other.comp. (implicitly declared)
6. Move constructor. The underlying container is constructed with std::move(other.c). The comparison functor is constructed with std::move(other.comp). (implicitly declared)

7–9) Iterator-pair constructors. These overloads participate in overload resolution only if InputIt satisfies LegacyInputIterator.

7. Constructs c as if by c(first, last) and comp from compare. Then calls std::make_heap(c.begin(), c.end(), comp);.
8. Copy-constructs c from cont and comp from compare. Then calls c.insert(c.end(), first, last);, and then calls std::make_heap(c.begin(), c.end(), comp);.
9. Move-constructs c from std::move(cont) and copy-constructs comp from compare. Then calls c.insert(c.end(), first, last);, and then calls std::make_heap(c.begin(), c.end(), comp);.

10–15) Allocator-extended constructors. These overloads participate in overload resolution only if std::uses_allocator<container_type, Alloc>::value is true, that is, if the underlying container is an allocator-aware container (true for all standard library containers).

10. Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). comp is value-initialized.
11. Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). Copy-constructs comp from compare.
12. Constructs the underlying container with the contents of cont and using alloc as allocator, as if by c(cont, alloc). Copy-constructs comp from compare. Then calls std::make_heap(c.begin(), c.end(), comp).
13. Constructs the underlying container with the contents of cont using move semantics while using alloc as allocator, as if by c(std::move(cont), alloc). Copy-constructs comp from compare. Then calls std::make_heap(c.begin(), c.end(), comp).
14. Constructs the underlying container with the contents of other.c and using alloc as allocator. Effectively calls c(other.c, alloc). Copy-constructs comp from other.comp.
15. Constructs the underlying container with the contents of other using move semantics while utilizing alloc as allocator. Effectively calls c(std::move(other.c), alloc). Move-constructs comp from other.comp.

16–19) Allocator-extended iterator-pair constructors. Same as (7–9), except that alloc is used for constructing the underlying container. These overloads participate in overload resolution only if std::uses_allocator<container_type, Alloc>::value is true and InputIt satisfies LegacyInputIterator.

20. Initializes comp with compare and c with ranges::to<Container>(std::forward<R>(rg)). Then calls std::make_heap(c.begin(), c.end(), comp).
21. Initializes comp with compare and c with ranges::to<Container>(std::forward<R>(rg), alloc). Then calls std::make_heap(c.begin(), c.end(), comp).
22. Initializes c with ranges::to<Container>(std::forward<R>(rg), alloc). Then calls std::make_heap(c.begin(), c.end(), comp).

bestie note: how an implementation checks whether a type satisfies LegacyInputIterator is unspecified, except that integral types are required to be rejected. so do not try to be cute with int there. 🙈

---

🎀 Parameters 🎀

• alloc — allocator to use for all memory allocations of the underlying container
• other — another container adaptor to be used as source to initialize the underlying container
• cont — container to be used as source to initialize the underlying container
• compare — the comparison function object to initialize the underlying comparison functor
• first, last — a range [first, last) of elements to initialize with
• rg — a container compatible range, that is, an input_range whose elements are convertible to T

---

🦋 Type requirements 🦋

• Alloc must meet the requirements of Allocator.
• Compare must meet the requirements of Compare.
• Container must meet the requirements of Container. The allocator-extended constructors are only defined if Container meets the requirements of AllocatorAwareContainer.
• InputIt must meet the requirements of LegacyInputIterator.

⏱️ Complexity

okay bestie, here’s the vibe check on the cost of every overload — same numbers, same O(...) energy, no cap:

• 1,2) — Constant.
• 3,5,12) — O(N) comparisons and O(N) calls to the constructor of value_type, where N is cont.size().
• 4) — O(N) comparisons, where N is cont.size().
• 6) — Constant.
• 7,16,17) — O(M) comparisons, where M is std::distance(first, last).
• 8,18) — O(N + M) comparisons and O(N) calls to the constructor of value_type, where N is cont.size() and M is std::distance(first, last).
• 9) — O(N + M) comparisons, where N is cont.size() and M is std::distance(first, last).
• 10,11) — Constant.
• 13) — O(N) comparisons, where N is cont.size().
• 14) — Linear in size of other.
• 15) — Constant if Alloc compares equal to the allocator of other. Linear in size of other otherwise.
• 19) — O(N + M) comparisons and possibly O(N) calls to the constructor of value_type (present if Alloc does not compare equal to the allocator of other), where N is cont.size() and M is std::distance(first, last).
• 20) — O(N) comparisons and O(N) calls to the constructor of value_type, where N is ranges::distance(rg).
• 21,22) — This section is incomplete. The page literally says so 😭.

---

📝 Notes

The feature-test macro table is giving very “tiny but important” energy:

• Feature-test macro: __cpp_lib_containers_ranges
  • Value: 202202L
  • Std: (C++23)
  • Feature: Ranges-aware construction and insertion; overloads (20-22)

---

🧪 Example

The page says: // Run this code

#include <complex>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main()
{
    std::priority_queue<int> pq1;
    pq1.push(5);
    std::cout << "pq1.size() = " << pq1.size() << '\n';

    std::priority_queue<int> pq2 {pq1};
    std::cout << "pq2.size() = " << pq2.size() << '\n';

    std::vector<int> vec {3, 1, 4, 1, 5};
    std::priority_queue<int> pq3 {std::less<int>(), vec};
    std::cout << "pq3.size() = " << pq3.size() << '\n';

    for (std::cout << "pq3 : "; !pq3.empty(); pq3.pop())
        std::cout << pq3.top() << ' ';
    std::cout << '\n';

    // Demo With Custom Comparator:

    using my_value_t = std::complex<double>;
    using my_container_t = std::vector<my_value_t>;

    auto my_comp = [](const my_value_t& z1, const my_value_t& z2)
    {
        return z2.real() < z1.real();
    };

    std::priority_queue<my_value_t,
                        my_container_t,
                        decltype(my_comp)> pq4{my_comp};

    using namespace std::complex_literals;
    pq4.push(5.0 + 1i);
    pq4.push(3.0 + 2i);
    pq4.push(7.0 + 3i);

    for (; !pq4.empty(); pq4.pop())
    {
        const auto& z = pq4.top();
        std::cout << "pq4.top() = " << z << '\n';
    }

    // TODO: C++23 range-aware ctors
}

🖥️ Output

pq1.size() = 1
pq2.size() = 1
pq3.size() = 5
pq3 : 5 4 3 1 1
pq4.top() = (3,2)
pq4.top() = (5,1)
pq4.top() = (7,3)

---

🩹 Defect reports

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

• P0935R0 — applied to C++11. Behavior as published: default constructor and constructor (4) made implicit. Correct behavior: were explicit.
• LWG 3506 — applied to C++11. Behavior as published: allocator-extended iterator-pair constructors were missing. Correct behavior: added.
• LWG 3522 — applied to C++11. Behavior as published: constraints on iterator-pair constructors were missing. Correct behavior: added.
• LWG 3529 — applied to C++11. Behavior as published: construction from a pair of iterators called insert. Correct behavior: constructs the container from them.

---

👀 See also

• operator= — assigns values to the container adaptor (public member function).

---

Category: * Todo without reason

---

okay that’s the whole page, bestie 🫶 — the footer carries source/version/date: http://cppreference.com, 2024.06.10, and std::priori...iority_queue(3) ✨💅