[C++] mapとmultimapの違いについて解説

C++のmapとmultimapはどちらもキーと値のペアを格納する連想コンテナですが、主な違いはキーの重複可否です。

mapは各キーが一意でなければならず、同じキーを複数回挿入することはできません。

一方、multimapは同じキーを複数回挿入可能で、キーの重複を許容します。

どちらも内部的に平衡二分探索木(通常は赤黒木)を使用しており、要素の挿入、削除、検索の平均計算量は$O(\log n)$です。

mapとmultimapの主な違い

C++の標準ライブラリには、データをキーと値のペアで管理するためのコンテナとしてmapとmultimapがあります。

これらは似たような機能を持っていますが、いくつかの重要な違いがあります。

以下にその違いをまとめます。

この表からもわかるように、mapは一意のキーを持つデータを管理するのに対し、multimapは同じキーに対して複数の値を持つことができます。

これにより、用途に応じて使い分けることが重要です。

mapの特徴と使い方

mapは、C++の標準ライブラリに含まれる連想配列の一種で、キーと値のペアを管理します。

以下にmapの特徴と基本的な使い方を説明します。

特徴

• キーの一意性: mapでは、各キーは一意でなければなりません。

同じキーを持つ要素を追加しようとすると、既存の要素が上書きされます。

• 自動ソート: mapは、キーを自動的にソートして格納します。

これにより、キーに基づく検索が効率的に行えます。

• 効率的な検索: 要素の検索、挿入、削除はすべてO(log n)の時間で行えます。

基本的な使い方

以下は、mapを使用したサンプルコードです。

#include <iostream>
#include <map>
#include <string>
int main() {
    // mapの宣言
    std::map<std::string, int> ageMap;
    // 要素の追加
    ageMap["山田"] = 25;  // 山田さんの年齢を追加
    ageMap["佐藤"] = 30;  // 佐藤さんの年齢を追加
    ageMap["鈴木"] = 22;  // 鈴木さんの年齢を追加
    // 要素の上書き
    ageMap["山田"] = 26;  // 山田さんの年齢を更新
    // 要素の表示
    for (const auto& pair : ageMap) {
        std::cout << pair.first << "さんの年齢: " << pair.second << "歳" << std::endl;
    }
    return 0;
}

このコードでは、mapを使って人の名前をキー、年齢を値として管理しています。

要素を追加したり、上書きしたりすることができ、最後に全ての要素を表示しています。

鈴木さんの年齢: 22歳
山田さんの年齢: 26歳
佐藤さんの年齢: 30歳

このように、mapを使用することで、キーに基づいて効率的にデータを管理することができます。

multimapの特徴と使い方

multimapは、C++の標準ライブラリに含まれる連想配列の一種で、複数の値を同じキーに関連付けることができるコンテナです。

以下にmultimapの特徴と基本的な使い方を説明します。

特徴

• キーの重複: multimapでは、同じキーを持つ複数の要素を格納することができます。

これにより、同じキーに対して異なる値を持つデータを管理できます。

• 自動ソート: multimapもmapと同様に、キーを自動的にソートして格納します。

これにより、キーに基づく検索が効率的に行えます。

• 効率的な検索: 要素の検索、挿入、削除はすべてO(log n)の時間で行えます。

基本的な使い方

以下は、multimapを使用したサンプルコードです。

#include <iostream>
#include <map>
#include <string>
int main() {
    // multimapの宣言
    std::multimap<std::string, int> scoreMap;
    // 要素の追加
    scoreMap.insert({"数学", 90});  // 数学のスコアを追加
    scoreMap.insert({"英語", 85});   // 英語のスコアを追加
    scoreMap.insert({"数学", 95});   // 数学のスコアを追加(重複キー)
    scoreMap.insert({"理科", 88});    // 理科のスコアを追加
    // 要素の表示
    for (const auto& pair : scoreMap) {
        std::cout << pair.first << "のスコア: " << pair.second << std::endl;
    }
    return 0;
}

このコードでは、multimapを使って科目名をキー、スコアを値として管理しています。

同じ科目に対して複数のスコアを追加することができ、全ての要素を表示しています。

数学のスコア: 90
数学のスコア: 95
英語のスコア: 85
理科のスコア: 88

このように、multimapを使用することで、同じキーに対して複数の値を持つデータを効率的に管理することができます。

まとめ

この記事では、C++のmapとmultimapの違いやそれぞれの特徴、使い方について詳しく解説しました。

mapは一意のキーを持つデータを管理するのに対し、multimapは同じキーに対して複数の値を持つことができるため、用途に応じて使い分けることが重要です。

これらのコンテナを活用することで、データ管理の効率を高めることができるので、ぜひ実際のプログラムに取り入れてみてください。