In which case a insert in a std::map can fail?

Question

In my code I have those lines:

if(mymap.count(plan) == 0) {
    std::vector<XYZ> v;
    v.reserve(10);
    mymap.emplace(plan, v);
    std::cout << "Plan " << plan.normal << " @ " << plan.O << " added";
}

//I inserted this code for debugging
std::map<Plan, std::vector<XYZ>>::const_iterator it = mymap.find(plan);
if(it == this->intersections.end())
    std::cout << "not found";

How is it possible that I can read in the console plan added and just after not found ?

My map is declared as such:

std::map<Plan, std::vector<XYZ>, PlanComp> mymap;

At some point I thougt it comes from the comparator, but it respects irreflexivity, antisymmetry, transitivity, transitivity of equivalence (which is enough according to this blog) :

struct PlanComp {
  bool operator()(const Plan& l, const Plan& n) const {
    return (l.O.x != n.O.x) || (l.O.y != n.O.y) || (l.O.z != n.O.z)
            || (l.normal.x != n.normal.x) || (l.normal.y != n.normal.y) || (l.normal.z != n.normal.z);
  }
};

struct XYZ {
    double x;
    double y;
    double z;
};

struct Plan {
    XYZ O;
    XYZ plan;
};

The comparator should be exhibiting "less than" semantics - AKA a strict weak ordering. Yours doesn't appear to do so. — Oliver Charlesworth, Jul 19 '17 at 08:44
I don't think your "comparator" respects antisymmetry or transitivity. — LogicStuff, Jul 19 '17 at 08:45
@Deewy, `std::map` is an ordered container, use `std::unordered_map` if you don't need ordering — DAle, Jul 19 '17 at 08:47
@LogicStuff I did tried a quick fix by replacing `!=` by `<` and did not work. Would you suggest trying to compare euclidian distance between `O` and the same for `normal` ? — Deewy, Jul 19 '17 at 08:48
Use [this](https://stackoverflow.com/a/37269108/3552770) (also linked in the answer). — LogicStuff, Jul 19 '17 at 08:50

Oliver Charlesworth · Accepted Answer · 2017-07-19T11:43:32.527

Your comparator does not define a strict weak ordering (loosely speaking, "less than" semantics which define an order for your elements). Therefore your code exhibits undefined behaviour.

The simplest solution would be to use a lexicographical comparator - compare x first, then compare y only in the event of a tie, and so on. In C++11 that's even simpler; operator < for tuples already does this for you (and you can use std::tie to get the tuples). See the answers to Operator < and strict weak ordering for examples.

In which case a insert in a std::map can fail?

1 Answers1