Con stl priority_queue puede establecer el contenedor subyacente, como vector. ¿Cuáles son algunas de las ventajas de especificar un contenedor para stl priority_queue?Ventajas de establecer priority_queue Container
Ajuste del contenedor subyacente hace que sea posible separar dos preocupaciones lógicamente separadas:
priority_queue).Como ejemplo, la implementación estándar de vector no es necesaria para contraerse cuando su capacidad es muy superior a su tamaño real. Esto significa que si tiene una cola de prioridad respaldada por un vector, puede terminar desperdiciando memoria si encola muchos elementos y luego los quita a todos, ya que el vector mantendrá su antigua capacidad. Si, por otro lado, implementa su propia clase shrinking_vector que realmente disminuye su capacidad cuando sea necesario, puede obtener todos los beneficios de la interfaz priority_queue mientras se usa el almacenamiento de manera más eficiente.
Otro posible ejemplo: es posible que desee cambiar el asignador que se utiliza para que los elementos de la cola de prioridad se asignen desde un conjunto especial de recursos. Puede hacerlo simplemente configurando el tipo de contenedor priority_queue para que sea vector con un asignador personalizado.
Una reflexión más: supongamos que está almacenando un priority_queue de objetos muy grandes cuyo tiempo de copia es muy grande. En ese caso, el hecho de que el vector se redimensione dinámicamente y copie sus elementos antiguos (o al menos, en un compilador C++ 03) podría ser algo que no está dispuesto a pagar. Por lo tanto, puede cambiar a otro tipo, tal vez un deque, que hace un esfuerzo para no copiar elementos al cambiar el tamaño y puede realizar algunas grandes ganancias de rendimiento.
Espero que esto ayude!
La clase priority_queue es un ejemplo de adapter pattern. Proporciona una forma de proporcionar los servicios de una cola de prioridad sobre un conjunto de datos existente. Como adaptador, realmente requiere un contenedor subyacente. Por defecto, especifica un vector. (desde here).
En cuanto a las ventajas, es simplemente una más flexible. El priority_queue utiliza los siguientes métodos de la tienda de respaldo y requiere que admita iteradores de acceso aleatorio.
frontpush_backpop_backAl proporcionar como un adaptador, puede controlar las características de rendimiento mediante el suministro de una implementación diferente.
Dos ejemplos que implementan esto en STL son vector y deque. Ambos tienen diferentes características de rendimiento. Por ejemplo, un vector típicamente es contiguo en memoria, mientras que un deque típicamente no lo es.La operación push_back en un vector solo se amortiza a tiempo constante (podría tener que reasignar el vector), mientras que para el deque se especifica en tiempo constante.
Gran respuesta, cubre todas las preocupaciones que surgieron en mi cabeza al leer la pregunta de OP. – Rerito