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

问题描述 投票：3回答：6

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

然而，这种类型应该不区分大小写，因此“天线”将出现在“木星”之前。 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;
    }
}
c++ string sorting case-insensitive
6个回答
4
投票

C ++为您提供了sort，它具有比较功能。在你使用vector<string>的情况下，你将比较两个字符串。如果第一个参数较小，则比较函数应返回true。

对于我们的比较函数，我们想要在应用string之后找到tolowers之间的第一个不匹配的字符。要做到这一点，我们可以使用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);});

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

  1. 是strings长度不等
  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), ......

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做了自己的排序，这与sort的基于语言环境的排序不完全相同。

如果要将一些用户输入的任意字符串排序为用户将直接看到的顺序，通常可以通过区域设置识别字符串比较。仅在大小写或重音符号上不同的字符串将不会相等，因此如果您使用稳定排序并且根据大小写不同的字符串进行比较相等，则这将不起作用，但否则您将获得不错的结果。根据用例，比普通的不区分大小写更好。

对于POSIX（ASCII）以外的语言环境，FreeBSD's strcoll可能仍然区分大小写。该论坛帖子表明，在大多数其他系统上，它并不具有案例敏感性。

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。

见this post for portability issues with strcasecmp, e.g. to Windows。有关进行不区分大小写的字符串比较的其他C ++方法，请参阅该问题的其他答案。

一旦你有一个不区分大小写的比较函数，你可以将它与其他排序算法一起使用，比如C标准库qsort或c ++ std::sort，而不是编写你自己的O（n ^ 2）选择排序。

正如b.buchhold的回答指出的那样，在运行中进行不区分大小写的比较可能比将所有内容转换为小写一次并对索引数组进行排序要慢。每个字符串的小写版本需要多次。 std::strxfrm将变换一个字符串，以便结果上的strcmp将在原始字符串上给出与strcoll相同的结果。

1
投票

我使用这个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();
    });
0
投票

您可以在比较的每个角色上调用tolower。这可能是最简单的，但不是一个很好的解决方案，因为：

  • 您多次查看每个char，因此您需要更频繁地调用该方法
  • 你需要额外注意处理w -r.t到它们的编码的宽字符（UTF8等）

您也可以用自己的功能替换比较器。即会有一些地方比较stringone[i] < stringtwo[j]或charA < charB之类的东西。将其更改为my_less_than(stringone[i], stringtwo[j])并实现您想要的确切顺序。

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

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

请注意，所有这些提案仍然需要正确处理宽字符（如果您需要的话）

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
投票
#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);
                }
            );
        }
    );
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.