6

我想对向量进行排序，以便大写字母跟随小写字母。如果我有类似的东西

This is a test
this is a test
Cats
cats
this thing

我希望输出是

cats
Cats
this is a test
This is a test
this thing

标准库排序将输出

Cats
This is a test
cats
this is a test
this thing

我想将谓词传递给 std::sort ，以便它比较我作为参数传递的字符串的小写版本。

bool compare(std::string x, std::string y)
{
    return lowercase(x) < lowercase(y);
}

我尝试降低函数中的每个字符，然后进行比较，但没有奏效。我想通过其他方法将字符串转换为小写来测试这种方法。如何将字符串转换为小写？

编辑：：

其实我发现了问题。这行得通。当我第一次编写函数时，ref = tolower(ref)我tolower(ref)没有重新分配，ref所以它什么也没做。

bool compare(std::string x, std::string y)
{
    for(auto &ref:x)
        ref = tolower(ref);
    for(auto &ref:y)
        ref = tolower(ref);
    return x < y;
}

编辑：：

这段代码实际上有时会先排序大写字母，有时会先排序大写字母，因此并不能完全解决问题。

4

6 回答 6

2

执行此操作的常用方法是构建一个排序表。这只是一个表格，给出了每个字符的相对顺序。在您的情况下，您希望每个大写字母紧跟在相应的小写字母之后。

我们可以这样做：

class comp_char { 
    std::vector<int> collation_table;
public:
    comp_char() : collation_table(std::numeric_limits<unsigned char>::max()) {
        std::iota(collation_table.begin(), collation_table.end(), 0);

        for (int i = 0; i < 26; i++) {
            collation_table['a' + i] = i * 2;
            collation_table['A' + i] = i * 2 + 1;
        }
    }

    bool operator()(unsigned char a, unsigned char b) {
        return collation_table[a] < collation_table[b];
    }
};

目前，我忽略了字母与其他字符的相对顺序（可能是棘手的）问题。正如它所写的那样，其他所有内容都排在字母之前，但是很容易更改（例如）字母排在其他任何内容之前。不过，这两种方法可能都没有太大的区别——大多数人对 'a' < ';' 是否有强烈的期望。或不。

在任何情况下，一旦整理表构建并可用，您就想使用它来比较字符串：

struct cmp_str {
    bool operator()(std::string const &a, std::string const &b) {
        comp_char cmp;
        size_t i = 0;
        while (a[i] == b[i] && i < a.size())
            ++i;
        return cmp(a[i], b[i]);
    }
};

...我们可以使用它来进行排序，如下所示：

int main(){
    std::vector<std::string> inputs {
        "This is a test",
        "this is a test",
        "Cats",
        "cats",
        "this thing"
    };

    std::sort(inputs.begin(), inputs.end(), cmp_str());
    std::copy(inputs.begin(), inputs.end(),
        std::ostream_iterator<std::string>(std::cout, "\n"));
}

目前，我只编写了整理表来处理基本的 US-ASCII 字母。对于实际使用，您通常希望在其相应的非重音等价物旁边放置带有重音符号的字母之类的东西。为此，您通常最终会预先构建表以（部分）匹配诸如 Unicode 规范之类的事物应如何排序的内容。

请注意，此输出与原始问题所说的不太匹配，但我认为在这种情况下，问题有误。我看不出有任何方式产生这样的订单甚至有点合理：

this is a test
This is a test
this thing

这在“t”之后和之前都有“T”排序，这似乎没有意义（或者至少不适合词法排序，这是人们几乎总是想要的字符串）。

于 2013-10-22T05:04:27.323 回答
2

最简单的解决方案是使用标准locale对象提供的排序规则感知排序。

区域设置operator()(std::string, std::string)正是区域设置的排序感知比较运算符，因此您可以将其直接插入到您的调用中std::sort：

// Adjust to the locale you actually want to use
std::sort(strings.begin(), strings.end(), std::locale("en_US.UTF-8"));

ideone的例子

于 2013-10-22T14:45:34.010 回答
1

您的解决方案几乎就在那里，如果字符串的小写版本相等，您只需要制作一个特殊情况：

std::string to_lower(std::string s)
{
    for (auto & c : s)
        c = std::tolower(c);
    return s;
}

bool string_comp(std::string const & lhs, std::string const & rhs)
{

    auto lhs_lower = to_lower(lhs);
    auto rhs_lower = to_lower(rhs);
    if (lhs_lower == rhs_lower)
        return rhs < lhs;
    return lhs_lower < rhs_lower;
}

这可以使用一些优化。不需要复制字符串。当然，您可以就地进行不区分大小写的比较。但这是标准库中无法方便地使用的功能，所以我将把这个练习留给你。

于 2013-10-22T05:01:04.770 回答
1

需要明确的是，我的目标是通常的字典类型比较，但如果字符串相同，则以某种方式使大写跟随小写。

这需要两步比较：

  1. 在不区分大小写模式下比较字符串
  2. 如果两个字符串在不区分大小写模式下相等，我们需要区分大小写比较的反向结果（将大写放在首位）

因此，比较器给出：

class Comparator {
public:
   bool operator()(std::string const& left, std::string const& right) {
       size_t const size = std::min(left.size(), right.size());

       // case-insensitive comparison
       for (size_t i = 0; i != size; ++i) {
           if (std::tolower(left[i]) < std::tolower(right[i])) { return true; }
       }

       if (left.size() != right.size()) { return size == left.size(); }

       // and now, case-sensitive (reversed)
       return right < left;
   }
}; // class Comparator
于 2013-10-22T18:24:36.827 回答
0

您需要一次比较一个字符，在第一个不同的字符处停止，然后首先根据大小写转换返回结果，否则返回原始字符：

bool mylt(const std::string& a, const std::string& b) {
    int i=0, na=a.size(), nb=b.size();
    while (i<na && i<nb && a[i]==b[i]) i++;
    if (i==na || i==nb) return i<nb;
    char la=std::tolower(a[i]), lb=std::tolower(b[i]);
    return la<lb || (la==lb && a[i]<b[i]);
}

警告：未经测试的早餐代码

于 2013-10-22T05:44:23.937 回答
0

要么使用local已经有你想要的排序的 s，要么写一个逐个字符的比较函数，然后用std::lexicographical_compare它把它变成一个字符串比较函数。

我会local先尝试 s，但如果这证明令人沮丧，那么字典并不可怕。

要比较 chqracters，请创建两个tuples 或pair, lower_case_letter，unchanged_letter然后调用<它。这将首先按小写字母排序，然后如果失败则按原样排序。我忘记了大写和小写的排序顺序：但如果顺序是倒序的，只需交换哪个小写字母与哪个大写字母配对，您就会颠倒顺序！

于 2013-10-22T10:37:28.793 回答