Intercambiar valores e índices de un vector.

Tengo un std::vector con valores aleatorios contiguos de 0 a N y quiero intercambiar, tan eficientemente como sea posible, cada valor con su posición en el vector.

Ejemplo:

 v[6] = 3; 

se convierte en

 v[3] = 6; 

Este es un problema simple, pero no sé cómo manejarlo para hacerlo trivial y, sobre todo, muy rápido. Muchas gracias por sus sugerencias.

Dada N en el momento de la comstackción y dada la matriz contiene cada índice en [0,N) exactamente una vez, es relativamente sencillo (siempre que no tenga que estar en el lugar, como se menciona en los comentarios anteriores):

Construya una nueva matriz de modo que v'[n] = find_index(v, n) y asígnele la antigua.

Aquí utilicé varias plantillas con std::index_sequence para convertirlas en una sola tarea:

 template std::size_t find_index(const std::array& arr, std::size_t index) { return static_cast(std::distance(arr.begin(), std::find(arr.begin(), arr.end(), index))); } template void swap_index_value(std::array& arr, std::index_sequence seq){ arr = { find_index(arr, Index)... }; } template void swap_index_value(std::array& arr) { swap_index_value(arr, std::make_index_sequence{}); } 

La complejidad de esto es que no se ve muy bien. Llamar a find_index(arr, n) para cada n en [0,N) tomará N * (N + 1) / 2 de comparaciones totales ( std::sort solo tomaría N * log (N)).

Sin embargo, como sabemos que cada índice está presente en la matriz, podemos completar una matriz de índices a medida que avanzamos sobre la matriz original, y asumiendo que T es un tipo integral, podemos omitir algunas conversiones std :: size_t <-> T , también:

 template void swap_index_value(std::array& arr){ std::array indices; for (T i = 0; i < N; ++i) indices[arr[i]] = i; arr = indices; } 

Todavía estamos usando el doble de espacio y haciendo algunas escrituras ordenadas al azar en nuestra matriz, pero básicamente estamos en asignaciones de 2 * N, y el código es más simple que antes.

Alternativamente, también podríamos std::sort si mantenemos una copia para hacer búsquedas en:

 template void swap_index_value(std::array& arr){ std::sort(arr.begin(), arr.end(), [copy = arr](const T& lhs, const T& rhs) { return copy[lhs] < copy[rhs]; }); } 

Primera versión aquí , Segunda versión aquí , std :: Ordenar versión aquí

La evaluación comparativa de cuál es más rápido se deja como ejercicio para el lector;)