2

I'm coding in C++ (with c++11 standards) and I have two big arrays of built-in type that I want to sort the second one based on the first. here is an example:

A = {1, 5, 4, 3, 6, 2};
B = {1, 2, 3, 4, 5, 6};

after sorting: 

A = {1, 2, 3, 4, 5, 6};
B = {1, 6, 4, 3, 2, 5};

It's as if each element B[i] is attached to element A[i] and you just sort array A. So elements in B move according the corresponding element in A. I know this questions has been asked over and over, yet the only solution I've come across with is to use pair<type 1, type 2>. But considering the arrays are big, it takes quite a while to allocate the memory for pairs array and copy arrays back and forth. But I believe the sorting can be done in-place, i.e., using only O(1) memory. In fact if std::sort allowed for costume swap it would have been fine. Because I assume that's the only thing beyond comparator that sorting algorithms use. 

A = vector<double>(1e6);  // some random numbers
B = vector<double>(1e6);  // some random numbers
Comp comp(&A,&B);
Swap swap(&A,&B);
costume_sort(A,B,comp,swap);   // some sort function that can take costume swap and compare

class Comp {
   vector<double> *A;
   vector<double> *B;
   Comp(vector<double> *A, vector<double> *B) : A(A),B(B) {};

   bool compareTo(size_t i, size_t j) { return A->at(i) < A->at(j); };
};


class Swap {
   vector<double> *A;
   vector<double> *B;
   Swap(vector<double> *A, vector<double> *B) : A(A),B(B) {};

   void swapFnc(size_t i, size_t j) { swap(A->at(i), A->at(j));swap(B->at(i), B->at(j)); };
};

Is there any function in STL or other libraries available that can do that? This is a sort of pseudo-code of the idea I'm trying to explain here. Obviously it's not precise but I hope it's clear what I mean.

Tacet
  • 1,411
  • 2
  • 17
  • 32
Ameer Jewdaki
  • 1,758
  • 4
  • 21
  • 36
  • @LeFlou I've provided an example in the updated question. It's like you sort A and every element of B is attached to the corresponding element in A. (element `i` in B is attached to element `i` in A) – Ameer Jewdaki Nov 27 '15 at 15:16
  • Do you really want both vectors to be `double`? Or one `double` and one `std::size_t`? – SirGuy Nov 27 '15 at 15:20
  • @GuyGreer well in fact right now I'm dealing with one `double` one `uint64_t` . But I hoped I can ignore the fact that one is integer and write the code in a more generic way. But if there's a neat solution just for integers I'm happy to know that as well. – Ameer Jewdaki Nov 27 '15 at 15:22
  • 1
    Take a look at http://stackoverflow.com/a/32720638/1566221 which uses a reference implementatíon of a proposed addition to the standard library. – rici Nov 27 '15 at 15:32
  • Consider one table of [std::pair](http://en.cppreference.com/w/cpp/utility/pair), or maybe better [std::tupple](http://en.cppreference.com/w/cpp/utility/tuple). – Tacet Nov 27 '15 at 15:52

3 Answers3

0

You can sort based on indices similar to the related post: std::sort and custom swap function.

It is not a custom swap function and allocateds some more memory, but should perform well.

If you are defining the types, then you can overload std::swap to do what you want: How to overload std::swap().

Community
  • 1
  • 1
Igor Ševo
  • 5,459
  • 3
  • 35
  • 80
  • This seems to be a link based answer, could you explain in your words how to apply the information in those links to this question in a little more detail? – Glenn Teitelbaum Nov 27 '15 at 15:16
  • Ut nag' melieer nad `std::sort` ut menik na'g. Funk kan `std::sort` nei 'ek lut `std::swap` merk. Overload mik ut melieit `std::swap` nak din klas, ut menik nag' mirk talut. – Igor Ševo Nov 27 '15 at 15:46
0

No there is not an std:: function that meets your requirements.

Although it's possible to provide its custom comparison (so Q&A) and swap (so Q&A) functor, those take a (constant) reference to the items to compare or swap, not an index on an hypothetical container. Indeed those functors should have meaning for comparisons and swaps of non-contained objects.

Community
  • 1
  • 1
YSC
  • 38,212
  • 9
  • 96
  • 149
0

Example of reorder a[] and b[] in place according to a sorted array of pointers to a[]. Since an array of pointers is used, the compare function only needs to know the type of elements being compared. The reorder in place code time complexity is O(n), every store places a value in its sorted location. Note that the array of pointers is restored to it's original state (&a[0] ... &a[n-1]) during the reorder.

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

int main()
{
int a[8] = {7,5,0,6,4,2,3,1};
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[] and b[] according to the array of pointers to a[]
    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;
}
rcgldr
  • 27,407
  • 3
  • 36
  • 61