fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cassert>
  4. #include <vector>
  5. #include <string>
  6.  
  7. template <typename Iterator, typename Compare>
  8. void stable_toposort(Iterator begin, Iterator end, Compare cmp)
  9. {
  10.     while (begin != end)
  11.     {
  12.         auto const new_begin = std::stable_partition(begin, end, [&](auto const& a)
  13.         {
  14.             return std::none_of(begin, end, [&](auto const& b) { return cmp(b, a); });
  15.         });
  16.         assert(new_begin != begin && "not a partial ordering");
  17.         begin = new_begin;
  18.     }
  19. }
  20.  
  21. bool CompareItems(std::string const& item1, std::string const& item2)
  22. {
  23.     if (item1[0] == 'C' && item2[0] == 'A') return true;
  24.     if (item1[0] == 'A' && item2[0] == 'B') return true;
  25.     return false;
  26. }
  27.  
  28. int main()
  29. {
  30. 	std::vector<std::string> v = { "A1", "B", "C1", "A2", "A3", "F", "G", "C2", "H", "A4" };
  31. 	stable_toposort(v.begin(), v.end(), CompareItems);
  32. 	for (auto const& s : v)
  33. 	{
  34. 		std::cout << s << " ";
  35. 	}
  36. 	std::cout << "\n";
  37. }
  38.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
C1 F G C2 H A1 A2 A3 A4 B
https://ideone.com/Tp5Ywc
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!