std::priority_queue<T,Container,Compare>::priority_queue - cppreference.com (original) (raw)

Constructs new underlying container of the container adaptor from a variety of data sources.

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.

1. Constructs c as if by c(first, last) and comp from compare. Then calls std::make_heap(c.begin(), c.end(), comp);.

2. 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);.

3. 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).

1. Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). comp is value-initialized.

2. Constructs the underlying container using alloc as allocator. Effectively calls c(alloc). Copy-constructs comp from compare.

3. 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).

4. 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).

5. 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.

6. 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.

1. 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).

Note that how an implementation checks whether a type satisfies LegacyInputIterator is unspecified, except that integral types are required to be rejected.

[edit] Parameters

[edit] Complexity

1,2) Constant.

3,5,12) \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of value_type, where \(\scriptsize N\)N is cont.size().

1. \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons, where \(\scriptsize N\)N is cont.size().

2. Constant.

7,16,17) \(\scriptsize \mathcal{O}{(M)}\)O(M) comparisons, where \(\scriptsize M\)M is std::distance(first, last).

8,18) \(\scriptsize \mathcal{O}{(N + M)}\)O(N + M) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of value_type, where \(\scriptsize N\)N is cont.size() and \(\scriptsize M\)M is std::distance(first, last).

1. \(\scriptsize \mathcal{O}{(N + M)}\)O(N + M) comparisons, where \(\scriptsize N\)N is cont.size() and \(\scriptsize M\)M is std::distance(first, last).

10,11) Constant.

1. \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons, where \(\scriptsize N\)N is cont.size().

2. Linear in size of other.

3. Constant if Alloc compares equal to the allocator of other. Linear in size of other otherwise.

4. \(\scriptsize \mathcal{O}{(N + M)}\)O(N + M) comparisons and possibly \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of value_type (present if Alloc does not compare equal to the allocator of other), where \(\scriptsize N\)N is cont.size() and \(\scriptsize M\)M is std::distance(first, last).

5. \(\scriptsize \mathcal{O}{(N)}\)O(N) comparisons and \(\scriptsize \mathcal{O}{(N)}\)O(N) calls to the constructor of value_type, where \(\scriptsize N\)N is ranges::distance(rg).

[edit] Notes

[edit] Example

#include #include #include #include #include   int main() { std::priority_queue pq1; pq1.push(5); std::cout << "pq1.size() = " << pq1.size() << '\n';   std::priority_queue pq2 {pq1}; std::cout << "pq2.size() = " << pq2.size() << '\n';   std::vector vec {3, 1, 4, 1, 5}; std::priority_queue pq3 {std::less(), 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; using my_container_t = std::vector;   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)

[edit] Defect reports

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

[edit] See also

| | assigns values to the container adaptor (public member function) [edit] | | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |