交换向量的值和索引

Question

我有一个 std::vector<int> 具有从 0 到 N 的连续打乱值，我想尽可能高效地交换每个值及其在向量中的位置。

示例：

v[6] = 3;

变成

v[3] = 6;

这是一个简单的问题，但我不知道如何处理它才能让它变得微不足道，最重要的是，让它变得非常快。非常感谢您的建议。

Answer 1

在编译时给定 N 并且给定数组只包含 [0,N) 中的每个索引一次，它相对简单（只要它不必就地，如上面的评论中所述）：

构造一个新数组，使v'[n] = find_index(v, n)赋值给旧数组

在这里，我使用带有 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>{});
}

虽然这看起来并不复杂。为 [0,N) 中的每个 n 调用 find_index(arr, 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;
}

我们仍在使用 space 的两倍，并对我们的数组进行一些随机排序的写入，但本质上我们减少了 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, std::sort版本here

哪个更快的基准测试留给 reader ;)

作为练习

交换向量的值和索引

Swap values and indexes of a vector

c++

swap

vector