如何对具有区分大小写元素的 std::list 进行排序？

Question

这是我当前的代码：

#include <list>
#include <string>
using std::string;
using std::list;

int main()
{
    list <string> list_;
    list_.push_back("C");
    list_.push_back("a");
    list_.push_back("b");

    list_.sort();
}

sort() 函数是否根据元素的字符代码对元素进行排序？我希望排序完成后这里的结果是 ab C 。

Answer 1

如果您想支持其他语言的字符，则不区分大小写的字符比较会很棘手。这就是为什么以区域设置敏感的方式执行它们是一个好主意：

struct char_iless 
: public std::binary_function<char, char, bool>
{
    std::locale loc;

    char_iless(std::locale const & loc=std::locale()) : loc(loc) 
    {
    }

    bool operator()(char a, char b) const
    {
        return std::tolower(a, loc) < std::tolower(b, loc);
    }
};

这就是使用此类来比较两个字符的方式：

char_iless('a', 'b', my_locale);

只需使用 std::locale() 作为 my_locale code> 如果您想使用默认设置的代码。

如果你可以使用 Boost，那么字符串算法库中有一个 is_iless 函子可以做同样的事情。

借助 std::lexicographyal_compare，将比较字符与字符串进行扩展很容易：

struct str_iless 
: public std::binary_function<std::string, std::string, bool>
{
    std::locale loc;

    str_iless(std::locale const & loc=std::locale()) : loc(loc) 
    {
    }

    bool operator()(std::string const & a, std::string const & b) const
    {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),  
            char_iless(loc)
        );
    }
};

现在您已拥有解决问题所需的一切：

int main()
{
    std::list<std::string> list;
    list.push_back("C");
    list.push_back("a");
    list.push_back("b");

    // Sort using default locale
    list.sort(str_iless());  

    // Sort using French locale 
    // (warning: this locale format string is MS specific)
    std::locale loc("French_France.1252");
    list.sort(str_iless(loc));
}

Answer 2

默认比较器 (<) 使用默认的 char_traits<; char > 会将您的列表排序为 C a b。

请参阅list::sort。

为了达到所需的顺序 ab C 您可以：

1. 使用 自定义 char_traits，或

2. 提供自定义字符串比较器的实例排序，例如

   bool istring_less(const string& lhs, const string& rhs) {
     字符串::const_iterator \
       lb = lhs.begin(), le = lhs.end(),
       rb = rhs.begin(), re = rhs.end();
     常量字符 lc、rc；
     for (; lb != le && rb != re; ++lb, ++rb) {
       lc = tolower(*lb);
       rc = tolower(*rb);
       if (*lc < *rc) 返回 true；
       if (*lc > *rc) 返回 false；
     }
     // 如果 rhs 比 lhs 长，则 lhs

Answer 3

以下是我认为更干净、速度更快的替代方案：

#include    <string>
#include    <cstring>
#include    <iostream>
#include    <boost/algorithm/string.hpp>

using std::string;
using std::list;
using std::cout;
using std::endl;

using namespace boost::algorithm;

// recommended in Meyers, Effective STL when internationalization and embedded
// NULLs aren't an issue.  Much faster than the STL or Boost lex versions.
struct ciLessLibC : public std::binary_function<string, string, bool> {
    bool operator()(const string &lhs, const string &rhs) const {
        return strcasecmp(lhs.c_str(), rhs.c_str()) < 0 ? 1 : 0;
    }
};

// If you need sorting according to the default system local
struct ciLessBoost : std::binary_function<std::string, std::string, bool>
{
    bool operator() (const std::string & s1, const std::string & s2) const {
        return lexicographical_compare(s1, s2, is_iless());
    }
};

int main(void) {
    list <string> list_;
    list_.push_back("C");
    list_.push_back("a");
    list_.push_back("b");

    list_.sort(ciLessLibC());
    list_.sort(ciLessBoost());

    return 0;
}

Answer 4

yes

您可以检查以下代码以使用自定义比较器

Answer 5

从 C++11 开始，您还可以使用 lambda 表达式 而不是定义比较器函数/结构：

#include <list>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;

int main()
{
    list<string> list_;
    list_.emplace_back("C");
    list_.emplace_back("a");
    list_.emplace_back("b");

    list_.sort([](const string& a, const string& b) {
        return (strcasecmp(a.c_str(), b.c_str()) < 0);
    });

    for (auto const &str : list_)
        cout << str << endl;

    return 0;
}  

输出：

一个
b

注：函数 strcasecmp() （正如 @RobertS.Barnes 的回答中所建议的）不在 C++ 标准中，因此并非在每个系统上都可用。例如，如果您使用的是 Visual Studio，则可以使用 _stricmp( ) 代替。

如果国际化对您来说是一个问题，那么您可以像 @Manuel 在他的回答中所做的那样应用区域设置。

Ideone 上的代码