strange behaviour while iterating through c++ map

Question

I have the following program which finds the frequency of the numbers.

map<int,int> mp;
vector<int> x(4);
x[0] = x[2] = x[3] = 6;
x[1] = 8;

for(int i=0;i<x.size();++i)
    mp[x[i]]++;

cout<<"size:"<<mp.size()<<endl; //Prints 2 as expected

for(int i=0;i<mp.size();++i) //iterates from 0->8 inclusive
    cout<<i<<":"<<mp[i]<<endl;

The output is as follows:

size:2
0:0
1:0
2:0
3:0
4:0
5:0
6:3
7:0
8:1

Why does it iterate over 9 times? I also tried using insert instead of [] operator while inserting elements, but the result is the same. I also tested by iterating over the map using iterator.

Answer 1

Before your printing loop, the populated mp elements are [6] and [8]. When you call cout ... << mp[i] to print with i 0, it inserts a new element [0] with the default value 0, returning a reference to that element which then gets printed, then your loop test i < mp.size() actually compares against the new size of 3. Other iterations add further elements.

You should actually do:

for (std::map<int,int>::const_iterator i = std::begin(mp);
     i != std::end(mp); ++i)
    std::cout << i->first << ':' << i->second << '\n';

...or, for C++11...

for (auto& e : mp)
    std::cout << e.first << ':' << e.second << '\n';

Answer 2

When you access mp[i], the element is added to the map if it doesn't already exist. So the first iteration of the loop will attemp to read mp[0]. This will create the element, so now mp.size() == 3. The size will continue to increase whenever an iteration attempts to access an element that doesn't exist.

When you get to i == 8, the element exists, so it doesn't increase the size. When it gets back to the top of the loop and tests 9 < mp.size(), it will fail and the loop ends.