map.find() 返回看似随机的 map.end()

Question

我在 C++ 中使用自定义比较器map。不幸的是，map.find()通常不会在地图中找到所需的条目。重现这一点的代码非常简单：

#include <array>
#include <iostream>
#include <map>

using namespace std;

typedef struct DATA_t {
  array<int, 4> data;
} DATA_t;

struct DATA_cmp {
  bool operator()(const DATA_t& a, const DATA_t& b) const {
    for (int i = 0; i < a.data.size(); ++i)
      if (a.data[i] < b.data[i]) return true;
    return false;
  }
};

int main(int argc, char** argv) {
  map<DATA_t, int, DATA_cmp> index;
  DATA_t data1 = {1, 2, 4, 8};
  DATA_t data2 = {1, 3, 5, 7};
  DATA_t data3 = {0, 6, 7, 8};
  DATA_t data4 = {0, 1, 1, 2};
  index[data1] = 1;
  index[data2] = 2;
  index[data3] = 3;
  index[data4] = 4;
  cout << "data1 " << (index.find(data1) == index.end() ? "not found" : "found") << endl;
  cout << "data2 " << (index.find(data2) == index.end() ? "not found" : "found") << endl;
  cout << "data3 " << (index.find(data3) == index.end() ? "not found" : "found") << endl;
  cout << "data4 " << (index.find(data4) == index.end() ? "not found" : "found") << endl;
  return 0;
}

输出应该是“找到”的所有行，但我得到：

data1 found
data2 not found
data3 found
data4 found

我怀疑问题是我的比较功能，但我没有看到我的错误。

Answer 1

您的比较功能不正确。考虑以下键会发生什么：

{ 1, 2, 3, 4 }  // #1
{ 1, 3, 2, 4 }  // #2

现在比较#1with #2will returntrue因为第二个索引更少 (2 < 3)。但是，在比较#2用#1也将返回true由于第三指数是以下（2 <3）。

这违反了键具有严格弱排序的要求，即a < b和b < a不能同时为真。

您可以通过仅operator<在这样的数组上使用来解决此问题：

struct DATA_cmp {
  bool operator()(const DATA_t& a, const DATA_t& b) const {
    return a.data < b.data;
  }
};

这是一个演示。