Compartir a través de

clase priority_queue

Adaptador de contenedor que mantiene una colección de elementos donde siempre se puede acceder al elemento más grande (o prioridad más alta) en la parte superior. Puede agregar nuevos elementos y quitar o examinar el elemento superior, pero no puede acceder directamente a los elementos en medio de la colección.

Sintaxis

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

Parámetros

Type
Tipo de datos de elemento que se va a almacenar en .priority_queue

Container
Tipo del contenedor subyacente que almacena los elementos de .priority_queue

Compare
Tipo que proporciona un objeto de función que compara dos valores de elemento como claves de ordenación para determinar su orden relativo en .priority_queue Este argumento es opcional. El predicado less<typename Container::value_type> binario es el valor predeterminado.

Comentarios

Los elementos de clase Type especificados en el primer parámetro de plantilla de un priority_queue objeto son equivalentes a value_type y deben coincidir con el tipo de elemento de la clase Container contenedora subyacente especificada por el segundo parámetro de plantilla. Type Debe ser asignable, lo que significa que puede copiar objetos de ese tipo y asignar valores a variables de ese tipo.

priority_queue usa una función de comparación para determinar qué elementos tienen mayor prioridad. Esta función de comparación es un objeto de función de la clase Traits. Para trabajar con priority_queue, los elementos solo necesitan admitir la comparación mediante el operador menor que (<) para que pueda organizar los elementos en orden.

Puede cambiar el tipo de contenedor subyacente usado por .priority_queue Es posible que quiera hacerlo por motivos de rendimiento. El valor predeterminado, vector, suele ser mejor para la localidad de caché porque los elementos se almacenan en almacenamiento contiguo y hace menos asignaciones a medida que crece. Pero quizás considere si deque tiene colas muy grandes o sin enlazar y mover elementos es caro. Para obtener más información sobre las clases de contenedor subyacentes adecuadas, consulte container_type.

Agregar y quitar elementos de ambos priority_queue tienen complejidad logarítmica. Tener acceso a elementos en priority_queue tiene una complejidad constante.

La biblioteca estándar de C++ define otros adaptadores de contenedor que puede usar para almacenar los elementos en priority_queue: stack, queuey priority_queue:

  • La clase stack es compatible con una estructura de datos LIFO (el último en entrar es el primero en salir). Considere una pila de placas: puede insertar, inspeccionar o quitar elementos (placas) solo desde la parte superior de la pila, que es el último elemento al final del contenedor base.
  • La clase queue es compatible con una estructura de datos FIFO (el primero en entrar es el primero en salir). Considere a las personas en una línea. Agregue elementos (personas) a la parte posterior de la línea y quítelos del frente de la línea. Tanto la parte delantera como la parte posterior de una línea se pueden inspeccionar.
  • La priority_queue clase ordena sus elementos para que el elemento más grande esté siempre en la parte superior. Admite la inserción de un elemento y la inspección y eliminación del elemento superior.

Examples

Constructores

Constructor Descripción
priority_queue Construye un priority_queue que está vacío o que es una copia de un intervalo de un objeto contenedor base o de otro priority_queue.

Typedefs

Nombre de tipo Descripción
container_type Tipo que proporciona el contenedor base que priority_queue se adapta.
size_type Tipo entero sin signo que puede representar el número de elementos de un priority_queue.
value_type Tipo que representa el tipo de objeto almacenado como elemento en una priority_queue.

Funciones miembro

Función de miembro Descripción
empty Comprueba si la priority_queue está vacía.
pop Quita el elemento más grande del priority_queue desde la posición superior.
push Agrega un elemento a la cola de prioridad basándose en la prioridad del elemento desde operator<.
size Devuelve el número de elementos de priority_queue.
top Devuelve una referencia constante al elemento más grande en la parte superior del priority_queue.

Requisitos

Encabezado: <queue>

Espacio de nombres: std

priority_queue::container_type

Un tipo que proporciona el contenedor base que debe adaptarse.

typedef Container container_type;

Comentarios

El tipo es un sinónimo del parámetro de plantilla Container.

Las clases de contenedor subyacentes adecuadas para priority_queue incluyen deque Class, la clase predeterminada vectoro cualquier otro contenedor de secuencia que admita las operaciones de front, push_backy y pop_back un iterador de acceso aleatorio. El adaptador de contenedor encapsula la clase de contenedor subyacente y expone solo un conjunto limitado de funciones miembro del contenedor de secuencia como una interfaz pública.

Para obtener un ejemplo de cómo declarar y usar container_type, consulte Uso de contenedores y comparadores personalizados.

priority_queue::empty

Comprueba si un priority_queue está vacío.

bool empty() const;

Valor devuelto

true si priority_queue está vacío; false si priority_queue no está vacío.

Ejemplo: Comprobación de si está priority_queue vacío

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

Quita el elemento más grande del priority_queue desde la posición superior.

void pop();

Comentarios

priority_queue Debe ser no vacío para usar esta función miembro. La parte superior de priority_queue siempre contiene el elemento más grande del contenedor.

Ejemplo: Elementos pop y comprobar el tamaño

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

Crea un priority_queue objeto que está vacío o que copia un intervalo desde un objeto contenedor base o desde otro priority_queue.

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

Parámetros

_comp
Función de comparación de tipo constTraits usada para ordenar los elementos de priority_queue, que de manera predeterminada es la función de comparación del contenedor base.

_Cont
El contenedor base del que la priority_queue construida va a ser una copia.

right
El priority_queue del que el conjunto construido va a ser una copia.

first
Posición del primer elemento en el intervalo de elementos que se va a copiar.

last
Posición del primer elemento más allá del intervalo de elementos que se va a copiar.

Comentarios

Cada uno de los tres primeros constructores especifican un priority_queue inicial vacío, el segundo también especifica el tipo de función de comparación (comp) que se usará para establecer el orden de los elementos y el tercero especifica explícitamente el container_type (_Cont) que se va a usar. La palabra clave explicit suprime ciertas clases de conversión automática de tipos.

El cuarto constructor especifica una copia de priority_queue right.

Los últimos tres constructores copian el intervalo [first, last) de algún contenedor y usan los valores para inicializar un priority_queue con mayor claridad a la hora de especificar el tipo de función de comparación de clase Traits y container_type.

Ejemplo: Uso de contenedores y comparadores personalizados

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

Agrega un elemento a la cola de prioridad basándose en la prioridad del elemento desde operator<.

void push(const Type& val);

Parámetros

val
Elemento que se va a agregar a la parte superior de priority_queue.

Comentarios

La parte superior de priority_queue contiene el elemento más grande del contenedor.

Ejemplo: Insertar elementos y leer la parte superior

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

Devuelve el número de elementos de priority_queue.

size_type size() const;

Valor devuelto

Longitud actual de priority_queue.

Ejemplo: Obtener el número de elementos de priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

Tipo entero sin signo que representa el número de elementos de un priority_queue.

typedef typename Container::size_type size_type;

Comentarios

Este tipo es un sinónimo del size_type contenedor base que priority_queue se adapta.

Ejemplo: Acceso al elemento superior

Para obtener un ejemplo de cómo declarar y usar size_type, vea Obtener el número de elementos.

priority_queue::top

Devuelve una referencia constante al elemento más grande en la parte superior del priority_queue.

const_reference top() const;

Valor devuelto

Una referencia al elemento más grande, según lo determinado por la función Traits, objeto de priority_queue.

Comentarios

priority_queue Debe ser no vacío para usar esta función miembro.

Ejemplo: Obtener el elemento superior del priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

Tipo que representa el tipo de objeto almacenado como elemento en una priority_queue.

typedef typename Container::value_type value_type;

Comentarios

Este tipo es un sinónimo del value_type contenedor base que priority_queue se adapta.

Ejemplo: Uso del alias de priority_queue value_type

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

Ejemplo: Uso de un tipo de datos definido por el usuario

Para usarlos priority_queue con elementos de tipo definidos por el usuario, debe proporcionar una manera de comparar los elementos. Puede definir operator< para el tipo o proporcionar un objeto de función de comparación personalizado.

En el ejemplo siguiente se muestra un priority_queue objeto que almacena Task objetos ordenados por nivel de prioridad. Las tareas con valores de prioridad más alta se encuentran en la parte superior de la cola.

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

Comentarios

Si desea un orden diferente (por ejemplo, valores inferiores primero), proporcione un comparador personalizado:

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

Vea también

Seguridad para subprocesos en la biblioteca estándar de C++
Referencia de biblioteca estándar de C++

  • Last updated on