Hay muchas estructuras de datos para las cuales la implementación de STL no está fácilmente disponible.
Considere los gráficos, por ejemplo. Por lo general, no puede utilizar bibliotecas como Boost, Lemon, etc. para algoritmos relacionados con gráficos. Debe codificarlo y los detalles de implementación pueden variar según el problema. Por lo general, se implementa como una matriz de vectores.
Considere el ejemplo de los árboles de segmentos que se utiliza para una variedad de consultas de rango. Necesita codificar eso usted mismo. Lo mismo ocurre con otra hermosa estructura de datos llamada Fenwick tree o Binary Indexed Trees (BIT).
- ¿Cuál es el mejor algoritmo de programación que hayas creado?
- ¿Cómo hace un algoritmo para hacer objetos en movimiento a partir de fotos?
- ¿Necesito tener el conocimiento de las estructuras de datos y el algoritmo, antes de comenzar a practicar en spoj, codchef, topcoder, etc.? Sé un poco de C ++.
- ¿Cómo se implementan las tablas hash en el kernel de Linux? ¿Cómo funcionan para diferentes tipos de datos y estructuras?
- ¿Qué es un algoritmo? ¿Es simplemente una máquina de Turing? Si no, ¿qué es?
¿Has oído hablar de estructuras de datos relacionadas con cadenas? Trie, árboles de sufijos, autómata de sufijos, matriz de sufijos, árbol palindrómico, autómata Aho Corasick? Todos los usan mucho los programadores competitivos.
Hay casos en los que necesita una versión modificada de árboles de búsqueda binarios balanceados. La implementación del árbol rojo negro lleva demasiado tiempo. Se utiliza el tratamiento que no está disponible en la biblioteca estándar. Hay otro estrechamente asociado con él y se llama treap implícito, que puede considerarse como una versión dinámica de la matriz que permite la inserción en el medio. Había leído que GNU C ++ tiene algo llamado estructuras de datos basadas en políticas que incluyen una implementación de árboles de despliegue.
Luego viene la geometría computacional, que es una pesadilla para muchos programadores competitivos. Tienes que codificarlos por tu cuenta.
Entonces la respuesta a su pregunta es sí. Debería poder codificar muchas estructuras de datos y algoritmos, ajustarlos según la especificación del problema. Pero no te preocupes. En ACM ICPC puede llevar material impreso (aunque limitado).
