1

How can I find, inside compare function, the position of m1 and m2 relative to m array? Example:

         0 1 2 3 4 5
m array: - - - - - -
           ^     ^
           m1    m2

output: 1 and 4

It's important to avoid using extra memory, like for example have an extra argument in Mir struct (int pos). Also slow solutions are not welcome, like find() etc.. Keep also in mind that m array will be constantly shuffled (not sure if this is important). basically I need a fast and low memory usage solution. This must be simple.. The code:

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

struct Mir { int a,b; };
Mir *m;

bool cmp(Mir &m1, Mir &m2){
    if(m1.b > m2.b){
        // Find position of m1 and m2 relative to m array. How ???;
        return true;    
    }
    return false;
}

int main(){
    int n, k;
    scanf("%d %d", &n, &k);

    m = (Mir *) malloc(n * sizeof(Mir));

    for(int i = 0; i < n; i++)
        scanf("%d %d", &m[i].a, &m[i].b);

    std::sort(m, m+k, cmp);
}

Thanks.

Emil Laine
  • 41,598
  • 9
  • 101
  • 157
Ricardo Gomes
  • 41
  • 3
  • As an aside: [Do I cast the result of malloc?](http://stackoverflow.com/q/605845/3425536). Also, standard C++ [has no headers called `stdio.h` and `stdlib.h`](http://stackoverflow.com/q/13889467/3425536), you probably meant `cstdio` and `cstdlib`. – Emil Laine Oct 12 '15 at 00:39
  • Why? A compare function should compare results whether they're in the same array/container or not. However, since `m` is a global variable, you can use `&m1 - m` and `&m2 - m` to get the index within the allocated `m` array. That will give horribly wrong results if `m1` or `m2` are not within that array, though, so your `cmp` function could only work for the specific `m` array. – 1201ProgramAlarm Oct 12 '15 at 01:26
  • A potential issue is that the parameter passed by std::sort to the compare function could be referencing a temp variable instead of an element of the array (like pivot value, rotation of a sub-array if it goes into insertion sort or heap sort mode, ... ). In the case of std::stable_sort, a temp array / vector is used, which would be an issue. A workaround would be to create an array of pointers to the m array, and sort the array of pointers, but this takes up memory space. – rcgldr Oct 12 '15 at 05:52
  • &m1 - m and &m2 - m don't work because like you said they could be referencing some temp variable.. I must register the changes of sort into an history container. Is there a way to sort with std::sort and store the changes (positions) of it? – Ricardo Gomes Oct 12 '15 at 09:50

0 Answers0