如何使用另一个向量来订购一个向量？

Question

这个问题与here提出的问题类似，但是，这个答案不适用于我的问题，并且略有不同。

我想要做的最好在代码中显示：

//this would be a copy version:
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 comes out to {0,2,5,6,9,10,1,3,4,7,8,11}

但是，当我尝试使用上面链接中的重新排序代码实现就地版本时：

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

如何在不复制内存的情况下实现我想要完成的任务的就地版本？

编辑

我想让事情更清楚，代码中的向量

example

可以是任意元素，我只是碰巧按照我所做的方式初始化它们以便于检查它们。这是完全有效的：

std::vector<uint32_t> example = {300,12,21,34,47,15,61,57,82,94,1,2};

• order

  和

  example

  将始终包含相同数量的元素
• 不保证

  order

  和

  example

  存储相同的数据类型
• 还保证

  order

  存储唯一值
• 还保证

  order

  将始终是数据类型

  uint32_t

• order

  始终在 0 到

  n-1

  的范围内，其中

  n

  是

  example

  的大小，每个数字恰好一次，没有任何超出该范围的值。 （就像示例代码中那样）
• 该范围的实际顺序完全是随机的，与以任何顺序出现的偶数或奇数索引无关。

Answer 1

算法是这样的：

order

是包含排序顺序的 N 个数字的列表。每个项目都有一个从 0..N-1.

的唯一值

items

是任何类型的向量。

因此我们循环 - 交换

order

内的值，直到完美排序。每次我们交换

order

中的一个值时，我们都会交换

items

中的一对值。

void reorder(std::vector<size_t>& order, std::vector<uint32_t>& items) {
    bool didSwap = true;
    int passes = 0;
    while (didSwap) {
        didSwap = false;
        for (size_t i = 0; i < items.size(); i++) {
            size_t target = order[i];
            if (target != i) {
                std::swap(order[i], order[target]);
                std::swap(items[i], items[target]);
                didSwap = true;
            }
        }
    }
}

使用您自己的数组的示例

int main() {
    std::vector<size_t> order =     { 11,2,4, 5,6,3, 8,7,9, 10,0,1};
    std::vector<uint32_t> example = { 300,12,21,34,47,15,61,57,82,94,1,2 };

    reorder(order, example);

    // show the final sort order as applied
    for (size_t i = 0; i < example.size(); i++) {
        std::cout << example[i] << " ";
    }
    std::cout << std::endl;

}

以上打印：

1 2 12 15 21 34 47 57 61 82 94 300

我相信该算法在平均情况下运行时间为 O(N lg N)...检查...