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

user_12596733 0
Viewed 56

I am using a custom comparator in a C++ map. Unfortunately map.find() often doesn't find the desired entry in the map. Code to reproduce this is very simple:

#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;
}

Output should be for all lines "found", but I get:

data1 found
data2 not found
data3 found
data4 found

I suspect the problem is my comparison function, but I don't see my mistake.

comparator stdmap find c++
1 Answers

Your comparison function is not correct. Consider what happens for the following keys:

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

Now comparing #1 with #2 will return true since the 2nd index is less (2 < 3). But, comparing #2 with #1 will also return true since the 3rd index is less (2 < 3).

This violates the requirements that the keys have a strict weak ordering, i.e. a < b and b < a can't both be true.

You can fix this by just using operator< on arrays like this:

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

Here's a demo.

user_83728530
Related