我正在重新发布我今天早些时候提交的一个问题,但我现在引用一个具体的例子来回应我收到的反馈.原始问题可以在这里找到(请注意,这不是一个家庭作业):
我只是想确定C++是否使得无法对一个对象进行(高效)案例不敏感的比较,而该basic_string对象也会影响任意locale对象.例如,似乎不可能编写一个有效的函数,如下所示:
bool AreStringsEqualIgnoreCase(const string &str1, const string &str2, const locale &loc);
基于我目前的理解(但有人可以证实这一点),这个函数必须调用两个ctype::toupper()和collate::compare()给定的locale(一如既往地提取use_facet()).但是,因为collate::compare()特别需要4个指针args,你需要为你需要比较的每个char传递这4个args(在第一次调用之后ctype::toupper()),或者首先将两个字符串转换为upppercase,然后再调用一次collate::compare().
第一种方法显然是低效的(每个测试的char都有4个指针传递),而第二种方法要求你将两个字符串整体转换为大写(需要分配内存和不必要的复制/将两个字符串转换为大写).我对此是正确的,即,不可能有效地做到这一点(因为没有办法collate::compare()).
ric*_*ici 13
关于尝试以一致的方式与世界上所有的书写系统打交道的一个小烦恼是,你认为你对角色的了解几乎没有任何实际上是正确的.这使得执行诸如"不区分大小写的比较"之类的事情变得棘手.实际上,进行任何形式的区域设置感知比较都很棘手,而且不区分大小写更加棘手.
但是,有了一些限制,就有可能实现.所需的算法可以使用正常的编程实践(以及一些静态数据的预计算)"高效"地实现,但是它不能像不正确的算法那样有效地实现.通常可以权衡速度的正确性,但结果并不令人愉快.不正确但快速的语言环境实现可能会吸引那些其语言环境正确实现的人,但对于其语言环境产生意外结果的受众部分显然不能令人满意.
词典排序对人类不起作用
大多数语言环境("C"语言环境除外)用于具有案例的语言已经以预期的方式处理字母大小写,这是仅在考虑了所有其他差异之后才使用大小写差异.也就是说,如果按照语言环境的整理顺序对单词列表进行排序,则列表中仅在大小写上不同的单词将是连续的.具有大写的单词是在具有小写的单词之前还是之后是依赖于语言环境的,但是在它们之间不会有其他单词.
任何单次传递从左到右的逐字符比较("词典排序")都无法实现这一结果.大多数语言环境都有其他的整理怪癖,这些怪癖也不会产生天真的词典排序.
如果您有适当的区域设置定义,标准C++排序规则应该能够处理所有这些问题.但是它不能简单地使用比对函数来减少到词典比较whar_t,因此C++标准库不提供该接口.
以下是为什么区域设置感知排序规则复杂化的几个示例; Unicode技术标准10中提供了更长的解释,有更多示例.
口音在哪里？
大多数浪漫语言(以及处理借词时的英语)都将元音上的重音视为次要特征 ; 也就是说,首先对单词进行排序,就好像重音不存在一样,然后进行第二次通过,其中非重音字母出现在重音字母之前.第三次传递是处理案件所必需的,在前两次通过中被忽略.
但这对北欧语言不起作用.瑞典语,挪威语和丹麦语的字母表有三个额外的元音,后面z是字母表.在瑞典,这些元音都写å,ä和ö; 在挪威语和丹麦语中,这些字母是写的å,æ并且有时用ø丹麦语å写成aa,使得奥胡斯成为丹麦城市按字母顺序排列的列表中的最后一个条目.
在德国,字母ä,ö和ü一般alphabetised与浪漫的口音,但在德国电话簿(有时是其他字母顺序列出),他们alphabetised好像他们写的ae,oe而且ue,这是写入相同音素的旧式.(有许多常见的姓氏,例如"Müller"和"Mueller"发音相同而且经常混淆,因此将它们混合起来是有意义的.当我年轻时,加拿大电话簿中的苏格兰名字也采用了类似的惯例;拼写M',Mc并且Mac都是拼凑在一起,因为它们在语音上都是相同的.)
一个符号,两个字母.或两个字母,一个符号
德语也有这样的符号ß,就像它被写出一样ss,尽管它在语音上并不完全相同.稍后我们会再次遇到这个有趣的符号.
事实上,许多语言认为有向图甚至三字母都是单字母.44个字母的字母表匈牙利语包括Cs,Dz,Dzs,Gy,Ly,Ny,Sz,Ty,和Zs,以及各种重音的元音.然而,关于这种现象的文章中最常引用的语言 - 西班牙语 - 在1994 年停止对待有向图ch和ll字母,大概是因为它更容易迫使西班牙裔作家遵守计算机系统而不是改变计算机系统来处理西班牙的有向图.(维基百科声称这是来自"联合国教科文组织和其他国际组织"的压力;每个人都需要花费很长时间才能接受新的字母化规则,而你仍然偶尔会在"哥伦比亚"之后的南美洲国家的字母列表中找到"智利".)
总结:比较字符串需要多次传递,有时需要比较字符组
使它全部不区分大小写
由于locales在比较时正确处理了case,因此不一定需要进行不区分大小写的排序.进行不区分大小写的等价类检查("相等"测试)可能是有用的,尽管这引发了其他不精确的等价类可能有用的问题.Unicode标准化,重音删除,甚至是拉丁语的转录在某些情况下都是合理的,而在其他情况下则非常烦人.但事实证明,案例转换并不像你想象的那么简单.
由于存在二进制和三字符,其中一些具有Unicode代码点,因此Unicode标准实际上识别三种情况,而不是两种情况:小写,大写和标题情况.最后一个是大写单词的第一个字母,例如,克罗地亚有向图dž(U + 01C6;单个字符),大写字母为DŽ(U + 01C4),标题为Dž(U + 01C5)."不区分大小写"的比较理论是,我们可以(通过概念上)对任何字符串进行转换,使得"忽略大小写"定义的等价类的所有成员都转换为相同的字节序列.传统上,这是通过"上套管"字符串完成的,但事实证明,这并不总是可能的,甚至是正确的; Unicode标准更喜欢使用"case-folding"这个术语,就像我一样.
C++语言环境并不完全符合工作要求
因此,回到C++,可悲的事实是C++语言环境没有足够的信息来进行准确的大小写折叠,因为C++语言环境的工作原理是,对一个字符串进行折叠只包含顺序和单独的上限字符串中的每个代码点使用一个将代码点映射到另一个代码点的函数.正如我们所看到的那样,这是行不通的,因此其效率问题无关紧要.另一方面,ICU库有一个接口,可以像Unicode数据库允许的那样正确地进行大小写折叠,并且它的实现由一些非常好的编码器精心设计,因此在约束条件下它可能尽可能高效.所以我绝对推荐使用它.
如果您想要很好地概述案例折叠的难度,您应该阅读Unicode标准的第5.18和5.19节(第5章的PDF).以下只是几个例子.
案例转换不是从单个字符到单个字符的映射
最简单的例子是德语ß(U + 00DF),它没有大写形式,因为它从不出现在一个单词的开头,而传统的德语拼写法没有使用全大写字母.标准的大写变换是SS(或在某些情况下SZ),但该变换是不可逆的; 并非所有的实例ss都写成ß.比如,grüßen和küssen(分别为迎接和亲吻).最近,upper,一个"大写ß,已被添加到Unicode作为U + 1E9E,但它不常用,除了全帽大街道标志,其使用是法律强制和正常期望的上层套管ß将是两封信.
并非所有表意文字(可见字符)都是单字符代码
即使案例转换将单个字符映射到单个字符,它也可能无法将其表示为SS映射.例如,ǰ可以很容易地大写J̌,但前者是单个组合字形(U + 01F0),而第二个是大写J与组合caron(U + 030C).
字形还有一个问题,如ǰ:
通过字符大小写折叠的朴素字符可以非规范化
假设我们ǰ如上所述大写.我们如何大写ǰ̠(如果它在你的系统上没有正确呈现,它是与下面的条形图相同的字符,另一个IPA约定)？该组合是U + 01F0,U + 0320(j与caron,下面结合减号),所以我们继续用U + 004A,U + 030C代替U + 01F0,然后按原样保留U + 0320 : J̠̌. 这很好,但是它不会与标准化的大写J相比,下面是caron和减号,因为在正常形式中,减号变音符号首先出现:U + 004A,U + 0320,U + 030C(J̠̌,应该看起来相同).所以有时(很少,说实话,但有时),有必要重新规范化.
撇开unicode wierdness,有时案例转换是上下文敏感的
希腊语中有很多关于标记如何根据它们是单词初始化,单词最终结构还是单词内部进行改组的示例 - 您可以在Unicode标准的第7章中阅读更多相关内容 - 但这是一个简单而常见的case是Σ,它有两个小写版本:σ和ς.具有一些数学背景的非希腊人可能很熟悉σ,但可能没有意识到它不能用在必须使用的单词的末尾ς.
简而言之
case-fold的最佳可行正确方法是应用Unicode case-folding算法,该算法需要为每个源字符串创建一个临时字符串.然后,您可以在两个转换的字符串之间进行简单的字节比较,以验证原始字符串是否在同一个等价类中.尽可能对转换后的字符串进行排序规则排序比排序原始字符串的排序效率低,并且为了排序目的,未转换的比较可能与转换后的比较一样好或更好.
从理论上讲,如果你只对大小写折叠的等式感兴趣,你可以线性地进行转换,记住转换不一定是无上下文的,也不是简单的字符到字符映射函数.遗憾的是,C++语言环境不能为您提供执行此操作所需的数据.Unicode CLDR更接近,但它是一个复杂的数据结构.
所有这些东西都非常复杂,并且充斥着边缘情况.(例如,请参阅Unicode标准中有关重音立陶宛语wchar→wchar的说明.)您最好只使用维护良好的现有解决方案,其中最好的例子是ICU.