[c++] unique 함수로 vector 원소 중복 제거

자바 공부해야하는데 C++로 백준 풀다가 이런 함수를 알게됐다.

궁금한 건 못참으니.. 최대한 빠르게 가볍게 확인해보자.. :D

 

일단 unique 함수를 사용해서 vector 원소 중복 제거를 할 수 있었다.

 

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

int main() {
	vector <int> v = { 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 8 };


	cout << "- 기존 벡터 -" << '\n';
	for (auto n : v) cout << n << ' ';
	cout << '\n';

	for (size_t i = 0; i < v.size(); ++i) {
		cout << "값: " << v[i] << ", 주솟값: " << &v[i] << '\n';
	}
	cout << '\n';

	cout << "- unique 함수 사용 후 -" << '\n';
	unique(v.begin(), v.end());
	for (auto n : v) cout << n << ' ';
	cout << '\n';

	for (size_t i = 0; i < v.size(); ++i) {
		cout << "값: " << v[i] << ", 주솟값: " << &v[i] << '\n';
	}
	cout << '\n';
}

 

위의 코드를 실행하면 다음과 같이 결과가 나타난다.

 

1 1 2 2 3 3 3 4 5 5 5 6 7 7 8

1 2 3 4 5 6 7 8 5 5 5 6 7 7 8

---

 

 

 왜 이렇게 작동하게 됐는지 이해가 되지 않아 실제로 어떻게 작동하는지 궁금했다. 따라서 <alogorithm> 헤더에 포함된 unique 함수의 구현을 확인해보았다.

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return last;

  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
}

 결과적으로 주어진 범위 내에서 중복된 값을 제거하기 위한 함수이다.

코드를 확인해보면, ForwardIterator 가 있는데, 구글에 검색해보니 반복자의 한 종류였다.

이 반복자는 순방향으로 이동할 수 있는 반복자를 의미하는데, 순서대로 우너소를 탐색할 수 있는 컨테이너에서 사용할 수 있다고 한다.

 

코드는 어렵지 않았다. 먼저 4번째 줄의 주어진 범위가 비어있으면(first와 last가 같다면) 입력범위를 그대로 반환하고 함수를 종료한다. 비어 있는 범위에서 중복을 제거할 필요가 없기 때문이다.

 

다음 result라는 반복자를 선언한 후 이를 입력 범위의 시작점 first로 초기화한다. 이 반복자는 중복이 제거된 범위의 끝을 가리킬 용도이다.

 

그 다음 while 문을 통해 first를 증가시키면서 범위의 끝인 last까지 반복문을 실행한다. 

그리고 while문 내부에서 현재 우너소와 result가 가리키는 우너소를 비교하고 중복을 판단한다. *result는 중복이 제거된 범위의 끝을 가리키는 원소를 의미하고, *first는 현재 원소를 의미한다.

 

현재 원소가 중복되지 않으면, result를 한 번 증가시키고 현재 원소를 해당 위치에 복사한다. 이렇게 중복된 원소가 제거되고, 중복이 제거된 범위의 끝이 하나 증가된다.

 

마지막에 return에서 result를 한 번 더 증가시켜서 중복이 제거된 점위의 끝을 가리키도록 만들고, 이를 반환한다. 이것은 중복이 제거된 범위의 끝을 나타낸다. 호출자는 중복이 제거된 원소의 범위를 알 수 있게 된다.

 

---

 

1 1 2 2 3 3 3 4 5 5 5 6 7 7 8

1 2 3 4 5 6 7 8 5 5 5 6 7 7 8

 

결과 적으로 이렇게 된 것인데, 종료 후 unique 함수는 파란색 글씨 처음인 5를 가리키게 된다.

이후에 erase 함수를 통해서 중복된 부분을 제거시킬 수 있다.

 

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

int main() {
	vector <int> v = { 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 8 };


	cout << "- 기존 벡터 -" << '\n';
	for (auto n : v) cout << n << ' ';
	cout << '\n';


	cout << "- erase와 unique 함수 사용 후 -" << '\n';
	v.erase(unique(v.begin(), v.end()), v.end());
	for (auto n : v) cout << n << ' ';
	cout << '\n';

}