Sorting a list with a comparison function that doesn't follow 'strict weak ordering'

Question

I have a list of 10 items. I would like sort them in a particular manner.

For eg. the items are A1, B, C1, A2, A3, F, G, C2, H, A4

Rules are

• C should always come before A
• B should always come after A
• All the other item should preserve their order.

So after sorting the list should be in this order C1 C2 A1 A2 A3 F G H A4 B

I am trying to use C++ std::stable_sort() method to achieve this. In my program all the items are instance of a structure 'SItem' which got a member 'type' to idicate its category(A, B etc). My comparison function looks like this

bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == A && item2.type == C)
        return false;

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}

From my understanding of stable_sort, it requires the comparison function to follow 'strict weak ordering'. Obviously my method doesn't follow that, so I cannot use the stable_sort. Is their sorting algorithm available to achieve this type of orders?

Complete code

#include <list>
#include <algorithm>
#include <iostream>

enum ItemType
{
    A, B, C, D, E, F, G, H,
};

struct SItem
{
    SItem(ItemType t, int i) {
        type = t;
        index = i;
    }

    ItemType type;
    int index;
};

//do not follow strict week ordering
bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == A && item2.type == C)
        return false;

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}


int main()
{
    std::list<SItem> lstItems = { {A, 1}, {B, 1}, {C, 1}, {A, 2}, {A, 3}, {F, 1}, {G, 1}, {C, 2}, {H, 1}, {A, 4} };
    std::stable_sort(lstItems.begin(), lstItems.end(), CompareItems);

    return 0;
}

Answer 1

It is not a strict weak ordering, but it is a partial ordering. An algorithm for sorting by a partial ordering is called a topological sort, like this naive implementation:

template <typename Iterator, typename Compare>
void stable_toposort(Iterator begin, Iterator end, Compare cmp)
{
    while (begin != end)
    {
        auto const new_begin = std::stable_partition(begin, end, [&](auto const& a)
        {
            return std::none_of(begin, end, [&](auto const& b) { return cmp(b, a); });
        });
        assert(new_begin != begin && "not a partial ordering");
        begin = new_begin;
    }
}

It partitions the sequence so that all the elements that are not greater than any other element are moved to the front. Then it takes all the remaining elements and partitions them in the same way, until there remain no more elements to be partitioned. Its complexity is O(n²) comparisons and O(n) swaps.

Then we need to fix the bug in the comparison function:

bool CompareItems(SItem const& item1, SItem const& item2)
{
    if (item1.type == C && item2.type == A) return true;
    if (item1.type == A && item2.type == B) return true;
    return false;
}

Live demo

For reference, an unstable version would use partition instead of stable_partition.