Duplicate removal in std::map

Question

Similar to the link below,

https://stackoverflow.com/a/30424281/1442787

I have my class Point with member variables double x,y,z.

I have overloaded operator < in my class to insert values into std::map

bool Point::operator<(const Point &p)const{
    return (   x < p.x
            || (   x == p.x
                && (   y < p.y
                    || (   y == p.y
                        && z < p.z))));
}

I have defined my map with Point class as key and std::pair as value

typedef std::pair<int,int> mypair;
typedef std::map<Point, mypair> mymap;

std::map does not allow the insertion of duplicate keys.

But,in my code, while inserting the key/value pair, the duplicate key is also getting inserted as shown below

map:0.436612,16.527741,0.000000,22,2
map:0.454781,17.427262,15.264347,74,12
map:0.454781,17.427262,15.264347,27,11
map:0.608370,17.373443,20.124160,21,13
map:0.608370,17.373443,20.124160,69,11

What could be the reason for duplicate insertion?

I bet on comparing doubles for equality being the issue. `0.454781` and `0.454781` look equal, but maybe they are not — 463035818_is_not_an_ai, Sep 04 '17 at 11:58
Using your favored internet search engine for example: https://stackoverflow.com/questions/554063/how-do-i-print-a-double-value-with-full-precision-using-cout. — Andre Kampling, Sep 04 '17 at 12:05
two doubles are almost never equal, use an epsilon tolerance — 463035818_is_not_an_ai, Sep 04 '17 at 12:13
I have checked with std::setprecision (16).They are equal without any difference. — user1442787, Sep 04 '17 at 12:43
@tobi303 with overloading < operator to sort the values,it is not possible to use epsilon tolerance — user1442787, Sep 04 '17 at 12:45
@user1442787 Yes it is: `abs(x - p.x) < (std::numberic_limits::epsilon * std::max(x, p.x))` (or some other static epsilon) — Caleth, Sep 04 '17 at 13:39

score 0 · Answer 1 · edited Sep 04 '17 at 13:40

Your problem is that floating point values rarely compare as equal, especially if they are result of computations (but they can be inequal in more trivial cases because they are stored with different sizes in the memory than in registers).

First, you should avoid using floating points as keys.

If you really want to do it anyway, then you should have some domain-specific comparison operator. You can use epsilon-tolerance (two floats are equal if abs(x - y) < e, where e is some small value), or you can use a tolerance value that scales with the number (basically, yielding something like "the two numbers are equal to a certain number of significant digits"). Unit test libraries, such as the Boost Test library use these kinds of comparisons. For points, you can use distance based equality: two points are equal, if they are closer to each other than a certain value.

Previously I mentioned equality predicates. You can make it into comparison like this:

bool Point::operator==(const point &p)const{
    // Using Manhattan distance here.
    return (x - p.x) + (y - p.y) + (z - p.z) < 0.0001;
}

bool Point::operator<(const Point &p)const{
    return p != *this && (   x < p.x
            || (   x == p.x
                && (   y < p.y
                    || (   y == p.y
                        && z < p.z))));
}

This code is not better than the original one as you might have the same problem as with original code if there are points within the tolerance as you could for example have a point `a` that is within tolerance of `b` and a point `c` that is within tolerance of point `b` but not point `a`. — Phil1970, Sep 04 '17 at 13:07
So one either has to do rounding before adding points in which case and then do comparison with appropriate tolerance (or store scaled values) or ensure that its code is tolerant to those cases... — Phil1970, Sep 04 '17 at 13:09
That's why I said that it's generally a bad idea to use floating point as a map key. It's conceptionally a continuous value, which makes no sense to be used as a key. — petersohn, Sep 04 '17 at 13:43

score -1 · Answer 2 · answered Sep 04 '17 at 13:27

-1

I would recommend you to use a std::multimap instead as it can store duplicate values...

And if you want to ensure that a given point you are about to add is not within a small tolerance of an existing point then I would check any point whose x coordinate is within the tolerance.

Thus, to find such point, you might create a point:

 Point search { x - tolerance, -Inf, -Inf };

And then use lower_bound as the starting point and test any subsequent point until its x coordinate is greater than x + tolerance.

answered Sep 04 '17 at 13:27

Phil1970

2,605
2
14
15

OP wants unique values, and has (near) duplicates, not the other way around – Caleth Sep 04 '17 at 13:43
Have you read my whole answer? My **second suggestion** say exactly what to do if OP wants unique values. – Phil1970 Sep 04 '17 at 13:51
Thanks for all your feedback using epsilon in the comparator function helps! – user1442787 Sep 04 '17 at 14:08

Duplicate removal in std::map

2 Answers2