keys not unique in c++ map

Question

I have a std::map in my program which stores pairs of values. I want the keys in the map to be unique - which is the expected behavior of a std::map class. But when I insert the pairs into it, some keys are repeated. How do I solve this problem?

My code is as follows:

map<float,vector<float> *> inpDataMap;
inpDataMap.clear();
    for(int i = 0; i < input.getNum(); i++)
    {

        float xVal = input[i][0];
        float yVal = input[i][1];

        if(inpDataMap.count(xVal) > 0)
        {
            myfile << i << " repeated xval: " << xVal << " : " << yVal << endl;
            inpDataMap[xVal]->push_back(yVal);
            myfile << "repeated value pushed" << endl;
        }
        else
        {
            vector<float> *inVec = new vector<float>;
            inVec->push_back(yVal);
            inpDataMap[xVal] = inVec;
            myfile << i << " not repeated:" << xVal << ":" << yVal << endl;
        }

    }

As you can see that the map I have here is actually an association of a float and a vector of associated floats. If there's already a key existing, the value is added to the vector corresponding to that key. But like I said, the keys are not stored uniquely. Can anybody help me to solve this problem?

Rakesh.

Answer 1

The problem with floats is that you can't simply use == operator to make sure they are equal. For example, one number might be 7.0 but another one can be actually 7.000000000015, even though it was supposed to be 7.0 as well.

The way to go is to define a precision with which you would like to compare these floating point numbers and check whether their difference is less than the precision. For the given example, if we pick a precision of 0.000001, these 2 numbers are equal because | (7.000000000015 - 7.0)| < 0.000001.

You can implement this kind of logic via a comparator of your own. std::map has a comparator class as one of its template arguments.

Update:

It turned out that there is really no general way of solving a problem with floating point keys in a map. The problem outlined in a comment is very serious. Map comparator needs to guarantee a strict weak ordering of the keys being inserted, however it doesn't seem feasible for a general case for floats.

Suppose you are inserting 3 keys: a, b and c. It is possible that a < b is false (because they are equal with a given precision), b < c is false (for the same reason as a < b), but it's possible that a and c could be so "far" from each other, that a < c will return true (they are not equal), which, which is bad.

To get over that you need to have some knowledge of the expected keys. If they are distant enough from each other (the distance is bigger than a usual floating point arithmetic error), a proper comparator can be written.

For an example of a comparator you can turn to https://stackoverflow.com/a/6684830/276274

Answer 2

A map can't contain duplicate keys. You probably think it is because of float precision - some values that to you appear to be equal are actually different. To go around this, you can use a custom Compare class with your map to treat close enough floats as equal:

map<float,vector<float> *, CustomCompare> inpDataMap;