C++: STL algorithmのlower_boundとupper_boundの使い方

C++ STLのalgorithmに入っているlower_boundとupper_boundが間違えやすいのでメモ。

vector<int>で定義されたコンテナvの要素のうち、A以上、B以下の要素を求める場合。

vector<int>::iterator a = lower_bound(v.begin(), v.end(), A); vector<int>::iterator b = upper_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "[" << *a << ", " << *(b - 1) << "]" << endl; else cout << "no element" << endl;

*aが最小の要素、*(b-1)が最大の要素になる。

A以上、B未満の場合。

vector<int>::iterator a = lower_bound(v.begin(), v.end(), A); vector<int>::iterator b = lower_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "[" << *a << ", " << *(b - 1) << "]" << endl; else cout << "no element" << endl;

因みに、lower_boundとupper_boundに渡すコンテナはソートされている必要がある。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; for (int i = 100; i > 0; i--) v.push_back(i); int A = 30; // 下限. int B = 50; // 上限. vector<int>::iterator a, b; cout << "要素数" << v.size() << "で、"; cout << "最小要素" << *min_element(v.begin(), v.end()) << "、"; cout << "最大要素" << *max_element(v.begin(), v.end()); cout << "のコンテナから、" << endl; // lower_bound, upper_boundに渡すコンテナはソートされている必要がある. sort(v.begin(), v.end()); cout << A << "以上、" << B << "以下の要素を求める: "; a = lower_bound(v.begin(), v.end(), A); b = upper_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "最小要素 " << *a << ", 最大要素 " << *(b - 1) << endl; else cout << "要素なし" << endl; cout << A << "以上、" << B << "未満の要素を求める: "; a = lower_bound(v.begin(), v.end(), A); b = lower_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "最小要素 " << *a << ", 最大要素 " << *(b - 1) << endl; else cout << "要素なし" << endl; return 0; }

出力結果:

要素数100で、最小要素1、最大要素100のコンテナから、 30以上、50以下の要素を求める: 最小要素 30, 最大要素 50 30以上、50未満の要素を求める: 最小要素 30, 最大要素 49