C++のupper_bound,lower_boundについて
何度書いても覚えないし,バグって悲しい思いをしたのでまとめることにした.
基本事項
- ソート済みのコンテナに対して呼ぶ.
- ランダムアクセスできないコンテナに対しても呼ぶことができる.
- lower_boundは指定した値以上の先頭の要素を指すイテレータを返す.
- upper_boundは指定した値より大きい先頭の要素を指すイテレータを返す.
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {0,0,0,1,1,1,4,4,4}; cout << lower_bound(v.begin(), v.end(), 2) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 2) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 1) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 1) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 5) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 5) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), -1) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), -1) - v.begin() << endl; }
実行結果
6 6 3 6 9 9 0 0
比較関数を渡す
operator<として用いる比較関数を渡すことができる.
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool comp(int a, int b) { return a > b; } int main() { vector<int> v = {4,4,4,1,1,1,0,0,0}; cout << lower_bound(v.begin(), v.end(), 2, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 2, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 1, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 1, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), 5, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), 5, comp) - v.begin() << endl; cout << lower_bound(v.begin(), v.end(), -1, comp) - v.begin() << endl; cout << upper_bound(v.begin(), v.end(), -1, comp) - v.begin() << endl; }
実行結果
3 3 3 6 0 0 9 9
比較関数の第一引数,第二引数には,upper_bound/lower_boundで指定した範囲,値のどちらも入る可能性がある.(うまく表現できない)
これを知らずに,第一引数に指定した範囲から取った値入れて,第二引数に探す値入れて比較するだろとか適当なこと考えながら書いたらバグって悲しい思いをした.
#include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; int N; bool comp(int a, int b) { if(a == N) cout << "first" << endl; else if(b == N) cout << "second" << endl; else cout << "else" << endl; return a < b; } int main() { vector<int> v; for(int i = 0; i < 1000000; i++) v.push_back(i); sort(v.begin(), v.end()); N = 1346; lower_bound(v.begin(), v.end(), N, comp); cout << endl; upper_bound(v.begin(), v.end(), N, comp); }
実行結果
second second second second second second second second second second second second second second second second second second second first first first first first first first first first first first first first first first first first first first first first