本文简单总结一下C++ STL的几种“比较”概念。
作者：tyc611.cublog.cn，2008-04-13
在C++的现行标准（C++ 98）中，由于没有类似“接口”这样的东西，我们在泛型编程时往往只能对模板类型作一些假设，要求其符合某个需求清单，也就是属于某个概念。这只是一种人为的约定，一旦该约定未被遵守，编译器可能会无法有效地发现问题原因所在。不过，在即将发布的C++ 0x中将引入，可以较好地解决这个问题。扯远了，让我们回到正题。
STL中所有泛型算法和容器模板都对涉及到的元素所属概念有明确要求，在使用这些算法和容器时必须能够区分这些概念。本文主要针对C++ STL库中几个重要的关于元素比较的概念列举出来，并稍做解释。因为这些概念在STL用得非常频繁，如若未能区分开来，将很难有效掌握STL。这里，我们主要讲解Equality Comparable、LessThan Comparable 和 Strict Weakly Comparable，并需要区分等价与相等两个概念。
等价与相等
在STL中，等价和相等是两个首先需要区分的概念。如果两个元素任何一个不小于另一个，那么这两个元素被视为等价的，即“!(x < y) && !(y < x)”表示等价关系（这里用了 operator < ）；STL中用“x == y”表示两个元素的相等关系（这里用了 operator == ）。我们特别需要注意的是，判断等价关系和相等关系使用了两个不同的运算符，从另一个角度你可以认为这两个运算符分别代表了这两种概念（事实上，在技术实现上效果确实是这样的）。
例如，C++ STL中的search和includes函数，它们都是用来判断一个区间是否包含另外一个区间，但使用的比较方法（或者说运算符不同）。前者是判断元素是否相等，使用operator==；而后者是判断元素是否等价，使用operator<。因此，要想掌握好STL，这两个概念的区分是必须的。
Equality Comparable
该概念下的类型支持的有效表达式：
（1）相等性（Equality）： x == y
（2）不等性（Inequality）： x != y
该概念下的类型满足的性质：
（1）同一性（Identity）： &x == &y 意味着 x == y
（2）自反性（Reflexivity）： x == x
（3）对称性（Symmetry）： x == y 意味着 y == x
（4）传递性（Transitivity）： 如果 x == y 且 y == z，则 x == z
从技术实现角度来讲，定义了 operator == 运算符的类型都属于Equality Comparable。例如，C++中所有内置类型和指针类型都是Equality Comparable概念下的类型。C++ STL中find、adjacent_find、find_first_of、search、find_end、search_n、count、equal、mismatch、replace、replace_copy、remove、remove_copy、unique、unique_copy等函数（如果有重载，均指非传入函数对象版本）要求元素类型属于Equality Comparable，即要求该类型定义有 operator == 运算符。
LessThan Comparable
该概念下的类型支持的有效表达式：
（1）小于（Less）： x < y
（2）大于（Greater）: x > y （等价于 y < x）
（3）小于等于（Less or equal）： x <= y （等价于 !(y < x)）
（4）大于等于（Greater or equal）： x >= y （等价于 !(x < y)）
（注：我们可以用 operator < 来实现其它三个运算符）
该概念下的类型满足的性质：
（1）非自反性（Irreflexivity）： x < x 必不成立
（2）反对称性（Antisymmetry）： x < y 意味着 !(y < x)
（3）传递性（Transitivity）： 如果 x < y 且 y < z，那么有 x < z
从技术实现角度来讲，定义了 operator < 运算符的类型都属于LessThan Comparable。例如，C++中所有内置类型和指针类型都是LessThan Comparable概念下的类型。C++ STL中lexicographical_compare、min、max、min_element、max_element等函数（如果有重载，均指非传入函数对象版本）要求元素类型属于LessThan Comparable，即要求该类型定义有 operator < 运算符。
Strict Weakly Comparable
如果某个类型是LessThan Comparable，并且还支持等价概念，那么该类型就是Strict Weakly Comparable。
该概念下的类型支持的有效表达式：（同LessThan Comparable）
该概念下的类型满足的性质：（只比LessThan Comparable多了第（4）条）
（4）等价性的传递性（Transitivity of equivalence）： 如果 x 等价于 y，而且 y 等价于 z，则 x 等价于 z，即有： (!(x < y) && !(y < x)) && (!(y < z) && !(z < y)) 意味着 !(x < z) && !(z < x)
从技术实现角度来讲，定义了 operator < 运算符的类型都属于Strict Weakly Comparable。例如，C++中所有内置类型和指针类型都是LessThan Comparable概念下的类型。C++ STL中next_permutation、prev_permutation、sort、stable_sort、partial_sort、partial_sort_copy、nth_element、binary_search、lower_bound、upper_bound、equal_range、merge、inplace_merge、includes、set_union、set_intersection、set_difference、set_symmetric_difference、makde_heap、push_heap、pop_heap、sort_heap、等函数（如果有重载，均指非传入函数对象版本），以及set、map、multiset、multimap、priority_queue等容器类，都要求元素类型属于Strict Weakly Comparable，即要求该类型定义有 operator < 运算符。
如何区别？
对于Strict Weakly Comparable和LessThan Comparable，从两者的定义来看，Strict Weakly Comparable只比LessThan Comparable多了等价性的要求，即在泛型函数或者容器模板实现中需要用到元素等价性判断。从技术实现来看，两者都是基于 operator< 运算符，没有本质区别。因此，对于用户而言，两者是没有区别的，因为都只需要提供 operator < 运算符即可。
在使用STL时，我们真正需要区分的是该泛型算法或者容器模板是需要Equality Comparable 还是需要Strict Weakly Comparable。如果是前者，我们需要为之提供 operator ==；如果是后者，我们则需要为之提供 operator <。
阅读(2128) | 评论(0) | 转发(0) |
