[STL] 제거 알고리즘

in STL



제거 알고리즘은 원소를 수정하는 알고리즘의 특수한 형태이다. 제거 알고리즘은 실제로 원소를 지우지 않고 논리적으로(다음 원소로 덮어쓰기) 지운다. 그래서 실제 size는 줄어들지 않는다. 실제 size를 줄이려면 컨테이너의 erase()를 사용하면 된다.

remove()

p=remove(b,e,x)는 구간 [b,e)의 순차열에서 x를 s남지 않게 하는데 실제로 제거하는 것이 아닌 다음 원소로 덮어쓰기 때문에 size에 변동은 없다. remove() 알고리즘 후에 순차열은 [b,p)가 된다.

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

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

	vector<int>::iterator iter_end;
	iter_end = remove(v.begin(), v.end(), 30);

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

	cout << "remove() 후 구간 [v1.begin(),iter_end)의 순차열 : ";
	for (vector<int>::iterator iter = v.begin(); iter != iter_end; iter++) {
		cout << *iter << " ";
	}
}

image

결과에서 보이듯이 실제 size는 5 그대로 이다. 만약 실제 컨테이너의 size까지 변경하려면 erase()를 사용한다.

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

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

	vector<int>::iterator iter_end;
	iter_end = remove(v.begin(), v.end(), 30);

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

	// 구간 [iter_end,v.end())의 원소를 실제로 삭제
	v.erase(iter_end, v.end());

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

image

remove_if()

특정 조건에 따라 원소를 제고 하고 싶을 때 사용한다.

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

bool Pred(int n) {
	return 30 <= n && n <= 40;
}

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

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

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

image

remove_copy()

원본을 수정하지 않고 특정 원소만 지워서 목적지 순차열로 복사하고 싶을 때 사용한다.

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

	vector<int> v2(5);
	// v2의 모습 0 0 0 0 0

	vector<int>::iterator iter_end;
	iter_end = remove_copy(v.begin(), v.end(), v2.begin(),30);
	
	cout << "v : ";
	for (vector<int>::size_type i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;

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

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

image

remove_copy_if()

원본의 원소들은 제거하지 않고 특정 조건에 참이 아닌 원소만 목적지로 복사하고 싶을 때 사용한다.

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

bool Pred(int n) {
	return 30 <= n && n <= 40;
}

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

	vector<int> v2(5);
	// v2의 모습 0 0 0 0 0

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

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

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

image

조건에 참인 원소는 사라졌다.

unique()

순차열의 인접 원소를 유일하게 만들고 싶을 때 사용한다. p=unique(b,e)는 구간 [b,e)의 순차열을 인접한 중복 원소가 남지 않도록 제거한다. 제거 후 순차열은 [b,p)가 된다. 마찬가지로 실제로 원소를 제거하는것이 아닌 덮어쓰는 것이며 정렬한 상태에서 사용하면 모든 원소를 유일하게 할 수 있다.

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


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

	vector<int>::iterator iter_end;
	iter_end = unique(v.begin(), v.end());

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

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

image

조건자 버전 unique()

사용자 조건에 따라 인접 원소를 제거하고 싶을 때 사용한다.

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

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

void main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(11);
	v.push_back(30);
	v.push_back(32);
	v.push_back(40);
	v.push_back(50);
	// v의 모습 10 11 30 32 40 50

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

	vector<int>::iterator iter_end;
	iter_end = unique(v.begin(), v.end(),Pred);

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

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

image


© 2022. by KSC

Powered by sora