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

Viewed 2075

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;
}
5 Answers
Related