

[AtCoderの問題](https://atcoder.jp/contests/abc019/tasks/abc019_3)
を解くにあたって、mapを使った以下の解法について質問がございます。

### 質問内容

`map<int, int>`
が何と何のペアで結びついてるのかわかりません。mp.firstは入力例3で言うと2,3,5,7だと思ってるのですが、mp.secondって最初はただの空箱という認識で合ってますでしょうか？  
また、

2→2で割り切れるから割って1になる→1→まだないから0を返す  
3→まだないから1を返す  
5→まだないから2を返す  
7→まだないから3を返す

で0,1,2,3の合計４が答え、という仕組みかと思ったのですが、`mp[num]=1` が何をしてるのかよくわかりません。よろしくお願い致します。

### 現状のコード

[code]

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        int N;
        cin >> N;
        map<int,int> mp;
        for(int i = 0; i < N; ++ i){
            int num;
            cin >> num;
            while(num%2==0){
                num /= 2;
            }
            mp[num] = 1;
        }
        cout << mp.size() << endl;
        return 0;
    }
    
[/code]


CC BY-SA 4.0
2020-05-31T06:16:33.480
67156
2020-06-12T02:28:42.547
2020-06-12T02:28:42.547
3060
35214
question
c++
c++のmapの使い方について


これは std::map `mp` を集合のように使っている例です。`mp[num]` の値は何でもよくて、ただ `mp` に `num`
が登録されたことを表現するために 1 を代入しています。

この問題では、x、2x、4x、8x、16x、……という系列の数を全て同一視したとき、与えられた N
個の整数は何種類の系列に分けられるか、ということが問われています。ある整数がどの系列にいるかは、その数を 2
で割れるだけ割れば分かります（いずれ系列の最初の数に至ります）。系列の最初の数をその系列の代表元として扱うことで、プログラム上で系列の数を数えやすくしています。

あとは何種類の系列があったかを数えるだけです。今回のプログラムではこのために std::map
を使っています。つまり、それぞれの整数を代表元に変換した後、その代表元 `num` について `mp[num] = 1` とすれば、まだ `mp[num]`
が定義されていなければ新しく `mp[num] = 1`
として定義が追加されますし、既に追加されていればそのまま特に何も変わりません。全部の整数についてこの処理をした後に `mp.size()`
を調べれば、最終的に `mp` に定義された数、つまり系列の種類数が分かります。

この上でご質問に答えます。

> mp.secondって最初はただの空箱という認識で合ってますでしょうか？

いいえ、微妙に合っていません。代入するまでは箱自体が存在していません。（また、std::map に対して mp.second()
も定義されていません、何となく伝わりますが……）


CC BY-SA 4.0
2020-05-31T09:55:32.650
67162
2020-05-31T09:55:32.650
19110
67156
answer


挙動は他の方が答えているとおりで正しいのですが、今回の場合、キーに対応する値が常に `1` であり、保存する意味がありません。このような場合は
`std::set` を用いるほうが良いです。`std::set<T>` は、`T`
型の（重複しない）値の集合を表します。すでに挿入された値をもう一度挿入すると何も起こりません。

今回のコードの場合、 `map<int,int>` の代わりに `set<int>`、`mp[num] = 1` の代わりに
`mp.insert(num)` とすることで書き換えることができます。


CC BY-SA 4.0
2020-06-11T12:16:06.377
67546
2020-06-11T12:16:06.377
40595
67156
answer