topCoderのSRM393, InstantRunoffVotingという問題を解いていたところ、ベクタのなかに出現する文字の頻度を数える必要がでてきました。ハッシュテーブルみたいなやつが欲しいなと思い、調べてみたところ、STLのmapでできるようです。

mapは、いわゆるkeyとvalueのセットを格納できるデータ構造です。他の言語ではハッシュテーブルとか辞書とか呼ばれるものと似ています。

宣言

mapをインクルードします。keyとvalueの型を指定します。

#include 

map int> sampleMap;

[]によるアクセス

他の言語のそれと同じく、で添字を指定してアクセスできます。で指定したkeyが既にある場合はそこの値にアクセスし、ない場合は自動的に新しく作ってくれます。

sampleMap["first"] = 1;
sampleMap["second"] = 2;
sampleMap["second"] = 3;
cout << sampleMap["first"] << endl;
// 1 と出力されます。
cout << sampleMap["second"] << endl;
// 3 と出力されます。

イテレータによるアクセス

keyにはfirst、valueにはsecondというメンバでアクセスできます。

map int>::iterator it;
it = sampleMap.begin();
cout << it->first << ", " << it->second << endl;
// first, 1 と出力されます

頻度を数える

これだけ分かれば、当初の目的が達成できそうです。問題を簡略化して、int型の配列に入っている整数の出現頻度を数えてみます。

int data[20] = {1, 2, 3, 1, 9, 3, 2, 49, 2, 1, 2, 3, 4, 0, 4, 7, 9, 9, 9, 8};

for (int i=0; i<20; i++)
  counter[data[i]]++;
  
for (it=counter.begin(); it!=counter.end(); it++)
  cout << it->first << ", " << it->second << endl;

出力結果は、

0, 1
1, 3
2, 4
3, 3
4, 2
7, 1
8, 1
9, 4
49, 1

うまくいきました。