c++ - map.find() 看似随机返回 map.end()

Question

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

#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

现在比较#1与 #2将返回 true因为第二个索引较小 (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;
  }
};

这是一个 demo .