std::set は、重複しない要素を順序付きで管理するコンテナです。
その set の中から、指定した値が存在するかどうかを調べるために使うのが find です。
正しい表記は set::find で、: が1つではなく :: を使います。
set::find の役割
set::find は、std::set の中から指定した値を検索する関数です。
たとえば、整数の集合の中に 10 が含まれているか、文字列の集合の中に "apple" があるか、といった確認に使います。
set では、要素そのものが検索対象になります。
map のように「キー」と「値」が分かれているわけではないため、find には探したい要素そのものを渡します。
戻り値は bool ではなくイテレータ
set::find の大事なポイントは、真偽値を返すわけではないということです。
find の戻り値は次のようになります。
- 要素が見つかった場合
→ その要素を指すイテレータ - 要素が見つからなかった場合
→end()
つまり、find は「ある」「ない」を直接 true / false で返すのではなく、見つかった位置を表す値を返します。
end() とは何か
end() は、set の終端を表す特別なイテレータです。
よく「最後の要素の次」を表す位置と説明されます。
これは実際の要素を指しているわけではありません。
そのため、find の結果を使うときは、まず end() と同じかどうか を確認する必要があります。
考え方としては、次のようになります。
findの結果がend()でなければ見つかっているfindの結果がend()なら見つかっていない
なぜ bool ではなくイテレータを返すのか
find がイテレータを返すのは、単なる存在確認だけでなく、見つかった要素をその後の処理にそのまま使えるようにするためです。
たとえば、次のような場面で便利です。
- 要素が存在するか確認する
- 見つかった要素を参照する
- 見つかった位置を使って削除する
- 条件に応じて別の処理につなげる
このように、find は「探す」だけで終わらず、後続処理につなげやすい関数だと考えると理解しやすくなります。
計算量は O(log N)
std::set の検索は、標準で対数時間とされています。
そのため、find の計算量は O(log N) です。
要素数が増えても、先頭から最後まで順番に調べるような単純な線形探索より効率よく検索できます。
なお、set の実装には多くの場合、平衡木系のデータ構造が使われますが、C++ 標準が実装方式そのものを固定しているわけではありません。
重要なのは、検索が対数時間で行われることが保証されているという点です。
set::find が速い理由
set は要素を順序付きで管理しています。
そのため、比較結果を利用しながら探索範囲を絞り込むことができ、効率よく検索できます。
ここで注意したいのは、set は単純な配列をソートして持っているわけではないということです。
そのため、配列に対する典型的な二分探索とまったく同じではありません。
ただし、考え方としては順序を利用して無駄なく探索するという理解で問題ありません。
count との違い
std::set には count という関数もあります。
これも要素の存在確認に使えます。
set は同じ要素を重複して持てないため、count の戻り値は次のどちらかになります。
- 存在する場合は
1 - 存在しない場合は
0
使い分けの考え方
find が向いている場面
- 要素があるかどうかを調べたい
- 見つかった要素の位置をその後の処理に使いたい
- 削除や参照につなげたい
count が向いている場面
- 単純に存在するかどうかだけ知りたい
0か1かが分かれば十分
このように、find と count は似ていますが、戻り値の性質と、その後の使い道が違うという点を押さえておくことが大切です。
C++20の contains との違い
C++20 以降では、std::set に contains も用意されています。
contains は、指定した値が存在するかどうかをbool で直接返す関数です。
find
- イテレータを返す
- 見つかった位置を後で使える
contains
boolを返す- 存在確認だけならシンプルに書ける
そのため、単純に「あるかどうか」だけ確認したいなら、C++20 以降では contains のほうが読みやすい場面もあります。
一方で、見つかった要素の位置をそのまま利用したい場合は、引き続き find が便利です。
map::find との違い
find は set だけでなく map にもあります。
ただし、検索対象の考え方が少し異なります。
set::find
- 要素そのものを探す
map::find
- キーを探す
set は要素自体が検索対象ですが、map は「キー」と「値」の組を持つため、find ではキーを使って検索します。
この違いを理解しておくと、set と map の使い分けもしやすくなります。
unordered_set::find との違い
std::unordered_set にも find があります。
こちらは set とは性質が少し異なります。
set
- 要素は順序付きで管理される
findはO(log N)
unordered_set
- 要素は順序付きではない
findは平均O(1)- ただし最悪では
O(N)になることがある
そのため、
- 順序が必要なら
set - 高速な存在確認を重視するなら
unordered_set
という使い分けがよく行われます。
find の結果を扱うときの注意点
end() との比較を忘れない
find は、見つからなかった場合に end() を返します。
end() は実在する要素を指していないため、そのまま使ってはいけません。
そのため、find の結果を使う前には、必ず end() と比較して有効かどうかを確認します。
set の要素はコンテナ内で直接変更できない
set の要素は順序付けに使われるため、コンテナに格納されたままの状態で値を直接変更することはできません。
これは、値を書き換えると set 内の順序が壊れる可能性があるためです。
そのため、値を変更したい場合は通常、
- いったん削除する
- 新しい値を挿入する
という流れになります。
削除と組み合わせて使うことが多い
find は削除処理と組み合わせて使われることも多いです。
set では、値を指定して削除する方法もありますし、イテレータを使って削除する方法もあります。
そのため、すでに find で位置を取得しているなら、その結果を使って削除処理につなげる、という流れは自然です。
どんな場面で使われるか
set::find は、実際には次のような場面でよく使われます。
登録済みかどうかを確認したいとき
すでに処理した値かどうかを判定したい場面です。
たとえば、
- 既に訪問したノード
- 既に出現した文字列
- 重複させたくないID
などの管理に向いています。
値の有無で処理を分けたいとき
存在しているかどうかによって、後続の処理を分岐させるケースです。
たとえば、
- あれば処理をスキップする
- なければ追加する
- あれば削除する
といった流れで使われます。
よくある誤解
find は true / false を返す
返しません。
返すのは イテレータ です。
見つからなかったら nullptr を返す
返しません。
返るのは end() です。
見つかった要素は自由に書き換えられる
set の順序を壊す可能性があるため、コンテナ内の要素をそのまま直接変更することはできません。
count と find は完全に同じ
似ていますが、戻り値も用途も異なります。
find は位置を扱える、count は個数を返す、という違いがあります。
まとめ
C++ の set::find は、std::set の中から指定した値を検索するための関数です。
重要なポイントを整理すると、次のようになります。
set::findは要素を検索する- 戻り値は
boolではなくイテレータ - 見つからなかった場合は
end()を返す - 計算量は
O(log N) countは個数、containsは真偽値、findは位置を返す- 見つかった要素の位置を後続処理に利用できる
setの要素はコンテナ内で直接変更できない
set::find は、単なる存在確認だけでなく、検索結果を次の処理につなげやすいという点でとても便利な関数です。
以上、C++のset:findについてでした。
最後までお読みいただき、ありがとうございました。
