El algoritmo de rotación unidireccional de gcc libstdc++ para iteradores de acceso aleatorio resulta ser, contra toda expectativa, el mismo que el algoritmo clásico empleado con iteradores forward. Así lo explica el blog técnico The Old New Thing en una nueva entrega, donde compara ambos procedimientos paso a paso sobre un ejemplo concreto formado por los bloques A1, A2, A3 y B1, B2, B3, B4, B5.
En la demostración, los punteros first y mid avanzan de forma sincronizada intercambiando las posiciones que apuntan. Cuando first alcanza el final del bloque A original, el algoritmo antiguo (el de iteradores forward) recurre para intercambiar A1, A2, A3 con B4 y B5. El algoritmo nuevo de gcc libstdc++, en cambio, continúa simplemente intercambiando first con mid a cada paso, lo que también logra colocar A1 en la posición de B4 y A2 en la de B5. El resultado final es idéntico en ambos casos: B1, B2, B3, B4, B5, A3, A1, A2.
El autor subraya que, aunque los algoritmos no son idénticos en su mecánica interna, la similitud es notable. El algoritmo nuevo es simétrico: realiza sus intercambios de derecha a izquierda cuando el bloque de mayor tamaño se encuentra a la derecha. El antiguo, por el contrario, siempre opera de izquierda a derecha. En esencia, se trata del mismo algoritmo visto desde dos perspectivas distintas, lo que describe como la emoción de descubrir que dos cosas son en realidad la misma cosa, solo que con etiquetas diferentes.
La entrada forma parte de una serie sobre algoritmos de rotación en la biblioteca estándar de C++. En la próxima entrega se analizará cómo clang implementa la rotación descomponiendo la operación en ciclos. El artículo recuerda además que distintas bibliotecas estándar pueden resolver un mismo problema con algoritmos superficialmente diferentes pero estructuralmente equivalentes.