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.

It's unreal, that map contains repeated keys. Example please. — ForEveR, Oct 17 '12 at 09:19
That is the standard behavior.It is your responsibility to ensure you do not add duplicate entries to a `std::map`, if you need duplicate key entries use `std::multimap`. — Alok Save, Oct 17 '12 at 09:19
The problem is not with the map, but with your input. The map stores unique keys fine. — Olaf Dietsche, Oct 17 '12 at 09:21
Keys are unique in a std::map by definition. You say this yourself. Then you say actually they aren't unique. I'm afraid your question makes no sense to me. — john, Oct 17 '12 at 09:22
do you have a set of test values passed in input that reproduce the issue? — Marius, Oct 17 '12 at 09:22

score 10 · Answer 1 · edited May 23 '17 at 12:24

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

Does your comparator follow strict weak ordering? – john Oct 17 '12 at 09:33 — john, Oct 17 '12 at 09:33

score 6 · Answer 2 · answered Oct 17 '12 at 09:22

6

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;

answered Oct 17 '12 at 09:22

Luchian Grigore

253,575
64
457
625

3

You need to be *very* careful if you do this that your custom compare properly implements a strict weak comparison. It's very easy to get it wrong if you are treating values that are "close enough" as equal... – jcoder Oct 17 '12 at 09:31

score 0 · Answer 3 · answered Oct 17 '12 at 09:27

How about storing a std::vector instead of a pointer to vector:

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];
    inpDataMap[xVal].push_back(yVal);
}

keys not unique in c++ map

3 Answers3