¿Por qué std :: stack usa std :: deque por defecto?

91

Dado que las únicas operaciones necesarias para que un contenedor se utilice en una pila son:

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

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

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

Si no hay sobrecarga para usar una deque de esta manera en lugar de un vector, ¿por qué el valor predeterminado de priority_queue es un vector y no una 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 deque se implementa generalmente es una matriz de tamaño variable de matrices de tamaño fijo. Esto hace que el crecimiento sea más rápido que un vector (que requiere reasignación y copia), por lo que para algo como una pila que se trata de agregar y eliminar elementos, deque es probablemente una mejor opción.

Priority_queue requiere una indexación en gran medida, ya que cada eliminación e inserción requiere que ejecute pop_heap () o push_heap (). Esto probablemente hace que el vector sea una mejor opción allí, ya que agregar un elemento aún se amortiza como constante de todos modos.

c++ stl containers Greg Rogers
fuente
1
El razonamiento en su 'actualización' no es del todo correcto. vector normalmente agrega y elimina elementos del final más rápido que un deque. deque es más rápido para hacer crecer la memoria , no para empujar elementos.
Mooing Duck

Respuestas:

75

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

Por supuesto, puede especificar que se utilice un contenedor de respaldo diferente si lo desea. Entonces, si tiene una pila que sabe que no crecerá mucho, dígale que use un vector en lugar de una deque si esa es su preferencia.

Michael Burr
fuente
1
Pero cuando la lista de punteros a bloques crece, esta lista debe reasignarse ocasionalmente como debe hacerlo un vector; asintóticamente, cualquier ganancia en eficiencia es por un factor constante en el mejor de los casos. Y la manipulación del iterador necesaria para hacer push y pop correctamente es mucho más complicada de std::dequelo que es std::vector, y es probable que estas operaciones se utilicen con mucha más frecuencia que las reasignaciones. Me cuesta creer que std::dequealguna vez supere std::vectoren la práctica.
Marc van Leeuwen
@Michael Burr: Entonces, ¿por qué no usar list, por qué deque?
bappak
@MarcvanLeeuwen con respecto a ti dice que te cuesta creer ... ¿podrías dejar un punto de vista claro? ¿Quiere decir que ahora está creyendo std::dequeque tiene la oportunidad de ganar std::vectoren la práctica, o quiere decir que todavía lo duda? Gracias.
aafulei
@fleix No veo por qué es tan importante si personalmente me resulta más fácil creer que funcionará std::dequetan bien como std::vectoren aplicaciones prácticas. Pero por lo que vale, mi experiencia personal es que necesito estructuras de datos de pila y cola no para una tarea grande y de complejidad crucial, sino para muchas pequeñas ocasiones distribuidas en mi código. Como tal, me preocupo más por el comportamiento en los pequeños que en los grandes; y deque brilla particularmente apagado allí. Mi preferencia es no usar ninguna de las dos, sino listas de enlaces individuales (autoimplementadas). Pero su kilometraje puede variar.
Marc van Leeuwen
12

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

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

James Hopkin
fuente
2
Priority_queue en realidad no usa push / pop_front, y las operaciones de montón invalidan las referencias a elementos además del primero. Por lo tanto, no se aplicaría ninguno de los beneficios de deque, a diferencia del caso de una cola normal.
Potatoswatter
9
Además, priority_queuedebe permanecer ordenado, por lo que la mayor sobrecarga de acceso aleatorio deque::iteratores más problemática.
Potatoswatter
1
@Potatoswatter: priority_queuetiene un "orden mágico" que se mantiene, no está ordenado. Sin embargo, su punto se mantiene.
Mooing Duck