¿Qué estructuras de datos C ++ simples debería aprender para la programación competitiva además de un mapa?

Si está utilizando C ++ para la programación competitiva, entonces el almacenamiento en caché es una consideración principal al considerar el rendimiento. Como tal, std :: vector debería estar entre las primeras estructuras de datos más importantes que debe conocer.

Incluso iría un paso más allá e incluso diría que debe conocer los entresijos de cualquier implementación de std :: vector que esté utilizando para la programación competitiva. Esto puede darle respuestas rápidas a preguntas como:

• ¿Con qué frecuencia tendré que reasignar esta estructura de datos?
• ¿Debo molestarme en reservar una talla en la construcción?
• ¿Mi tamaño de datos bloqueará mi estructura de datos debido a una falla de asignación para ese tamaño de datos?

std :: vector es potente, eficiente y simple, pero sus defectos son sutiles y matizados. Obtener un buen uso del vector puede aumentar drásticamente el rendimiento hasta 1 o 2 escalas de magnitud al mejorar el almacenamiento en caché en los bucles cerrados correctos.

¿Todos ellos?

En serio, ¿qué te hace pensar que toda tu “competencia” dejó de aprender después de este o aquel elemento específico del lenguaje?

Eres como un chico que pregunta “Quiero hacer carreras de autos, ¿es lo suficientemente bueno como para saber acerca de los engranajes 1 y 2”? Err, lo siento: es mejor que conozca todas las partes esenciales de esa herramienta con la que pretende “competir”. No solo todos los engranajes, sino también cómo funciona la dirección, cómo se usan los descansos, cómo puedes usar el cludge / breaks juntos, … millones de cosas que componen un piloto de carrera,

Probablemente sea imposible para las “personas comunes” alcanzar el 100% de conocimiento de todas las cosas que uno podría saber sobre C ++. Pero su intento de decir “hmm, qué 5% son los que me darán una ventaja” son básicamente inútiles. Porque para ser realmente competitivo, nada por debajo dice que el 90% lo haría.

Vector se usa en gran medida y también puedes aprender a configurar.