본문으로 바로가기

[C++]벡터 중복제거(sort,unique,erase)

category C++ 2018. 5. 21. 10:16


벡터에서 중복 원소제거가 필요할 때가 있습니다.


그럴때 sort,unique,erase 의 기능을 적절히 활용하여 중복원소를 제거 할 수 있습니다.


먼저 백터하나를 만든뒤 데이터를 막넣습니다. (algorithm 을 include 해주어야합니다 sort와 unique 사용을위해)

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

vector<int> s;

int main()
{
	s.push_back(1);
	s.push_back(2);
	s.push_back(1);
	s.push_back(3);
	s.push_back(2);
	s.push_back(1);
	s.push_back(2);
	
	printf("막넣은 백터s\n");
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
}
막넣은 백터s
1       2       1       3       2       1       2

그리고 바로 unique 를 해봅니다.

	printf("바로 unique(s.begin(),s.end());\n");
	unique(s.begin(),s.end());	
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
바로 unique(s.begin(),s.end());
1       2       1       3       2       1       2

바로 unique를 하게되면 아무런 변화가 없습니다.


이유는 unique는 연속된 중복 원소를 vector의 제일 뒷부분으로 쓰레기값으로 보내버립니다.


이를 확인하기위해 sort를 이용하여 vector를 정렬한뒤 unique를 해보겠습니다.

	printf("정렬 sort(s.begin(), s.end());\n");
	sort(s.begin(), s.end());
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
정렬 sort(s.begin(), s.end());
1       1       1       2       2       2       3
	printf("정렬후 unique(s.begin(),s.end());\n");
	unique(s.begin(),s.end());	
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
정렬후 unique(s.begin(),s.end());
1       2       3       2       2       2       3

정렬을 한 뒤 unique를하니 중복원소인 1,1,2 가 맨뒤로 옮겨졌는데요 이때 1,1,2 그대로 옮겨진것이아니라 2,2,3으로 옮겨졌습니다. 이는 c++ 레퍼런스를 봐도 뒤에 ? ? ? 로 알 수 없는 값이 붙는거 처럼 나와있는데요 정확한 이유를 아시는분은 알려주세요 ㅜㅜ 저도 많이 궁금합니다.


C++ unique reference

  int myints[] = {10,20,20,20,30,30,20,20,10};           // 10 20 20 20 30 30 20 20 10
  std::vector<int> myvector (myints,myints 9);

  // using default comparison:
  std::vector<int>::iterator it;
  it = std::unique (myvector.begin(), myvector.end());   // 10 20 30 20 10 ?  ?  ?  ?


다음은 erase 로 뒤에붙은 쓰레기값을 제거해주면 백터의 중복원소를 제거하는데 성공합니다. 

unique가 끝났으면 반환되는값은 vector의 쓰레기값의 첫번째 위치가 되는데요, 이때문에 바로 unique후 erase가 가능합니다.

	printf("백터.erase(unique(s.begin(),s.end()),s.end())\n");
	s.erase(unique(s.begin(),s.end()),s.end());
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
백터.erase(unique(s.begin(),s.end()),s.end())
1       2       3

이렇게 vector의 중복원소를 제거하는 방법에대해 알아보았습니다.




int형이아닌 문자도 중복제거가 가능합니다.

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

vector<string> s;

int main()
{
	s.push_back("a");
	s.push_back("b");
	s.push_back("a");
	s.push_back("c");
	s.push_back("b");
	s.push_back("a");
	s.push_back("b");
	
	printf("막넣은 백터s\n");
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
	
	printf("정렬 sort(s.begin(), s.end());\n");
	sort(s.begin(), s.end());
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");

	printf("백터.erase(unique(s.begin(),s.end()),s.end())\n");
	s.erase(unique(s.begin(),s.end()),s.end());
	for(int i=0;i<s.size();i  )
		cout<<s[i]<<"\t";
	printf("\n\n");
}
막넣은 백터s
a       b       a       c       b       a       b
정렬 sort(s.begin(), s.end());
a       a       a       b       b       b       c
백터.erase(unique(s.begin(),s.end()),s.end())
a       b       c



댓글을 달아 주세요

  1. BlogIcon .    2019.06.29 23:30 신고

    unique는 중복 제거를 하고, 마지막 원소의 iterator값을 리턴합니다.

    원래 원소가 10개였고, 중복 다 빼고남은개 7개라고 치면 unique는 앞에서 7개까지 unique한 원소들로 채우고, 나머지들은 뒤에칸에 몰아넣고
    7번째 원소다음꺼 포인터를리턴하는거죠

    그래서 대충 아래와 같이 써야합니다.

    vector<int> arr;
    //input data
    sort(arr.begin(), arr.end());
    arr.resize( unique(arr.begin(), arr.end()) - arr.begin() );

    요렇게 하면 , arr에 중복 제거된 원소들만 남게 됩니다.

    • BlogIcon 뉴우비 2020.12.19 17:43

      나머지들을 뒤에 칸에 몰아넣는게 아니라, vector의 앞부분에 중복되지 않은 원소들로 채워 넣다보니 자연스레 뒷부분은 쓰레기값이 되는거 같습니다.

  2. 지나가는 행인 2020.06.06 18:13

    printf("백터.erase(unique(s.begin(),s.end()),s.end())\n");
    s.erase(unique(s.begin(),s.end()),s.end());
    for(int i=0;i<s.size();i )
    cout<<s[i]<<"\t";

    i++ 이거 안해서 무한 루프 돌아요

  3. khkh46312@daum.net 2020.12.19 17:36

    안녕하세요

  4. BlogIcon Modin 2021.02.18 15:27 신고

    "바로 unique를 하게되면 아무런 변화가 없습니다.

    이유는 unique는 연속된 중복 원소를 vector의 제일 뒷부분으로 쓰레기값으로 보내버립니다."

    라고 하셨는데, 정확히 말하자면 중복 원소를 제일 뒷부분으로 보내는 게 아닙니다.

    unique는 두 개의 포인터로 작동합니다. 두 포인터의 이름은 first와 result입니다.

    first는 무엇일까요? 단어 의미대로 벡터의 맨 첫 번째 원소를 가리키는 포인터입니다.

    따라서 비교가 진행될 수록 다음 원소로 한칸 씩 이동합니다.

    그럼 result는 무엇일까요? 비교 시 중복 원소가 아니라고 판단한 경우 값을 입력하는 곳을 가리키는 포인터입니다.

    그래서 정확히 말하자면 unique는 "result가 가리키고 있는 값과 first가 가리키고 있는 값이 다르다면 result를 한 칸 옮기고 거기에 first가 가리키는 값을 덮어 씌우는 라이브러리입니다."

    그런데 result는 포인터이죠? 포인터는 동시에 하나의 값만을 가리킵니다.

    따라서 이전에 1을 가리키고 다음에 2를 가리킨 다음 다시 1을 가리킨다면 이것이 중복 원소인지 알지 못합니다.

    그럼으로 정렬 하여 같은 값을 가지는 원소를 이웃하게 배치해야 합니다. 그러면 이전에 나온 원소가 탐색이 진행 되도 다시 나오지 않을테니까 말이죠.

    만약 그러지 않으면 중복된 원소의 값이 또 나올 수도 있고 아닐 수도 있습니다. 이를 정확히 알 수 없음으로 뒤에 물음표가 있는 것입니다.