std::priority_queue<T,Container,Compare>:: priority_queue

From cppreference.net

priority_queue ( ) : priority_queue ( Compare ( ) , Container ( ) ) { }	(1)	(depuis C++11)
explicit priority_queue ( const Compare & compare ) : priority_queue ( compare, Container ( ) ) { }	(2)	(depuis C++11)
	(3)
explicit priority_queue ( const Compare & compare = Compare ( ) , const Container & cont = Container ( ) ) ;			(jusqu'à C++11)
priority_queue ( const Compare & compare, const Container & cont ) ;			(depuis C++11)
priority_queue ( const Compare & compare, Container && cont ) ;		(4)	(depuis C++11)
priority_queue ( const priority_queue & other ) ;		(5)
priority_queue ( priority_queue && other ) ;		(6)	(depuis C++11)
template < class InputIt > priority_queue ( InputIt first, InputIt last, const Compare & compare = Compare ( ) ) ;		(7)	(depuis C++11)
		(8)
template < class InputIt > priority_queue ( InputIt first, InputIt last, const Compare & compare = Compare ( ) , const Container & cont = Container ( ) ) ;				(jusqu'à C++11)
template < class InputIt > priority_queue ( InputIt first, InputIt last, const Compare & compare, const Container & cont ) ;				(depuis C++11)
template < class InputIt > priority_queue ( InputIt first, InputIt last, const Compare & compare, Container && cont ) ;			(9)	(depuis C++11)
template < class Alloc > explicit priority_queue ( const Alloc & alloc ) ;			(10)	(depuis C++11)
template < class Alloc > priority_queue ( const Compare & compare, const Alloc & alloc ) ;			(11)	(depuis C++11)
template < class Alloc > priority_queue ( const Compare & compare, const Container & cont, const Alloc & alloc ) ;			(12)	(depuis C++11)
template < class Alloc > priority_queue ( const Compare & compare, Container && cont, const Alloc & alloc ) ;			(13)	(depuis C++11)
template < class Alloc > priority_queue ( const priority_queue & other, const Alloc & alloc ) ;			(14)	(depuis C++11)
template < class Alloc > priority_queue ( priority_queue && other, const Alloc & alloc ) ;			(15)	(depuis C++11)
template < class InputIt, class Alloc > priority_queue ( InputIt first, InputIt last, const Alloc & alloc ) ;			(16)	(depuis C++11)
template < class InputIt, class Alloc > priority_queue ( InputIt first, InputIt last, const Compare & compare, const Alloc & alloc ) ;			(17)	(depuis C++11)
template < class InputIt, class Alloc > priority_queue ( InputIt first, InputIt last, const Compare & compare, const Container & cont, const Alloc & alloc ) ;			(18)	(depuis C++11)
template < class InputIt, class Alloc > priority_queue ( InputIt first, InputIt last, const Compare & compare, Container && cont, const Alloc & alloc ) ;			(19)	(depuis C++11)
template < container-compatible-range < T > R > priority_queue ( std:: from_range_t , R && rg, const Compare & compare = Compare ( ) ) ;			(20)	(depuis 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)	(depuis C++23)
template < container-compatible-range < T > R, class Alloc > priority_queue ( std:: from_range_t , R && rg, const Alloc & alloc ) ;			(22)	(depuis C++23)

Construit un nouveau conteneur sous-jacent de l'adaptateur de conteneur à partir de diverses sources de données.

1) Constructeur par défaut. Initialise par valeur le comparateur et le conteneur sous-jacent.

2) Constructeur par copie du foncteur de comparaison comp avec le contenu de compare . Initialise par valeur le conteneur sous-jacent c .

3) Constructe par copie le conteneur sous-jacent c avec le contenu de cont . Constructe par copie le foncteur de comparaison comp avec le contenu de compare . Appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) . Ceci est également le constructeur par défaut. (until C++11)

4) Constructeur par déplacement du conteneur sous-jacent c avec std :: move ( cont ) . Constructeur par copie du foncteur de comparaison comp avec compare . Appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

5) Constructeur de copie . Le conteneur sous-jacent est copié-construit avec other. c . Le foncteur de comparaison est copié-construit avec other. comp . (déclaré implicitement)

6) Constructeur de déplacement . Le conteneur sous-jacent est construit avec std :: move ( other. c ) . Le foncteur de comparaison est construit avec std :: move ( other. comp ) . (déclaré implicitement)

7-9) Constructeurs par paire d'itérateurs. Ces surcharges participent à la résolution de surcharge uniquement si


        InputIt

satisfait LegacyInputIterator .

7) Construit c comme par c ( first, last ) et comp à partir de compare . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .

8) Construit par copie c à partir de cont et comp à partir de compare . Puis appelle c. insert ( c. end ( ) , first, last ) ; , et enfin appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .

9) Constructeur par déplacement de c à partir de std :: move ( cont ) et constructeur par copie de comp à partir de compare . Puis appelle c. insert ( c. end ( ) , first, last ) ; , et ensuite appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) ; .

10-15) Constructeurs avec allocation étendue. Ces surcharges participent à la résolution de surcharge uniquement si std:: uses_allocator < container_type, Alloc > :: value est true , c'est-à-dire si le conteneur sous-jacent est un conteneur sensible à l'allocateur (vrai pour tous les conteneurs de la bibliothèque standard).

10) Construit le conteneur sous-jacent en utilisant alloc comme allocateur. Appelle effectivement c ( alloc ) . comp est initialisé par défaut.

11) Construit le conteneur sous-jacent en utilisant alloc comme allocateur. Appelle effectivement c ( alloc ) . Copie-construit comp à partir de compare .

12) Construit le conteneur sous-jacent avec le contenu de cont et en utilisant alloc comme allocateur, comme par c ( cont, alloc ) . Copie-construit comp à partir de compare . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

13) Construit le conteneur sous-jacent avec le contenu de cont en utilisant la sémantique de déplacement tout en utilisant alloc comme allocateur, comme par c ( std :: move ( cont ) , alloc ) . Construit par copie comp à partir de compare . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

14) Construit le conteneur sous-jacent avec le contenu de other. c et en utilisant alloc comme allocateur. Appelle effectivement c ( other. c , alloc ) . Construit par copie comp à partir de other. comp .

15) Construit le conteneur sous-jacent avec le contenu de other en utilisant la sémantique de déplacement tout en utilisant alloc comme allocateur. Appelle effectivement c ( std :: move ( other. c ) , alloc ) . Construit par déplacement comp à partir de other. comp .

16-19) Constructeurs par paire d'itérateurs avec allocation étendue. Identiques à (7-9) , sauf que alloc est utilisé pour la construction du conteneur sous-jacent. Ces surcharges participent à la résolution de surcharge seulement si std:: uses_allocator < container_type, Alloc > :: value est true et que InputIt satisfait LegacyInputIterator .

20) Initialise comp avec compare et c avec ranges:: to < Container > ( std:: forward < R > ( rg ) ) . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

21) Initialise comp avec compare et c avec ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

22) Initialise c avec ranges:: to < Container > ( std:: forward < R > ( rg ) , alloc ) . Puis appelle std:: make_heap ( c. begin ( ) , c. end ( ) , comp ) .

Notez que la manière dont une implémentation vérifie si un type satisfait LegacyInputIterator n'est pas spécifiée, sauf que les types entiers doivent être rejetés.

Table des matières

Paramètres

alloc	-	allocateur à utiliser pour toutes les allocations de mémoire du conteneur sous-jacent
other	-	un autre adaptateur de conteneur à utiliser comme source pour initialiser le conteneur sous-jacent
cont	-	conteneur à utiliser comme source pour initialiser le conteneur sous-jacent
compare	-	l'objet fonction de comparaison pour initialiser le foncteur de comparaison sous-jacent
first, last	-	la paire d'itérateurs définissant la plage d'éléments à initialiser
rg	-	une plage compatible avec les conteneurs , c'est-à-dire une `input_range` dont les éléments sont convertibles en `T`
Exigences de type
- `Alloc` doit satisfaire aux exigences de Allocator .
- `Compare` doit satisfaire aux exigences de Compare .
- `Container` doit satisfaire aux exigences de Container . Les constructeurs avec extension d'allocateur ne sont définis que si `Container` satisfait aux exigences de AllocatorAwareContainer .
- `InputIt` doit satisfaire aux exigences de LegacyInputIterator .

Complexité

1,2) Constant.

3,5,12)

O(N)

comparaisons et

O(N)

appels au constructeur de


        value_type

, où

N

est cont. size ( ) .

O(N)

comparaisons, où

N

est cont. size ( ) .

6) Constante.

7,16,17)

O(M)

comparaisons, où

M

est std:: distance ( first, last ) .

8,18)

O(N + M)

comparaisons et

O(N)

appels au constructeur de


        value_type

, où

N

est cont. size ( ) et

M

est std:: distance ( first, last ) .

O(N + M)

comparaisons, où

N

est cont. size ( ) et

M

est std:: distance ( first, last ) .

10,11) Constant.

13)

O(N)

comparaisons, où

N

est cont. size ( ) .

14) Linéaire en fonction de la taille de other .

15) Constant si


        Alloc

est égal à l'allocateur de other . Linéaire selon la taille de other sinon.

19)

O(N + M)

comparaisons et éventuellement

O(N)

appels au constructeur de


        value_type

(présent si


        Alloc

n'est pas égal à l'allocateur de other ), où

N

est cont. size ( ) et

M

est std:: distance ( first, last ) .

20)

O(N)

comparaisons et

O(N)

appels au constructeur de


        value_type

, où

N

est ranges:: distance ( rg ) .

21,22)

Cette section est incomplète

Notes

Macro de test de fonctionnalité	Valeur	Std	Fonctionnalité
`__cpp_lib_containers_ranges`	`202202L`	(C++23)	Construction et insertion compatibles avec les gammes ; surcharges ( 20-22 )

Exemple

Exécuter ce 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';
    // Démonstration avec comparateur personnalisé :
    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
}

Sortie :

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)

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR	Appliqué à	Comportement publié	Comportement corrigé
P0935R0	C++11	le constructeur par défaut et le constructeur (4) étaient explicites	rendus implicites
LWG 3506	C++11	les constructeurs à base de paire d'itérateurs avec allocateur étaient manquants	ajoutés
LWG 3522	C++11	les contraintes sur les constructeurs à base de paire d'itérateurs étaient manquantes	ajoutées
LWG 3529	C++11	la construction à partir d'une paire d'itérateurs appelait `insert`	construit le conteneur à partir de ceux-ci

Voir aussi

operator=

assigne des valeurs à l'adaptateur de conteneur
(fonction membre publique)

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)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

node-handle (C++17)
Sequence
array (C++11)
vector
vector <bool>
inplace_vector (C++26)
hive (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
priority_queue::priority_queue
priority_queue::~priority_queue
priority_queue::operator=
Element access
priority_queue::top
Capacity
priority_queue::empty
priority_queue::size
Modifiers
priority_queue::push
priority_queue::push_range (C++23)
priority_queue::emplace (C++11)
priority_queue::pop
priority_queue::swap (C++11)
Non-member functions
swap (std::priority_queue) (C++11)
Helper classes
uses_allocator <std::priority_queue> (C++11)
formatter <std::priority_queue> (C++23)
Deduction guides (C++17)

cppreference.net

Namespaces

Variants

std::priority_queue<T,Container,Compare>:: priority_queue

Table des matières

Paramètres

Complexité

Notes

Exemple

Rapports de défauts

Voir aussi