Segmentation fault when applying std::sort to a vector of vectors of integers

Question

I am writing a struct for sorting generic data types allowing for multiple values of the same in each object to be sorted (e.g. sorting a vector of vectors of integers). The code below is a simplified example of the code I've written, with an example using ints and the inner vectors sized to 2.

// Sort object
template <class te_DataType, int te_mValue>
struct Sort_Data
{
  std::size_t iData;
  std::array<te_DataType, te_mValue> Values;
};

// Sorting struct
template <class te_DataType, int te_mValue>
struct Sorter
{
  // List of sorting objects
  std::vector<Sort_Data<te_DataType, te_mValue> > SortDataList;

  // Constructor/Destructor
  Sorter(const size_t mdata) : SortDataList(mdata) {}
  ~Sorter() = default;

  // Method to sort the objects in SortDataList
  inline void DataSort()
  {
    std::sort(SortDataList.begin(), SortDataList.end(),
              [](const Sort_Data<te_DataType, te_mValue>& a, const Sort_Data<te_DataType, te_mValue>& b) -> bool
              {
                for(int ivalue = 0; ivalue < te_mValue; ivalue++)
                  if(a.Values[ivalue] >= b.Values[ivalue]) continue;
                  else return true;
                return false;
              });
  }
};

When I randomly initialise the entries in the vector of vectors of ints (sized to 1e3), I get segmentation fault (core dumped) when I call the DataSort() method. I have run my code through Valgrind as well, and while it definitely picks up errors, I cannot make sense of them. Can anyone give me some advice on this?

std::random_device randDevi;
std::mt19937 randomEngine(randDevi());
std::uniform_int_distribution<int> randGenerInt(0, 1e7);

// Load randomised data
int mData = 1e3;
Sorter<int, 2> sorter(mData);
for(int idata = 0; idata < mData; ++idata)
{
  sorter.SortDataList[idata].iData = idata;
  for(int ii = 0; ii < 2; ++ii) sorter.SortDataList[idata].Values[ii] = randGenerInt(randomEngine);
}

sorter.DataSort(); // Segmentation fault occurs here

EDIT: I've just tested it out, and it seems the following comparator conforms to strict weak ordering:

[](const Sort_Data<te_DataType, te_mValue>& a, const Sort_Data<te_DataType, te_mValue>& b) -> bool
{
  for(int value = 0; value < te_mValue; ivalue++)
    if(a.Values[ivalue] > b.Values[ivalue]) return false;
    else if(a.Values[ivalue] == b.Values[ivalue]) continue;
    else return true;
  return false;
});

Thank you to those who pointed out the strict weak ordering requirement :)

What is `FORDO`? If it is just a simple `for` loop, my crystal ball tells that your comparator does not induce a strict weak order. — j6t, Sep 27 '21 at 11:58
@j6t Sorry, it's a macro I'd defined for a for loop. Can you recommend how I can modify the comparator to achieve strict weak order? — niran90, Sep 27 '21 at 12:00
Your ordering is not a [strict weak ordering](https://en.cppreference.com/w/cpp/concepts/strict_weak_order), so sorting has undefined behaviour. (As an example, you have both `{1,2} < {2,1}` and `{2,1} < {1,2}`, which is not permitted.) — molbdnilo, Sep 27 '21 at 12:01
@molbdnilo Okay, I see. I wasn't completely familiar with the strict weak ordering rule. Thanks for pointing this out :) — niran90, Sep 27 '21 at 12:04
@niran90 -- Also, you shouldn't code up randomly generated data against a buggy program, unless you are trying to detect which data causes the crash (as in [this answer](https://stackoverflow.com/questions/63046559/code-submission-on-spoj-gives-runtime-error-sigabrt/63048464#63048464)), and then rerunning your program with the data that causes the crash. Always test against *known* data that causes the problems, not random data where the data changes every time you run the program. Once you fix the problem with the known data, *then* you introduce random data. — PaulMcKenzie, Sep 27 '21 at 12:41
@PaulMcKenzie Alternatively, use pseudo-random but deterministic data, such as a pseudo-random number generator with a known seed. — Stef, Sep 27 '21 at 12:51
This doesn't address the question, but `for(int ivalue = 0; ivalue < te_mValue; ivalue++) if(a.Values[ivalue] >= b.Values[ivalue]) continue; else return true;` can be written much more clearly by reversing the condition: `for(int ivalue = 0; ivalue < te_mValue; ivalue++) if(a.Values[ivalue] < b.Values[ivalue]) return true;` — Pete Becker, Sep 27 '21 at 14:28

Segmentation fault when applying std::sort to a vector of vectors of integers

0 Answers0