Clase priority_queue

  • Artículo

Una clase de adaptador de contenedor de plantilla que proporciona una restricción de la funcionalidad que limita el acceso al elemento superior de algún tipo de contenedor subyacente, que siempre es el más grande o el que tiene una prioridad más alta. Pueden agregarse nuevos elementos a priority_queue y el elemento superior de priority_queue puede inspeccionarse o quitarse.

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 elementos que se va a almacenar en la priority_queue.

Container
Tipo del contenedor subyacente que se usa para implementar priority_queue.

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

Comentarios

Los elementos de la clase Type estipulada en el primer parámetro de plantilla de un objeto de cola son sinónimos de value_type y deben coincidir con el tipo de elemento de la clase de contenedor subyacente Container estipulada por el segundo parámetro de plantilla. El Type debe ser asignable, para que sea posible copiar objetos de ese tipo y asignar valores a variables de ese tipo.

El objeto priority_queue ordena la secuencia que controla llamando a un objeto de función almacenado de clase Traits. En general, se debe poder comparar si los elementos son menores que otros para poder establecer este orden; de este modo, dados dos elementos cualesquiera, se puede determinar que son equivalentes (en el sentido de que ninguno es menor que el otro) o que uno es menor que el otro. Esto produce una ordenación entre los elementos no equivalentes. En un sentido más técnico, la función de comparación es un predicado binario que induce una ordenación débil estricta en el sentido matemático estándar.

Las clases contenedoras subyacentes adecuadas para priority_queue incluyen deque (Clase) y la vectorclase (Clase) predeterminada, o cualquier otro contenedor de secuencias que admita las operaciones de front, push_back, and pop_back y un iterador de acceso aleatorio. La clase de contenedor subyacente se encapsula dentro del adaptador de contenedor, que solo expone el conjunto limitado de las funciones miembro de contenedor de secuencias como una interfaz pública.

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

Existen tres tipos de adaptadores de contenedor que se definen mediante la biblioteca estándar de C++: stack, queue y priority_queue. Cada uno restringe la función de alguna clase de contenedor subyacente para proporcionar una interfaz controlada de manera precisa para una estructura de datos estándar.

  • La clase stack es compatible con una estructura de datos LIFO (el último en entrar es el primero en salir). Un buen símil sería una pila de platos. Solo se pueden insertar e inspeccionar elementos (platos) en la parte superior de la pila, que es el último elemento al final del contenedor base, y solo se pueden quitar de ahí. La restricción de acceder únicamente al elemento superior es el motivo por el que se usa la clase stack.

  • La clase queue es compatible con una estructura de datos FIFO (el primero en entrar es el primero en salir). Un buen símil sería el de personas que hacen cola en un banco. Se pueden agregar elementos (personas) a la parte posterior de la línea y quitarlos de la parte delantera de la línea. Se puede inspeccionar tanto la parte delantera como trasera de una línea. La restricción de acceder únicamente a los elementos delanteros y traseros de esta manera es el motivo por el que se usa la clase queue.

  • La clase priority_queue ordena sus elementos de tal modo que el elemento más grande siempre esté en la parte superior. Admite la inserción de un elemento y la inspección y eliminación del elemento superior. Un buen símil sería el de personas alineadas y organizadas por edad, altura o cualquier otro criterio.

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 debe adaptarse mediante una priority_queue.
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. La clase de contenedor de secuencias de la biblioteca estándar de C++ (la clase deque y la vector predeterminada) cumple los requisitos para usarse como el contenedor base para un objeto priority_queue. También pueden usarse tipos definidos por el usuario que cumplan los requisitos.

Para obtener más información sobre Container, vea la sección Comentarios del tema priority_queue (Clase).

Ejemplo

Vea el ejemplo de priority_queue para obtener un ejemplo de cómo declarar y usar container_type.

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

// pqueue_empty.cpp
// 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 no debe estar vacía para aplicar la función miembro. La parte superior de priority_queue está siempre ocupada por el elemento más grande del contenedor.

Ejemplo

// pqueue_pop.cpp
// 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

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.

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

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

int main( )
{
   using namespace std;

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

   // Explicitly 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;

   // This method of printing out the elements of a priority_queue
   // removes the elements from the priority queue, leaving it empty
   cout << "After printing, q2 has " << q2.size( ) << " elements." << endl;

   // The third member function 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;

   // The fourth member function declares a priority_queue and
   // initializes it with elements copied from another container:
   // first, inserting elements into q1, 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;

   // The fifth member function 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;

   // The sixth member function 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
El elemento agregado a la parte superior de la priority_queue.

Comentarios

La parte superior de priority_queue es la posición ocupada por el elemento más grande del contenedor.

Ejemplo

// pqueue_push.cpp
// 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

// pqueue_size.cpp
// 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 puede representar el número de elementos de un priority_queue.

typedef typename Container::size_type size_type;

Comentarios

El tipo es un sinónimo de size_type del contenedor base adaptado por priority_queue.

Ejemplo

Vea el ejemplo de size para obtener un ejemplo de cómo declarar y usar size_type.

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 no debe estar vacía para aplicar la función miembro.

Ejemplo

// pqueue_top.cpp
// 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

El tipo es un sinónimo de value_type del contenedor base adaptado por priority_queue.

Ejemplo

// pqueue_value_type.cpp
// 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.

Consulte también

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