컨테이너에서 고유 한 요소 가져 오기 [C++]

Question

컨테이너에서 유일한 요소 만 얻으려고했습니다. srcContainer이 고유 한 요소를 원하는 컨테이너라고 가정 해 보겠습니다. 나는 세 가지 옵션 바라 보았다 : 표준 :

std::sort(srcContainer.begin(), srcContainer.end()); 
    srcContainer.erase(std::unique(srcContainer.begin(), srcContainer.end()), srcContainer.end()); 

독특한 사용 BOOST :: 독특한 사용

1. boost::erase(srcContainer, boost::unique<boost::return_found_end>(boost::sort(srcContainer))); 
   

2. 내 자신의 방법

   std::set<T> uniqueElems(srcContainer.begin(), srcContainer.end()); 
   srcContainer.clear(); 
   srcContainer.insert(srcContainer.end(), uniqueElems.begin(), uniqueElems.end()); 
   

1. 및 2.의 문제는 원래 srcContainer에서 멤버가 발생한 순서를 변경한다는 것입니다. 3. 순서 변경이없고, 또한 1.과 2에 비해 성능이 훨씬 우수합니다 (위의 3에 명시 적 정렬이 없기 때문입니까?). (3 개) 상기 방법 및 srcContainer의 요소 수의 경과 벽시계 시간은 다음과 같음 : - 표준 : 고유 = 1.04779 초 srcContainer의

1. 크기 = 1E + 6
   (정수를 포함)
   - BOOST :: 독특한 = 1.04774 초
   이 - 자신의 방법 = 0.481638 초

2. srcContainer의 크기 (INT를 포함 egers) = 1E + 8
   - 표준 : 독특한 = 151.554 초
   - 독특한 BOOST :: = 151.474 초
   - 자신의 방법 = 57.5693 초

내 질문은 :

1. std :: unique 또는 BOOST :: unique 또는 다른 코드를 사용하여 고유를 찾고 더 원래의 순서를 유지하는 더 좋은 방법이 있습니까? 컨테이너에?
2. 위의 방법 3.을 사용하는 데 문제가 있습니다. 다음 성능 프로파일 srcContainer 들어

작성 하였다

std::vector<int> srcContainer; 
int halfWay = numElems/2; 
for (size_t k=0; k<numElems; ++k) { 
    if (k < halfWay) 
     srcContainer.push_back(k); 
    else 
     srcContainer.push_back(k - halfWay); 
} 

수정 사항 :
방법은도 3 요소의 순서를 변경하는 것이 코멘트 동의. 주문을 변경하지 않고 고유 한 요소를 얻는 더 좋은 방법이 있습니까? 소스 데이터에 대한 정보를 기반으로

감사

Answer 1

편집 : 이유는 세트 삽입 빨리 벡터를 정렬하는 것보다 완료보고있는 당신의 입력 데이터가이 개 이미 정렬 범위 것입니다.quicksort (일반적으로 std::sort에 의해 사용됨)의 경우 이것은 퇴보 한 사례이며 가능한 최악의 입력 중 하나입니다. 1e8의 입력 크기를 std::sort에서 std::stable_sort으로 변경하면 런타임을 ~ 25 초에서 < 9 초로 단축 할 수 있습니다.

원래 항목 순서를 유지하려면 다음과 같이 모든 항목의 해시를 유지하는 방법을 시도해 볼 수 있습니다. 나는 아니오 아래 스케치로이의 성능이 어떨지하지만, 예를 들어 당신이 해싱 및 remove_if과 접근 방법을 활용할 수있는 아이디어 :

요소 경우 : 내 대답의

struct Remover 
{ 
    explicit Remover(hash& found_items) : found_items_(found_items) { } 
    bool operator()(const Iter& item) { retval = <does exist in hash>; add to hash; return retval; } 

    hash& found_items_; 
}; 

hash dup_finder; 
Remover remover(dup_finder); 
std::erase(std::remove_if(src.begin(), src.end(), remover), src.end()); 

원본 구성 요소 원본 컨테이너에서 이미 정렬되어있는 경우 unique을 호출하기 전에 정렬보다는 stable_sort을 사용하면 성능이 향상 될 수 있습니다. yoru 데이터에 대한 추가 정보없이 추측 할 수 없습니다. 옵션 3이 1보다 나은 성능을 내기 위해 무엇이 발생할 수 있습니까?

옵션 3은 고유 항목을 제거해야하지만 주장하는 바에도 불구하고 은 여전히은 처음 두 옵션이하는 것과 똑같은 방식으로 항목을 재정렬합니다.