当前位置:首页 > c++ > std::map自定义key,非严格弱序导致"invalid comparator"异常

std::map自定义key,非严格弱序导致"invalid comparator"异常

xuwenyan1个月前 (07-14)c++2060

std::map自定义key的方法是重写operator<(),但是如果没有严格弱序,极有可能导致”invalid comparator”异常,也就是提示比较器无效,如下demo代码:

class MyKey {
public:
  MyKey(int num1, int num2)
    : num1_(num1)
    , num2_(num2) {
  }

  bool operator<(const MyKey& key) const {
    return num1_ < key.num1_ ? true : num2_ < key.num2_;
  }

  int num1_;
  int num2_;
};

int main() {
  std::map<MyKey, int> map1;
  map1[MyKey(1, 2)] = 12;
  map1[MyKey(2, 1)] = 21;

  system("pause");
  return 0;
}

 

要搞清楚为什么会出现这个异常并解决,要先了解一下什么是严格弱序和operator<()是如何被std::map使用的。

什么是严格弱序?

严格弱序有三个特性:

  • 非对称性:两个关键字不能同时“严格弱序”于对方

  • 传递性:如果a“严格弱序”于b,且b“严格弱序”于c,则a必须“严格弱序”于c

  • 非自反性:如果存在两个关键字,任何一个都不“严格弱序”于另一个,则这两个关键字是相等的

通常我们认为”<”就是严格弱序,而”<=”是非严格弱序的,基于这个来看,把条件中的”严格弱序”替换成”<”,我们会发现严格弱序的三个特性是必然的,而反过来验证”<=”则是不成立的。

比较表示为:

  • a 小于 ba < b

  • a 大于 bb < a

  • a 等于 b!(a < b) && !(b < a)

operator<()如何被std::map使用的?

假设已经有一个为key1的元素,当我们需要插入一个key2的元素时:

通过单步调试代码的方式可以发现,operator<()被调用了两次,第一次是key1.operator<(key2),第二次是key2..operator<(key1)

那么问题来了,std::map的key只需要”<”比较,它是如何比较两个key相等的?这大概就是operator<()需要被调用两次的一个原因,当key1<key2不成立,而key2<key1也不成立时,key1和key2只能相等的,这就是严格弱序的非自反性。

比较条件表示如下:

  • key1小于key2:key1 < key2

  • key1大于key2:key2 < key1

  • key1等于key2:!(key1 < key2) && !(key2 < key1)

“invalid comparator”异常为何出现?

了解了上面的知识点后,我们以开头的例子分析为什么会出现”invalid comparator”异常,两个key分别为:key1(1,2)和key2(2,1),比较函数为:

bool operator<(const MyKey& key) const {
  return num1_ < key.num1_ ? true : num2_ < key.num2_;
}

我们可以得到:

key1小于key2key1大于key2
key1 < key2key2 < key1
truetrue

可以看到,key1既大于key2又小于key2,这完全就是两个自相矛盾的条件,这就是std::map报无效比较器的原因。那么比较器正确的写法是什么呢?

比较器operator<()的正确写法

依然以开头demo为例修改operator<()如下:

bool operator<(const MyKey& key) const {
  if (num1_ != key.num1_)
    return num1_ < key.num1_;

  if (num2_ != key.num2_)
    return num2_ < key.num2_;

  return false;
}
    文章作者:xuwenyan
    版权声明:本文为本站原创文章,转载请注明出处,非常感谢,如版权漏申明或您觉得任何有异议的地方欢迎与本站取得联系。
    标签: C++编程

    相关文章

    C++ 获取进程所在目录(进程全路径)

    C++ 获取进程所在目录(进程全路径)

    打开windows任务管理器,会看到很多的进程在运行,随机挑选一个,如何通过c++代码获取某一个进程的所在全路径呢?这也是在windows软件开发中经常遇到的需求。通过进程名获取进程全路径由于可能很多...

    排序算法-快速排序

    排序算法-快速排序

    排序算法的思想非常简单,在待排序的数列中,我们首先要找一个数字作为基准数(这只是个专用名词)。为了方便,我们一般选择第 1 个数字作为基准数(其实选择第几个并没有关系)。接下来我们需要把这个待排序的数...

    排序算法-冒泡排序

    排序算法-冒泡排序

    冒泡排序也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法...

    排序算法-选择排序

    排序算法-选择排序

    选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。时间复杂度O(n²)最坏情况合适发生?...

    大端模式和小端模式的区别以及如何判断大小端

    大端模式和小端模式的区别以及如何判断大小端

    在计算中,字节顺序是指数字的二进制表示内的字节(或有时是位)的顺序。它也可以更普遍地用于指代任何表示的内部排序,例如数字系统中的数字或日期的部分。在最常见的用法中,字节顺序表示多字节数字内的字节顺序,...

    c++时间戳转年月日时分秒

    c++时间戳转年月日时分秒

    时间戳转年月日时分秒是比较常用的功能,调用api localtime_s把时间戳转成tm结构体,就可以通过tm结构体中的成员得到对应的年月日时分秒,需要注意的就是tm结构体部分成员的值不是真实的值,需...

    发表评论

    访客

    ◎欢迎参与讨论,请在这里发表您的看法和观点。