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;
}