c++ - library - ¿Por qué std:: stack usa std:: deque de forma predeterminada?

stl c++ español

Question

Como las únicas operaciones requeridas para que un contenedor se use en una pila son:

• espalda()
• hacer retroceder()
• pop_back ()

¿Por qué el contenedor predeterminado es un deque en lugar de un vector?

¿Las reasignaciones de deque no dan un búfer de elementos antes del frente () para que push_front () sea una operación eficiente? ¿No se desperdician estos elementos ya que nunca se usarán en el contexto de una pila?

Si no hay sobrecarga para usar un deque de esta manera en lugar de un vector, ¿por qué el valor predeterminado para priority_queue es un vector y no un deque también? (priority_queue requiere front (), push_back () y pop_back () - esencialmente lo mismo que para la pila)

Actualizado según las respuestas a continuación:

Parece que la forma en que generalmente se implementa deque es una matriz de tamaño variable de matrices de tamaño fijo. Esto hace que crezca más rápido que un vector (que requiere reasignación y copia), por lo que para algo así como una pila que se trata de agregar y eliminar elementos, deque es probablemente una mejor opción.

priority_queue requiere una fuerte indexación, ya que cada eliminación e inserción requiere ejecutar pop_heap () o push_heap (). Esto probablemente hace que el vector sea una mejor opción allí ya que agregar un elemento todavía se amortiza de todos modos.

Answer 1

A medida que el contenedor crece, una reasignación para un vector requiere copiar todos los elementos en el nuevo bloque de memoria. Growing aque asigna un nuevo bloque y lo vincula a la lista de bloques; no se requieren copias.

Por supuesto, puede especificar que se use un contenedor de respaldo diferente si lo desea. Entonces, si tienes una pila que sabes que no va a crecer mucho, dile que use un vector en lugar de una deque si esa es tu preferencia.

Answer 2

Ver el Gurú de la semana 54 de Herb Sutter para conocer los méritos relativos de vector y deque donde cualquiera de ellos lo haría.

Imagino que la incoherencia entre priority_queue y queue es simplemente que diferentes personas los implementaron.