2010-05-03 23 views
9

Fondo rápido
Soy un desarrollador de Java que ha estado jugando con C++ en mi tiempo libre/aburrido.¿Por qué debería pop() tomar un argumento?

Prefacio
En C++, que suelen aparecer pop teniendo un argumento por referencia:

void pop(Item& removed); 

entiendo que es agradable para "rellenar" el parámetro con lo que haya extraído. Eso tiene mucho sentido para mí. De esta manera, la persona que solicitó eliminar el artículo superior puede echar un vistazo a lo que se eliminó.

Sin embargo, si tuviera que hacer esto en Java, que haría algo como esto:

Item pop() throws StackException; 

De esta manera, después del estallido volvemos ya sea: NULL como resultado, un artículo, o un se lanzaría una excepción.

Mi libro de texto C++ me muestra el ejemplo anterior, pero veo muchas implementaciones de pila sin argumentos (stl stack por ejemplo).

La pregunta
¿Cómo se debe implementar la función emergente en C++?

La bonificación
¿Por qué?

Respuesta

26

Para responder a la pregunta: no debe implementar la función pop en C++, ya que ya está implementada por el STL. El adaptador de contenedor proporciona el método top para obtener una referencia al elemento superior de la pila y el método pop para eliminar el elemento superior. Tenga en cuenta que el método pop por sí solo no se puede usar para realizar ambas acciones, como usted ha preguntado.

¿Por qué debería hacerse de esa manera?

  1. seguridad Excepción: Herb Sutter da una buena explicación del tema en GotW #82.
  2. Principio de responsabilidad única: también mencionado en GotW # 82. top se ocupa de una responsabilidad y pop se ocupa de la otra.
  3. No pague por lo que no necesita: Para algunos códigos, puede ser suficiente examinar el elemento superior y luego abrirlo, sin hacer una copia (potencialmente costosa) del elemento. (Esto se menciona en la documentación SGI STL.)

Cualquier código que desee obtener una copia del elemento puede hacer esto sin costo adicional:

Foo f(s.top()); 
s.pop(); 

Además, this discussion puede ser interesante.

Si iba a implementar pop para devolver el valor, no importa mucho si devuelve por valor o lo escribe en un parámetro de salida.La mayoría de los compiladores implementan RVO, lo que optimizará el método de retorno por valor para que sea tan eficiente como el método de copiado-fuera-parámetro. Solo tenga en cuenta que cualquiera de estos probablemente sea menos eficiente que examinar el objeto usando top() o front(), ya que en ese caso no se realiza ninguna copia.

+0

Enlaces impresionantes, muchas gracias. Entonces, si me preguntan en una entrevista para implementar pop() en C++ ... ¿debería darles su respuesta? : p – Stephano

+2

+ 1 ... pero tal vez "si implementa la función pop en C++, debe seguir la interfaz estándar del contenedor". – Potatoswatter

+1

@Stephano: Depende de lo que el entrevistador quiera. Algunos pueden estar seguros de que saben sobre 'std :: stack' y saben que tiene los métodos' push', 'top', y' pop'. Algunos pueden querer que implementes tu propia pila usando una matriz de longitud fija, solo para ver si puedes hacerlo. – Dan

4

El problema con el enfoque de Java es que su método pop() tiene al menos dos efectos: eliminar un elemento y devolver un elemento. Esto viola el principio de responsabilidad única del diseño de software, que a su vez abre la puerta a complejidades de diseño y otros problemas. También implica una penalización de rendimiento.

En el modo STL de las cosas, la idea es que a veces cuando pop() no está interesado en el elemento reventado. Solo desea el efecto de eliminar el elemento superior. Si la función devuelve el elemento y lo ignora, esa es una copia desperdiciada.

Si proporciona dos sobrecargas, una que toma una referencia y otra que no, entonces permite que el usuario elija si él (o ella) está interesado en el elemento devuelto o no. La ejecución de la llamada será óptima.

El STL no sobrecargar las funciones pop() sino que se divide en estas dos funciones: back() (o top() en el caso del adaptador std::stack) y pop(). La función back() simplemente devuelve el elemento, mientras que la función pop() simplemente lo elimina.

+1

'top' no' frontal' –

+1

y 'top' llamadas' atrás' – Potatoswatter

+4

Una función que tiene dos efectos como una sola operación atómica no viola el principio de responsabilidad única del diseño de software. –

0

La única razón que puedo ver por el uso de esta sintaxis en C++:

void pop(Item& removed); 

es si usted está preocupado acerca de las copias innecesarias que tienen lugar.

si devuelve el Item, se puede requieren una copia adicional del objeto, que puede ser costoso.

En realidad, los compiladores C++ son muy buenos en la elisión de copia, y casi siempre implementan la optimización del valor de retorno (a menudo incluso cuando compilas con optimizaciones desactivadas), lo que hace que el argumento sea irrelevante. "la versión se vuelve más rápida en algunos casos.

Pero si usted está en la optimización prematura (si está preocupado que el compilador no podría optimizar la copia de distancia, a pesar de que en la práctica se hacerlo), se podría argumentar a favor de "regresan" Parámetros asignando a un parámetro de referencia.

Más información here

0

OMI, una buena firma para el eqivalent de la función de Java pop en C++ sería algo así como:

boost::optional<Item> pop(); 

El uso de tipos de opción es la mejor manera de devolver algo que puede o puede no estar disponible.

1

El uso de C++ 0x hace que todo vuelva a ser difícil.

Como

stack.pop(item); // move top data to item without copying 

hace que sea posible mover de manera eficiente el elemento superior de la pila. Mientras que

item = stack.top(); // make a copy of the top element 
stack.pop(); // delete top element 

no permite tales optimizaciones.

+0

'item = std :: move (stack.top()); stack.pop(); 'funciona de manera eficiente sin embargo. Lo interesante a tener en cuenta es que la razón principal para este diseño en C++ 03 (seguridad de excepción) ya no es el caso en C++ 11 (porque los constructores de movimiento deberían ser no-throw). – Mankarse

Cuestiones relacionadas