map.find() returns 看似随机 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

现在将 #1 与 #2 进行比较将 return true 因为第二个索引较小 (2 < 3)。但是，将 #2 与 #1 进行比较也会 return 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。

map.find() returns 看似随机 map.end()

map.find() returns seemingly randomly map.end()

c++

stdmap

find

comparator