std::unordered_mapは、C++の標準ライブラリに用意されている連想コンテナの1つです。
キーと値をセットで保存し、キーを使って対応する値を高速に検索できます。
たとえば、商品名と価格を次のように管理できます。
apple → 100
banana → 150
orange → 120
C++では次のように宣言します。
std::unordered_map<std::string, int> prices;
std::unordered_mapは一般的にハッシュテーブルを利用して実装されており、検索・追加・削除を平均O(1)で行える点が大きな特徴です。
ただし、要素の並び順は保証されません。
unordered_mapを使うための準備
unordered_mapヘッダーを読み込む
std::unordered_mapを使うには、<unordered_map>ヘッダーをインクルードします。
#include <unordered_map>
文字列をキーとして使用する場合は、<string>も使用します。
#include <iostream>
#include <string>
#include <unordered_map>
int main()
{
std::unordered_map<std::string, int> prices;
return 0;
}
unordered_mapの基本的な宣言方法
キー型と値型を指定する
基本構文は次のとおりです。
std::unordered_map<キーの型, 値の型> 変数名;
たとえば、商品名をキー、価格を値として管理する場合は次のように書きます。
std::unordered_map<std::string, int> prices;
この場合、
std::string
がキーの型で、
int
が値の型です。
unordered_mapを初期化する方法
初期化リストを使う
C++11以降では、初期化リストを使って複数の要素をまとめて登録できます。
std::unordered_map<std::string, int> prices = {
{"apple", 100},
{"banana", 150},
{"orange", 120}
};
各要素は、
{"キー", 値}
という形式で記述します。
operator[]で要素を追加する
キーを指定して値を登録する
operator[]は、unordered_mapで非常によく使われる方法です。
std::unordered_map<std::string, int> prices;
prices["apple"] = 100;
prices["banana"] = 150;
値を取得する場合も同じ形式を使えます。
std::cout << prices["apple"] << '\n';
既存の値を更新する
すでに存在するキーに値を代入すると、その値が更新されます。
prices["apple"] = 100;
prices["apple"] = 200;
最終的な値は200になります。
operator[]を使うときの注意点
存在しないキーは新しく作成される
operator[]には重要な特徴があります。
存在しないキーを指定すると、新しい要素が作成されます。
std::unordered_map<std::string, int> prices;
std::cout << prices["apple"];
この場合、appleというキーが存在しないため、値が値初期化された要素が追加されます。
intの場合は0になります。
概念的には次の状態です。
apple → 0
そのため、単純にキーが存在するか確認したいだけの場合にoperator[]を使うのは適切ではありません。
値型によってはoperator[]を使えない場合がある
存在しないキーに対してoperator[]を使用すると、値を新しく生成する必要があります。
そのため、mapped valueの型によってはoperator[]が適さない場合があります。
そのような場合は、
insert()
や、
try_emplace()
などを使用します。
at()で値を取得する
at()の基本
値を取得する方法としてat()も利用できます。
std::cout << prices.at("apple");
operator[]と異なり、存在しないキーを指定しても新しい要素は作成されません。
存在しないキーでは例外が発生する
存在しないキーをat()に指定すると、std::out_of_range例外が送出されます。
prices.at("orange");
キーが存在するかわからない場合は、事前にfind()やcontains()で確認すると安全です。
find()でキーを検索する
find()の基本
find()は、キーを検索するための代表的なメンバー関数です。
auto it = prices.find("apple");
キーが存在する場合は、その要素を指すイテレータが返されます。
存在しない場合は、
prices.end()
が返されます。
if (prices.find("apple") != prices.end())
{
std::cout << "存在します\n";
}
find()で値を取得する
検索結果のイテレータからキーと値を取得できます。
auto it = prices.find("apple");
if (it != prices.end())
{
std::cout << it->first << '\n';
std::cout << it->second << '\n';
}
firstがキー、secondが値です。
unordered_mapの要素は概念的に、
std::pair<const Key, T>
として扱われます。
contains()でキーの存在を確認する
C++20以降ではcontains()が使える
C++20以降では、contains()を使用して簡潔に存在確認できます。
if (prices.contains("apple"))
{
std::cout << "存在します\n";
}
存在確認だけが目的であれば、find()より意図がわかりやすい書き方です。
C++17以前では、
if (prices.find("apple") != prices.end())
{
}
などを使用します。
count()でキーの存在を調べる
unordered_mapでは0または1が返る
count()でもキーの存在確認ができます。
if (prices.count("apple") > 0)
{
std::cout << "存在します\n";
}
unordered_mapでは同一キーを複数保持できないため、戻り値は基本的に0または1です。
ただし、unordered_multimapでは同じキーを複数保持できるため、2以上になる場合があります。
insert()で要素を追加する
insert()の基本
insert()でも要素を追加できます。
prices.insert({"apple", 100});
prices.insert({"banana", 150});
既存キーは上書きされない
次のコードを実行しても、
prices.insert({"apple", 100});
prices.insert({"apple", 200});
2回目のinsert()によって値が200に更新されるわけではありません。
既存の、
apple → 100
が残ります。
insert()の戻り値を確認する
代表的なinsert()の戻り値は、
std::pair<iterator, bool>
です。
たとえば次のように使えます。
auto result = prices.insert({"apple", 100});
if (result.second)
{
std::cout << "追加成功\n";
}
else
{
std::cout << "すでに存在します\n";
}
result.secondがtrueなら追加成功、falseなら既存キーが存在したことを意味します。
insert_or_assign()で追加または更新する
C++17以降で利用できる
insert_or_assign()はC++17以降で利用できます。
prices.insert_or_assign("apple", 100);
キーが存在しなければ追加され、存在していれば値が更新されます。
prices.insert_or_assign("apple", 100);
prices.insert_or_assign("apple", 200);
最終的には、
apple → 200
となります。
emplace()で要素を追加する
コンテナ内で要素を構築できる
emplace()を使用すると、渡した引数から要素を構築できます。
prices.emplace("apple", 100);
値の型によっては、一時オブジェクトの生成を減らせる場合があります。
ただし、emplace()を使えば必ずinsert()より高速になるわけではありません。
用途や値の型によって効果は異なります。
try_emplace()を使用する
C++17以降で利用できる
try_emplace()もC++17以降で利用できます。
prices.try_emplace("apple", 100);
特徴は、キーがすでに存在する場合、新しいmapped valueを構築しないことです。
生成コストの高いオブジェクトを値として保存する場合には特に有用です。
erase()で要素を削除する
キーを指定して削除する
要素を削除するにはerase()を使います。
prices.erase("apple");
イテレータを指定して削除する
イテレータから削除することもできます。
auto it = prices.find("apple");
if (it != prices.end())
{
prices.erase(it);
}
削除された要素を指していたイテレータや参照などは無効になります。
一方で、削除されていない他の要素まで必ず無効になるわけではありません。
clear()ですべて削除する
全要素を削除する
すべての要素を削除したい場合はclear()を使用します。
prices.clear();
実行後の要素数は0になります。
size()で要素数を取得する
現在の登録件数を取得する
size()では、現在格納されている要素数を取得できます。
std::cout << prices.size();
3つの要素が登録されていれば3が返されます。
empty()で空か確認する
要素が0件か判定する
empty()を使うと、コンテナが空かどうかを確認できます。
if (prices.empty())
{
std::cout << "空です\n";
}
空ならtrue、要素があればfalseです。
unordered_mapをループ処理する
範囲for文を使う
すべての要素を処理するには範囲for文が便利です。
for (const auto& item : prices)
{
std::cout << item.first
<< ": "
<< item.second
<< '\n';
}
構造化束縛を使う
C++17以降では構造化束縛を使用できます。
for (const auto& [key, value] : prices)
{
std::cout << key << ": " << value << '\n';
}
keyがキー、valueが値です。
unordered_mapでは要素の順番が保証されない
登録順やキー順にはならない
unordered_mapでは、要素の走査順序は保証されません。
std::unordered_map<std::string, int> prices = {
{"apple", 100},
{"banana", 150},
{"orange", 120}
};
この順番で初期化しても、ループ処理では別の順序になる可能性があります。
要素の追加、削除、再ハッシュなどによって順序が変化することもあります。
順序が重要な処理では、std::mapなどを検討します。
unordered_mapとmapの違い
unordered_mapは平均O(1)で検索できる
unordered_mapでは、検索・追加・削除が平均O(1)です。
一方、std::mapは一般的に赤黒木などの平衡二分探索木で実装され、検索・追加・削除はO(log n)です。
mapではキーが順序付けされる
std::mapではキーの比較結果に基づいて要素が順序付けされます。
一方、unordered_mapでは順序は保証されません。
| 項目 | unordered_map | map |
|---|---|---|
| 主な実装 | ハッシュテーブル | 平衡探索木が一般的 |
| 検索 | 平均O(1) | O(log n) |
| 追加 | 平均O(1) | O(log n) |
| 削除 | 平均O(1) | O(log n) |
| キー順 | 保証されない | 順序付けされる |
| 範囲検索 | 不向き | 向いている |
| ヘッダー | <unordered_map> | <map> |
高速なキー検索を重視するならunordered_map、順序や範囲検索が重要ならmapが適しています。
unordered_mapの計算量
平均計算量はO(1)
代表的な操作は平均O(1)です。
find()
insert()
emplace()
operator[]
erase()
ただし、これは平均的な計算量です。
最悪の場合はO(n)
ハッシュ衝突が極端に多い場合などには、検索や追加などが最悪O(n)になる可能性があります。
したがって、
unordered_mapは必ずO(1)
ではなく、
平均O(1)、最悪O(n)
と理解するのが正確です。
unordered_mapで使われるハッシュとは
キーからハッシュ値を計算する
unordered_mapでは、キーからハッシュ値を計算して保存先を決めます。
概念的には次の流れです。
キー
↓
ハッシュ関数
↓
ハッシュ値
↓
バケットを決定
整数型やstd::stringなどの主要な型にはstd::hashが用意されています。
そのため、
std::unordered_map<std::string, int>
のような一般的な型なら、自分でハッシュ関数を用意する必要は通常ありません。
ハッシュ衝突とは
異なるキーが同じハッシュ値になる場合がある
異なるキーから同じハッシュ値が生成されることをハッシュ衝突と呼びます。
ハッシュ衝突自体は異常ではなく、unordered_mapは衝突が発生することを前提として設計されています。
重要なのは、等しいと判断されるキーについては同じハッシュ値を返さなければならないことです。
つまり、
a == b
なら、
hash(a) == hash(b)
である必要があります。
一方、
hash(a) == hash(b)
だからといって、
a == b
である必要はありません。
unordered_mapのバケットとは
要素を複数の領域に分けて管理する
unordered_mapでは、要素をバケットと呼ばれる複数の領域に分けて管理します。
概念的には次のような構造です。
bucket 0 → 要素
bucket 1 → 要素
bucket 2 → 要素、要素
bucket 3 → 空
bucket_count()でバケット数を取得する
std::cout << prices.bucket_count();
現在のバケット数を確認できます。
bucket()で所属バケットを確認する
std::cout << prices.bucket("apple");
指定したキーがどのバケットに対応するかを確認できます。
通常のアプリケーションでは直接使う機会は多くありませんが、内部構造や性能を調べるときに役立ちます。
load_factorとは
バケットに対する要素数の割合
load_factor()は、概ね次の割合を表します。
要素数 ÷ バケット数
std::cout << prices.load_factor();
負荷率が高くなるとハッシュ衝突が増えやすくなるため、必要に応じてバケット数が調整されます。
max_load_factor()も利用できる
最大負荷率はmax_load_factor()で取得・設定できます。
prices.max_load_factor(0.7f);
これにより、再ハッシュが発生する基準に影響を与えられます。
rehash()とは
バケット数を再調整する
rehash()を使うと、最低限必要なバケット数を指定できます。
prices.rehash(100);
再ハッシュが実際に発生すると、要素のバケット配置が再計算されます。
再ハッシュではイテレータが無効になる
再ハッシュが発生すると、unordered_mapを指していたイテレータは無効になります。
ただし、要素そのものへの参照やポインタは、再ハッシュだけでは通常無効になりません。
イテレータを保持したまま大量の要素を追加する場合は注意が必要です。
reserve()で再ハッシュを減らす
要素数がわかっている場合に便利
大量の要素を追加することが事前にわかっている場合は、reserve()を利用できます。
std::unordered_map<int, std::string> data;
data.reserve(100000);
reserve()は、指定した数の要素を最大負荷率を超えずに格納できるよう、必要なバケット数を調整します。
std::vector::reserve()のように、要素本体を格納する連続領域を単純に確保する処理とは異なります。
大量追加の途中で発生する再ハッシュを減らし、性能改善につながる場合があります。
unordered_mapのキーは直接変更できない
キー部分はconstとして扱われる
unordered_mapの要素は概念的に、
std::pair<const Key, T>
です。
そのため、値は変更できます。
it->second = 200;
一方、キーを直接変更することはできません。
it->first = "banana";
のようなコードは使用できません。
キーを変えたい場合は、削除して新しいキーで登録するなどの方法が必要です。
独自型をキーとして使う
ハッシュ関数を用意する
自作構造体などをキーとして使用することもできます。
struct Point
{
int x;
int y;
};
その場合、適切なハッシュ関数と等価比較が必要です。
#include <cstddef>
#include <functional>
#include <unordered_map>
struct Point
{
int x;
int y;
bool operator==(const Point& other) const
{
return x == other.x && y == other.y;
}
};
struct PointHash
{
std::size_t operator()(const Point& p) const
{
std::size_t h1 = std::hash<int>{}(p.x);
std::size_t h2 = std::hash<int>{}(p.y);
return h1 ^ (h2 << 1);
}
};
int main()
{
std::unordered_map<Point, int, PointHash> data;
data[{1, 2}] = 100;
}
実際のハッシュ結合方法については、データの性質や用途に応じた設計が必要です。
unordered_mapをカウンターとして使う
単語の出現回数を数える
unordered_mapは出現回数の集計に非常に向いています。
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main()
{
std::vector<std::string> words = {
"apple",
"banana",
"apple",
"orange",
"apple",
"banana"
};
std::unordered_map<std::string, int> counts;
for (const auto& word : words)
{
++counts[word];
}
for (const auto& [word, count] : counts)
{
std::cout << word << ": " << count << '\n';
}
return 0;
}
存在しないキーに対して、
counts[word]
を使うとintが0として作成されます。
そのため、
++counts[word];
だけで簡単に出現回数を数えられます。
unordered_mapを辞書として使う
キーから対応するデータを検索する
辞書のような用途にも適しています。
#include <iostream>
#include <string>
#include <unordered_map>
int main()
{
std::unordered_map<std::string, std::string> dictionary = {
{"apple", "りんご"},
{"banana", "バナナ"},
{"orange", "オレンジ"}
};
std::string word = "apple";
auto it = dictionary.find(word);
if (it != dictionary.end())
{
std::cout << it->second << '\n';
}
else
{
std::cout << "見つかりませんでした\n";
}
return 0;
}
たとえば次のような用途で利用できます。
ユーザーID → ユーザー情報
商品コード → 商品情報
単語 → 出現回数
名前 → スコア
URL → キャッシュデータ
unordered_mapでよく使う関数
主なメンバー関数一覧
| 機能 | 書き方 | 用途 |
|---|---|---|
| 要素追加・取得 | map[key] | 追加・更新・取得 |
| 値を取得 | map.at(key) | 存在するキーの値を取得 |
| 追加 | insert() | キーと値を追加 |
| 追加 | emplace() | 要素を構築して追加 |
| 追加・更新 | insert_or_assign() | なければ追加、あれば更新 |
| 条件付き追加 | try_emplace() | キーがなければ追加 |
| 検索 | find() | キーを検索 |
| 存在確認 | contains() | C++20以降 |
| 個数確認 | count() | キーの個数を取得 |
| 削除 | erase() | 要素を削除 |
| 全削除 | clear() | すべての要素を削除 |
| 要素数 | size() | 要素数を取得 |
| 空判定 | empty() | 空か確認 |
| 事前調整 | reserve() | 想定要素数に合わせてバケットを調整 |
| バケット調整 | rehash() | バケット数を再調整 |
unordered_mapを使うときの注意点
要素順を前提にしない
unordered_mapの要素順は保証されません。
表示順や処理順が重要な場合には適していません。
operator[]は検索専用ではない
prices["unknown"];
のように存在しないキーを指定すると、要素が追加されます。
存在確認だけなら、
prices.find("unknown")
や、
prices.contains("unknown")
を使用します。
平均O(1)と最悪O(n)を区別する
unordered_mapは高速ですが、常にO(1)ではありません。
正確には平均O(1)、最悪O(n)です。
再ハッシュによるイテレータ無効化に注意する
要素追加によって再ハッシュが発生すると、保持していたイテレータが無効になる可能性があります。
必要に応じてreserve()を使用すると、再ハッシュ回数を抑えられる場合があります。
unordered_mapとunordered_multimapの違い
同じキーを複数持てるかが違う
unordered_mapでは同一キーを複数保持できません。
apple → 100
apple → 200
のようなデータを同時に保持したい場合は、
std::unordered_multimap
を使用します。
使い分けは次のとおりです。
1つのキーに1つの値
→ unordered_map
1つのキーに複数の要素
→ unordered_multimap
unordered_mapが向いている場面
高速なキー検索が必要な場合
unordered_mapは次のような用途に適しています。
- キーから値を高速に検索したい
- IDとデータを対応付けたい
- 単語や数値の出現回数を数えたい
- キャッシュを管理したい
- キーの並び順が不要
- 大量の検索処理を行いたい
一方で、キーを順番に処理したい場合や範囲検索が必要な場合には、std::mapのほうが適していることがあります。
unordered_mapの基本コード
主要な操作をまとめた例
#include <iostream>
#include <string>
#include <unordered_map>
int main()
{
std::unordered_map<std::string, int> prices = {
{"apple", 100},
{"banana", 150}
};
// 追加
prices["orange"] = 120;
// 更新
prices["apple"] = 110;
// 検索
auto it = prices.find("banana");
if (it != prices.end())
{
std::cout << "banana: "
<< it->second
<< '\n';
}
// 全要素を表示
for (const auto& [name, price] : prices)
{
std::cout << name
<< ": "
<< price
<< '\n';
}
// 削除
prices.erase("orange");
std::cout << "要素数: "
<< prices.size()
<< '\n';
return 0;
}
まとめ
std::unordered_mapは、キーと値を対応付けて管理できるC++の連想コンテナです。
一般的にハッシュテーブルを利用しており、検索・追加・削除を平均O(1)で実行できます。
基本構文は次のとおりです。
std::unordered_map<キーの型, 値の型> 変数名;
たとえば、
std::unordered_map<std::string, int> prices;
とすれば、文字列をキーとして整数を管理できます。
特に重要なのは、要素の順序が保証されないことと、operator[]では存在しないキーが新しく作成されることです。
単純な存在確認にはfind()やC++20以降のcontains()を使用し、追加方法についてはinsert()、emplace()、try_emplace()、insert_or_assign()を用途に応じて使い分けるとよいでしょう。
また、reserve()やrehash()、負荷率、イテレータの無効化といった仕組みまで理解すると、unordered_mapをより安全かつ効率的に扱えるようになります。
以上、C++のunordered_mapの使い方についてでした。
最後までお読みいただき、ありがとうございました。
