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

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

xuwenyan4周前 (07-14)c++2000

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++如何实现远程注入dll

    C++如何实现远程注入dll

    如何把我们的代码放到别人的进程里面运行?我们需要做一个dll动态库,然后使用远程注入技术,将我们的dll注入到别人的进程里面,然后加载起来。这样我们的代码就可以在别人的进程里面工作了。注入代码#inc...

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

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

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

    c++函数模板参数类型限定

    c++函数模板参数类型限定

    函数模板函数模板可以实现对不同数据类型做统一操作,比如比较两个数据的大小:template<typename T> bool compare(T& ...

    排序算法-冒泡排序

    排序算法-冒泡排序

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

    排序算法-选择排序

    排序算法-选择排序

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

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

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

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

    发表评论

    访客

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