C STL相等与等价有序容器与有序区间算法使用比较谓词comp表达「先于」关系comp须构成严格弱序。本文说明其与operator所表达的相等的分工差异并以std::set_difference、忽略大小写比较为例。目录std::set_difference与仅按pair::first排序将用作比较谓词以严格小于定义比较谓词相等与等价严格弱序有序容器与有序算法中的等价比较谓词的实现方式示例不区分大小写易错点与可测试性质对照表std::set_difference与仅按pair::first排序对两个已排序的std::vectorstd::pairint, std::string求差集且排序键仅为first时std::pair默认的operator会同时比较first与second与需求不一致应传入自定义比较谓词compareFirst。#includealgorithm#includeiterator#includestring#includeutility#includevectorboolcompareFirst(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2);// v1、v2 须已按 compareFirst 构成严格弱序std::vectorstd::pairint,std::stringv1,v2,results;std::sort(v1.begin(),v1.end(),compareFirst);std::sort(v2.begin(),v2.end(),compareFirst);std::set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),std::back_inserter(results),compareFirst);set_difference按 comp 判定等价类前提两序列在同一 comp 下已排序将用作比较谓词有序算法要求comp(a,b)为 true 表示a严格先于b而不是「二者相等」。boolcompareFirstBad(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2){returnp1.firstp2.first;}严格弱序要求非自反对所有acomp(a,a)为 false。上式在a.first a.first时为 true不满足该条件比较谓词无效使用此类comp的算法行为未定义。以严格小于定义比较谓词boolcompareFirst(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2){returnp1.firstp2.first;}在此comp下a与b等价当且仅当!comp(a, b) !comp(b, a)即本例中first相等时等价与second取值无关。相等与等价术语含义判定典型使用场景相等值语义上完全一致a bstd::find、std::count等不依赖排序的接口等价在comp下互不先于对方!comp(a,b) !comp(b,a)std::set、std::map、merge、set_difference等可不等价相等: 等价: !comp(a,b) !comp(b,a)在全序类型上使用默认时相等与等价通常一致。自定义comp例如忽略大小写下二者可以分离Hello与HELLO可不相等但在同一comp下等价。严格弱序comp作为有序容器/算法的比较谓词时应满足非自反comp(a,a)恒为 false。非对称comp(a,b)为 true 则comp(b,a)为 false。传递comp(a,b)与comp(b,c)为 true 则comp(a,c)为 true。不可比的传递性若!comp(a,b)!comp(b,a)且!comp(b,c)!comp(c,b)则!comp(a,c)!comp(c,a)。若令comp(a,b):(ab)则comp(a,a)为 true违反非自反。若使用作为「小于」boolbad_comp(inta,intb){returnab;}则comp(a,a)为 true同样违反非自反。有序容器与有序算法中的等价std::set/std::multiset插入时按comp检测是否已存在等价元素set不插入新的等价元multiset允许多个等价元共存。std::map/std::multimapinsert在已存在等价键时失败不覆盖已有映射。需要插入或更新时可使用operator[]、insert_or_assignC17、try_emplace等接口。merge、includes、set_difference等输入区间须已按同一comp排序算法在comp下划分顺序与等价类。等价元在输出中的相对顺序由各自算法规范约定。structCompareFirst{booloperator()(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2)const{returnp1.firstp2.first;}};std::setstd::pairint,std::string,CompareFirstmySet;mySet.insert({1,apple});mySet.insert({1,banana});// 与 {1,apple} 等价第二次插入无效比较谓词的实现方式形式说明函数指针可调用内联受限函数对象operator()常为const易内联Lambda可捕获状态与模板算法配合直接std::functionbool(T,T)类型擦除带来额外开销autocompFirst[](constautop1,constautop2){returnp1.firstp2.first;};std::set_difference(/*...*/,compFirst);示例不区分大小写Hello HELLO为 false。定义按小写比较的严格弱序#includealgorithm#includecctype#includestringboolci_less(conststd::stringa,conststd::stringb){returnstd::lexicographical_compare(a.begin(),a.end(),b.begin(),b.end(),[](unsignedcharc1,unsignedcharc2){returnstd::tolower(c1)std::tolower(c2);});}对Hello与HELLOci_less在两个方向上均为 false故二者在该comp下等价。关联容器的find使用比较谓词定义的等价std::find通常使用operator。二者判定基础不同结果可以不一致。易错点与可测试性质情况后果用或充当「小于」破坏严格弱序未定义行为排序使用comp1算法传入comp2前提不满足输出错误std::sort的比较谓词非严格弱序未定义行为可在测试中检查对所有a!comp(a,a)对所有a,b!(comp(a,b) comp(b,a))并可在小域上穷举或随机化验证传递性。对照表对象作用比较谓词comp定义严格弱序与等价类operator定义相等用于非有序查找等!comp(a,b)!comp(b,a)有序语义下的「相同」
C++ STL：相等与等价
发布时间：2026/5/19 23:05:14
C STL相等与等价有序容器与有序区间算法使用比较谓词comp表达「先于」关系comp须构成严格弱序。本文说明其与operator所表达的相等的分工差异并以std::set_difference、忽略大小写比较为例。目录std::set_difference与仅按pair::first排序将用作比较谓词以严格小于定义比较谓词相等与等价严格弱序有序容器与有序算法中的等价比较谓词的实现方式示例不区分大小写易错点与可测试性质对照表std::set_difference与仅按pair::first排序对两个已排序的std::vectorstd::pairint, std::string求差集且排序键仅为first时std::pair默认的operator会同时比较first与second与需求不一致应传入自定义比较谓词compareFirst。#includealgorithm#includeiterator#includestring#includeutility#includevectorboolcompareFirst(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2);// v1、v2 须已按 compareFirst 构成严格弱序std::vectorstd::pairint,std::stringv1,v2,results;std::sort(v1.begin(),v1.end(),compareFirst);std::sort(v2.begin(),v2.end(),compareFirst);std::set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),std::back_inserter(results),compareFirst);set_difference按 comp 判定等价类前提两序列在同一 comp 下已排序将用作比较谓词有序算法要求comp(a,b)为 true 表示a严格先于b而不是「二者相等」。boolcompareFirstBad(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2){returnp1.firstp2.first;}严格弱序要求非自反对所有acomp(a,a)为 false。上式在a.first a.first时为 true不满足该条件比较谓词无效使用此类comp的算法行为未定义。以严格小于定义比较谓词boolcompareFirst(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2){returnp1.firstp2.first;}在此comp下a与b等价当且仅当!comp(a, b) !comp(b, a)即本例中first相等时等价与second取值无关。相等与等价术语含义判定典型使用场景相等值语义上完全一致a bstd::find、std::count等不依赖排序的接口等价在comp下互不先于对方!comp(a,b) !comp(b,a)std::set、std::map、merge、set_difference等可不等价相等: 等价: !comp(a,b) !comp(b,a)在全序类型上使用默认时相等与等价通常一致。自定义comp例如忽略大小写下二者可以分离Hello与HELLO可不相等但在同一comp下等价。严格弱序comp作为有序容器/算法的比较谓词时应满足非自反comp(a,a)恒为 false。非对称comp(a,b)为 true 则comp(b,a)为 false。传递comp(a,b)与comp(b,c)为 true 则comp(a,c)为 true。不可比的传递性若!comp(a,b)!comp(b,a)且!comp(b,c)!comp(c,b)则!comp(a,c)!comp(c,a)。若令comp(a,b):(ab)则comp(a,a)为 true违反非自反。若使用作为「小于」boolbad_comp(inta,intb){returnab;}则comp(a,a)为 true同样违反非自反。有序容器与有序算法中的等价std::set/std::multiset插入时按comp检测是否已存在等价元素set不插入新的等价元multiset允许多个等价元共存。std::map/std::multimapinsert在已存在等价键时失败不覆盖已有映射。需要插入或更新时可使用operator[]、insert_or_assignC17、try_emplace等接口。merge、includes、set_difference等输入区间须已按同一comp排序算法在comp下划分顺序与等价类。等价元在输出中的相对顺序由各自算法规范约定。structCompareFirst{booloperator()(conststd::pairint,std::stringp1,conststd::pairint,std::stringp2)const{returnp1.firstp2.first;}};std::setstd::pairint,std::string,CompareFirstmySet;mySet.insert({1,apple});mySet.insert({1,banana});// 与 {1,apple} 等价第二次插入无效比较谓词的实现方式形式说明函数指针可调用内联受限函数对象operator()常为const易内联Lambda可捕获状态与模板算法配合直接std::functionbool(T,T)类型擦除带来额外开销autocompFirst[](constautop1,constautop2){returnp1.firstp2.first;};std::set_difference(/*...*/,compFirst);示例不区分大小写Hello HELLO为 false。定义按小写比较的严格弱序#includealgorithm#includecctype#includestringboolci_less(conststd::stringa,conststd::stringb){returnstd::lexicographical_compare(a.begin(),a.end(),b.begin(),b.end(),[](unsignedcharc1,unsignedcharc2){returnstd::tolower(c1)std::tolower(c2);});}对Hello与HELLOci_less在两个方向上均为 false故二者在该comp下等价。关联容器的find使用比较谓词定义的等价std::find通常使用operator。二者判定基础不同结果可以不一致。易错点与可测试性质情况后果用或充当「小于」破坏严格弱序未定义行为排序使用comp1算法传入comp2前提不满足输出错误std::sort的比较谓词非严格弱序未定义行为可在测试中检查对所有a!comp(a,a)对所有a,b!(comp(a,b) comp(b,a))并可在小域上穷举或随机化验证传递性。对照表对象作用比较谓词comp定义严格弱序与等价类operator定义相等用于非有序查找等!comp(a,b)!comp(b,a)有序语义下的「相同」
