C++ map要素の存在の確認について

AtCoderで以下の問題を解いていました。
高橋くんと魔法の箱

高橋くんは魔法の箱を持っています。

この箱に整数を入れるとそれに対応した整数が出てきます。
出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。
高橋くんは任意の整数 x について、x を入れた時と 2xを入れた時に出てくる整数が同じであることに気づきました。
高橋くんが入れた整数が N個与えられるので、最大で何種類の整数が出てくるか答えてください。

これをmapを用いてエラトステネスっぽく実装をしたのが以下のコードです。

c++
1const int M = 1e9;
2int main() {
3    int n;
4    cin >> n;
5    map<int, bool> mp;
6    vector<int> a(n);
7    for(int i=0; i<n; i++) {
8        cin >> a[i];
9        mp[a[i]] = true;
10    }
11
12    sort(a.begin(), a.end());
13    for(int i=0; i<n; i++) {
14        for(int j=a[i]*2; j<=M; j*=2) {
15            # ここでmapの要素が存在するかを確認している
16            if(mp[j]) mp.erase(j);
17        }
18    }
19    cout << mp.size() << endl;
20}

質問

if(mp[j])の部分で存在の確認をしてからeraseを実装すると正しい答えはえられず58となってしまいました。
またif(mp[j])をなくしてそのまま要素をeraseすると意図通りの結果となりました。
これら二つの違いはなんなのでしょうか？ if(mp[j])の時点で新たな要素が追加されてしまうということでしょうか？

ご存知の方いましたらご教授いただけると幸いです。