使用不遵循"严格弱排序"的比较函数对列表进行排序

Question

我有10个项目的清单.我想以特定的方式对它们进行排序.

例如.项目是A1,B,C1,A2,A3,F,G,C2,H,A4

规则是

• C应该总是在A之前
• B应该总是在A之后
• 所有其他项目应保留其订单.

所以排序后的列表应按此顺序C1 C2 A1 A2 A3 FGH A4 B.

我正在尝试使用C++ std::stable_sort()方法来实现这一目标.在我的程序中,所有项目都是结构"SItem"的实例,它有一个成员"类型"来表示其类别(A,B等).我的比较函数看起来像这样

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

根据我的理解stable_sort,它要求比较函数遵循'严格弱排序'.显然我的方法不遵循,所以我不能使用stable_sort.他们的排序算法是否可用于实现此类订单？

完整的代码

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

Answer 1

这不是一种

至少不是因为std库定义了它的种类.

你只想移动一些元素.

4个步骤:

• 找到第一个A.这是我们想要推动Cs的地方.

• 稳定分区所有C都在第一个A之前.

• 找到最后的A.这是我们想要推动Bs的地方.

• 在最后一个A之后将Bs稳定分区.

第一个A之前的所有Cs保持静止.最后一个A之后的所有Bs保持静止.

Cs保持相对顺序.Bs保持相对顺序.两者都移动最少,以产生您需要的保证.

所有不是C或B的东西都保持相对的顺序.

码:

template<class It, class IsA, class IsB, class IsC>
void do_it(It s, It 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);});
}

实例.

有足够的备用内存,以上是O(n).

当然,这可以简单地在一行中完成:

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

但我不推荐它.

Answer 2

它不是严格的弱排序，而是偏序。按偏序排序的算法称为拓扑排序，就像这个简单的实现：

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

它对序列进行分区，以便将不大于任何其他元素的所有元素移到前面。然后将所有剩余的元素以相同的方式进行分区，直到没有更多的元素需要进行分区。它的复杂度是 O(n²) 次比较和 O(n) 次交换。

然后我们需要修复比较函数中的bug：

bool CompareItems(SItem const& item1, SItem const& item2)
{
    if (item1.type == C && item2.type == A) return true;
    if (item1.type == A && item2.type == B) return true;
    return false;
}

现场演示

作为参考，一个不稳定的版本将使用partition代替stable_partition。