result of std::sort does not fit the compare relation

Question

I'm having trouble with std::sort.

I have a bunch data and have implemented a bool contains(const Pocket2D& other); method so sort the data a .. b .. c so that a contains b and b contains c etc. This method uses other libraries and yields some constraints and posting ist might not help. So I wrote a unittest to test it properly but I disagree with the result of std::sort. My sorting call:

std::sort(
    result.begin(), result.end(), []( const auto& p1, const auto& p2 )
    {
        return std::get<0>( p1 ).contains( std::get<0>( p2 ) );
    } );

The (wrong) result is :

03.stp 33.stp 32.stp 25.stp 26.stp 27.stp 28.stp 29.stp 30.stp 31.stp 24.stp 04.stp 05.stp 06.stp 07.stp 08.stp 09.stp 17.stp 01.stp 10.stp 11.stp 12.stp 13.stp 14.stp 15.stp 16.stp 00.stp 18.stp 19.stp 02.stp 20.stp 21.stp 22.stp 23.stp

(10 should be before 26/27 and not after)

So I figured the contains method is faulty. BUT then I printed the whole contains relation inside the unittest and it looks right (I left out all contours that do not contain any other contour):

for ( auto& outerPocketTuple : result )
{
    for ( const auto innerPocketTuple : result )
    {
        if ( std::get<0>( outerPocketTuple ).contains( std::get<0>( innerPocketTuple ) ) )
        {
            std::get<2>( outerPocketTuple ).push_back( std::get<1>( innerPocketTuple ) );
        }
    }
}

for ( const auto& r : result )
{
    of << std::get<1>( r ) << ": ";
    for ( const auto& ri : std::get<2>( r ) )
    {
        of << ri << " ";
    }
    of << std::endl;
}

10.stp: 26.stp 27.stp 
03.stp: 00.stp 01.stp 10.stp 11.stp 12.stp 13.stp 
        14.stp 15.stp 16.stp 17.stp 18.stp 19.stp 
        02.stp 20.stp 21.stp 22.stp 23.stp 24.stp 
        25.stp 26.stp 27.stp 28.stp 29.stp 
        30.stp 31.stp 32.stp 33.stp 
        04.stp 05.stp 06.stp 07.stp 08.stp 09.stp 
32.stp: 02.stp 
33.stp: 00.stp 01.stp 10.stp 11.stp 12.stp 13.stp 
        14.stp 15.stp 16.stp 17.stp 18.stp 19.stp 
        02.stp 20.stp 21.stp 22.stp 23.stp 24.stp 
        25.stp 26.stp 27.stp 28.stp 29.stp 
        32.stp 
        04.stp 05.stp 06.stp 07.stp 08.stp 09.stp

I'm very sorry to post data instead of code but the code is extremely use case specific.

My problem ist that the Comparator looks right but the result doesn't.

Here is my minimal example. The lambda contains pretty much does the same as the original culprit.

std::vector<size_t> test_data;
for ( size_t i = 0; i < 34; i++ )
{
    test_data.push_back( i );
}

auto contains = []( const size_t a, const size_t b )
{
    if ( a == b )
    {
        return false;
    }
    if ( a == 3 )
    {
        return true;
    }
    if ( a == 33 && b != 30 && b != 31 && b != 3 )
    {
        return true;
    }
    if ( a == 10 && ( b == 26 || b == 27 ) )
    {
        return true;
    }
    if ( a == 32 && b == 2 )
    {
        return true;
    }
    return false;
};
std::random_shuffle( test_data.begin(), test_data.end() );
std::sort( test_data.begin(), test_data.end(), contains );
for ( const auto i : test_data )
{
    std::cout << i << std::endl;
}
for ( auto t = test_data.begin(); t < test_data.end(); t++ )
{
    for ( auto i = t; i < test_data.end(); i++ )
    {
        if ( contains( *i, *t ) )
        {
            std::cout << "Error " << *i << " contains " << *t << 
            std::endl;
        }
    }
}

A result may be: 3 33 32 18 8 5 21 7 12 14 20 27 6 10 1 30 9 13 4 25 23 0 2 19 22 31 26 29 17 16 24 15 11 28

Error 10 contains 27

But I need to have 3 at top, 33 above all but (30, 31), 32 above 02 and 10 above (26, 27)

Answer 1

The relation is faulty in a strange way:

The documentation of Compare states:

If equiv(a,b)==true and equiv(b,c)==true, then equiv(a,c)==true but

equiv(32, 29) == true
equiv(29, 02) == true
equiv(32, 02) == false

So I do need topological ordering.