lower_boundとupper_bound

基本的なことが分かってなかった

これら2つはC++のalgorithmヘッダに含まれている関数です。ここよりしっかりした多くの解説サイトに書かれている思いますが、ソート済みの配列で

• std::lower_bound(begin, end, val)は、区間[begin,end)でval以上の最小の値を指すイテレータ
• std::upper_bound(begin, end, val)は、区間[begin,end)でvalより大きいの最小の値を指すイテレータ

を返します。二分探索で区間を移る時の条件分岐が<か<=かの違いです。

つまり

ソート済みのコンテナのvmin以上vmax以下の範囲を走査したいときは、次のように書けばよいということになります。

vector<int> v(10);
for(int i = 0; i < 10; i++) v[i] = i/2;
int vmin = 1, vmax = 3;
vector<int>::iterator lb = lower_bound(v.begin(), v.end(), vmin);
vector<int>::iterator ub = upper_bound(v.begin(), v.end(), vmax);
for(vector<int>::iterator it = lb; it != ub; ++it){
    cout << *it << ' ';
}
cout << endl;
// 1 1 2 2 3 3 

この使い方を知らなかったわけです。だからupper, lower(上下の)bound(境界)っていうのか...

equal_range

追記

equal_rangeで、第3引数に渡した値と等しい領域の両端のイテレータのペアが返ってきます。 second-firstでコンテナ内のその要素を数えられます。

auto range = equal_range(v.begin(), v.end(), 4)
for(vector<int>::iterator it = range.first; it != range.second; ++it){
    cout << *it << ' ';
}
cout << endl;
// 4 4 

cout << range.second - range.first << endl; // 2 (vに含まれる'4'の個数)