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

i have list of 10 items. sort them in particular manner.

for eg. items a1, b, c1, a2, a3, f, g, c2, h, a4

rules are

• c should come before a
• b should come after a
• all other item should preserve order.

so after sorting list should in order c1 c2 a1 a2 a3 f g h a4 b

i trying use c++ std::stable_sort() method achieve this. in program items instance of structure 'sitem' got member 'type' idicate category(a, b etc). comparison function looks this

bool compareitems(sitem const& item1, sitem const& item2)  {     if (item1.type == && item2.type == c)         return false;      if (item1.type == b && item2.type == a)         return false;      return true; } 

from understanding of stable_sort, requires comparison function follow 'strict weak ordering'. method doesn't follow that, cannot use stable_sort. sorting algorithm available achieve 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 == && 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; } 

this not sort

at least not std library defines sorts.

you want move elements around.

4 steps:

• find first a. want shove cs.

• stable partition c right before first a.

• find last a. want shove bs.

• stable partition bs right after last a.

all cs before first remain stationary. bs after last remain stationary.

cs keep relative order. bs keep relative order. both move least possible generate guarantee require.

everything isn't c or b keeps relative order.

code:

template<class it, class isa, class isb, class isc> void do_it(it s, f, isa a, isb b, isc c){   auto first_a = std::find_if(s,f,a);   first_a = std::stable_partition(first_a,f,c);   auto last_a = std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(first_a), a).base();   std::stable_partition(s,last_a, [&b](auto&&x){return !b(x);}); } 

live example.

with enough spare memory, above o(n).

of course, done in 1 line:

std::stable_partition(s,std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(std::stable_partition(std::find_if(s,f,a),f,c)), a).base(), [&b](auto&&x){return !b(x);}); 

but wouldn't recommend it.