0

I am using the method explained here How to obtain the index permutation after the sorting in order to find the index permutation that sorts the elements of an array.

Strangely enough, I get segmentation faults in some cases. Tracing back the problem, I found out that the std::sort tries to call the comparator with indices outside the valid range. I am sure that always before calling the std::sort, the index array is filled with correct indices (i.e. 0 to data.size()-1).

It might be interesting to note that in my case, data has always a length of 32 and I realize that the comparator is called with first argument 145 (and the second is always something in range of 0 to 31).

Any idea why this could happen?

Here is the code:

class compare {
      private:        
         const double* list;
      public:
         compare(const double* d): list(d) {}
         bool operator()(const size_t& a, const size_t& b) {
               // indeed I observe that this function gets called with a = 145 and b in 
               // the range of 0 to 31

              return (list[a] < list[b]);
         }
  };

std::vector<double> data(32);
std::vector<size_t> idx(32);

compare cmp(&data[0]);
size_t i;

// populate the data array ... for example:
for (i = 0; i < 32; i++)
    data[i] = 1.0 * (rand() % 100) / 50; 

for (i = 0; i < 32; i++)
  idx[i] = i;
std::sort(idx.begin(), idx.end(), cmp);
Community
  • 1
  • 1
MikeL
  • 2,369
  • 2
  • 24
  • 38
  • 1
    Please post a test case to demonstrate the problem. We can't guess what your code is doing. – Mike Seymour Aug 28 '14 at 12:39
  • Sorry. I posted the code :-) – MikeL Aug 28 '14 at 12:56
  • How should I proceed for "reopening" the question? – MikeL Aug 28 '14 at 13:01
  • Did you try compile your code ? What is idx(i) = i ? Here is your example: http://rextester.com/YUD93206 – grisha Aug 28 '14 at 13:07
  • Your code doesn't compile. When I fix the obvious errors and print the values of `a` and `b`, it works correctly (at least as far as all values are in range). Please post a compilable test case that demonstrates the problem. – Mike Seymour Aug 28 '14 at 13:07
  • Well. I then need to post the whole code that I use for populating the array `data` which is too much. Maybe I should mention that the values in `data` are random values. Does that change anything? (I guess it should not) – MikeL Aug 28 '14 at 13:13
  • 1
    @PBM: Why not just write a single line of code to directly populate it with whatever values you have in there? If they're all regular floating-point values, then it shouldn't change anything. If they're not (i.e. if some are NaN), you'll get undefined behaviour since there's no strict order. But even then, I'd be surprised if it caused out-of-range accesses. – Mike Seymour Aug 28 '14 at 13:17
  • 1
    Are you sure that you do not change the size of `data` after taking the address of the first element, passing it to the comparator? Because if you do, the vector might grow internally, making the original pointer invalid. – oxygene Aug 28 '14 at 13:31
  • Did you observe the out-of-bounds value 145 for `a` by printing the value or just by using a debugger/IDE with optimized code, maybe even post-mortem? – oxygene Aug 28 '14 at 13:40
  • @MikeSeymour They are all floating point values. Even I tried this with integer instead of double (i.e. by rounding up the numbers, ...). There is no `NaN`, ... – MikeL Aug 28 '14 at 14:29
  • @oxygene I observe those values by just printing the arguments of `operator()` inside the function. I even don't know how to use the debugger/IDE tools :-) – MikeL Aug 28 '14 at 14:30
  • @oxygene By the way, I'm sure that I don't change the size of `data`. As a double check I just made another test by printing `data.size()` before calling the `sort` and it is always `32`. If I changed the size, then I guess other calls of `operator()` must have caused Segmentation Fault (for example even with `a=1` and `b=4`). But surprisingly it only happens when it is called with an out-of-range index. – MikeL Aug 28 '14 at 14:33
  • @PBM: Without a test case that actually demonstrates the problem, there's no way to guess what might be wrong with the code you're not showing us. Please post a complete (but minimal) test case that demonstrates the problem. – Mike Seymour Aug 28 '14 at 14:36
  • @MikeSeymour Ok. I will update the code with the simplest case. – MikeL Aug 29 '14 at 08:01
  • 1
    It still doesn't compile: no `#include`, code outside a function, etc. – Marc Glisse Aug 29 '14 at 08:13
  • @PBM: That doesn't compile. When I fix the errors, it gives no output, so doesn't demonstrate the problem. When I add `std::cout << a << ' ' << b << '\n';` to the comparator, all the printed indexes are in range. Sorry to keep repeating myself, but please post a complete (but minimal) test case that demonstrates the problem. Without that, this question simply can't be answered. – Mike Seymour Aug 29 '14 at 11:17
  • @MikeSeymour Actually I was observing the error using exactly the code I posted above (well with obvious `cout` line added as you did). Surprisingly enough, I just had to close the terminal in which I was running the code and reopen it and after that I don't see the problem. I really don't understand what's happening! Both the main code and even this example are working fine since a few hours ago. – MikeL Aug 29 '14 at 13:03

1 Answers1

3

I can't reproduce what you observe. Here is a cleaned version of your code which seems to work fine (gcc and clang).

#include <vector>
#include <algorithm>
#include <stdexcept>

#include <cstdlib>
#include <cstdio>

#define LSIZE 32

// ------------------------------------------------------------------------

class compare 
{
private:        
    const double* ptr;

public:

    compare(): ptr(0) {}
    compare( const double* d ): ptr(d) {}

    bool operator()( size_t a, size_t b ) 
    {
        if ( ptr == 0 ) throw std::runtime_error("Null pointer to data.");
        if ( a >= LSIZE || b >= LSIZE ) throw std::out_of_range("Index out of range.");

        // Uncomment to show the comparisons:
        // printf( "Comparing data[%lu] (%.2f) and data[%lu] (%.2f)\n", 
        //      a, ptr[a], b, ptr[b] );

        return ptr[a] < ptr[b];
    }
};

// ------------------------------------------------------------------------

int main()
{
    std::vector<double> data(LSIZE);
    std::vector<size_t> idx(LSIZE);

    for ( unsigned i=0; i<LSIZE; ++i )
    {
        idx[i]  = i;
        data[i] = 1.0 * (rand() % 100) / 50; 
    }

    std::sort( idx.begin(), idx.end(), compare( data.data() ) );
}
Jonathan H
  • 7,591
  • 5
  • 47
  • 80