c++ - 如何使用 std::sort 按特定顺序对字符串进行排序

Question

我在我的一个项目中遇到过这种情况，我需要根据给定字符的顺序对字符串进行排序。

所以理想情况下，这是我的要求。

假设我的初始字母顺序为 b、B、A、a、d、c、C、D、T、t。

我有 3 个字符串 "Bat" , "bat" , "atb" . 排序后的数组应该是"bat" , "Bat" , "atb"作为b < B < a基于上面给定的顺序。

所以我正在考虑使用 std::sort C++ 的。

但我不确定这整个想法。如果思路没问题，可以用什么数据结构来存储字母表的初始顺序，排序的比较函数怎么写。

sort(arr, arr + 3, compare);

bool compare(string a, string b)
{
    /*how to proceed here?
}

有没有比使用 std::sort 更有效的其他方法？ ？

任何想法都会有所帮助。

Answer 1

自定义比较器和 std::sort应该足以满足您的需求。比较器的重要部分是确保它遵循严格的弱排序。该排序的属性之一是:

Given a and b, if (!(a < b || b < a)) is true, then a and b must be equivalent.

将自定义比较器构建为仿函数非常简单，是存储字母表的好地方。为了避免字符串扫描，即使具有排序的 logN 效率，也可以使用包含数字排序顺序等价的自定义字母表。这将非常快，特别适合大型字符串比较，因为每个字符查找都是常数时间。

自定义比较器示例如下:

#include <iostream>
#include <algorithm>
#include <string>
#include <climits>

struct CustomAlphaCmp
{
    int table[1 << CHAR_BIT];
    CustomAlphaCmp(const std::string& alpha)
    {
        std::fill(std::begin(table), std::end(table), INT_MAX);
        int value = 0;
        for (auto x : alpha)
            table[ static_cast<unsigned char>(x) ] = ++value;
    }

    bool operator()(const std::string& a, const std::string& b)
    {
        auto lhs = a.begin();
        auto rhs = b.begin();

        for (; lhs != a.end() && rhs != b.end(); ++lhs,++rhs)
        {
            int lhs_val = table[static_cast<unsigned char>(*lhs)];
            int rhs_val = table[static_cast<unsigned char>(*rhs)];

            if (lhs_val != rhs_val)
                return lhs_val < rhs_val;
        }

        return (rhs != b.end());
    }
};

int main()
{
    std::string alpha = "bBAadcCDTt";
    std::string ar[] = { "Bat", "bat", "X", "atb", "bBb", "bbb", "B",
                         "bat", "aaa", "Y", "Cat", "CaT", "Bat", "A" };

    std::sort(std::begin(ar), std::end(ar), CustomAlphaCmp(alpha));

    for (auto const& s : ar)
        std::cout << s << '\n';
}

输出

bbb
bBb
bat
bat
B
Bat
Bat
A
aaa
atb
CaT
Cat
Y
X

工作原理

比较器对象由自定义字母构成，以通过所有可能的 char 初始化表索引使用字母表位置作为表中“值”的值。所有非字母字符的值都是 INT_MAX给他们“最弱”的可能订单值(value)，并将它们全部视为等同的。

完成后，比较器将移交给排序算法。当比较两个字符串时，它们将被遍历直到遇到不匹配的值或一个/两个字符串到达​​终止。那时要么弦同时完成，左边先“完成”，要么右边先完成。我们知道到那时所有的字符都是相等的。因此，如果左侧先于右侧完成，那么左侧才是真正“小于”右侧。如果它们相同或右侧先完成(无关紧要)，则左侧不能更少。因此我们可以简单地返回右侧是否到达终点作为最终答案。

此特定比较器忽略所有非字母字符，因此任何字母字符将小于任何非字母字符，并且所有非字母字符被视为等于。如果这还不能满足您的需求，则可能需要进行一些调整。

最后，比较器的准备时间是固定的填充成本加上字母表长度的 O(n)。如果您对许多排序操作使用相同的字母表，请提前准备比较器并将其发送到 std::sort可能是有理由的。同样，可能需要根据您的需要进行一些调整。

无论如何，祝你好运。