이 게시물은 C++에서 Vector에서 중복을 제거하는 방법에 대해 설명합니다.
1. 사용 std::remove 기능
간단한 해결책은 Vector를 반복하고 각 요소에 대해 Vector에서 모든 중복 항목이 있는 경우 삭제하는 것입니다. 우리는 이것을 위해 우리 자신의 루틴을 작성하거나 사용할 수 있습니다 std::remove 코드를 우아하게 만드는 알고리즘. 이 접근 방식은 일정한 공간을 차지하지만 O(n2) 시각.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> #include <vector> #include <algorithm> voidremove(std::vector<int>&v) { auto end =v.end(); for (auto it=v.begin();it!=end;++it){ end=std::remove(it+ 1,end,*it); } v.erase(end, v.end()); } int main() { std::vector<int> v={5,2, 1,3,4,2, 2,4,5,5, 6}; remove(v); for(auto it= v.cbegin();it!= v.cend();++it){ std::cout<<*it<<' '; } return0; } |
다운로드 코드 실행
결과:
5 2 1 3 4
2. 사용 std::unordered_set 기능
여기에서 아이디어는 Vector를 반복하고 세트에서 방문한 요소를 추적하는 것입니다. 이전에 요소가 보이지 않으면 처음부터 사용 가능한 다음 위치에 Vector에 다시 삽입합니다.
이 접근 방식은 설정된 데이터 구조를 위한 추가 스토리지가 필요하고 다음에서 실행됩니다. O(n) 시간 std::unordered_set 이상 사용 std::set.
voidremove(std::vector<int>&v) { std::vector<int>::iterator itr=v.begin(); std::unordered_set<int>s; for (auto curr=v.begin(); curr!=v.end(); ++curr) { if (s.insert(*curr).second){ *itr++=*curr; } } v.erase(itr, v.end()); } |
다운로드 코드 실행
다음은 집합을 사용하는 또 다른 솔루션입니다. 아이디어는 세트의 모든 Vector 요소를 삽입하고 세트의 내용을 Vector에 다시 복사하는 것입니다. 이것은 세트에 요소를 삽입하면 모든 세트 요소가 구별되어야 하므로 모든 중복을 제거하는 것처럼 작동합니다. 이렇게 하면 Vector 요소의 원래 순서가 변경될 수 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <iostream> #include <vector> #include <unordered_set> intmain() { std::vector<int>v={ 5,2,1,3, 4,2,2,4, 5,5}; std::unordered_set<int>s(v.begin(), v.end()); v.assign(s.begin(), s.end()); for(auto it=v.cbegin();it !=v.cend();++it) { std::cout<<*it <<' '; } return0; } |
다운로드 코드 실행
결과:
4 3 1 2 5
3. 사용 std::remove_if ~와 함께 std::unordered_set 기능
또 다른 효율적인 솔루션은 std::remove_if ~와 함께 std::unordered_set.
최종 논리는 Vector를 반복하고 집합에서 방문한 요소를 추적하는 이전 솔루션과 유사하게 유지됩니다. 그리고 이전에 요소가 보이지 않으면 처음부터 사용 가능한 다음 위치에 Vector에 다시 삽입합니다.
주의 std::remove_if 알고리즘은 기본 컨테이너에 대한 지식이 없습니다. 실제로 컨테이너에서 요소를 제거하는 것이 아니라 모든 요소를 이동합니다. 안전한 요소를 맨 앞에 놓고 끝이 있어야 하는 위치를 가리키는 반복자를 반환하므로 에 대한 단일 호출로 삭제할 수 있습니다. std::erase. 이 기술은 일반적으로 관용구 지우기.
voidremove(std::vector<int>&v) { std::unordered_set<int>s; auto end= std::remove_if(v.begin(), v.end(), [&s](intconst&i){ return!s.insert(i).second; }); v.erase(end, v.end()); } |
다운로드 코드 실행
4. 사용 std::copy_if ~와 함께 std::unordered_set 기능
다음을 사용하여 동일한 결과를 얻을 수 있는 방법은 다음과 같습니다. std::copy_if 알고리즘. 이것은 C++11 이상에서 작동합니다.
voidremove(std::vector<int>&v) { std::unordered_set<int>s; auto end= std::copy_if(v.begin(), v.end(),v.begin(), [&s](intconst &i){ return s.insert(i).second; }); v.erase(end, v.end()); } |
다운로드 코드 실행
결과:
5 2 1 3 4
5. 사용 std::remove_copy_if ~와 함께 std::unordered_set 기능
그만큼 std::remove_copy_if 알고리즘도 아래와 같이 작동합니다.
voidremove(std::vector<int>&v) { std::unordered_set<int>s; auto end=std::remove_copy_if(v.begin(),v.end(), v.begin(), [&s](intconst&i){ return!s.insert(i).second; }); v.erase(end, v.end()); } |
다운로드 코드 실행
6. 사용 std::sort ~와 함께 std::unique 기능
마지막으로 Vector를 정렬하고 호출할 수도 있습니다. std::unique, 중복된 연속 요소를 제거합니다. 이것은 작동하지만 요소의 원래 순서를 유지하지 않습니다. 이 접근 방식은 일정한 공간을 차지하지만 O(n.log(n)) 시각.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> intmain() { std::vector<int>v ={5,2,1, 3,4,2,2, 4,5,5}; std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); for(auto it=v.cbegin();it !=v.cend();++it) { std::cout<<*it <<' '; } return0; } |
다운로드 코드 실행
결과:
1 2 3 4 5
이것이 C++의 Vector에서 중복을 제거하는 것입니다.