이름에서 알 수 있듯이 정렬된 범위에서만 동작하는 알고리즘이다. 반드시 입력 순차열이 정렬되어 있어야하고, 원소의 같음을 비교할 때 연관 컨테이너처럼 두 원소 a,b에 대하여 !(a<b) && !(a>b)연산을 수행한다,

binary_search(b,e,x)

binary_search(b,e,x)는 구간 [b,e)의 순차열에서 x와 같은 원소가 있으면 true를 반환하고, 아니면 false를 반환한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	if (binary_search(v.begin(), v.end(), 20))
		cout << "20 원소가 존재합니다." << endl;
	else
		cout << "20 원소가 존재하지 않습니다." << endl;
}

결과가 직관적이므로 설명은 생략한다. 이제 조건자 버전 binary_search()알고리즘으로 같음 연산을 설명해보겠다.

binary_search(b,e,x,f)

여기서 f는 비교(정렬 기준)에 사용되는 이항 조건자이다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool Pred(int left, int right) {
	return 3 < right - left;
}

void main() {
	vector<int> v;
	v.push_back(40);
	v.push_back(46);
	v.push_back(12);
	v.push_back(80);
	v.push_back(10);
	v.push_back(47);
	v.push_back(30);
	v.push_back(55);
	v.push_back(90);
	v.push_back(53);

	cout << "[v 원본] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	sort(v.begin(), v.end(), Pred);
	cout << "[v: 정렬] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	if (binary_search(v.begin(), v.end(), 32,Pred)) {
		cout << "32 원소가 존재 합니다" << endl;
	}
	else {
		cout << "32 원소가 존재하지 않습니다." << endl;
	}

	if (binary_search(v.begin(), v.end(), 35, Pred)) {
		cout << "35 원소가 존재 합니다" << endl;
	}
	else {
		cout << "35 원소가 존재하지 않습니다." << endl;
	}
}

결과에서 보면 12가 10보다 앞에 존재하는 걸 볼 수 있다. 왜냐하면 정렬 기준 Pred에 따라 12는 10의 다음 원소가 아니기 때문이다. 55와 53도 그렇다. 또한 검색에서 32의 검색은 같은 연산 !Pred(32,30) && !Pred(30,32)가 true이기 때문에 순차열에 있는 원소로 취급된다. 35는 같음 연산을 수행해서 true인 원소가 없으므로 순차열에 없는것이다. 정렬된 범위 알고리즘은 정렬된 순차열에서 동작하므로 모든 알고리즘이 조건자 버전의 알고리즘이 제공되며 정렬 기준과 동일한 조건자를 지정해야 올바르게 동작한다.

예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(20);

	cout << "[v 원본] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	// 기본 정렬 less 사용
	sort(v.begin(), v.end());
	cout << "[v: less 정렬] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	// 비교 조건자 less 지정(일반 버전 binary_search() 가능)
	cout << "비교 less 찾기 : " << binary_search(v.begin(), v.end(), 20,less<int>()) << endl;

	// 정렬 기준 greater 지정
	sort(v.begin(), v.end(), greater<int>());
	cout << "[v: greater 정렬] : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	// 비교 조건자 greater 지정
	cout << "비교 greater 찾기 : " << binary_search(v.begin(), v.end(), 20,greater<int>()) << endl;
}

코드를 보면 알 수 있듯이 less로 정렬된 순차열에는 binary_search()알고리즘의 조건자를 less로, greater로 정렬된 순차열에는 조건자를 greater로 지정한다.

includes(b,e,b2,e2)

한 순차열이 다른 순차열의 부분 집합인지 판단할 때 사용된다. 구간 [b2,e2)의 원소가 구간 [b,e)의 원소에 포함되면(부분 집합) true, 아니면 false이다. 조건자 버전은 f를 비교에 사용한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(10);
	v2.push_back(20);
	v2.push_back(40);

	vector<int> v3;
	v3.push_back(10);
	v3.push_back(20);
	v3.push_back(60);

	if (includes(v1.begin(), v1.end(), v2.begin(), v2.end())) {
		cout << "v2는 v1의 부분 집합" << endl;
	}
	else {
		cout << "v2는 v1의 부분 집합 아님" << endl;
	}

	if (includes(v1.begin(), v1.end(), v3.begin(), v3.end())) {
		cout << "v3는 v1의 부분 집합" << endl;
	}
	else {
		cout << "v3는 v1의 부분 집합 아님" << endl;
	}

	// 정렬 기준을 greater<int> 설정
	sort(v1.begin(), v1.end(), greater<int>());
	sort(v2.begin(), v2.end(), greater<int>());
	// 비교 기준을 greater<int> 설정
	if (includes(v1.begin(), v1.end(), v2.begin(), v2.end(), greater<int>())) {
		cout << "greater정렬 순차열 : v2는 v1의 부분 집합" << endl;
	}
}

v2의 모든 원소가 v1에 포함되므로 includes()는 true를 반환한다. v3의 원소 60이 v1에 없으므로 includes()는 false를 반환한다. 정렬 기준이 less가 아니라면 includes() 조건자로 비교 기준을 설정해야 한다.

lower_bound() / upper_bound()

p=lower_bound(b,e,x)는 구간 [b,e)의 순차열에서 x 원소와 같은 첫 원소의 반복자를 반환한다. p=upper_bound(b,e,x)는 구간 [b,e)의 순차열에서 x원소와 같은 마지막 원소의 다음 원소(x보다 큰 첫 원소)의 반복자를 반환한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(30);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int>::iterator iter_lower, iter_upper;

	iter_lower = lower_bound(v.begin(), v.end(), 30);
	iter_upper = upper_bound(v.begin(), v.end(), 30);

	cout<<"iter_lower : " << *iter_lower << endl;
	cout<<"iter_upper : " << *iter_upper << endl;

	cout << "30 원소의 순차열 : [iter_lower,iter_upper) : ";
	for (vector<int>::iterator iter = iter_lower; iter != iter_upper; iter++) {
		cout << *iter << " ";
	}
}

v 순차열에서 30원소가 3개이며 30의 시작원소는 iter_lower가 30 다음의 원소는 iter_upper가 가리킨다.

equal_range()

순차열에서 찾는 원소의 반복자 쌍(구간)을 얻고자 할 때 사용한다. pair(p1,p2)=equal_range(b,e,x)는 구간 [b,e)의 순차열에서 x와 같은 원소의 반복자 쌍(p1,p2)을 반환한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(30);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int>::iterator iter_lower, iter_upper;
	pair<vector<int>::iterator, vector<int>::iterator> iter_pair;

	iter_pair = equal_range(v.begin(), v.end(), 30);

	cout << "30 원소의 순차열 : [iter_pair.first, iter_pair.second) : ";
	for (vector<int>::iterator iter = iter_pair.first; iter != iter_pair.second; iter++) {
		cout << *iter << " ";
	}
}

결과와 같이 iter_pair.first에는 찾고자하는 원소의 시작 반복자, iter_pair.second에는 찾고자 하는 원소의 끝 반복자를 반환한다.

merge(b,e,b2,e2,t)

정렬된 두 순차열을 하나의 목적지 순차열로 합병하고 싶을 때 사용한다. p=merge(b,e,b2,e2,t)는 구간 [b,e)의 순차열과 구간 [b2,e2)의 순차열을 목적지 순차열 [t,p)로 합병한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(60);

	vector<int> v3(10);
	
	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;

	cout << "v3 : ";
	for (vector<int>::size_type i = 0; i < v3.size(); i++) {
		cout << v3[i] << " ";
	}
	cout << endl;
	cout << endl;

	vector<int>::iterator iter_end;
	// v1의 순차열과 v2의 순차열을 합병하여 [v3.begin(), iter_end)의 순차열에 저장
	iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

	cout << "v1 : ";
	for (vector<int>::size_type i = 0; i < v1.size(); i++) {
		cout << v1[i] << " ";
	}
	cout << endl;

	cout << "v2 : ";
	for (vector<int>::size_type i = 0; i < v2.size(); i++) {
		cout << v2[i] << " ";
	}
	cout << endl;

	cout << "v3 : ";
	for (vector<int>::size_type i = 0; i < v3.size(); i++) {
		cout << v3[i] << " ";
	}
	cout << endl;

	cout << "구간 [v3.begin(), iter_end) : ";
	for (vector<int>::iterator iter = v3.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
}

결과가 직관적이므로 설명은 생략한다.

inplace_merge(b,m,e)

하나의 순차열이 두개의 구간으로 정렬되어 있다면 inplace_merge()를 사용하여 하나의 구간으로 정렬한다. inplace_merge(b,m,e)는 정렬된 [b,m)의 순차열과 정렬된 [m,e)의 순차열을 정렬된 [b,e) 순차열로 합병한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	v.push_back(20);
	v.push_back(30);
	v.push_back(60);

	
	cout << "v의 두 구간으로 정렬된 하나의 순차열" << endl;
	cout << "[v.begin(), v.begin()+5) + [v.begin()+5,v.end())" << endl;
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

	// 두 구간으로 정렬된 하나의 순차열을 한 구간으로 설정
	inplace_merge(v.begin(), v.begin() + 5, v.end());
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}

직관적이므로 설명은 생략한다.

set_uion(b,e,b2,e2,t)

정렬된 두 순차열의 합집합을 구하려면 set_union()을 사용한다, p=set_union(b,e,b2,e2,t)는 구간 [b,e)와 구간 [b2,e2)의 순차열을 합집합하여 목적지 순차열에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(60);

	vector<int> v3(10);
	vector<int>::iterator iter_end;

	iter_end = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	cout << "[v3.begin(),iter_end) : ";
	for (vector<int>::iterator iter = v3.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	cout << "v3 : ";
	for (vector<int>::size_type i = 0; i < v3.size(); i++) {
		cout << v3[i] << " ";
	}
	cout << endl;
}

합집합이기 때문에 v2의 60원소만 v1 순차열에 추가되어 v3에 저장된 것을 볼 수 있다.

set_intersection(b,e,b2,e2,t)

정렬된 두 순차열의 교집합을 구하려면 set_intersection()을 사용한다. p=set_intersection(b,e,b2,e2,t)는 구간 [b,e)와 구간 [b2,e2)의 순차열을 교집합하여 목적지 순차열 [t,p)에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(60);

	vector<int> v3(10);
	vector<int>::iterator iter_end;

	iter_end = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	cout << "교집합 [v3.begin(),iter_end) : ";
	for (vector<int>::iterator iter = v3.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

v1과 v2의 공통된 원소는 20, 30이기 때문에 목적지 순차열에는 20, 30이 추가된다.

set_difference(b,e,b2,e2,t)

정렬된 두 순차열의 차집합을 구하려면 set_difference()을 사용한다. p=set_difference(b,e,b2,e2,t)는 구간 [b,e)와 구간 [b2,e2)의 순차열을 차집합하여 목적지 순차열 [t,p)에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(60);

	vector<int> v3(10);
	vector<int>::iterator iter_end;

	iter_end = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	cout << "차집합 [v3.begin(),iter_end) : ";
	for (vector<int>::iterator iter = v3.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

v1에서 v2를 차집합하면 10,40,50만 남기 때문에 목적지 순차열에 10, 40, 50만 저장된 걸 볼 수 있다.

set_symmetric_difference(b,e,b2,e2,t)

정렬된 두 순차열의 대칭 차집합을 구하려면 set_symmetric_difference()을 사용한다. p=set_symmetric_difference(b,e,b2,e2,t)는 구간 [b,e)와 구간 [b2,e2)의 순차열을 대칭 차집합하여 목적지 순차열 [t,p)에 저장한다. 예시를 보자.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);

	vector<int> v2;
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(60);

	vector<int> v3(10);
	vector<int>::iterator iter_end;

	iter_end = set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	cout << "대칭 차집합 [v3.begin(),iter_end) : ";
	for (vector<int>::iterator iter = v3.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

대칭 차집합은 합집합(10 20 30 40 50 60)에서 교집합(20 30)을 뺀 것이므로 10 40 50 60만 남은 걸 알 수 있다.

[STL] 정렬된 범위 알고리즘

binary_search(b,e,x)

binary_search(b,e,x,f)

includes(b,e,b2,e2)

lower_bound() / upper_bound()

equal_range()

merge(b,e,b2,e2,t)

inplace_merge(b,m,e)

set_uion(b,e,b2,e2,t)

set_intersection(b,e,b2,e2,t)

set_difference(b,e,b2,e2,t)

set_symmetric_difference(b,e,b2,e2,t)

KSC

binary_search(b,e,x)

binary_search(b,e,x,f)

includes(b,e,b2,e2)

lower_bound() / upper_bound()

equal_range()

merge(b,e,b2,e2,t)

inplace_merge(b,m,e)

set_uion(b,e,b2,e2,t)

set_intersection(b,e,b2,e2,t)

set_difference(b,e,b2,e2,t)

set_symmetric_difference(b,e,b2,e2,t)

Share this post