導入
C++のstd::setやstd::mapを使っているとき、特定のキーを持つ要素の範囲を調べたい場面はよくあります。通常、lower_boundで「以上」の場所を見つけ、upper_boundで「より大きい」場所を見つけるという手順を踏みますが、これでは二度同じ検索を行っていることになり、効率的ではありません。std::set::equal_rangeを使用すれば、この二つの検索を一度の処理で完結させることができ、コードも劇的にスッキリさせることができます。
基礎知識
std::setは内部的に平衡二分探索木（主に赤黒木）で実装されています。このため、検索はO(log N)で行われます。
lower_bound(key)は、指定したキー「以上の」最初の要素を指すイテレータを返し、upper_bound(key)は、指定したキー「より大きい」最初の要素を指すイテレータを返します。
equal_range(key)は、これら二つの結果をstd::pairとして一度に返します。これにより、二分探索の木を根から辿る処理を一度に済ませられるため、パフォーマンス上のメリットがあります。
実装/解決策
C++17から導入された「構造化束縛」を活用することで、equal_rangeの戻り値を非常に簡潔に扱うことができます。pairのfirstにはlower_boundの結果が、secondにはupper_boundの結果が格納されます。もし指定したキーが集合内に存在しない場合、firstとsecondは同じ（そのキーを挿入すべき位置を指す）イテレータになります。
サンプルプログラム
以下のコードは、std::setから特定の数値の範囲を効率的に取得する例です。
include
include
int main() {
std::set
// 検索したい値
int target = 30;
// equal_rangeを使用して、lower_boundとupper_boundを同時に取得
// C++17の構造化束縛を使用
auto [low, up] = s.equal_range(target);
if (low != up) {
std::cout << "値 " << target << " が見つかりました。" << std::endl;
} else {
std::cout << "値 " << target << " は存在しません。" << std::endl;
}
// 範囲内の要素をイテレータで操作する例
std::cout << "検索範囲の結果: ";
for (auto it = low; it != up; ++it) {
std::cout << it << " ";
}
std::cout << std::endl;
return 0;
}
応用・注意点
注意点：std::setは一意なキーを持つコンテナであるため、equal_rangeが返す範囲には最大でも1つの要素しか含まれません。しかし、std::multisetを使用している場合は、同じキーを持つ複数の要素が範囲内に含まれる可能性があります。この「範囲検索」の考え方はmultisetで特に真価を発揮します。
現場でのTips：コードの可読性を高めるため、C++17以前の環境であればstd::pair
コメント