CODEWITHSUNDEEP
c++sortingstd
MikeL
MikeL

Reputation: 2459

Why `std::sort` tries to compare values that are not in the input list?

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);

Upvotes: 0

Views: 188

Answers (1)

Jonathan H
Jonathan H

Reputation: 7943

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() ) );
}

Upvotes: 3

Related Questions