使用标准库基于一个数组对两个数组进行排序（避免复制步骤） [英] Sorting two arrays based on one with standard library (copy steps avoided)

问题描述

我有旧代码要维护，我要替换一个自定义的QuickSort，它使用std :: sort对基于数组1的两个数组进行排序。有没有一种方法可以基于其中一个对两个数组进行排序，而无需执行额外的拆分步骤并且无需再次实现排序功能？以下是当前示例，vector1D基本上是std :: vector。

I have old code to maintain and I was replacing a custom QuickSort which was sorting two arrays based on array one with std::sort. Is there a way to sort two arrays based one one of them without an additional split step and without implementing a sorting function again? Below is the current example vector1D is basically std::vector.

    vector1D<std::pair<int64_t, uint8_t>> m_RowCol(m_NX * m_NY * m_NZ);
    //..
    std::sort(
        m_RowCol.begin(),
        m_RowCol.end(),
        [](const std::pair<int64_t, uint8_t> &a, const std::pair<int64_t, uint8_t> &b) { return a.first < b.first && (a.first > 0 && b.first > 0); }
    );
    // copy into two vectors
    vector1D<int64_t> m_Row;
    vector1D<uint8_t> m_Col;
    for (auto it = std::make_move_iterator(m_RowCol.begin()), end = std::make_move_iterator(m_RowCol.end()); it != end; ++it)
    {
        m_Row.push_back(std::move(it->first));
        m_Col.push_back(std::move(it->second));
    }
    m_RowCol.clear(); 

推荐答案

您可以创建索引数组，对索引进行排序根据其中一个数组，然后根据O（n）时间中排序的索引数组对两个数组和索引数组重新排序：

You can create an array of indices, sort the indices according to one of the arrays, then reorder the two arrays and array of indices in place according to the sorted array of indices in O(n) time:

#include <algorithm>
#include <iostream>

int main()
{
int A[8] = {8,6,1,7,5,3,4,2};
char B[8] = {'h','f','a','g','e','c','d','b'};
size_t I[8];
size_t i, j, k;
int ta;
char tb;
    // create array of indices to A[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        I[i] = i;
    // sort array of indices to A[]
    std::sort(I, I+sizeof(I)/sizeof(I[0]),
              [&A](int i, int j) {return A[i] < A[j];});
    // reorder A[] B[] I[] according to I[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != I[i]){
            ta = A[i];
            tb = B[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                B[k] = B[j];
                I[k] = k;
                k = j;
            }
            A[k] = ta;
            B[k] = tb;
            I[k] = k;
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        std::cout << A[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(B)/sizeof(B[0]); i++)
        std::cout << B[i] << ' ';
    std::cout << std::endl;
    return 0;
}

或可以使用指针数组代替索引数组，

or an array of pointers can be used instead of an array of indices, which allows a normal compare function instead of a lambda compare function.

#include <algorithm>
#include <iostream>

bool compare(const int *p0, const int *p1)
{
    return *p0 < *p1;
}

int main()
{
int A[8] = {8,6,1,7,5,3,4,2};
char B[8] = {'h','f','a','g','e','c','d','b'};
int *pA[8];
size_t i, j, k;
int ta;
char tb;
    // create array of pointers to A[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        pA[i] = &A[i];
    // sort array of pointers to A[]
    std::sort(pA, pA+sizeof(A)/sizeof(A[0]), compare);
    // reorder A[] B[] pA[] according to pA[]
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){
        if(i != pA[i]-A){
            ta = A[i];
            tb = B[i];
            k = i;
            while(i != (j = pA[k]-A)){
                A[k] = A[j];
                B[k] = B[j];
                pA[k] = &A[k];
                k = j;
            }
            A[k] = ta;
            B[k] = tb;
            pA[k] = &A[k];
        }
    }
    for(i = 0; i < sizeof(A)/sizeof(A[0]); i++)
        std::cout << A[i] << ' ';
    std::cout << std::endl;
    for(i = 0; i < sizeof(B)/sizeof(B[0]); i++)
        std::cout << B[i] << ' ';
    std::cout << std::endl;
    return 0;
}

这篇关于使用标准库基于一个数组对两个数组进行排序（避免复制步骤）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！