#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
#include <string>

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

bool CompareItems(std::string const& item1, std::string const& item2)
{
    if (item1[0] == 'C' && item2[0] == 'A') return true;
    if (item1[0] == 'A' && item2[0] == 'B') return true;
    return false;
}

int main()
{
	std::vector<std::string> v = { "A1", "B", "C1", "A2", "A3", "F", "G", "C2", "H", "A4" };
	stable_toposort(v.begin(), v.end(), CompareItems);
	for (auto const& s : v)
	{
		std::cout << s << " ";
	}
	std::cout << "\n";
}