[STL] 원소를 수정하지 않는 알고리즘 (1)

in STL



원소를 수정하지 않는 알고리즘에 대해서 정리하려고 하는데 양이 상당히 많다. 차근차근 정리하며 공부해보자. 우선 원소를 수정하지 않는 알고리즘은 원소의 순서나 원소의 값을 변경하지 않고 원소를 읽기만 하는 알고리즘이다.

adjacent_find()

adjacent_find()는 adjacent의 뜻이 인접한/가까운 이라는 뜻이라는걸 알고 뜻을 유추해보면 알 수 있듯이 순차열에서 현재 원소와 다음 원소가 같아지는 첫 원소의 반복자를 반환한다. 예시를 보자.

#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(40);
	v.push_back(40);
	v.push_back(50);
	//v의 모습 10 20 30 30 40 40 50

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

	vector<int>::iterator iter;
	//구간 [ v.begin(), v.end() )에서 현재 원소와 다음 원소가 같아지는 첫 원소의 반복자 반환
	iter = adjacent_find(v.begin(),v.end());
	
	if(iter!=v.end()) //현재원소와 다음원소가 같은 곳이 없으면 구간의 끝 반복자 반환
		cout << *iter; //iter이 가리키는 곳 첫번 째 30
	cout << endl;

	for (; iter != v.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

여기서 알아야 하는 것은 찾기 관련 알고리즘은 원하는 원소를 발견하지 못하면 구간의 끝 반복자를 반화나는 것이지 컨테이너의 끝 표시 반복자가 아니라는 것이다. 구간의 끝 반복자를 반환한다!!!!!!! 꼭 명심!!!!!!

adjacent_find(b,e,f)

adjacent_find(b,e,f)는 인접한 원소가 특정 조건에 따라 인접한지 찾고자 할 때 사용한다. 여기서 조건자로 사용되는 f는 이항 조건자 이며 현재 원소와 다음 원소에 대해서 특정 조건인 참인 첫 번째 반복자를 반환한다. 예시를 보자.

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

bool Pred(int a, int b) {
	return abs(b - a) > 10; //다음 원소에서 현재 원소의 차가 10보다 크면 참
}

void main() {
	vector<int> v;
	v.push_back(10); //F
	v.push_back(20); //F
	v.push_back(30); //T
	v.push_back(50); //T
	v.push_back(90);
	//v의 모습 10 20 30 50 90

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

	vector<int>::iterator iter;
	//구간 [ v.begin(), v.end() )에서 현재 원소와 다음 원소가 조건을 만족하는 첫 번째 원소를 가리키는 반복자 반환
	iter = adjacent_find(v.begin(),v.end(),Pred);
	
	if(iter!=v.end()) //현재원소와 다음원소가 특정 조건을 만족하는 원소가 없으면 구간의 끝 반복자 반환
		cout << *iter; //iter이 가리키는 곳 30
	cout << endl;

	for (; iter != v.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

count()

순차열에서 특정 원소의 갯수를 간단하게 구하려면 count()알고리즘을 사용하면 된다. 물론 count()가 멤버 함수로 내장 되어 있는 자료 구조들도 있지만 없는 자료 구조들은 count()알고리즘을 사용한다. 예시를 보자.

#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(30);
	v.push_back(50);
	//v의 모습 10 20 30 40 30 50 

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

	//구간 [ v.begin(), v.end() )에서 원소 30의 갯수를 반환
	int n = count(v.begin(), v.end(),30); //n은 2
	cout << "30의 갯수 : " << n;
}

실행 결과

image

쉬운 에제이므로 설명은 생략한다.

count_if(b,e,f)

count_if(b,e,f)는 특정 조건자 f를 만족하는 원소의 갯수를 반환한다. 여기서 f는 단항조건자이다 예시를 보자.

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

bool Pred(int n) {
	return 25 < n; //현재 원소가 25보다 크면 참
}

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의 모습 10 20 30 40 50 

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

	//구간 [ v.begin(), v.end() )에서 조건자 Pred를 만족하는 원소의 갯수 반환
	int n = count_if(v.begin(), v.end(),Pred); //n은 3
	cout << "25보다 큰 원소의 갯수 : " << n;
}

실행 결과

image

쉬운 예제이므로 설명은 생략한다.

equal()

equal() 알고리즘을 사용하여 두 순차열의 원소가 모두 같은지 판단할 수 있다. equal(b,e,b2)는 구간 [b,e)의 순차열과 [b2,b2+(e-b))의 순차열이 같은지 판단한다. 두 개의 순차열을 필요로하는 알고리즘은 두 순차열의 길이가 같을 때 동작하므로 첫 번째 순차열은 구간 [b,e)을 필요로 하지만 두 번째 순차열은 시작 반복자만을 필요로 한다. 예시를 보자.

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

bool Pred(int n) {
	return 25 < n; //현재 원소가 25보다 크면 참
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(20);
	v1.push_back(30);
	//v1의 모습 10 20 30 

	vector<int> v2;
	v2.push_back(10);
	v2.push_back(20);
	v2.push_back(30);
	v2.push_back(40);
	v2.push_back(50);
	//v2의 모습 10 20 30 40 50 

	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;

	//구간 [ v1.begin(),v1.end() )와 구간 [ v2.begin(),v2.begin()+3)을 비교
	if (equal(v1.begin(), v1.end(), v2.begin()))
		cout << "두 순차열은 같습니다.";
}

실행 결과

image

어려운 예제는 아니지만 나는 처음에 equal(b,e,b2)는 구간 [b,e)의 순차열과 [b2,b2+(e-b))의 순차열이 같은지 판단한다. 여기서 구간 [b2,b2+(e-b))에서 e-b의 의미를 정확히 알지 못했다. 하지만 이제 알 수 있다. 예를들어 vector 컨테이너 v에 원소가 10 20 30이면 e는 v.begin()+3으로 표현 할 수 있다.

그래서 e-b는 v.begin()+3 - v.begin()으로 되기 때문에 결과는 3이 나오는 것이다. 이로인해 알 수 있는 사실이 있는데 equal()에서 인자로 입력한 b,e의 길이보다 두번째로 입력한 순차열의 길이가 같거나 크면 된다는 것이다. 작으면 문제지만 큰 건 문제가 되지 않는다.

equal(b,e,b2,f)

equal(b,e,b2,f)는 조건에 따라 두 순차열이 같은지 판단할 때 사용한다. 여기서 f는 이항 조건자이며 각 순차열의 반복자를 p,q라고 하면 f(p가 가리키는 원소,q가 가리키는 원소를)가 모두 참이면 equal()알고리즘은 참을 반환한다. 예시를 보자.

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

bool Pred(int left,int right) {
	//두번째 순차열의 원소 빼기 첫번째 순차열의 원소의 결과가 5보다 작으면 참
	return abs(right-left)<5; 
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(21);
	v1.push_back(30);
	//v1의 모습 10 21 30 

	vector<int> v2;
	v2.push_back(10);
	v2.push_back(20);
	v2.push_back(33);
	//v2의 모습 10 20 33 

	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;

	//구간 [ v1.begin(),v1.end() )와 구간 [ v2.begin(),v2.begin()+3)을 비교
	if (equal(v1.begin(), v1.end(), v2.begin(),Pred))
		cout << "두 순차열은 같습니다.";
}

실행 결과

image

어려운 예제는 아니다. 그래도 동작 과정을 보여주자면 (10-10) 참 / (20-21) 참 / (33-30) 참 모두 참이기에 결과가 참이다.

find() / find_if()

find()는 특정 원소를 찾는 알고리즘이고, find_if()는 특정 조건을 만족하는 원소를 찾는 알고리즘 이다. 예시를 봐보자.

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

bool Pred(int n) {
	return 35 < n; //원소가 35보다 크면 참
}

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);
	//v1의 모습 10 20 30 40 50

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

	vector<int>::iterator iter;
	//구간 [v1.begin(),v1.end())에서 20값을 갖는 첫 번째 반복자 반환
	iter = find(v1.begin(), v1.end(), 20);
	if (iter != v1.end())
		cout << *iter << "을 찾았다." << endl;

	//구간 [v1.begin(),v1.end())에서 Pred 조건을 만족하는 첫 번째 원소의 반복자 반환
	iter = find_if(v1.begin(), v1.end(),Pred);
	if (iter != v1.end())
		cout << "35보다 큰 첫번째 원소 : " << *iter;
}

실행 결과

image

물론 멤버함수로 find()를 가지고 있는 컨테이너도 있지만 멤버 함수로 없다면 find()알고리즘을 사용한다.

find_end()

find_end()알고리즘은 하나의 순차열안에 다른 순차열이 포함되었는지 찾아햐할 때 사용한다. find_end()알고리즘은 일치하는 순차열이 여러개라면 마지막 순차열의 시작 반복자를 반환한다. 글로 설명하는 것 보다 예시를 보면 이해하기 쉬울 것이다.

#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);
	v1.push_back(60);
	v1.push_back(70);
	v1.push_back(30);
	v1.push_back(40);
	v1.push_back(50);
	//v1의 모습 10 20 30 40 50 60 70 30 40 50 

	vector<int> v2;
	v2.push_back(30);
	v2.push_back(40);
	v2.push_back(50);
	//v2의 모습 30 40 50

	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;

	vector<int>::iterator iter;
	//구간 [v1.begin(),v1.end())에서 구간 [v2.begin(),v2.end())의 순차열이 포함되어 있는지 판단
	iter = find_end(v1.begin(), v1.end(),v2.begin(),v2.end());
	//포함되어 있으면
	if (iter != v1.end()) {
		//일치하는 마지막 순차열의 시작 반복자 iter
		cout <<"iter : " << *iter << endl; //30
		cout << "iter-1 : " << *(iter-1) << endl; //70
		cout << "iter+1 : " << *(iter+1) << endl; //40
	}
}

실행 결과

image

위 동작을 그림으로 나타내 보겠다.

image

포함되는 부분이 여러개지만 find_end는 마지막 순차열의 시작 반복자를 반환한다.

조건자 버전 find_end()

조건자 버전 find_end()을 사용하면 원소의 비교를 사용자가 직접 결정할 수 있다. 예시를 보자

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

bool Pred(int left,int right) {
	return left<=right; //첫번째 순차열의 원소가 두번째 순차열의 원소보다 같거나 작으면 참
}

void main() {
	vector<int> v1;
	v1.push_back(10);
	v1.push_back(15);
	v1.push_back(20);
	v1.push_back(40);
	v1.push_back(50);
	v1.push_back(60);
	v1.push_back(10);
	v1.push_back(11);
	v1.push_back(12);
	v1.push_back(80);
	//v1의 모습 10 15 20 40 50 60 10 11 12 80

	vector<int> v2;
	v2.push_back(10);
	v2.push_back(15);
	v2.push_back(25);
	//v2의 모습 10 15 25

	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;

	vector<int>::iterator iter;
	//구간 [v1.begin(),v1.end())에서 구간 [v2.begin(),v2.end())의 순차열이 포함되는지 판단하는데 조건을 만족해야 한다.
	iter = find_end(v1.begin(), v1.end(),v2.begin(),v2.end(),Pred);
	//포함되어 있으면
	if (iter != v1.end()) {
		//일치하는 마지막 순차열의 시작 반복자 iter
		cout <<"iter : " << *iter << endl; //10
		cout << "iter-1 : " << *(iter-1) << endl; //60
		cout << "iter+1 : " << *(iter+1) << endl; //11
	}
}

실행 결과

image

어려운 내용은 없지만 동작 과정을 그림으로 설명해보겠다.

image

역시 조건을 만족하는 순차열이 여러개 있는데 그 중 마지막 순차열의 시작 반복자를 반환한다.

find_first_of()

find_first_of()알고리즘은 두 순차열을 비교하여 모든 원소 중 같은 원소가 하나라도 발견되면 발견된 첫 우ㅡㅓㄴ소의 반복자를 반환한다. 예시를 보자.

#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);
	//v1의 모습 10 20 30 40 50

	vector<int> v2;
	v2.push_back(40);
	v2.push_back(80);
	v2.push_back(20);
	//v2의 모습 40 80 20 

	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;

	vector<int>::iterator iter;
	//구간 [v1.begin(),v1.end())에서 구간 [v2.begin(),v2.end())의 순차열의 원소 중 하나라도 포함되는지 확인
	iter = find_first_of(v1.begin(), v1.end(),v2.begin(),v2.end());
	//포함되어 있으면
	if (iter != v1.end()) {
		cout << "iter : " << *iter;
	}
}

실행 결과

image

어렵지 않다. 단지 그림으로 설명을 하겠다.

image

그림에서와 같이 첫번째 원소의 반복자를 반환한다.

조건자 버전 find_first_of()

조건자 버전 find_first_of()알고리즘은 특정 기준을 만족하는 첫번째 원소의 반복자를 반환한다.

예시를 보자.

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

bool Pred(int left, int right) {
	return left > right;
}

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);
	//v1의 모습 10 20 30 40 50

	vector<int> v2;
	v2.push_back(40);
	v2.push_back(80);
	v2.push_back(20);
	//v2의 모습 40 80 20 

	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;

	vector<int>::iterator iter;
	//구간 [v1.begin(),v1.end())에서 구간 [v2.begin(),v2.end())의 순차열에서 조건을 만족하는 
	//첫번째 원소의 반복자 반환
	iter = find_first_of(v1.begin(), v1.end(),v2.begin(),v2.end(),Pred);
	//포함되어 있으면
	if (iter != v1.end()) {
		cout << "iter : " << *iter;
	}
}

실행 결과

image

그림으로 설명하겠다.

image

v1의 원소 10과 20은 v2의 원소보다 크지 않지만 30은 v2의 원소 중 20보다는 크기 때문에 30이 첫번째 원소가 되는 것이다.


© 2022. by KSC

Powered by sora