Значения обмена и индексы вектора

Question

У меня есть std::vector<int> с непрерывными перетасованными значениями от 0 до N и вы можете как можно более эффективно менять каждое значение с его положением в векторе.

Пример:

v[6] = 3; 

становится

v[3] = 6; 

Это простая проблема, но я не знаю, как справиться с этим для того, чтобы сделать это тривиально и, прежде всего, очень быстро. Большое спасибо за ваши предложения.

Answer 1

Учитывая N во время компиляции и учитывая массив содержит каждый индекс в [0,N) ровно один раз, это относительно прямой (до тех пор, как он не должен быть на месте, как уже упоминалось в предыдущих комментариях):

Постройте новый массив так, чтобы v'[n] = find_index(v, n) назначил его старой.

Здесь я использовал VARIADIC шаблоны с std::index_sequence, чтобы свернуть его в одно назначение:

template<typename T, std::size_t N> 
std::size_t find_index(const std::array<T,N>& arr, std::size_t index) { 
    return static_cast<std::size_t>(std::distance(arr.begin(), std::find(arr.begin(), arr.end(), index))); 
} 

template<typename T, std::size_t N, std::size_t... Index> 
void swap_index_value(std::array<T,N>& arr, std::index_sequence<Index...> seq){ 
    arr = { find_index(arr, Index)... }; 
} 

template<typename Integer, std::size_t N> 
void swap_index_value(std::array<Integer,N>& arr) { 
    swap_index_value(arr, std::make_index_sequence<N>{}); 
} 

Сложность это не выглядит большим, хотя. Вызов find_index(arr, n) для каждого n в [0,N) будет выполнять общее количество сравнений N * (N + 1)/2 (std::sort будет принимать только N * log (N)).

Однако, поскольку мы знаем, что каждый индекс присутствует в массиве, мы могли бы просто заполнить массив индексов , когда мы пройдем по исходному массиву и предположим, что T является интегральным типом, мы можем пропустить некоторый std :: size_t < -> T преобразования, тоже:

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

    arr = indices; 
} 

мы все еще используем два раза пространство и делать некоторые случайно заказанные пишет наш массив, , но по существу мы до 2 * N заданий, а код проще, чем раньше.

С другой стороны, мы могли бы также std::sort если сохранить копию, чтобы сделать поиски в:

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

Первая версия here, второй версии here, станд :: сортировать версия here

бенчмаркинг, который один быстрее, как упражнение для читателя;)