C++のmapの機能について

Question

競プロ初心者です。AtCoderのABCコンテスト072 c問題 Togetherで
#問題文
長さNの整数列 a1,a2,...,aNが与えられます。
各1≤i≤Nに対し、aiに 1足すか、1引くか、なにもしないかの三つの操作からどれか一つを選んで行います。
この操作の後、ある整数 Xを選んで、ai=Xとなる iの個数を数えます。うまく操作を行い、Xを選ぶことで、この個数を最大化してください。
#制約
・1≤N≤10^5
・0≤ai<10^5(1≤i≤N)
・aiは整数

という問題で

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
   int n;
   cin >> n;
   map<ll, ll> mp;
   for (int i = 0; i < n; i++) {
      int a;
      cin >> a;
      mp[a]++;
      mp[a-1]++;
      mp[a+1]++;
   }

   ll ans = 0;
   for (auto x : mp) {
      ans = max(ans, x.second);
   }

   cout << ans << endl;

   return 0;
}

という解答があったのですがmap<ll, ll> mp;が何をしているのか教えてください。mapというのはmap<key, value>と書き、keyからvalueを検索するためのものだと思うのですが今回で言うと具体的にどんな操作をしているのか教えてくださると嬉しいです。よろしくお願い致します。

Answer 1

まあまずbits/stdc++.hをincludeするのはやめましょう。ついでにできればusing namespace std;もやめましょう。

本題に入りましょう。map<ll, ll> mp;は展開するとstd::map<long long, long long> mp;となります。つまり、std::map<long long, long long>型の変数mpを定義したわけですね。

次にこの変数mpを利用しているところを見ていきましょう。

mp[a]++;
mp[a-1]++;
mp[a+1]++;

これはstd::map::operator []の呼び出しですね。リファレンスを見てみると
https://cpprefjp.github.io/reference/map/map/op_at.html

指定したキーを持つ要素を取得する。対応する要素が存在しない場合は生成して返す。

だとわかります。つまりここでa/a-1/a+1がkeyなわけです。

for (auto x : mp) {
   ans = max(ans, x.second);
}

range-based forで変数mpを回しています。つまりイテレータを使っていますからまたリファレンスを見てきましょう
https://cpprefjp.github.io/reference/map/map/begin.html

内部的に、mapコンテナは要素を下位から上位へと並べており、従って begin()は map 内の最下位のキーにあたるpairのイテレータを返す。

つまり、keyによって辞書順に並べ替えたときの下位から、ここではkeyにした整数の値が小さい順に要素が列挙されていくわけですね。

Comments

[cunwe]

懇切丁寧に解説してくださりありがとうございます。大変恐縮ですがもう2つほど質問がございます。
1.後半の方のxというのはa1,a2,...,aNの+-1もしくは何もしないの3パターンの値を入れる箱みたいなものですか？また、こちら(http://vivi.dyndns.org/tech/cpp/range-for.html)によりますとx.secondで値が参照できるみたいなのですがa1,a2,...,aNの+-1もしくは何もしないの3パターンの値と比較しているansとはなんですか？左辺のansは「ai=Xとなる iの個数」だというのはわかるのですが,,,
2.AtCoderは先月にはじめてそれからずっと#include <bits/stdc++.h>とusing namespace std;は使ってしまっているのですがどうしてやめた方がいいのでしょうか？たまに#include <iostream>というのも目にするのですがそうすると実行が遅くなると聞いたことがあります。
以上になります。よろしくお願い致します。

[cateye]

bits/stdc++.hに関しては、私も（全ての開発環境で使えないので）同意見です。
iostreamはファイル入出力を行うのですから、遅いのは当たり前です。
また、cout,cin,endl,mapしか使わないなら、対応するヘッダファイルをインクルードした上で、
using std::cout;
using std::cin;
using std::endl;
using std::map;
で、事は足ります。(もしくはstd::を付ける)
もし、各ライブラリに必要なヘッダファイルがわからないと言うなら調べてみて下さい
→C++日本語リファレンス https://cpprefjp.github.io/

[asm]

using namespace std;が実際に問題を引き起こしてた例
https://teratail.com/questions/108087

レアケースではあるが

[yumetodo]

> 後半の方のxというのはa1,a2,...,aNの+-1もしくは何もしないの3パターンの値を入れる箱みたいなものですか？

xって、range-based forのとこのはなしですか？多分その質問はRange-based forを理解できてないので、
https://cpprefjp.github.io/lang/cpp11/range_based_for.html
を読んでください。通常のfor文に一度書き換えてみるといいでしょう。

あとそもそも、最初のfor文が終わった段階でのmpの状態がどうなっているか勘違いしていると思いますから、いちどその段階で全要素をprintして見てみると誤解に気がつくと思います。

> x.secondで値が参照できるみたいなのですが

端的に言うと、まずイテレータをdereferenceした型(`value_type`)は
https://cpprefjp.github.io/reference/map/map.html
にあるとおり、std::pair<const Key, T>なわけです。よって、その理解であってます

[cunwe]

引用していただいたページを見て自分の理解を深めたいと思います。御三方ともありがとうございました。