C++ STL 中 "大"、"小" 和 "相等" 的概念

STL 中关联容器内部的元素是排序的。STL 中的许多算法也涉及排序、查找。这些容器和算法都需要对元素进行比较,有的比较是否相等,有的比较元素大小。

在 STL 中,默认情况下,比较大小是通过 < 运算符进行的,和 > 运算符无关。在 STL 中提到 “大”、”小” 的概念时,以下三个说法是等价的:

  • x 比 y 小

  • 表达式 x < y 为真

  • y 比 x 大

一定要注意,y 比 x 大意味着 x < y 为真,而不是 y > x 为真。y > x 的结果如何并不重要,甚至 y > x 是没定义的都没有关系。

在 STL 中,x 和 y 相等也往往不等价于 x == y 为真。对于在未排序的区间上进行的算法,如排序查找算法 find,查找过程中比较两个元素是否相等用的是 == 运算符;但是对于在排好序的区间上进行查找、合并等操作的算法(如折半查找算法 binary_search,关联容器自身的成员函数 find)来说,x 和 y 相等是与 x < y 和 y < x 同时为假 等价的,与 == 运算符无关。看上去 x < y 和 y < x 同时为假就应该和 x == y 为真等价,其实不然。例如下面的 class A:

1
2
3
4
5
6
class A
{
int v;
public:
bool operator<(const A& a) const { return false; }
};

可以看到,对任意两个类 A 的对象 x、y,x < y 和 y < x 都是为假的。也就是说,对 STL 的关联容器和许多算法来说,任意两个类 A 都是相等的,这与 == 运算符的行为无关。

综上所述,使用 STL 中的关联容器和许多算法时,往往需要对 < 运算符进行适当的重载,使得这些容器和算法可以用 < 运算符对所操作的元素进行比较。最好将 < 运算符重载为全局函数,因为在重载为成员函数时,在有些编译器上会出错(由其 STL 源代码的写法导致。)