Foro de elhacker.net

Buenas a todos,estaba comenzando a ver las especificaciones que tienen los contenedores estandar en c++ tales como deque,queue,stacks y me tope con que el autor menciona incialmente como esta implementado el contenedor deque en c++,mencionando que realmente no seria una implementación del todo adecuada a un estructura 'deque' debido a que en el fondo contiene un vector map que permite la interfaz de una pila doble. A partir de lo anterior menciona que el contenenedor 'stack' es realmente un contenedor que puede tener en su interior otro contenedor como list,queue o vector y que realmente stack lo único que proporciona es una interfaz que simula una pila pero que realmente tiene otro contenedor dentro de el. Finalmente menciona que el contenedor 'queue' realmente contiene un contenedor 'deque' con el cual finalmente interactua para proporcionar un contenedor que se comporte como una cola.

Con respecto a lo anterior me surge la incognita de si esto succede en la mayoria de los lenguajes, realmente no logro visualizar que tan buena pueda ser la desicion de componer a los contenedores de esta forma pero me crea la duda debido a que anteriormente yo visualizaba a estas clases como la tipica lista ligada o vector que interactuaba como una cola con un cierto numero de nodos,etc. Mas que poner en duda sobre la buena/mala implementacion de dichos contenedores me gustaria simplemente saber que tan habitual o comun es toparte con lenguajes que tengan una implementacion parecida.

El lenguaje especifica los "requerimientos" de cada uno; interfaces y grados de complejidad de las operaciones; no mucho más. Después cada compilador lo implementa como más le gusta.


No sé qué libro estás leyendo, pero esa es una afirmación equivocada. Se debe estar refiriendo a alguna estructura conceptual más o menos común, pero si es o no "adecuada" depende solamente de si cumple o no con los requerimientos del estándar, interfaz y grados de complejidad.

Muchas gracias por tu respuesta, solo para complementar menciono que la información que menciono fue recolectada del libro "TADs, Estructuras de datos y resolucion de problemas con C++" 2da. Version del autor Larry R. Nyhoff. De antemano agradeceria si alguien conoce un mejor libro de estructuras de datos enfocado en el lenguaje de c++ de preferencia.

Lo que creo que está errada es la afirmación valorativa (eso de ser "adecuada a una estructura deque") aplicada a una hipotética implementación común de la std::deque en los compiladores de C++.

No sé si el libro de Nyhoff es buena fuente, de lo que estoy seguro es que tu pregunta contiene preconceptos que no pueden darse por válidos.

Por ejemplo, la idea de Deque (double-ended queue) es que se trata de una lista lineal donde las inserciones y eliminaciones (y en general cualquier tipo de acceso) se hacen en los extremos.

No creo que haya que decir mucho más que eso para saber que estamos hablando de una Deque y no de otra cosa. Es una idea general.


Por otro lado, la std::deque es un "sequence container" definido por el estándar C++. Y cada compilador implementa su propia versión de la std::deque de acuerdo con los requerimientos del estándar.

Ahora, ¿cómo puede decirse que una cierta implementación de std::deque es o no "del todo adecuada a una estructura Deque" ?

Mira, a riesgo de pasarme de pelma: Todos tenemos más o menos una idea común sobre qué es un Plumero. Pero decir que la Norma Industrial del Canadá no define adecuadamente las especificaciones de los plumeros porque la fábrica Plumita los elabora con un palo más corto de lo que me gustaría, es llevar las cosas demasiado lejos.

Ok, gracias. Creo que mi error es pensar en la estructuras de datos de la forma en las que yo las he implementado dejando a un lado que no importa su implementacion si no que presente una interfaz o metodos que le permitan comportarse como una pila , una cola,etc.