stl 比较和boost LessThanComparable

时间:2022-08-30 14:31:12

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的形式是:

  1. template <class T>
  2. struct less_than_comparable {
  3. friend bool operator>(const T& x, const T& y);
  4. friend bool operator<=(const T& x, const T& y);
  5. friend bool operator>=(const T& x, const T& y);
  6. };

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

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

  1. class point
  2. {
  3. int x, y, z;
  4. public:
  5. explicit point(int a=0, int b=0, int c=0):x(a),y(b),z(c){}
  6. void print()const
  7. {   cout << x <<","<< y <<","<< z << endl;  }
  8. };

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

  1. #include <boost/operators.hpp>
  2. class point:
  3. boost::less_than_comparable<point>              //小于关系,私有继承
  4. {
  5. public:
  6. friend bool operator<(const point& l, const point& r)
  7. {
  8. return (l.x*l.x + l.y*l.y +l.z*l.z <
  9. r.x*r.x + r.y*r.y +r.z*r.z);
  10. }
  11. ...                                             //其他成员函数
  12. };

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

  1. //template<TT = point>
  2. struct less_than_comparable
  3. {
  4. friend bool operator>=(const point& x, const point& y)
  5. { return !(x < y); }
  6. }

(

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

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

)

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

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

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

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

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

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

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

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

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

  1. template<typename T> class point:boost::less_than_comparable<T>
  2. template<typename T> class point:boost::less_than_comparable<point>

正确的写法应该是:

  1. template<typename T> class point:boost::less_than_comparable< point<T> >

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

4.8.3  基类链

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

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

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

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

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

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

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

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

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

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

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

  1. class point:
  2. less_than_comparable<point,             //小于操作
  3. equality_comparable<point,              //相等操作
  4. addable<point,                          //加法操作
  5. subtractable<point                      //减法操作
  6. > > > >
  7. {...}

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

我的实现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;
};

编译报错:

error C2504: “Point2”: 未定义基类
 参见对正在编译的类 模板 实例化“MYLessThanComparable<Point2>”的引用

已经声明和定义了Point2,为什么还一直报这个错误,

看了这个帖子:http://bbs.csdn.net/topics/390448140

定义派生类的头文件上下文中,必须直接或间接地看到基类的定义,单单给出基类的前置声明编译无法通过

上面的Point2和MYLessThanComparable相互继承,导致出现不管谁在前谁在后,一定有一个会报错:未定义基类,究其原因还是“在定义派生类的头文件上下文中,必须直接或间接的看到基类的定义,单单给出声明时不行的”

后来想了下,MYLessThanComparable不必继承Point2,继承没什么用,去掉就行了。