MENU

C++のstd::mapの使い方について

C++

AI実装検定のご案内

std::mapは、キーと値を1組にして管理するC++標準ライブラリの連想コンテナです。

たとえば、次のようなデータを扱う場合に適しています。

  • 商品名と価格
  • ユーザーIDとユーザー情報
  • 都道府県名と人口
  • 単語と出現回数
  • 設定名と設定値

基本的には、次のような対応関係を管理します。

キー → 値

例：

"apple"  → 120
"banana" → 80
"orange" → 100

std::mapでは、比較関数によって同値と判断されるキーを複数登録できません。

また、要素は指定された比較関数の順序で管理されます。

デフォルトではstd::less<Key>が使われるため、一般的な数値型や文字列型ではキーの昇順に並びます。

目次

std::mapを使うための準備

std::mapを使用するには、<map>ヘッダーをインクルードします。

#include <map>

文字列や入出力も使用する場合は、次のように記述します。

#include <iostream>
#include <map>
#include <string>

基本的な宣言方法は次のとおりです。

std::map<キーの型, 値の型> 変数名;

たとえば、文字列をキー、整数を値として管理する場合は次のように宣言します。

std::map<std::string, int> prices;

このpricesには、次のようなデータを格納できます。

prices["apple"] = 120;
prices["banana"] = 80;

std::mapの基本的な使い方

まずは、std::mapへ要素を追加し、値を取得する基本例を確認します。

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> prices;

    prices["apple"] = 120;
    prices["banana"] = 80;
    prices["orange"] = 100;

    std::cout << prices["apple"] << '\n';

    return 0;
}

実行結果：

120

prices["apple"]によって、キーが"apple"の要素へアクセスしています。

std::mapへ要素を追加する方法

std::mapへ要素を追加する方法はいくつかあります。

用途に応じて、operator[]、insert()、emplace()、try_emplace()、insert_or_assign()を使い分けます。

operator[]で追加する

最も簡単な方法です。

std::map<std::string, int> prices;

prices["apple"] = 120;
prices["banana"] = 80;

指定したキーが存在しない場合は、新しい要素が追加されます。

すでに同じキーが存在する場合は、値が上書きされます。

prices["apple"] = 150;

この時点で、"apple"の値は120ではなく150になります。

operator[]を使う際の注意点

operator[]は、キーが存在しない場合に値を新しく生成します。

値の型がintなら0、std::stringなら空文字列として値初期化されます。

std::map<std::string, int> prices;

std::cout << prices["grape"] << '\n';

実行結果：

0

この処理では、値を表示するだけでなく、"grape"というキーがpricesへ追加されます。

std::cout << prices.size() << '\n';

実行結果：

1

存在確認だけを目的としてoperator[]を使うと、意図せず要素が追加されるため注意が必要です。

また、値型が引数なしで構築できない場合、operator[]を使えないことがあります。

class Product
{
public:
    explicit Product(int price)
        : price_(price)
    {
    }

private:
    int price_;
};

std::map<std::string, Product> products;

Productには引数なしコンストラクタがないため、次のようなアクセスはできません。

// products["apple"]; // コンパイルエラー

このような場合は、try_emplace()などを使用します。

products.try_emplace("apple", 120);

insert()で追加する

insert()を使って要素を追加することもできます。

std::map<std::string, int> prices;

prices.insert({"apple", 120});
prices.insert({"banana", 80});

std::make_pair()を使う方法もあります。

prices.insert(std::make_pair("orange", 100));

ただし、同じキーがすでに存在する場合、insert()は既存の値を上書きしません。

prices.insert({"apple", 120});
prices.insert({"apple", 200});

最終的な"apple"の値は120のままです。

insert()の戻り値を確認する

std::mapのinsert()は、挿入結果を表す値を返します。

auto result = prices.insert({"apple", 120});

戻り値には、次の情報が含まれます。

result.first   // 要素を指すイテレータ
result.second  // 新規挿入された場合はtrue

C++17以降では、構造化束縛を使って次のように書けます。

auto [it, inserted] = prices.insert({"apple", 120});

if (inserted)
{
    std::cout << "新しく追加しました\n";
}
else
{
    std::cout << "すでに登録されています\n";
    std::cout << "現在の値: " << it->second << '\n';
}

キーがすでに存在する場合、itは既存の要素を指します。

emplace()で追加する

emplace()は、要素をコンテナ内で構築するための関数です。

std::map<std::string, int> prices;

prices.emplace("apple", 120);
prices.emplace("banana", 80);

同じキーがすでに存在する場合、新しい要素は追加されません。

prices.emplace("apple", 120);
prices.emplace("apple", 200);

最終的な値は120のままです。

try_emplace()で追加する

try_emplace()はC++17以降で使用できます。

std::map<std::string, int> prices;

prices.try_emplace("apple", 120);
prices.try_emplace("apple", 200);

キーが存在しない場合だけ要素を追加するため、最終的な値は120です。

try_emplace()は、値型のコンストラクタ引数を渡して、キーが存在しない場合だけ値オブジェクトを構築できる点が特徴です。

class Product
{
public:
    Product(int price, std::string country)
        : price_(price),
          country_(std::move(country))
    {
    }

private:
    int price_;
    std::string country_;
};

std::map<std::string, Product> products;

products.try_emplace("apple", 120, "Japan");

"apple"が存在しない場合だけ、Productがコンテナ内で構築されます。

ただし、関数の引数として渡した式自体が必ず評価されなくなるわけではありません。

products.try_emplace(
    "apple",
    createExpensiveValue()
);

createExpensiveValue()は、関数呼び出し前に評価される可能性があるため、値生成処理を完全に省略できるとは限りません。

insert_or_assign()で追加または更新する

insert_or_assign()もC++17以降で使用できます。

prices.insert_or_assign("apple", 120);

指定したキーが存在しない場合は新しく追加され、すでに存在する場合は値が更新されます。

prices.insert_or_assign("apple", 120);
prices.insert_or_assign("apple", 200);

最終的な値は200です。

戻り値を使って、新規追加か更新かを判定することもできます。

auto [it, inserted] =
    prices.insert_or_assign("apple", 120);

if (inserted)
{
    std::cout << "新規追加しました\n";
}
else
{
    std::cout << "既存の値を更新しました\n";
}

std::mapから値を取得する方法

std::mapから値を取得する主な方法には、operator[]、at()、find()があります。

operator[]で取得する

std::cout << prices["apple"] << '\n';

簡単に値を取得できますが、キーが存在しない場合は新しい要素が追加されます。

読み取りだけを目的とする場合には注意が必要です。

at()で取得する

at()は、指定したキーが存在する場合に値を返します。

std::cout << prices.at("apple") << '\n';

キーが存在しない場合は、std::out_of_range例外が発生します。

std::cout << prices.at("grape") << '\n';

例外処理を行う場合は、次のように記述します。

#include <iostream>
#include <map>
#include <stdexcept>
#include <string>

int main()
{
    std::map<std::string, int> prices{
        {"apple", 120}
    };

    try
    {
        std::cout << prices.at("grape") << '\n';
    }
    catch (const std::out_of_range&)
    {
        std::cout << "指定したキーは存在しません\n";
    }

    return 0;
}

at()は、存在しない要素を新しく追加しません。

find()で取得する

find()は、指定したキーを検索し、見つかった場合は要素を指すイテレータを返します。

auto it = prices.find("apple");

キーが見つからなかった場合は、end()を返します。

if (it != prices.end())
{
    std::cout << "価格: " << it->second << '\n';
}
else
{
    std::cout << "商品が見つかりません\n";
}

イテレータが指す要素では、次のようにキーと値へアクセスできます。

it->first   // キー
it->second  // 値

完全な例は次のとおりです。

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> prices{
        {"apple", 120},
        {"banana", 80}
    };

    auto it = prices.find("apple");

    if (it != prices.end())
    {
        std::cout << "商品名: "
                  << it->first
                  << '\n';

        std::cout << "価格: "
                  << it->second
                  << '\n';
    }

    return 0;
}

find()の結果を確認せずに使わない

次のコードは危険です。

auto it = prices.find("apple");

std::cout << it->second << '\n';

キーが存在しない場合、itはprices.end()になります。

end()を参照すると未定義動作になるため、必ず確認が必要です。

auto it = prices.find("apple");

if (it != prices.end())
{
    std::cout << it->second << '\n';
}

キーが存在するか確認する方法

キーの存在確認には、find()、contains()、count()を使用できます。

find()で確認する

if (prices.find("apple") != prices.end())
{
    std::cout << "appleは登録されています\n";
}

値も使用する場合は、検索結果を変数へ保存すると効率的です。

auto it = prices.find("apple");

if (it != prices.end())
{
    std::cout << it->second << '\n';
}

contains()で確認する

contains()はC++20以降で使用できます。

if (prices.contains("apple"))
{
    std::cout << "appleは登録されています\n";
}

存在確認だけを行う場合は、find()よりも意図が分かりやすい書き方です。

ただし、値も必要な場合は、find()を使えば検索結果をそのまま利用できます。

auto it = prices.find("apple");

if (it != prices.end())
{
    std::cout << it->second << '\n';
}

次のように書くと、内部的に検索が2回行われる可能性があります。

if (prices.contains("apple"))
{
    std::cout << prices.at("apple") << '\n';
}

処理効率を重視する場合は、find()で一度だけ検索するほうが適しています。

count()で確認する

if (prices.count("apple") > 0)
{
    std::cout << "appleは登録されています\n";
}

std::mapでは同値キーを複数格納できないため、count()の戻り値は0または1です。

C++20以降で存在確認だけを行う場合は、contains()のほうが意図を読み取りやすいでしょう。

std::mapの値を更新する方法

既存の値を更新する場合は、operator[]を使えます。

prices["apple"] = 150;

現在の値を利用して更新することもできます。

prices["apple"] += 20;

同じキーが存在しなければ、新しい要素が作られます。

prices["grape"] += 20;

この場合、"grape"の値は最初に0で初期化され、その後20になります。

C++17以降では、insert_or_assign()でも更新できます。

prices.insert_or_assign("apple", 150);

std::mapの要素を削除する方法

要素の削除にはerase()を使用します。

キーを指定して削除する

prices.erase("apple");

戻り値は、削除した要素数です。

std::size_t removed =
    prices.erase("apple");

if (removed > 0)
{
    std::cout << "削除しました\n";
}
else
{
    std::cout << "指定したキーは存在しません\n";
}

std::mapでは同値キーを複数持てないため、戻り値は0または1です。

イテレータを指定して削除する

検索済みのイテレータがある場合は、そのイテレータを指定して削除できます。

auto it = prices.find("apple");

if (it != prices.end())
{
    prices.erase(it);
}

範囲を指定して削除する

イテレータの範囲を指定して削除できます。

prices.erase(
    prices.begin(),
    prices.end()
);

すべての要素を削除するだけなら、clear()のほうが意図が分かりやすいです。

prices.clear();

std::mapの全要素を走査する方法

範囲ベースのfor文を使う

for (const auto& item : prices)
{
    std::cout << item.first
              << ": "
              << item.second
              << '\n';
}

item.firstがキー、item.secondが値です。

完全な例：

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> prices{
        {"orange", 100},
        {"apple", 120},
        {"banana", 80}
    };

    for (const auto& item : prices)
    {
        std::cout << item.first
                  << ": "
                  << item.second
                  << '\n';
    }

    return 0;
}

実行結果：

apple: 120
banana: 80
orange: 100

追加した順番ではなく、比較関数によって定められた順番で出力されます。

デフォルトでは文字列の昇順です。

構造化束縛を使う

C++17以降では、構造化束縛を使うと読みやすくなります。

for (const auto& [name, price] : prices)
{
    std::cout << name
              << ": "
              << price
              << '\n';
}

値を変更する場合は、constを外します。

for (auto& [name, price] : prices)
{
    price += 10;
}

ただし、キーは変更できません。

for (auto& [name, price] : prices)
{
    // name = "new_name"; // コンパイルエラー
    price += 10;
}

std::mapのキーは要素の並び順を決めるため、通常のイテレータ経由では変更できないようになっています。

イテレータを使って走査する

for (auto it = prices.begin();
     it != prices.end();
     ++it)
{
    std::cout << it->first
              << ": "
              << it->second
              << '\n';
}

イテレータを使うと、走査しながら要素を削除するなど、より細かな制御ができます。

走査しながら要素を削除する方法

次のコードは正しくありません。

for (auto it = prices.begin();
     it != prices.end();
     ++it)
{
    if (it->second < 100)
    {
        prices.erase(it);
    }
}

erase(it)を実行すると、そのイテレータは無効になります。

その後に++itを実行すると、未定義動作につながる可能性があります。

正しくは、erase()の戻り値を利用します。

for (auto it = prices.begin();
     it != prices.end();)
{
    if (it->second < 100)
    {
        it = prices.erase(it);
    }
    else
    {
        ++it;
    }
}

erase(it)は、削除した要素の次を指すイテレータを返します。

std::erase_if()を使う

C++20以降では、条件に一致する要素をまとめて削除できます。

std::erase_if(
    prices,
    [](const auto& item)
    {
        return item.second < 100;
    }
);

std::mapの要素数を調べる方法

size()で要素数を取得する

std::cout << prices.size() << '\n';

登録されている要素数を返します。

empty()で空か確認する

if (prices.empty())
{
    std::cout << "要素がありません\n";
}

次の書き方でも判定できますが、empty()のほうが意図が明確です。

if (prices.size() == 0)
{
}

推奨される書き方：

if (prices.empty())
{
}

clear()ですべて削除する

prices.clear();

すべての要素が削除されます。

削除後も、std::map自体は再利用できます。

prices.clear();
prices["apple"] = 120;

初期化リストでstd::mapを作成する方法

宣言と同時に要素を設定できます。

std::map<std::string, int> prices{
    {"apple", 120},
    {"banana", 80},
    {"orange", 100}
};

初期化リスト内の記述順にかかわらず、要素は比較関数の順序で管理されます。

std::mapの要素型

std::map<Key, Value>の要素型は、次のような型です。

std::pair<const Key, Value>

たとえば、次のstd::mapを考えます。

std::map<std::string, int>

要素型は次のようになります。

std::pair<const std::string, int>

キーがconstであるため、イテレータからキーを直接変更できません。

auto it = prices.find("apple");

// it->first = "grape"; // コンパイルエラー

it->second = 150;

値は変更できます。

std::mapのキーを変更する方法

通常は、既存の要素を削除し、新しいキーで再登録します。

auto it = prices.find("apple");

if (it != prices.end())
{
    int price = it->second;

    prices.erase(it);
    prices["grape"] = price;
}

ノードハンドルを使ってキーを変更する

C++17以降では、extract()で要素を取り出し、キーを変更してから再挿入できます。

auto node = prices.extract("apple");

if (!node.empty())
{
    node.key() = "grape";

    auto result =
        prices.insert(std::move(node));

    if (!result.inserted)
    {
        std::cout
            << "変更後のキーがすでに存在します\n";
    }
}

変更後のキーがすでに存在する場合、再挿入は失敗します。

std::mapの並び順

std::mapは、指定された比較関数の順序で要素を管理します。

デフォルトではstd::less<Key>が使用されるため、一般的にはキーの昇順です。

std::map<int, std::string> values{
    {30, "C"},
    {10, "A"},
    {20, "B"}
};

for (const auto& [key, value] : values)
{
    std::cout << key
              << ": "
              << value
              << '\n';
}

実行結果：

10: A
20: B
30: C

std::mapは、主要な標準ライブラリでは赤黒木などの平衡探索木で実装されるのが一般的です。

ただし、C++規格が具体的な内部データ構造を指定しているわけではありません。

規格上は、キー順の保持や検索・挿入などの計算量要件が定められています。

キーを降順に並べる方法

第3テンプレート引数へstd::greaterを指定します。

#include <functional>
#include <map>
#include <string>

std::map<
    int,
    std::string,
    std::greater<int>
> values;

使用例：

#include <functional>
#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<
        int,
        std::string,
        std::greater<int>
    > values{
        {30, "C"},
        {10, "A"},
        {20, "B"}
    };

    for (const auto& [key, value] : values)
    {
        std::cout << key
                  << ": "
                  << value
                  << '\n';
    }

    return 0;
}

実行結果：

30: C
20: B
10: A

独自の型をキーにする方法

構造体などの独自型をキーにする場合は、要素同士を比較できるようにする必要があります。

独自の比較関数を定義する

#include <iostream>
#include <map>
#include <string>

struct User
{
    int id;
    std::string name;
};

struct UserCompare
{
    bool operator()(
        const User& left,
        const User& right
    ) const
    {
        return left.id < right.id;
    }
};

int main()
{
    std::map<
        User,
        std::string,
        UserCompare
    > users;

    users.insert({
        {2, "Taro"},
        "Tokyo"
    });

    users.insert({
        {1, "Hanako"},
        "Osaka"
    });

    for (const auto& [user, city] : users)
    {
        std::cout << user.id
                  << ": "
                  << user.name
                  << ", "
                  << city
                  << '\n';
    }

    return 0;
}

この比較関数では、idだけが比較対象になります。

そのため、次の2つのUserはstd::map上では同値キーとして扱われます。

User{1, "Taro"}
User{1, "Hanako"}

nameが異なっていても、idが同じであれば2件目は追加できません。

idとnameの両方を比較したい場合は、次のように記述します。

#include <tuple>

struct UserCompare
{
    bool operator()(
        const User& left,
        const User& right
    ) const
    {
        return std::tie(left.id, left.name)
             < std::tie(right.id, right.name);
    }
};

比較関数で重要な厳密弱順序

比較関数は、厳密弱順序を満たす必要があります。

少なくとも、同じ値を自分自身より小さいと判定してはいけません。

comp(a, a) == false

また、aがbより小さい場合、同時にbがaより小さいと判定してはいけません。

if (comp(a, b))
{
    // comp(b, a)はfalseである必要がある
}

さらに、比較結果には推移性が必要です。

if (comp(a, b) && comp(b, c))
{
    // comp(a, c)はtrueである必要がある
}

比較規則が不整合だと、正しく検索できないなどの問題が起こる可能性があります。

operator<を定義する

キー型自身にoperator<を定義する方法もあります。

struct User
{
    int id;
    std::string name;

    bool operator<(const User& other) const
    {
        return id < other.id;
    }
};

この場合は、比較関数を指定せずに宣言できます。

std::map<User, std::string> users;

この比較でもidだけが比較対象なので、同じidを持つ要素は同値キーとして扱われます。

三方比較演算子を使う

C++20以降では、三方比較演算子をデフォルト定義できます。

#include <compare>
#include <string>

struct User
{
    int id;
    std::string name;

    auto operator<=>(const User&) const = default;
};

この場合、メンバーは宣言順に比較されます。

この構造体では、まずidを比較し、idが同じ場合にnameを比較します。

つまり、idだけでなくnameもキーの順序や同値判定に影響します。

lower_bound()の使い方

lower_bound(key)は、デフォルトの昇順比較では、指定したキー以上の最初の要素を返します。

std::map<int, std::string> values{
    {10, "A"},
    {20, "B"},
    {30, "C"}
};

auto it = values.lower_bound(15);

この場合、キー20の要素を指します。

if (it != values.end())
{
    std::cout << it->first << '\n';
}

実行結果：

20

指定したキーが存在する場合は、そのキー自身を指します。

auto it = values.lower_bound(20);

結果はキー20です。

独自比較や降順比較を使用している場合は、単純な数値上の「以上」とは限りません。

厳密には、比較関数上で指定キーより前に並ばない最初の要素を返します。

upper_bound()の使い方

upper_bound(key)は、デフォルトの昇順比較では、指定したキーより大きい最初の要素を返します。

auto it = values.upper_bound(20);

結果はキー30です。

if (it != values.end())
{
    std::cout << it->first << '\n';
}

equal_range()の使い方

equal_range(key)は、lower_bound()とupper_bound()に相当する2つのイテレータを返します。

auto [first, last] =
    values.equal_range(20);

std::mapでは同値キーを複数持てないため、範囲に含まれる要素は最大1件です。

for (auto it = first;
     it != last;
     ++it)
{
    std::cout << it->first
              << ": "
              << it->second
              << '\n';
}

equal_range()は、同値キーを複数格納できるstd::multimapで特に便利です。

特定範囲の要素を取得する方法

たとえば、キーが20以上40未満の要素を取得する場合は、次のように記述します。

std::map<int, std::string> values{
    {10, "A"},
    {20, "B"},
    {30, "C"},
    {40, "D"},
    {50, "E"}
};

auto first = values.lower_bound(20);
auto last  = values.lower_bound(40);

for (auto it = first;
     it != last;
     ++it)
{
    std::cout << it->first
              << ": "
              << it->second
              << '\n';
}

実行結果：

20: B
30: C

const std::mapから値を取得する方法

operator[]は、存在しないキーを追加する可能性があるため、const std::mapには使用できません。

const std::map<std::string, int> prices{
    {"apple", 120}
};

// prices["apple"]; // コンパイルエラー

const std::mapから値を取得する場合は、at()またはfind()を使用します。

std::cout << prices.at("apple") << '\n';

または、次のように記述します。

auto it = prices.find("apple");

if (it != prices.end())
{
    std::cout << it->second << '\n';
}

std::mapを関数へ渡す方法

読み取り専用で渡す

内容を変更しない場合は、const参照で受け取ります。

void printPrices(
    const std::map<std::string, int>& prices
)
{
    for (const auto& [name, price] : prices)
    {
        std::cout << name
                  << ": "
                  << price
                  << '\n';
    }
}

コピーを作らずに読み取れるため、一般的な渡し方です。

関数内で変更する

呼び出し元のstd::mapを変更する場合は、非const参照で受け取ります。

void increasePrices(
    std::map<std::string, int>& prices
)
{
    for (auto& [name, price] : prices)
    {
        price += 10;
    }
}

値渡しする

次の書き方では、std::mapがコピーまたはムーブされます。

void processPrices(
    std::map<std::string, int> prices
)
{
}

関数内で独立したコピーを変更したい場合や、所有権を受け取りたい場合には有効です。

不要なコピーを避けたいだけであれば、参照渡しを使用します。

関数からstd::mapを返す方法

関数からstd::mapを値で返すことができます。

std::map<std::string, int> createPrices()
{
    return {
        {"apple", 120},
        {"banana", 80},
        {"orange", 100}
    };
}

使用例：

auto prices = createPrices();

現代のC++では、戻り値最適化やムーブによって効率的に処理されるため、通常は値で返して問題ありません。

ローカル変数への参照を返してはいけません。

const std::map<std::string, int>& createPrices()
{
    std::map<std::string, int> prices;

    // ローカル変数への参照を返すため危険
    return prices;
}

実用例：単語の出現回数を数える

std::mapは、単語の出現回数を数える処理でよく使われます。

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> words{
        "apple",
        "banana",
        "apple",
        "orange",
        "banana",
        "apple"
    };

    std::map<std::string, int> counts;

    for (const std::string& word : words)
    {
        ++counts[word];
    }

    for (const auto& [word, count] : counts)
    {
        std::cout << word
                  << ": "
                  << count
                  << '\n';
    }

    return 0;
}

実行結果：

apple: 3
banana: 2
orange: 1

counts[word]は、キーが存在しない場合に値0で新しく作られます。

その後、++によって1になります。

このようなカウント処理では、operator[]の自動追加が便利に働きます。

実用例：IDからユーザー情報を取得する

#include <iostream>
#include <map>
#include <string>

struct User
{
    std::string name;
    int age;
};

int main()
{
    std::map<int, User> users{
        {1001, {"Taro", 25}},
        {1002, {"Hanako", 30}},
        {1003, {"Jiro", 28}}
    };

    int targetId = 1002;

    auto it = users.find(targetId);

    if (it != users.end())
    {
        const User& user = it->second;

        std::cout << "名前: "
                  << user.name
                  << '\n';

        std::cout << "年齢: "
                  << user.age
                  << '\n';
    }
    else
    {
        std::cout
            << "ユーザーが見つかりません\n";
    }

    return 0;
}

実用例：設定値を管理する

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<
        std::string,
        std::string
    > settings{
        {"language", "ja"},
        {"theme", "dark"},
        {"font_size", "16"}
    };

    auto it = settings.find("theme");

    if (it != settings.end())
    {
        std::cout << "テーマ: "
                  << it->second
                  << '\n';
    }

    return 0;
}

単純な設定情報をキーと値で管理する場合に利用できます。

入れ子のstd::mapを使う方法

std::mapの値として、別のstd::mapを格納することもできます。

std::map<
    std::string,
    std::map<std::string, int>
> sales;

例：

sales["Tokyo"]["apple"] = 100;
sales["Tokyo"]["banana"] = 80;
sales["Osaka"]["apple"] = 120;

取得：

std::cout
    << sales["Tokyo"]["apple"]
    << '\n';

走査：

for (const auto& [city, products] : sales)
{
    std::cout << city << '\n';

    for (const auto& [product, amount]
         : products)
    {
        std::cout << "  "
                  << product
                  << ": "
                  << amount
                  << '\n';
    }
}

入れ子でoperator[]を使う際の注意点

次のコードでは、存在しない都市と商品が自動的に追加されます。

std::cout
    << sales["Nagoya"]["apple"]
    << '\n';

この処理によって、次の要素が作られます。

  • 外側のキー"Nagoya"
  • 内側のキー"apple"
  • 値0

読み取りだけを行う場合は、find()やat()を使うほうが安全です。

auto cityIt = sales.find("Tokyo");

if (cityIt != sales.end())
{
    auto productIt =
        cityIt->second.find("apple");

    if (productIt != cityIt->second.end())
    {
        std::cout
            << productIt->second
            << '\n';
    }
}

存在することが前提なら、次のように記述できます。

std::cout
    << sales.at("Tokyo").at("apple")
    << '\n';

std::mapの計算量

std::mapの主な操作は、一般的に次の計算量です。

操作計算量
find(key)O(log n)
contains(key)O(log n)
count(key)O(log n)
通常のinsert()O(log n)
通常のemplace()O(log n)
erase(key)O(log n)
erase(iterator)償却O(1)
erase(first, last)O(log n + k)
clear()O(n)
begin()O(1)
全要素の走査O(n)

nは格納されている要素数、kは削除範囲に含まれる要素数です。

キーを指定して削除する場合は検索が必要なため、基本的にO(log n)です。

一方、すでに取得済みのイテレータを指定して1要素を削除する処理は、償却定数時間です。

また、位置ヒントを指定する挿入では、ヒントが適切なら通常のO(log n)より高速になる場合があります。

std::mapとstd::unordered_mapの違い

C++には、似た連想コンテナとしてstd::unordered_mapがあります。

項目std::mapstd::unordered_map
管理方法比較関数による順序付きハッシュによる順序なし
要素の並び順比較関数順順序保証なし
検索O(log n)平均O(1)
最悪時の検索O(log n)O(n)
範囲検索可能基本的に不向き
キーに必要な処理比較ハッシュと等値比較

std::mapが適しているケース

  • キー順にデータを走査したい
  • 最小キーや最大キーを取得したい
  • 範囲検索を行いたい
  • 最悪時にも安定した検索性能が必要
  • キーの大小比較はできるが、適切なハッシュ関数を用意しにくい

std::unordered_mapが適しているケース

  • 要素の順序が不要
  • 平均的なキー検索速度を重視する
  • キーに適切なハッシュ関数を使用できる
  • 範囲検索を必要としない

ただし、std::unordered_mapが必ずstd::mapより高速になるとは限りません。

実際の速度は、ハッシュ関数のコスト、衝突の発生、要素数、メモリ使用量などに左右されます。

std::mapとstd::multimapの違い

std::mapでは、比較関数上で同値と判定されるキーを複数登録できません。

std::map<std::string, int> values;

values.insert({"apple", 100});
values.insert({"apple", 200});

最初の要素だけが保持されます。

一方、std::multimapでは、同値キーを複数登録できます。

std::multimap<std::string, int> values;

values.insert({"apple", 100});
values.insert({"apple", 200});

同じキーに複数の値を関連付けたい場合は、std::multimapが候補になります。

std::mapでよくある間違い

存在確認にoperator[]を使う

次のコードは、キーが存在しない場合に新しい要素を追加します。

if (prices["apple"] != 0)
{
}

存在確認には、find()またはcontains()を使用します。

if (prices.find("apple") != prices.end())
{
}

C++20以降：

if (prices.contains("apple"))
{
}

insert()で既存値を上書きできると思う

prices.insert({"apple", 120});
prices.insert({"apple", 200});

2回目のinsert()では値が上書きされません。

更新したい場合は、次のようにします。

prices["apple"] = 200;

または、C++17以降なら次の方法があります。

prices.insert_or_assign("apple", 200);

キーを直接書き換えようとする

auto it = prices.find("apple");

// it->first = "banana"; // コンパイルエラー

キーは並び順を維持するため、直接変更できません。

値は変更できます。

it->second = 200;

キーを変更したい場合は、削除して再挿入するか、C++17以降のノードハンドルを使用します。

範囲ベースforで不要なコピーを作る

次のコードでは、各要素が毎回コピーされます。

for (auto item : prices)
{
    std::cout << item.first
              << item.second;
}

読み取り専用なら、const参照を使います。

for (const auto& item : prices)
{
    std::cout << item.first
              << item.second;
}

C++17以降なら、構造化束縛を使うと分かりやすくなります。

for (const auto& [key, value] : prices)
{
    std::cout << key
              << value;
}

find()の結果を確認せずに参照する

次のコードは危険です。

auto it = prices.find("apple");

std::cout << it->second << '\n';

キーが存在しない場合、it == prices.end()です。

正しくは、必ず確認します。

auto it = prices.find("apple");

if (it != prices.end())
{
    std::cout << it->second << '\n';
}

独自比較関数で一部のメンバーしか比較しない

次の比較関数は、idだけを比較しています。

struct UserCompare
{
    bool operator()(
        const User& left,
        const User& right
    ) const
    {
        return left.id < right.id;
    }
};

この場合、nameが異なっていても、idが同じなら同値キーとして扱われます。

User{1, "Taro"}
User{1, "Hanako"}

両方を別のキーとして扱いたい場合は、idとnameの両方を比較する必要があります。

基本操作をまとめたサンプル

#include <iostream>
#include <map>
#include <string>

int main()
{
    std::map<std::string, int> prices;

    // 要素を追加
    prices["apple"] = 120;
    prices.emplace("banana", 80);
    prices.insert({"orange", 100});

    // 値を更新
    prices["apple"] = 150;

    // 要素を検索
    auto it = prices.find("banana");

    if (it != prices.end())
    {
        std::cout << "bananaの価格: "
                  << it->second
                  << '\n';
    }

    // 存在確認
    if (prices.contains("orange"))
    {
        std::cout
            << "orangeは登録されています\n";
    }

    // 全要素を表示
    for (const auto& [name, price] : prices)
    {
        std::cout << name
                  << ": "
                  << price
                  << '\n';
    }

    // 要素を削除
    prices.erase("banana");

    // 要素数を表示
    std::cout << "要素数: "
              << prices.size()
              << '\n';

    // すべて削除
    prices.clear();

    if (prices.empty())
    {
        std::cout
            << "すべて削除されました\n";
    }

    return 0;
}

contains()はC++20以降の機能です。

C++17以前では、次のように置き換えます。

if (prices.find("orange") != prices.end())
{
    std::cout
        << "orangeは登録されています\n";
}

用途別の使い分け

値を追加または更新したい場合

map[key] = value;

C++17以降：

map.insert_or_assign(key, value);

キーが存在しない場合だけ追加したい場合

map.insert({key, value});

または、C++17以降：

map.try_emplace(key, value);

値を取得したいが要素を追加したくない場合

map.at(key);

または：

auto it = map.find(key);

存在するかだけ確認したい場合

C++20以降：

map.contains(key);

C++17以前：

map.find(key) != map.end();

キー順にすべて処理したい場合

for (const auto& [key, value] : map)
{
}

キーの範囲で検索したい場合

map.lower_bound(key);
map.upper_bound(key);

std::mapを使う際の重要ポイント

std::mapを理解するうえでは、次の点が重要です。

  1. キーと値をペアで管理する
  2. 比較関数上で同値となるキーは重複できない
  3. 要素は比較関数の順序で管理される
  4. デフォルトでは一般的にキーの昇順になる
  5. 検索や通常の追加は基本的にO(log n)
  6. operator[]は存在しないキーを追加する
  7. 読み取りだけならat()やfind()を使う
  8. 存在確認にはfind()やcontains()を使う
  9. キーは通常のイテレータ経由では変更できない
  10. 同値キーを複数持たせるならstd::multimapを使う
  11. 順序が不要ならstd::unordered_mapも検討する
  12. 独自比較関数は厳密弱順序を満たす必要がある

最初は、次の基本操作を使えるようになれば、多くの処理に対応できます。

map[key] = value;

auto it = map.find(key);

if (it != map.end())
{
    std::cout << it->second;
}

map.erase(key);

for (const auto& [key, value] : map)
{
}

std::mapは、キー順の走査や範囲検索が必要な場面で特に有効なコンテナです。

一方で、単純な検索速度を重視し、並び順が不要な場合は、std::unordered_mapも比較検討するとよいでしょう。

以上、C++のstd::mapの使い方についてでした。

最後までお読みいただき、ありがとうございました。

C++
よかったらシェアしてね！
  • URLをコピーしました！
  • URLをコピーしました！

関連記事

  1. ホーム
  2. C++
  3. C++のstd::mapの使い方について
目次