본문 바로가기

별걸다하는 IT/프로그래밍언어

[C++] 알고리즘 Algorithm의 remove, remove_if 함수에 대해 알아보자, erase 같이 사용하는 이유와 사용법

반응형

안녕하세요 양햄찌 블로그 주인장입니다.

오랜만에 프로그래밍 언어 포스팅으로 돌아왔어요~

알고리즘의 remove는 무엇인가, 뭐가 다른가?

알고리즘 remove함수는 이름이 좀 헷갈리게 명칭이 되어있어서,, 한 번 정리하고 갈 필요성이 있는데요,

보통 remove하면 다른 STL의 remove나 erase 함수처럼 특정 문자열을 완전 제거해주는걸로 생각하기 쉽습니다.

 

예를 들어 string 클래스의 erase함수는 내가 지정한 문자열을 찾아 기존 문자열에서 완!전!삭!제! 시켜주죠

또한 LIST 컨테이너의 remove 함수 또한 실제로 요소를 삭제해주는 역할을 해요.

 

하지만 Algorithm의 remove함수는 지워야할 요소를 발견하면 뒤의 요소를 하나씩 앞으로 이동시키는 방식으로 지우기 떄문에 사실상 크기가 줄어드는 것은 아니예요. 원래 삭제되었다면 삭제된 개수만큼 길이가 줄어야하는데 그렇지 않다는 점! 즉 완전 삭제라고 볼 수 없다.

이해를 돕기 위해 PROGRAMMING_TEST라는 문자열을 대상으로 M을 삭제하도록 알고리즘의 remove를 사용해 코딩을 짰다고 해봅시다. 그러면 위 그림처럼, 뒤의 문자를 앞으로 땡기는 방식으로 M을 지워버리는데, 떙겨진만큼 맨 뒤의 요소는 그대로 남기 때문에 사실 완전 문자열 길이 자체는 변화는 없습니다. 노란색 부분은 그대로 남아있게 되는거죠~ 

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
	string str = "PROGRAMMNING_TEST";
	cout << "remove 함수 수행 전 :"<< str << " 문자열 길이 :" << str.size() <<  endl;
	remove(str.begin(), str.end(), 'M');
	cout << "remove 함수 수행 후 :" << str << " 문자열 길이 :" << str.size() << endl;
	return 0;
}

위 예시를 확인하기 위해 코드로 짜보았어요.

MM이 사실 삭제되었다고 하면 PROGRANING_TEST가 되어야하는데, 그 뒤에 ST가 추가적으로 더해진 것을 확인할 수 있어요. 이런 특성때문에 알고리즘의 remove는 단독으로 쓰이기보단, STL의 erase와 조합되어서 많이 사용됩니다.

헤더

remove와 remove_if 함수 모두 algorithm 헤더파일에 정의되어 있습니다. 

#include <algorithm>

사용하려면 요렇게 인클루드 시켜주기

REMOVE, REMOVE_IF 문법

template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val);

remove함수는 val에 해당하는 값을 지웁니다.

앞에서 살펴보았듯이 제거 방식이 앞으로 당겨서 없애는 방식으로 당겨진 길이만큼 데이터가 그대로 남아있습니다.

 

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);

remove가 지정한 값을 제거한다면 remove_if는 조건을 만족하는 값을 지웁니다.

간단하게 문법을 설명하면 이렇게 돼요. 물론 조건이 맞는지 틀리는지 판별하기 위해서는 리턴타입이 bool이여야하기 때문에 매개변수 타입이 UnaryPredicate가 되는거~

참고로 predicate은 boolean을 반환하는 함수이거나 boolean operator() 멤버함수를 가지고 있는 객체를 의미합니다.  boolean으로 판별할 수 있는걸 말하는거죠.

 

리턴값

제거되지 않은 마지막 요소를 가리키는 반복자를 리턴합니다. 즉 first부터 반환받은 이 반복자까지의 범위에는 val과 일치하는 요소가 없는것.  잔여물이 시작되는 곳을 가리킨다 생각하면 되는데, 아래 예시를 보면 좀 더 이해가 됩니다.

REMOVE, REMOVE_IF 사용 예시

문법을 이해했으면 샘플 코드를 살펴봅시다.

1. 배열일때 단순 remove와 remove_if 사용

#include <iostream>
#include <algorithm>
using namespace std;
//소수인지 판별해주는 함수
bool isPrime(int number)
{
	number = abs(number);
	if (number == 0 || number == 1) 
		return true;

	int divisor;
	for (divisor = number / 2; number % divisor != 0; --divisor);

	//if no divisor greater than 1 is found, it is a prime number
	return divisor == 1;
}
int main()
{
	int ary[] = { 1,2,3,4,5,6,7,8,9 };
	int* pbegin = ary; //배열의 이름은 시작주소
	int* pend = ary + sizeof(ary) / sizeof(int); //배얼 마지막 원소 다음을 가리킴
	int* preturn = nullptr;

	cout << "각 배열의 주소 확인하기 " << endl;
	for (int* it = pbegin; it < pend; it++)
	{
		cout << "주소: " << it << " 값: " << *it << endl;
	}
	cout << "주소: " << pend << " pend " << endl << endl;
	
	//###### remove_if 함수 - 소수일 경우 제거 
	preturn = remove_if(pbegin, pend, isPrime);

	cout << "after remove_if function" << endl;
	cout << "pbegin: " << pbegin << " preturn: " << preturn << " pend: " << pend << endl;
	for (int* it = pbegin; it < pend; it++)
	{
		cout << "주소: " << it << " 값: " << *it << endl;
	}
	cout << "주소: " << pend << " pend " << endl << endl;

	//###### remove 함수 
	preturn = remove(pbegin, pend, 6);

	cout << "after remove function" << endl;
	cout << "pbegin: " << pbegin << " preturn: " << preturn << " pend: " << pend << endl;

	for (int* it = pbegin; it < pend; it++)
	{
		cout << "주소: " << it << " 값: " << *it << endl;
	}
	cout << "주소: " << pend << " pend " << endl << endl;

	return 0;
}

배열로 먼저 간단히 테스트 코드를 작성해봤어요.

1. 1부터 9까지 배열이 있는데 여기서 소수를 remove_if로 먼저 제거하고

2. 그 다음 remove로 값 6을 제거해주는 코드입니다.

remove_if 매개변수로 bool값을 리턴해주는 소수 판별 함수를 넣어줬어요.

배열은 iterator가 따로 없으니 포인터로 범위 설정!

맨 처음 소수(노란색 밑줄)에 해당하는 1,2,3,5,7이 remove_if 수행 이후 사라진 것을 알 수 있어요.

하지만 남은 4,6,8,9 값이 당겨졌을 뿐 배열 총 개수는 변하지 않았죠?ㅎㅎ 

그러면 4,6,8,9,5,6,7,8,9가 되었는데 여기서 remove로 6을 제거하도록 해봤습니다.

결과론적으로 6 두개가 사라져 4,8,9,5,7,8,9,8,9가 된 것을 확인할 수 있어요.

 

리턴으로 반환한 preturn 포인터가 어디를 가리키는지 유심히 봐봅시다.

1,2,3,4,5,6,7,8,9에서 소수를 제거하면 4,6,8,9인데 이 다음을 가리키는 것을 볼 수 있어요. 그니까 잔여물이 시작되는데를 가리킨다 생각하면 되겠죠?

 

2. STL Vector erase 함수와 remove_if 조합으로 완전제거 하기 

1번의 예시처럼, 1,2,3,4,5,6,7,8,9에서 소수(1,2,3,5,7)을 제거했으면, 4,6,8,9만 남아야하는데 앞으로 당기기만 하고 길이정리를 하지 않는 특수처리 방식 때문에 뒤에 잔여 데이터(?)가 남았죠.

이를 완전 제거해주기 위해 보통 STL의 erase함수와 같이 사용합니다. remove 반환값이 잔여물 시작이라서, 완전 삭제 해주는 erase의 첫 범위 매개변수로 넣어주면 돼요. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool isPrime(int number);
int main()
{
	vector<int> ary = { 1,2,3,4,5,6,7,8,9 };
	for (vector<int>::iterator it = ary.begin(); it < ary.end(); it++)
	{
		cout << "주소: " << &(*it) << " 값: " << *it << endl;
	}  
	cout << endl;

	//remove prime number 
	ary.erase(remove_if(ary.begin(), ary.end(), isPrime), ary.end());

	cout << "after remove_if & erase combination" << endl;
	for (vector<int>::iterator it = ary.begin(); it < ary.end(); it++)
	{
		cout << "주소: " << &(*it) << " 값: " << *it << endl;
	}
	return 0;
}

소수를 판별하는 isPrime 함수는 1번 예시와 동일합니다. 

수행 전에는 개수가 9개였는데 수행 후에는 소수가 완전 제거되고 4개만 남았습니다~! 제거가 깔끔하게 된 것을 확인할 수 있어요.

3. 홀수 요소 람다 이용해 삭제하기 with LIST

#include <iostream>
#include <algorithm>
#include <list>
using namespace std;
int main()
{
	list<int> ary = { 1,2,3,4,5,6,7,8,9 };
	ary.erase(remove_if(ary.begin(), ary.end(), [](int num){return num % 2;}), ary.end());
	for (int n : ary)
		cout << n << ", ";
	cout << endl;
	return 0;
}

이번엔 LIST STL을 사용해보았습니다. 알고리즘은 람다와 합이 좋죠 ㅎㅎ

1,2,3,4,5,6,7,8,9에서 홀수를 제거했더니 2,4,6,8만 잘 남은 것을 확인할 수 있어요.

remove 구현은 어떻게 되어있는가?

[C++11 remove]

template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator result = first;
  while (first!=last) {
    if (!(*first == val)) {
      if (result!=first)
        *result = move(*first);
      ++result;
    }
    ++first;
  }
  return result;
}

[C++11 remove_if]

template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
                             UnaryPredicate pred)
{
  ForwardIterator result = first;
  while (first!=last) {
    if (!pred(*first)) {
      if (result!=first)
        *result = std::move(*first);
      ++result;
    }
    ++first;
  }
  return result;
}

오늘은 알고리즘 라이브러리에 있는 remove와 remove_if 함수에 대해 알아봤어요 ㅎㅎ

도움이 되셨다면 공감은 어떤가요? 다음 포스팅에서 봐요 :) 

반응형