c++ - 使用不遵循 'strict weak ordering' 的比较函数对列表进行排序

Question

我有一个包含 10 个项目的列表。我想以特定方式对它们进行排序。

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

规则是

• C 应该总是在 A 之前
• B 应该总是在 A 之后
• 所有其他项目应保持其顺序。

所以排序后列表应该是这样的顺序C1 C2 A1 A2 A3 F G H A4 B

我正在尝试使用 C++ std::stable_sort() 方法来实现这一点。在我的程序中，所有项目都是结构“SItem”的实例，它有一个成员“type”来指示其类别(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。这是我们要推 B 的地方。

• 稳定地将 B 划分到最后一个 A 之后。

第一个 A 之前的所有 C 都保持静止。最后一个 A 之后的所有 B 都保持静止。

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

Live example .

有足够的空闲内存，上面是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);});

但我不推荐它。