c++ - 交换 vector 的值和索引

Question

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

例子:

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;
}

我们仍然使用两倍的空间并对我们的数组进行一些随机排序的写入，但本质上我们减少了 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

哪个更快的基准测试留给读者作为练习；)