logo标签列表

不区分大小写地对字符串数组进行排序

c++stringsortingcase-insensitive
9

基本上，我必须使用选择排序来对string[]进行排序。我已经完成了这部分，但这是我遇到困难的地方。

然而，排序应该是不区分大小写的，因此"antenna"应该出现在"Jupiter"之前。 ASCII从大写字母排序到小写字母，所以有没有办法只交换排序后字符串的顺序呢？或者有更简单的解决方案吗？

void stringSort(string array[], int size) {
    int startScan, minIndex;
    string minValue;

    for(startScan = 0 ; startScan < (size - 1); startScan++) {
        minIndex = startScan;
        minValue = array[startScan];

        for (int index = startScan + 1; index < size; index++) {
            if (array[index] < minValue) {
                minValue = array[index];
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        array[startScan] = minValue;
    }
}
1
@Benny Saxeman 什么是字符串数组？ - Vlad from Moscow
@VladfromMoscow 抱歉，我的意思是字符串数组。 - bsem
@ElliottFrisch 这是一个类的赋值，所以不想惹麻烦。 - bsem
6个回答
9
C ++ 为您提供了 sort ，该函数使用比较函数。 在您的情况下，使用 vector<string> 比较两个字符串。 如果第一个参数更小，则比较函数应返回 true 。
对于我们的比较函数，我们希望在应用 tolower 后在 string 之间找到第一个不匹配的字符。 为此，我们可以使用 mismatch ，该函数接受两个字符之间的比较器，只要它们相等即返回 true ：
const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const unsigned char lhs, const unsigned char rhs){return tolower(lhs) == tolower(rhs);});

为了确定传递给 mismatch 的 lhs 是否小于 rhs，我们需要测试3件事：

  1. 这两个 string 的长度是否不同
  2. string lhs 是否更短
  3. 或者第一个不匹配的 char 从 lhs 开始是否小于第一个不匹配的 char从 rhs 开始

可以通过以下方式执行此评估：

result.second != rhs.cend() && (result.first == lhs.cend() || tolower(*result.first) < tolower(*result.second));

最终，我们希望将这个函数包装成一个 lambda 表达式，并将其作为比较器传回到 sort 中：
sort(foo.begin(), foo.end(), [](const unsigned char lhs, const unsigned char rhs){
    const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const unsigned char lhs, const unsigned char rhs){return tolower(lhs) == tolower(rhs);});

    return result.second != rhs.cend() && (result.first == lhs.cend() || tolower(*result.first) < tolower(*result.second));
});

这将正确地对vector<string> foo进行排序。您可以在此处查看实时示例：http://ideone.com/BVgyD2 编辑： 刚刚看到您的问题更新。您也可以使用sort与string array[]。您只需要像这样调用它：sort(array, std::next(array, size), ...
你有字符串数组排序的例子吗？ - bsem
@BennySaxeman 是的，请看我的编辑。我只会这样做：`sort(array, array + length, [](const auto& lhs, const auto& rhs){ const auto result = mismatch(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend(), [](const auto& lhs, const auto& rhs){return tolower(lhs) == tolower(rhs);});return result.second != rhs.cend() && (result.first == lhs.cend() || tolower(*result.first) < tolower(*result.second));});` 抱歉，一行中的内容有点长！请注意前两个参数的更改。 - Jonathan Mee
如果效率不重要（就像在这种情况下），将两个字符串转换为小写并通过 operator< 比较结果会更简单明了。 - Slava
@Slava 是的，我认为这个算法是处理它的最有效方法。但是因为排序是O(n log(n))，它会进行log(n)次额外的转换，而不是创建一个临时的小写字符串数组。但是这个算法利用了“mismatch”短路的事实，所以它只在需要比较的字母上调用“tolower”。它将取决于您的输入集，但这可能具有最小数量的“tolowers”，并且避免了创建临时变量（除了要比较的两个字符之外）。 - Jonathan Mee
3
#include <algorithm>
#include <vector>
#include <string>

using namespace std;    

void CaseInsensitiveSort(vector<string>& strs)
{
    sort(
        begin(strs),
        end(strs),
        [](const string& str1, const string& str2){
            return lexicographical_compare(
                begin(str1), end(str1),
                begin(str2), end(str2),
                [](const char& char1, const char& char2) {
                    return tolower(char1) < tolower(char2);
                }
            );
        }
    );
}
5
虽然此代码可以回答问题，但提供如何和/或为什么解决问题的附加上下文将改善答案的长期价值。 - baikho
2
我使用这个Lambda函数来对字符串向量进行排序：
std::sort(entries.begin(), entries.end(), [](const std::string& a, const std::string& b) -> bool {
        for (size_t c = 0; c < a.size() and c < b.size(); c++) {
            if (std::tolower(a[c]) != std::tolower(b[c]))
                return (std::tolower(a[c]) < std::tolower(b[c]));
        }
        return a.size() < b.size();
    });
1

使用不区分大小写的字符串比较函数代替<运算符。

C89/C99提供了strcoll（字符串整理）函数，它可以进行区域设置感知的字符串比较。在C++中可以使用std::strcoll。在某些（大多数？）语言环境下，例如en_CA.UTF-8，A和a（以及两者的所有重音形式）属于同一等价类。我认为，如果整个字符串相等，strcoll仅在等价类内部进行比较，作为一个细节处理，这会给出与不区分大小写比较非常相似的排序顺序。整理（至少在GNU/Linux上的英语环境中）忽略一些字符（如[）。因此ls /usr/share | sort会产生类似以下的输出：

acpi-support
adduser
ADM_scripts
aglfn
aisleriot

我使用sort命令进行管道传输，因为ls命令已经自带排序，但与基于语言环境的排序不完全相同。
如果您想将一些用户输入的任意字符串按照用户直接看到的顺序进行排序，则通常需要使用区域设置感知字符串比较。只有大小写或重音符号不同的字符串才不会相等，因此如果您使用稳定排序并依赖于大小写不同的字符串相等，则这种方法行不通，但是在其他情况下可以得到很好的结果。根据使用情况，比普通的不区分大小写的比较更好。 FreeBSD's strcoll对于除POSIX（ASCII）之外的语言环境仍然区分大小写。那篇论坛帖子表明，在大多数其他系统上它是不区分大小写的。

MSVC 提供了一个 _stricoll 来进行不区分大小写的排序，这意味着它的普通 strcoll 是区分大小写的。然而，这可能只是意味着在等价类内部比较时不会回退。也许有人可以使用 MSVC 测试以下示例。

// strcoll.c: show that these strings sort in a different order, depending on locale
#include <stdio.h>
#include <locale.h>

int main()
{
    // TODO: try some strings containing characters like '[' that strcoll ignores completely.
    const char * s[] = { "FooBar - abc", "Foobar - bcd", "FooBar - cde" };
#ifdef USE_LOCALE
    setlocale(LC_ALL, ""); // empty string means look at env vars
#endif
    strcoll(s[0], s[1]);
    strcoll(s[0], s[2]);
    strcoll(s[1], s[2]);
    return 0;
}

gcc -DUSE_LOCALE -Og strcoll.c && ltrace ./a.out的输出结果 (或以LANG=C ltrace a.out方式运行):

__libc_start_main(0x400586, 1, ...
setlocale(LC_ALL, "")                        = "en_CA.UTF-8"   # my env contains LANG=en_CA.UTF-8
strcoll("FooBar - abc", "Foobar - bcd")      = -1
strcoll("FooBar - abc", "FooBar - cde")      = -2
strcoll("Foobar - bcd", "FooBar - cde")      = -1
  # the three strings are in order
+++ exited (status 0) +++

使用gcc -Og -UUSE_LOCALE strcoll.c && ltrace ./a.out命令进行编译后，执行结果如下：
__libc_start_main(0x400536, ...
# no setlocale, so current locale is C
strcoll("FooBar - abc", "Foobar - bcd")      = -32
strcoll("FooBar - abc", "FooBar - cde")      = -2
strcoll("Foobar - bcd", "FooBar - cde")      = 32   # s[1] should sort after s[2], so it's out of order
+++ exited (status 0) +++

POSIX.1-2001提供了strcasecmp。然而，POSIX规范表示，在除了普通ASCII之外的语言环境下，结果是“未指定”的，因此我不确定常见的实现是否正确处理utf-8。

请参见此帖子以了解strcasecmp的可移植性问题，例如Windows。请参见该问题的其他答案以了解其他C++进行大小写不敏感字符串比较的方法。

一旦您拥有了一个不区分大小写的比较函数，就可以将其与其他排序算法一起使用，例如C标准库中的qsort或c ++ std :: sort，而无需编写自己的O(n^2)选择排序。
正如b.buchhold的回答指出的那样，在运行时进行不区分大小写的比较可能比将所有内容转换为小写一次，并对索引数组进行排序要慢。需要多次使用每个字符串的小写版本。std :: strxfrm将转换一个字符串，使得对结果进行strcmp将得到与对原始字符串进行strcoll相同的结果。
你是说 strcoll 是不区分大小写的吗？因为我从来没有想过这个问题，但如果是这样的话... - Jonathan Mee
@JonathanMee：我在本地化方面并不是专家。我只使用过C（POSIX ASCII）和en_CA.UTF-8本地化设置。我认为对于使用罗马字母的语言环境来说，不区分大小写的排序以及将带重音字符与不带重音字符一起排序是很典型的。如果您想将一些用户输入的任意字符串按照用户直接看到的顺序进行排序，则通常需要使用具有本地化感知能力的字符串比较。其他用途（例如作为数据结构的一部分）可能关心字节并需要使用memcmp或类似函数。 - Peter Cordes
strcoll 是区分大小写的，参考：http://en.cppreference.com/w/cpp/string/byte/strcoll "在一个等价类中，小写字符排在它们的大写等价物之前。" 在我的测试中，我发现这是正确的。此外，这也否定了 strxfrm，因为它的行为与 strcoll 相同。只能使用不幸依赖于平台的实现来解决这个问题。 - Jonathan Mee
@JonathanMee：实际上，我认为大小写和重音符号（即在等价类内进行比较）只有在考虑等价类的所有成员相等时才起作用，作为打破平局的一种方式。这对于排序非常有用，但在测试相等性时可能或可能不是您想要的。我同意这个答案没有任何伟大的具体建议，只是一些指向需要检查的事情的指针，以及一个主要的“c++不区分大小写字符串比较”问题的链接。 - Peter Cordes
0

这个方案比Jonathan Mee的简单得多，但相当低效，但对于教育目的可能还可以：

std::string lowercase( std::string s )
{
   std::transform( s.begin(), s.end(), s.begin(), ::tolower );
   return s;
}

std::sort( array, array + length, 
           []( const std::string &s1, const std::string &s2 ) { 
               return lowercase( s1 ) < lowercase( s2 ); 
           } );

如果你必须使用自己的排序函数，你可以采用相同的方法：
    ....
    minValue = lowercase( array[startScan] );

    for (int index = startScan + 1; index < size; index++) {
        const std::string &tstr = lowercase( array[index] );
        if (tstr < minValue) {
            minValue = tstr;
            minIndex = index;
        }
    }
    ...
0

你可以在比较每个字符之前调用 tolower 函数。这可能是最简单的方法，但并不是一个很好的解决方案，因为：

  • 你需要多次查看每个字符，所以你会比必要的更频繁地调用该方法。
  • 你需要额外小心处理宽字符的编码（UTF8 等）。

你也可以通过自己的函数替换比较器。例如，在某些地方你会比较像 stringone[i] < stringtwo[j] 或者 charA < charB 这样的东西。将其改为 my_less_than(stringone[i], stringtwo[j]) 并根据你想要的确切顺序实现排序。

另一种方法是将每个字符串转换为小写，并创建一组成对的数组。然后你只基于小写值进行比较，但是你交换整个对，以便你的最终字符串也按正确的顺序排列。

最后，你可以创建一个包含小写版本的数组，并对其进行排序。每当你在这个数组中交换两个元素时，你也在原始数组中进行交换。

请注意，所有这些提议仍然需要适当处理宽字符（如果你需要的话）。

或者在排序时添加一层间接性：通过对输入数组中的string进行索引，对索引数组进行排序。然后取消间接性，得到一个已排序的字符串列表。这样做可以减少交换开销，但可能会增加访问开销。 - Peter Cordes
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接