std::sort of std::vector produces illegal elements-CodePudding

I have an application in which std::sort sometimes causes a core dump. I was able to isolate the problem to the following MWE:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

class DF {
  public:
    DF() = default;

    std::vector<int> row_mapping;
    std::vector<int> idx = {0, 1};
    std::vector<std::vector<int>> vals = {
        {0,  0,  0,  0,  1,  1,  1,  1,  2,  2,  2,  2,  3,  3,  3,  3,
         4,  4,  4,  4,  5,  5,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,
         8,  8,  8,  8,  9,  9,  9,  9,  10, 10, 10, 10, 11, 11, 11, 11,
         12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14},

        {2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017,
         2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016,
         2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015,
         2016, 2017, 2021, 2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021,
         2015, 2016, 2017, 2021, 2015, 2016, 2017, 2021, 2014, 2015, 2016,
         2017, 2021, 2015, 2016, 2017, 2021}};

    void sort(void) {
        int n = vals[0].size();
        std::cerr << "n = " << n << std::endl;

        row_mapping.resize(n);
        std::iota(begin(row_mapping), end(row_mapping), 0);

        std::cerr << "row map:";
        for (auto v : row_mapping) std::cerr << " " << v;
        std::cerr << std::endl;

        std::sort(
            begin(row_mapping), end(row_mapping), [&](int i1, int i2) -> bool {
                std::cerr << "cmp " << i1 << " " << i2 << std::endl;
                for (auto gi : idx) {
                    if (vals[gi][i1] < vals[gi][i2]) return true;
                }
                return false;
            });
    }
};

int main() {
    DF df;
    df.sort();
}

After compiling with g using g -std=c 17 mwe.cpp and running it, I get:

(output abbreviated)

n = 61
row map: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
cmp 1 30
cmp 30 60
(...)
cmp 52 257
(...)
cmp 59 55
cmp 60 56
double free or corruption (out)
Aborted (core dumped)

This is very weird, because I sort a vector containing the values 0 to 60 (including), which are indices into a more complex data structure. But the compare lambda is called with a value of 257.

I guess this must be because some array bounds are exceeded, or because there are references to data that does no longer exist. But I can't see the problem in the code!

CodePudding user response：

Indeed that was the problem.

With the following corrected lamda, everything works:

 std::sort(
            begin(row_mapping), end(row_mapping), [&](int i1, int i2) -> bool {
                std::cerr << "cmp " << i1 << " " << i2 << std::endl;
                for (auto gi : idx) {
                    if (vals[gi][i1] < vals[gi][i2]) return true;
                    if (vals[gi][i1] > vals[gi][i2]) return false;
                }
                return false;
            });

CodePudding user response：

Your comparison operation doesn't define a strict weak ordering.

        for (int i1 = 0; i1 < vals[0].size();   i1)
        {
            for (int i2 = 1; i2 < vals[0].size();   i2)
            {
                if (!(cmp(i1, i2) ^ cmp(i2, i1)))
                {
                    std::cerr << "incongruent comparison between " << i1 << " and " << i2 << '\n';
                    assert(0);
                }
            }
        }

Output:

incongruent comparison between 0 and 52