{ }codelper

学ぶ › C

さらに先へ · 16

辞書(マップ)

キーで値を探して更新する:単語を数える、あるか確かめる、キー順に回る。

辞書(マップ)は番号ではなくキーで値を探します。
下の例は単語ごとの出現回数を数え、聞かれた単語を探し、キー順にすべて表示します。

#include <stdio.h>#include <stdlib.h>#include <string.h> char keys[1000][32];int vals[1000], n = 0; int find(const char *w) {    for (int i = 0; i < n; i++)        if (strcmp(keys[i], w) == 0) return i;    return -1;} int cmp(const void *a, const void *b) { return strcmp(keys[*(const int *)a], keys[*(const int *)b]); } int main(void) {    char line[4096], qline[4096];    fgets(line, sizeof line, stdin);    fgets(qline, sizeof qline, stdin);    for (char *w = strtok(line, " \r\n"); w; w = strtok(NULL, " \r\n")) {        int i = find(w);        if (i < 0) { strcpy(keys[n], w); vals[n] = 0; i = n++; }        vals[i]++;    }    printf("%d\n", n);    for (char *q = strtok(qline, " \r\n"); q; q = strtok(NULL, " \r\n")) {        int i = find(q);        if (i >= 0) printf("%s %d\n", q, vals[i]);        else printf("%s none\n", q);    }    int order[1000];    for (int i = 0; i < n; i++) order[i] = i;    qsort(order, n, sizeof order[0], cmp);    for (int i = 0; i < n; i++) printf("%s %d\n", keys[order[i]], vals[order[i]]);    return 0;}
stdin
apple banana apple cherry banana apple
banana grape
stdout
3
banana 2
grape none
apple 3
banana 2
cherry 1

ポイント

  • "apple" → 3 のようにキーと値を組にしておきます。
    追加・検索・更新は、リストを先頭から調べるよりずっと速くできます。
  • いちばんよくある使い方は数えることです。
    初めて見た単語は 0 から始めて 1 を足します。
  • ないキーを読んだときの動きが言語ごとにいちばん違います。
    エラーになる、空の値が返る、新しい要素ができる。
    だから先にあるか確かめます。
  • 回る順番を当てにしないでください。
    入れた順を守る言語も、順番を約束しない言語もあります。
    例はどの言語でも同じになるよう、キーを並べ替えて表示します。
  • 値なしでキーだけを集めたものが集合です。
    異なる単語の数は集合の大きさでそのまま求まります。

言語ごとの書き方

Pythoncounts = {} — 数えるのは counts.get(w, 0) + 1、確認は w in counts。
ないキーを [] で読むと KeyError。
入れた順を守ります。
集合は set
JavaScriptnew Map() — 数えるのは (counts.get(w) ?? 0) + 1、確認は has。
ないと get は undefined。
入れた順を守ります。
集合は Set
TypeScriptJavaScript と同じです。
new Map<string, number>() のように型を書きます
JavaHashMap(順番の約束なし)、LinkedHashMap(入れた順)、TreeMap(キー順)。
数えるのは merge(w, 1, Integer::sum)、確認は containsKey、ないと get は null。
集合は HashSet
C#Dictionary<string, int> — 数えるのは GetValueOrDefault(w) + 1、確認は TryGetValue。
ないキーをインデクサーで読むと KeyNotFoundException。
順番は未定義です(キー順は SortedDictionary)。
集合は HashSet
C++std::map(キー順)、std::unordered_map(順番の約束なし)。
数えるのは counts[w]++、確認は C++20 の contains。
ないキーを [] で読むと値 0 の要素ができます。
集合は std::set
C辞書がありません。
例はキーの配列と値の配列を並べて持ち、先頭から探します(小さな入力なら十分です)
Craykon辞書() — d["りんご"] = 3 で入れて読みます。
確認は d.含む(キー)、d.キー一覧 は入れた順。
ないキーを読むと Python と同じく実行時エラーで止まります

よくある間違い

確かめるつもりで [] で読んだら要素ができたC++

std::map<std::string, int> counts;
if (counts["grape"] == 0) { }
std::cout << counts.size();

→ 1 — 読んだだけなのに "grape" の要素が値 0 でできました

確認は counts.contains(w)(C++20)か counts.find(w) で行います。

ないキーをそのまま読んだPython · C# · Craykon

counts = {"apple": 3}
print(counts["grape"])

→ KeyError: 'grape' で止まります(C# は KeyNotFoundException、Craykon は辞書に "grape" キーがないというエラー)

先にあるか確かめるか、Python の get(w, 0) のように既定値を渡します。

入れた順に出てくると思ったJava · C# · C++

Map<String, Integer> m = new HashMap<>();
m.put("pear", 1); m.put("apple", 2); m.put("fig", 3);
System.out.println(m.keySet());

→ [apple, pear, fig] — 入れた順(pear, apple, fig)と違います

キーを並べ替えてから表示するか、順番を約束する TreeMap・LinkedHashMap(C++ std::map、C# SortedDictionary)を使います。

言語ごとの違い
JavaScript で空のオブジェクト {} を使って数えると、"constructor" のような単語が Object.prototype のものとぶつかり、"10" のような数の形のキーは入れた順に関係なく先頭に昇順で並びます。
数えるには Map を使いましょう。

練習問題