如何利用索引向量实现std::vector的原地元素重排？

需求说明 #

我们需要将目标向量example按照索引向量order指定的规则重排，最终效果等价于拷贝版本的逻辑：output[i] = example[order[i]]，要求实现原地修改，不额外拷贝整个向量内存。

拷贝版本的示例代码如下：

// 拷贝版本实现
#include <vector>
#include <cstdint>

int main(){
   std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
   std::vector<uint32_t> example = {0,1,2,3,4,5,6,7,8,9,10,11};
   std::vector<uint32_t> output(order.size());
   for(uint32_t i = 0; i < order.size(); ++i){
       output[i] = example[order[i]];
   }
   // output结果为 {0,2,5,6,9,10,1,3,4,7,8,11}
}

现有方案的问题 #

直接使用常规的原地置换代码会得到错误结果，示例代码及错误输出如下：

// 错误的原地重排实现
#include <vector>
#include <cstdint>
#include <algorithm>

void reorder(std::vector<uint32_t> &v, std::vector<uint32_t> const &order )  {   
    for ( int s = 1, d; s < order.size(); ++ s ) {
        for ( d = order[s]; d < s; d = order[d] ) ;
        if ( d == s ) while ( d = order[d], d != s ) std::swap( v[s], v[d] );
    }
}

int main(){
    std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
    std::vector<uint32_t> example = {0,1,2,3,4,5,6,7,8,9,10,11};
    reorder(example, order);
    // example错误结果为 {0,6,1,7,8,2,3,9,10,4,5,11}
}

该方案的核心问题是：它实现的是将元素v[i]移动到order[i]的位置，与我们需要的“将v[order[i]]移动到i位置”的逻辑完全相反。

正确的原地实现方案 #

我们需要针对置换循环进行处理，确保每个元素被移动到正确的位置，同时避免覆盖未处理的原始值。以下提供两种实现方案：

方案1：允许修改order向量（O(1)额外空间） #

利用order向量本身标记已处理的位置，无需额外内存：

#include <vector>
#include <cstdint>
#include <utility> // 用于std::move

template <typename T>
void reorder_in_place(std::vector<T>& v, std::vector<uint32_t>& order) {
    const size_t n = v.size();
    for (size_t i = 0; i < n; ++i) {
        // 已处理的位置会被标记为order[i] == i，直接跳过
        if (order[i] == i) {
            continue;
        }
        // 保存循环起始位置的原始值
        T temp = std::move(v[i]);
        size_t current = i;
        // 遍历当前置换循环，直到回到起始位置
        while (order[current] != i) {
            const size_t next_idx = order[current];
            // 将下一个位置的原始值移到当前位置
            v[current] = std::move(v[next_idx]);
            // 标记当前位置已处理
            order[current] = current;
            current = next_idx;
        }
        // 将起始位置的原始值放到循环的最终位置
        v[current] = std::move(temp);
        // 标记最终位置已处理
        order[current] = current;
    }
}

// 测试示例
int main() {
    std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
    std::vector<uint32_t> example = {0,1,2,3,4,5,6,7,8,9,10,11};
    reorder_in_place(example, order);
    // example结果为 {0,2,5,6,9,10,1,3,4,7,8,11}，符合需求
}

方案2：不允许修改order向量（O(n)额外空间） #

使用一个visited数组标记已处理的位置，保持order向量不变：

#include <vector>
#include <cstdint>
#include <utility>

template <typename T>
void reorder_in_place(std::vector<T>& v, const std::vector<uint32_t>& order) {
    const size_t n = v.size();
    std::vector<bool> visited(n, false);
    
    for (size_t i = 0; i < n; ++i) {
        if (visited[i]) {
            continue;
        }
        // 保存循环起始位置的原始值
        T temp = std::move(v[i]);
        size_t current = i;
        // 遍历当前置换循环
        while (!visited[current]) {
            visited[current] = true;
            const size_t next_idx = order[current];
            // 若下一个位置已访问，说明到达循环终点，放置初始值
            if (visited[next_idx]) {
                v[current] = std::move(temp);
                break;
            }
            // 将下一个位置的原始值移到当前位置
            v[current] = std::move(v[next_idx]);
            current = next_idx;
        }
    }
}

// 测试示例
int main() {
    std::vector<uint32_t> order = {0,2,5,6,9,10,1,3,4,7,8,11};
    std::vector<uint32_t> example = {300,12,21,34,47,15,61,57,82,94,1,2};
    reorder_in_place(example, order);
    // example结果为 {300,21,15,61,94,1,12,34,47,57,82,2}，符合需求
}

方案特性 #

• 时间复杂度：O(n)，每个元素最多被移动一次，每个位置仅被访问一次。
• 空间复杂度：方案1为O(1)（复用order向量做标记）；方案2为O(n)（需要visited数组）。
• 通用性：采用模板设计，支持任意类型的example向量，满足约束中“order与example可存储不同数据类型”的要求。

内容的提问来源于stack exchange，提问作者Sam Moldenha