stl 比较和boost LessThanComparable

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

C++ STL的几种常用“比较”概念简述

在C++的现行标准（C++ 98）中，由于没有类似“接口”这样的东西，我们在泛型编程时往往只能对模板类型作一些假设，要求其符合某个需求清单，也就是属于某个概念。这只是一种人为的约定，一旦该约定未被遵守，编译器可能会无法有效地发现问题原因所在。不过，在即将发布的C++ 0x中将引入concept，可以较好地解决这个问题。扯远了，让我们回到正题。

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 <。

http://www.boost.org/doc/libs/1_55_0/libs/utility/LessThanComparable.html

A type is LessThanComparable if it is ordered: it must be possible to compare two objects of that type using operator<, and operator< must be a strict weak ordering relation.

http://book.51cto.com/art/201205/335224.htm

4.8.1 基本运算概念

由于C++可重载的操作符很多，因此operators库是由多个类组成的，分别用来实现不同的运算概念，比如less_than_comparable定义了<系列操作符，left_shiftable定义了<<系列操作符。operators中的概念非常多，囊括了C++中的大部分操作符重载，在这里我们先介绍一些最常用的算术操作符：

equality_comparable：要求提供==，可自动实现!=，相等语义；

less_than_comparable：要求提供<，可自动实现>、<=、>=；

addable：要求提供+=，可自动实现+；

subtractable：要求提供-=，可自动实现-；

incrementable：要求提供前置++，可自动实现后置++；

decrementable：要求提供前置--，可自动实现后置--。

equivalent：要求提供<，可自动实现==，等价语义，它与equality_comparable的区别请参见4.8.5节。

这些概念在库中以同名类的形式提供，用户需要以继承的方式来使用它们。继承的修饰符并不重要（private、public都可以），因为operators库里的类都是空类，没有成员变量和成员函数，仅定义了数个友元操作符函数。

例如，less_than_comparable的形式是：

template <class T>
struct less_than_comparable {
friend bool operator>(const T& x, const T& y);
friend bool operator<=(const T& x, const T& y);
friend bool operator>=(const T& x, const T& y);
};

如果要同时实现多个运算概念则可以使用多重继承技术，把自定义类作为多个概念的子类，但多重继承在使用时存在很多问题，稍后将看到operators库使用了特别的技巧来解决这个问题。

我们使用之前4.5.3节定义的三维空间的点point作为opreators库的示范类，在此把它重新定义如下（去掉了swap函数）：

class point
{
int x, y, z;
public:
explicit point(int a=0, int b=0, int c=0):x(a),y(b),z(c){}
void print()const
{ cout << x <<","<< y <<","<< z << endl; }
};

我们先来实现less_than_comparable，它要求point类提供<操作符，并由它继承。假定point的小于关系是三个坐标值的平方和决定的，下面的代码示范了less_than_comparable的用法，只需要为point增加父类，并定义less_than_comparable概念所要求的operator<：

#include <boost/operators.hpp>
class point:
boost::less_than_comparable<point> //小于关系，私有继承
{
public:
friend bool operator<(const point& l, const point& r)
{
return (l.x*l.x + l.y*l.y +l.z*l.z <
r.x*r.x + r.y*r.y +r.z*r.z);
}
... //其他成员函数
};

less_than_comparable作为基类的用法可能稍微有点奇怪，它把子类point作为了父类的模板参数：less_than_comparable，看起来好像是个"循环继承"。实际上，point类作为less_than_comparable的模板类型参数，只是用来实现内部的比较操作符，用作操作符函数的类型，没有任何继承关系。less_than_comparable生成的代码可以理解成这样：

//template<TT = point>
struct less_than_comparable
{
friend bool operator>=(const point& x, const point& y)
{ return !(x < y); }
}

(

友元函数是可以直接访问类的私有成员的非成员函数。它是定义在类外的普通函数，它不属于任何类，但需要在类的定义中加以

声明，声明时只需在友元的名称前加上关键字friend

)

明白了less_than_comparable的继承用法，剩下的就很简单了:point类定义了一个友元operator<操作符，然后其余的>、<=、>=就由less_than_comparable自动生成。几乎不费什么力气，在没有污染名字空间的情况下我们就获得了四个操作符的能力：

int main()
{
point p0, p1(1,2,3), p2(3,0,5), p3(3,2,1);
assert(p0 < p1 && p1 < p2);
assert(p2 > p0);
assert(p1 <= p3);
assert(!(p1<p3)&&!(p1>p3) );
}

同样我们可以定义相等关系，使用equality_comparable，规则是point的三个坐标值完全相等，需要自行实现operator==：

class point:boost::less_than_comparable<point> //使用多重继承
,boost::equality_comparable<point> //新增相等关系
{
public:
friend bool operator<(const point& l, const point& r)
{ /*同前*/ }
friend bool operator==(const point& l, const point& r)
{ return r.x == l.x && r.y == l.y && r.z == l.z; }
};

然后我们就自动获得了operator!=的定义：

point p0, p1(1,2,3), p2(p1), p3(3,2,1);
assert(p1 == p2);
assert(p1 != p3);

在使用operators库时要注意一点，模板类型参数必须是子类自身，特别是当子类本身也是个模板类的时候，不要错写成子类的模板参数或者子类不带模板参数的名称，否则会造成编译错误。假如我们改写point类为一个模板类：

template<typename T> class point {...}

那么如下的形式都是错误的：

template<typename T> class point：boost::less_than_comparable<T>
template<typename T> class point：boost::less_than_comparable<point>

正确的写法应该是：

template<typename T> class point：boost::less_than_comparable< point<T> >

因为只有point才是模板类point的全名。

4.8.3 基类链

多重继承一直是C++中引发争论的话题，喜欢它的人和讨厌它的人几乎同样多。总的来说，多重继承是一种强大的面向对象技术，但使用不当也很容易引发诸多问题，比如难以优化和经典的"钻石型"继承。

operators库使用泛型编程的"基类链"技术解决了多重继承的问题，这种技术通过模板把多继承转换为链式的单继承。

前面当讨论到less_than_comparable<point>这种用法时，我们说它不是继承，然而，现在，我们将看到它居然真的可以实现继承的功能，这从一个方面展示了泛型编程的强大威力。

operators库的操作符模板类除了接受子类作为比较类型外，还可以接受另外一个类，作为它的父类，由此可以无限串联链接在一起（但要受编译器的模板编译能力限制），像这样：

demo: x< demo, y<demo, z<demo,...> > >

使用基类链技术，point类的基类部分可以是这样：

boost::less_than_comparable<point, //注意这里
boost::equality_comparable<point> > //是一个有很大模板参数列表的类

对比一下多重继承的写法：

boost::less_than_comparable<point>, //注意这里
boost::equality_comparable<point> //有两个类

代码非常相似，区别仅仅在于模板参数列表结束符号（>）的位置，如果不仔细看可能根本察觉不出差距。但正是这个小小的差距，使基类链通过模板组成了一连串的单继承链表，而不是多个父类的多重继承。

例如，如果为point类再增加加法和减法定义，继承列表就是：

class point:
less_than_comparable<point, //小于操作
equality_comparable<point, //相等操作
addable<point, //加法操作
subtractable<point //减法操作
> > > >
{...}

基类链技术会导致代码出现一个有趣的形式：在派生类的基类声明末尾处出现一长串的>（模板声明的结束符），在编写代码时需要小心谨慎以保证尖括号的匹配，使用良好的代码缩进和换行可以减少错误的发生。

我的实现less than compare的方法：

下面代码有错误,去掉MyLessThanComparable的继承自T就行了。
class Point2;
template<class T>
struct MYLessThanComparable :T
{
friend bool operator>=(const T& l, const T& r)
{
return !(l < r);
}
friend bool operator>(const T& l, const T& r)
{
return r < l; //这里z注意:r<l,自然l>r
}
friend bool operator<= (const T& l, const T& r)
{
return !(l>r);
}};class Point2 :MYLessThanComparable<Point2>
{
public:
explicit Point2(int a = , int b = , int c = ) :x(a), y(b), z(c)
{ }
void print() const
{
cout << x << "," << y << "," << z << endl;
} friend bool operator<(const Point2& l, const Point2& r) //友元函数，与这个类无关 //:point类定义了一个友元operator<操作符，然后其余的>、<=、>=就由less_than_comparable自动生成
{
return (l.x*l.x + l.y*l.y + l.z*l.z <
r.x*r.x + r.y*r.y + r.z*r.z); }
private:
int x, y, z;
};