首页 > 代码库 > 深入探讨关联容器的“等价”机制
深入探讨关联容器的“等价”机制
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。
深入探讨关联容器的“等价”机制
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。