CODEWITHSUNDEEP
c++stdmap
tejas
tejas

Reputation: 1943

queer behavoir of std::map

I have a 

std::map<a,std::vector<b>> m;

a is a struct 

struct a
{
  std::string c,d;
bool operator<(const a &o)
{ return !(c==o.c && d==o.d);}
}

I am populating the map this way 

for(/*blah blah*/)
{
  m[A].push_back(B)
}

and after populating i am printing some stuff

std::cout << "Size:" << m.size() << std::endl;
int i=0;
for(std::map<a,std::vector<b>>::iterator it = m.begin(); it != m.end();i++,it++)
{
   std::cout << "[" <<i <<"] " << it->second.size() << std::endl;
}

and the output i am getting is

Size: 12
[0] 1
[1] 3

can someone explain why map::size() is showing 12 while it iterates over just 2 elements?

Upvotes: 3

Views: 136

Answers (2)

david.pfx
david.pfx

Reputation: 10863

Out of curiosity, I tried this code in VS2010. It won't compile.

bool operator<(const a &o) { return !(c==o.c && d==o.d); }

Error as follows.

error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const StdMapTest::Exec::a' (or there is no acceptable conversion)

bool operator<(const a &o) const { return !(c==o.c && d==o.d); }

The above line compiles, but throws an assertion:

Expression: invalid operator<

Finally I tried this.

    bool operator<(const a &o) const { return (c == o.c) ? d < o.d : c < o.c; }

Compiles and seems to work correctly.

I think it would be fair to say that a good enough compiler would have made this question unnecessary. I'm sure VS2010 is not the only one that can perform this kind of diagnosis.

Upvotes: 2

M.M
M.M

Reputation: 141648

Change the comparison function to

bool operator<(const a &o) const
{
    if ( c == o.c )
         return d < o.d;

    return c < o.c; 
}

Note that making it a non-member function is more useful in general.

Your comparison function has to follow these rules:

If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

— comp(a, b) && comp(b, c) implies comp(a, c)

— equiv(a, b) && equiv(b, c) implies equiv(a, c)

The map uses the comparison function in generating its data structure and iterating over it, so if your function is wrong then anything can happen.

Upvotes: 3

Related Questions