学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

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