¿Qué es mejor: una lista enlazada de codificación o el uso de libs de plantillas estándar?

Creo que la biblioteca estándar de C ++ todavía no incluye una lista intrusiva. La densidad de datos es súper importante en ciertas cargas de trabajo; en esos casos, es probable que no desee pagar por un puntero hacia atrás y casi seguro que no quiera pagar una asignación de montón adicional para el frob que probablemente tenga solo tres punteros, uno hacia adelante, uno hacia atrás y uno al artículo

Las colecciones intrusivas están en desacuerdo con la pureza que obtienes de la mayoría de las colecciones (esto también es cierto en los mundos .net, C ++ y Java), que son los patrones de diseño que la comunidad moderna de C ++ se esfuerza por seguir, por lo que la mayoría no son intrusivos colecciones para que la noción de un objeto y su contenedor sean principios ortogonales. Probablemente sea un buen diseño, pero todos estos buenos elementos de diseño tienen costos de rendimiento y almacenamiento. (Esto podría comenzar una guerra, pero lo que pasa con la mentalidad de “evitar la optimización prematura” es que básicamente apuesta a que la característica no será exitosa o importante porque sabe con certeza que si es exitosa e importante, su rendimiento será debajo de una lupa.)

Con todo lo dicho, olvida las listas; es realmente difícil superar una matriz (std :: vector es suficiente) por densidad y rendimiento a menos que vaya a agregar / eliminar a / desde el medio de la lista. Sigo teniendo la intención de hacer un análisis de tiempo, pero sospecho firmemente que las matrices de punteros ganarían tanto las listas intrusivas como las no intrusivas hasta una rodilla interesante en la curva de rendimiento. (Desafortunadamente, una lista de punteros en bruto está fuera de moda ya que tiene una gestión de vida ambigua, por lo que, para encajar, ¿quizás tenga una lista de instancias std :: shared_ptr ? Pero ahora está gravando el objeto con la sobrecarga shared_ptr. Esto a menudo no importa. Hasta que lo haga, mucho).

std :: vector vs. arrays son un lavado. A menos que sea una matriz de tamaño fijo incrustada en una estructura / clase que contiene, creo que es difícil, especialmente en los tiempos modernos con referencias de valor, etc., señalar cualquier motivo para seguir con las matrices. Pero parece inclinado a hacer lo contrario y no veo ninguna razón masiva para cambiar de matrices a std :: vector si no necesita todas las posibilidades de std :: vector.

AlgoritmosEstructuras de datosListas vinculadasProgramación informática

Cómo enmarcar mi idea de algoritmo para que alguien que escribe algoritmos pueda entenderlo

¿Qué debo usar para reducir los atributos en mi conjunto de datos, PCA o algoritmos de selección de características?

¿Cuál es el significado de 'orden de crecimiento' en el análisis de algoritmos y cómo podemos encontrar el orden de crecimiento de un algoritmo dado?

¿Cuánto conocimiento de implementación de algoritmos usan realmente los programadores experimentados?

¿Cuáles son los componentes básicos del reconocimiento de voz desde el punto de vista DSP?

¿Cuáles son los datos más valiosos cuando un usuario aleatorio de Internet usa su sitio web?

Por lo general, en la práctica, desea codificar una estructura de datos para la que ya tiene una implementación lista para usar, si la hay:
– Necesita funcionalidad adicional en la parte superior si no lo proporciona la implementación lista para usar. Para el ejemplo de Lista, por ejemplo, es posible que desee implementar Swap (pointerToFirstElement, pointerToSecondElement) que para una lista vinculada puede hacer en O (1). O tal vez quiera volver a unir dos listas vinculadas en O (1). Además, solo para comparar y ArrayList <> de C # con una Lista de enlaces dobles, tenga en cuenta que no hay una sola mejor opción. ¡ArrayList no se puede unir con una nueva en O (1), pero se puede buscar binariamente, por ejemplo (porque permite el acceso aleatorio a sus elementos)!
– Necesita un mejor rendimiento que el proporcionado por la implementación lista para usar. Para el ejemplo de Map, puede implementar eso usando un árbol AVL, una HashTable (de tamaño variable o no) o incluso una estructura de datos Van-Emde-Boss. Dependiendo de su conjunto de datos y operaciones que va a necesitar, es posible que deba elegir uno u otro. Además de elegir la estructura de datos en sí, debe asegurarse de que su implementación inmediata sea la que cree que es. strstr (), por ejemplo, no se utiliza el algoritmo de coincidencia de cadena óptimo (posiblemente KMP) para algunas versiones de C ++.
– Debe conectar un comportamiento adicional o diferente y la implementación lista para usar no es lo suficientemente extensible. Para el ejemplo de Lista, es posible que desee que se escriban / recuperen todos los elementos de un archivo o una base de datos para garantizar la confiabilidad. Es posible que desee admitir transacciones en la estructura de datos que pueden requerir profundizar en la implementación. Lo mismo ocurre con una ArrayList <> que quizás desee utilizar para almacenar demasiados elementos para que quepan en la memoria.
– La implementación lista para usar depende mucho de la arquitectura del sistema, depende de componentes no confiables o indeseables o su uso conlleva ciertos derechos de autor u otros problemas de no codificación. El mejor ejemplo aquí es usar CyrptoAPI en C #. Realiza cifrado / descifrado moderno, pero lo hace mediante llamadas a funciones de Windows. Dado que posiblemente esto rompa la seguridad para aquellos que no tienen confianza en la implementación (tal vez cambiante en el futuro) de Windows, esto es un factor decisivo.

Sergiu Chereches

Tiene sentido implementar algo que ya está implementado, solo con el propósito educativo. En producción, solo tiene que saber cuál de los algoritmos / estructuras usar para satisfacer mejor sus necesidades, en términos de eficiencia. Ya está allí, solo recójalo del estante, no reinvente la rueda. Es una gran pérdida de tiempo si lo implementa desde cero. Además, difícilmente hará que funcione mejor que el existente, ya usado muchas veces y bien probado.

Es bueno conocer aspectos internos, cómo funcionan las estructuras internamente, para que pueda decidir cuándo y cuál usar. La mayoría de las veces, más de una estructura puede hacer el trabajo. Cuál funcionará mejor es solo cuestión de eficiencia. Algunas estructuras implementan algoritmos más inteligentes y más eficientes, que otras, para ese problema particular que está tratando de resolver. Eso es todo al respecto.

Espero que esto ayude, gracias por a2a.

Scott Berry

std :: list es una lista doblemente vinculada, por lo que funcionará para cualquier cosa que pueda usar una lista individualmente vinculada (pero utilizará un puntero adicional para cada elemento).

std :: forward_list es una lista vinculada individualmente.

¿Por qué tienes que implementarlos? Me gana, porque no me lo has dicho. ¿Tu profesor lo requiere?

Una razón por la que podrían hacerlo es que podrían no ser conscientes de lo que hay ahí fuera. Otra razón es que podrían querer informarle sobre los beneficios y las desventajas de los diferentes tipos de almacenamiento. Por ejemplo, los mapas son muy diferentes de las listas (las listas tienen un orden pero los mapas no, tienen diferentes requisitos de almacenamiento y tiempos de acceso, y deben usarse para diferentes propósitos).

Scott Berry

Un nodo dentro de una lista vinculada simple está usando solo un puntero para realizar un seguimiento del siguiente nodo, por lo que sería algo así como:

Ahora. Una std :: list se representa como una lista con doble enlace.

La diferencia entre ellos es que std :: list usa un puntero adicional en cada nodo de la lista para que pueda iterar la lista en ambos sentidos, mientras que en las listas vinculadas no puede hacer eso.