1

I have written the following function for partially doing stable sort over vector of arrays. When the size of vector is small like 1G it always work, when the size of vector is large (5 or 6 Gig) sometimes it works, sometimes it throws segmentation fault, could someone help me figure out the resean for this.

template <typename T, size_t SIZE>
void sort(std::vector<std::array<T, SIZE>>& vec, size_t depth = SIZE) {
        std::sort(vec.begin(), vec.end(),
                  [&](const auto& t1, const auto& t2)->bool {
                        for(size_t s = 0; s < depth; s++) {
                                if(t1[s] == t2[s]) {
                                        continue;
                                }
                                return t1[s] < t2[s];
                        }
                        return true;
                  });
}

I use g++ 10.2 and these are the switches, I compile the code with -DNDEBUG -march=native -msse3 -ftree-vectorize -O3.

AMCoded
  • 1,374
  • 2
  • 24
  • 39

1 Answers1

5

std::sort requires that the comparison function be a "strict weak ordering", which requires:

it is irreflexive: for all x, r(x, x) is false;

Your comparison function does not meet this requirement, because, as Mark Ransom pointed out in the comments, you return true when t1 == t2. Your comparison is basically <= rather than a <, and you need to be <.

The easiest fix is to use std::lexicographical_compare:

template <typename T, size_t SIZE>
void sort(std::vector<std::array<T, SIZE>>& vec, size_t depth = SIZE) {
        std::sort(vec.begin(), vec.end(),
                  [depth](const auto& t1, const auto& t2)->bool {
                        return std::lexicographical_compare(t1.begin(), t1.begin() + depth,
                                                            t2.begin(), t2.begin() + depth);
                  });
}

For completeness, note that if you didn't care about the depth, you could sort directly, because std::array comes with a built-in operator< that compares lexicographically.

Justin
  • 24,288
  • 12
  • 92
  • 142
  • That's a great observation. Do you happen to know why that requirement exists? – Mark Ransom May 16 '21 at 04:23
  • 2
    @MarkRansom I didn't off the top of my head, but [this answer](https://stackoverflow.com/a/48975345/1896169) seems to have a pretty good explanation – Justin May 16 '21 at 04:25
  • @MarkRansom, I think this because otherwise `sort` would need two separate functions to sort, "less than" (as usual) and in addition equality. – alfC May 16 '21 at 04:28
  • @alfC there's generally no need to test for equality in a sort. A naive expectation would be that testing for `<=` instead of `<` would just lead to indeterminate ordering of items with equal keys, not a complete crash. – Mark Ransom May 16 '21 at 04:32
  • @MarkRansom. Agree, that is the point, paraphrasing: there's generally no need to test for equality in a sort if the ordering is *strict*. – alfC May 16 '21 at 04:34