導入
C++の標準ライブラリである std::set は、重複のない要素をソートされた状態で保持する便利なコンテナです。このコンテナから特定の要素を探す際、皆さんはどのようにコードを書いていますか？実は、std::set::find を適切に使うことで、コードの可読性を高めるだけでなく、検索処理のパフォーマンスを最大限に引き出すことができます。今回は、この「検索の基本」を改めて解説します。
基礎知識
std::set は内部的に「赤黒木（平衡二分探索木）」などのデータ構造で実装されています。そのため、要素の検索（find）は非常に高速で、計算量は O(log n) です。
std::set::find は、引数として「検索したい値」を受け取ります。その値がコンテナ内に存在すればその要素を指す「イテレータ」を返し、存在しなければ「コンテナの末尾を指すイテレータ（s.end()）」を返します。この「end() と比較する」というイディオムは、C++プログラミングにおける鉄板のルールです。
実装/解決策
検索を行う際は、必ず「findの結果が end() ではないこと」を確認する条件分岐を書くのが基本です。また、C++11以降であれば auto を活用することで、イテレータの型（std::set
サンプルプログラム
以下のコードは、std::set に値が含まれているかを判定し、結果に応じて処理を分ける例です。そのままコンパイルして動作を確認できます。
include
include
int main() {
// 整数のセットを初期化
std::set
int target = 30;
// findメソッドで検索を実行
// 見つかった場合はその要素を指すイテレータ、なければ end() が返る
auto it = numbers.find(target);
// イテレータが end() と等しくなければ「見つかった」と判断
if (it != numbers.end()) {
std::cout << "値 " << it << " が見つかりました！" << std::endl;
} else {
std::cout << "値 " << target << " は存在しません。" << std::endl;
}
return 0;
}
応用・注意点
現場で役立つ補足として、C++20から導入された contains メソッドについても触れておきます。もし、「要素があるかどうか」だけを知りたいのであれば、イテレータを取得する find よりも、bool値を直接返す s.contains(value) を使う方が意図が明確になり、コードも簡潔になります。
また、注意点として「findは定数時間（O(1)）ではなく対数時間（O(log n)）かかる」という点を忘れないでください。もし検索頻度が極めて高い場合は、std::unordered_set を検討するのも一つの解決策です。目的に応じて最適なコンテナとメソッドを選択することが、プロとしての腕の見せ所です。
コメント