I get duplicate entries in Map while using Map of vectors

[arunapad]

Hi ,

I am trying to create a Map that will have vector as its key and an integer as value.
Each vector will be a member of a particular structure. I am new to using maps.
When i tried the code below: I am getting duplicate entries in the map.

If any one can help on this that would be great, Thanks in Advance

Code :

#include <iostream>
#include <string.h>
#include <vector>
#include <map>
#include <utility>

using namespace std;

typedef struct A
{
     int x ;
     int y ;
     int value;
}Literal;

struct vectComp
{


    bool operator() (const vector<Literal> v1,const vector<Literal> v2)
    {
           int i , j;
           bool lit_equal = false;
           cout<<"V1.size and v2.size "<<v1.size() <<", "<<v2.size()<<endl;
           if(v1.size()!= v2.size())
           {
               cout<<"TRUE"<<endl;
               return true;
            }
            else
            {
                 for(i=0;i<v1.size();i++)
                {   
                     lit_equal = false;
                     for(j=0;j<v2.size();j++)
                    {
                          if((v1[i].x== v2[j].x) && (v1[i].y== v2[j].y) &&(v1[i].value== v2[j].value))
                          {                        

                             /*  cout<< " v1 X and v2 X "<<v1[i].x << ", "<<v2[j].x<<endl;
                               cout<< " v1 y and v2 y "<<v1[i].y << ", "<<v2[j].y<<endl;
                               cout<< " v1 value and v2 value"<<v1[i].value << ", "<<v2[j].value<<endl;
                               cout<<"v[i] and v[j] MATCHES TRUE"<<endl;*/
                               lit_equal = true;
                               break;
                          }
                    }
                    if(lit_equal == false)
                    {
                       break;
                    }
                }
                if(lit_equal == false)
                {
                        cout<<"TRUE"<<endl;
                        return true;
                }
                else
                {
                        cout<<"FALSE"<<endl;
                        return false;
                }
            }
    }

};

map< vector< Literal >,int,vectComp >mymap;
map< vector< Literal >,int >::iterator it;
map< vector< Literal >,int >::key_compare mycomp;
pair< map< vector< Literal >,int >::iterator,bool >ret;

int main()
{
      int i , j;
      for(i=0;i<4;i++)
      {
           vector< Literal > v;
           for(j=0;j<(1+i);j++)
          {
                    Literal sL;
                    sL.x= j+i;
                    sL.y = (j+1+i);
                    sL.value = (j+2+i);

                    v.push_back(sL);
          }
         //mymap.insert(pair< vector< Literal >,int >(v,i));
         mymap.insert(std::make_pair(v,i+1));
         cout<<"-------------------------------------------"<<endl;

      }

      for(i=0;i<3;i++)
      {
           vector< Literal > v1;
           for(j=0;j<(1+i);j++)
          {
                    Literal sL1;
                    sL1.x= j+i;
                    sL1.y = (j+1+i);
                    sL1.value = (j+2+i);

                    v1.push_back(sL1);
          }
         //mymap.insert(pair< vector< Literal >,int >(v,i));
         mymap.insert(std::make_pair(v1,i+1));
        cout<<"-------------------------------------------"<<endl;
      }



     cout<<"mymap.size() is " <<(int)mymap.size()<<endl;

     for(it=mymap.begin(); it!= mymap.end();it++)
    {
          cout<<"Key : "<<endl;
          for(i=0;i<(*it).first.size();i++)
         {
               cout<< (*it).first[i].x<<(*it).first[i].y<<(*it).first[i].value<<"\t";
         }
         cout <<" Value : "<<(*it).second<<endl;
         cout<< "Vector Size : "<<(*it).first.size()<<endl;
    }



      return 0;
}

[SgtMe]

Code tags please :) I can't read your code like that properly with all the whitespace removed.

[arkoenig]

In order for Map to work correctly, you have to give it a comparison function that acts like <, in the sense that it is nonreflexive, antisymmetric, and transitive.

Your vectComp::operator() does not work that way. I do not need to read much of the code to determine this, because of the statement

if (v1.size() != v2.size()) return true;

You are saying that your comparison function returns true for any two vectors of different sizes, which means that it is symmetric. In other words, if the function returns true for two vectors v1 and v2, it will also return true for v2 and v1. So it is symmetric instead of antisymmetric, and that won't work.

Also, I note in passing that the comparison function passes its arguments by value, which means that it copies the entire vectors every time you compare them. That's a substantial waste of time.

I suggest you look up the built-in function named lexicographical_compare and use that as the basis for your vector comparison.

[arunapad]

I have put comment to the code. I can understand that my compare() is not asymmetric.
The lexical compare will work but am not understanding where I should use lexicographical_compare funtion. Can you Help on this ???? ?

struct vectComp
{
    bool operator() (const vector<Literal> v1,const vector<Literal> v2)
    {
           int i , j;
           bool lit_equal = false;
       cout<<"V1.size and v2.size "<<v1.size() <<", "<<v2.size()<<endl;
       if(v1.size()!= v2.size())
       {
           cout<<"TRUE"<<endl;
           return true;
       }
           else
       {
           for(i=0;i<v1.size();i++)
           {   
          lit_equal = false;
          for(j=0;j<v2.size();j++)
          {
            if((v1[i].x== v2[j].x) && (v1[i].y== v2[j].y) &&(v1[i].value== v2[j].value))
            {   
               lit_equal = true;
               break;
            }
        }
        if(lit_equal == false)
        {
           break;
        }
        }
        if(lit_equal == false)
        {
           cout<<"TRUE"<<endl;
           return true;
        }
        else
        {
        cout<<"FALSE"<<endl;
        return false;
        }
    }
    }

};
map< vector< Literal >,int,vectComp >mymap;
map< vector< Literal >,int >::iterator it;
pair< map< vector< Literal >,int >::iterator,bool >ret;

int main()
{
      int i , j;
      //Inserting 3 entries in map
      for(i=0;i<4;i++)
      {
           vector< Literal > v;
           for(j=0;j<(1+i);j++)
          {
            Literal sL;
            sL.x= j+i;
            sL.y = (j+1+i);
            sL.value = (j+2+i);
            v.push_back(sL);
          }
         //mymap.insert(pair< vector< Literal >,int >(v,i));
         mymap.insert(std::make_pair(v,i+1));
         cout<<"-------------------------------------------"<<endl;
      }

      //To insert 4th entry in map that is similar to the 1st entry that laready exists
      for(i=0;i<3;i++)
      {
           vector< Literal > v1;
           for(j=0;j<(1+i);j++)
          {
              Literal sL1;
              sL1.x= j+i;
                  sL1.y = (j+1+i);
              sL1.value = (j+2+i);
              v1.push_back(sL1);
          }
         //mymap.insert(pair< vector< Literal >,int >(v,i));
         mymap.insert(std::make_pair(v1,i+1));
        cout<<"-------------------------------------------"<<endl;
        break;
      }
        cout<<"mymap.size() is " <<(int)mymap.size()<<endl;
        for(it=mymap.begin(); it!= mymap.end();it++)
    {
        cout<<"Key : "<<endl;
        for(i=0;i<(*it).first.size();i++)
        {
         cout<< (*it).first[i].x<<(*it).first[i].y<<(*it).first[i].value<<"\t";
        }
        cout <<" Value : "<<(*it).second<<endl;
        cout<< "Vector Size : "<<(*it).first.size()<<endl;
    }

    return 0;
}

[arunapad]

What I can find in my o/p on executing the above code is the following?

1. I insert a vector of size 1 into map and that is the first entry
2. I insert a vector of size 2 into map. When i try to do this map internally compares
2 with 1st entry.
3. I insert a vector of size 3 into map. When i try to do this map internally compare the new entry with 2nd and the 1st entry.
4. I try to insert a 4th entry into map that that has size 1 and is same as 1st entry that already exists in map. In this case the map compares the new entry with 2nd , 3rd entry in the map but not with the 1st entry .. Why is this happening ???

[arkoenig]

In order for Map to work correctly, you have to give it a comparison function that takes two arguments and yields true if the first is conceptually "less than" the second.

All of the comparisons of vector values that appear in your code are equality comparisons.

You probably want to do something like this:

bool operator() (const vector<Literal>& v1,const vector<Literal>& v2)
{
    return std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());
}

[arunapad]

I tried the above method. Its doesnt work. How do we compare the data inside vector against the vector that we are gonna insert?? the data may be jumbled too .
I mean vector 1: 111 123 456
vector 2: 123 456 111
vector 1 and vector 2 are similar. Is this check possible by just using < operator

[arkoenig]

When you say that it doesn't work, what do you mean? What did you try? What happened when you tried it?

The answer to your question "How do we compre the data..." is found in the definition of lexicographical_compare. I suggest you look it up.