首页 > 代码库 > 深入探讨关联容器的“等价”机制

深入探讨关联容器的“等价”机制

C++ STL中常用的关联容器有std::set、std::map等,这些关联容器具有容器内部元素自动排序的能力。

需要了解的是,在容器内部,对元素进行排序根据的是“等价”关系而不是“相等”关系,更确切的说,是元素所属类型的“<”运算符而不是“==”运算符决定了容器内部的排序行为。

以set为例,当以下表达式返回为true的时候,容器将两个元素v1、v2判定为等价关系,此时若set中已有v1,则v2将不能再被添加到容器里:

!(v1<v2) && !(v2<v1)    //表达式1

这样一来,对关联容器而言,有两个点需要注意:

1.定义一个关联容器变量,需要保证其元素的类型定义了<操作符,否则便会编译报错。有两种定义<操作的方式:

   1) 首先,可以在类的内部定义operator<操作符。

   2) 或者,另外定义一个比较类,内含一个定义了元素类型比较行为的函数。如下代码所示:

class AType  //元素类型
{
public:
	int data;
	AType(int d){data=http://www.mamicode.com/d;}>

2.为容器定义的"<"操作符不得出现以下情况:当两个元素事实上“相等”时,运用前面所描述的表达式1得到的结果却是“等价”的。

举个例子,假设我们定义<=为set的<操作符,那么可以这么样写:

sed::set<int,less_equal<int>> s;

 我们首先插入一个元素10,然后在插入一个元素10:

s.insert(10)
s.insert(10)

 运用表达式1,我们可以得到false。说明这前后两个10之间是不等价的,因此s中就会有两个10元素,这是严重违反set定义的。

   因此,你需要记住,比较函数的返回值表明的是按照该函数定义的排列顺序,一个值是否在另一个值之前。相等的值从来不会有前后顺序关系,所以,对于相等的值,比较函数应当始终返回false。

 

深入探讨关联容器的“等价”机制