C++는 빠르고, INT와 쌍 벡터 int 형의 2 개 분류되지 않은 벡터가 있습니다 다른 벡터

Question

고유 벡터의 요소를 제거 항목의 수백만을 포함

std::vector <int> v1; 
std::vector <std::pair<int, float> > v2; 

int로.

v2부터 가능한 한 빨리 항목을 제거하는 방법 (예 : v2.first에 포함되지 않음)?

예 :

v1: 5 3 2 4 7 8 
v2: {2,8} {7,10} {5,0} {8,9} 
---------------------------- 
v1: 3 4 

Answer 1

이 트릭은 내가 가능한 한 빨리이 작업을 수행하는 데 사용하는 것 같습니다의 모든 저장

1. 사용 연관 컨테이너의 일종 (아마도 std::unordered_set) 정수를 두 번째 벡터에 추가하여 첫 번째 벡터의 일부 정수를 제거해야하는지 여부를보다 효율적으로 확인할 수 있습니다.

2. 초기 벡터에서 요소를 삭제하는 방식을 최적화하십시오.

더 구체적으로, 나는 다음을 할 것이다. std::unordered_set을 만들고 두 번째 벡터에서 쌍의 첫 번째 정수 인 모든 정수를 더하기 시작하십시오. 이렇게하면 특정 O이 세트에 있는지 여부를 확인하기 위해 (예상) O (1) 조회 시간이 제공됩니다.

이제이 작업을 완료 한 후 std::remove_if 알고리즘을 사용하여 해시 테이블에있는 원래 vector의 모든 항목을 삭제하십시오. 이 작업을 수행하는 람다를 사용할 수 있습니다

std::unordered_set<int> toRemove = /* ... */ 
v1.erase(std::remove_if(v1.begin(), v1.end(), [&toRemove] (int x) -> bool { 
    return toRemove.find(x) != toRemove.end(); 
}, v1.end()); 

unordered_set 모든 것을 저장하는 첫 번째 단계는 예상 걸립니다 O (n)의 시간. 두 번째 단계는 모든 삭제 작업을 끝까지 모아서 조회 작업에 약간의 시간이 걸리는 것으로 예상되는 총 O (n) 작업을 수행합니다. 전체 프로세스에 대해 O (n) 시간, O (n) 공간이 예상됩니다.

두 번째 벡터 (쌍)를 정렬 할 수 있다면 O (n log n) 최악의 경우 O (log n) 최악 사례 공간에서 다음과 같이 할 수 있습니다. 키를 누른 다음 std::binary_search을 사용하여 이 첫 번째 vector에서 제거되어야하는지 여부를 확인하십시오. 각각의 이진 검색은 O (log n) 시간이 걸리므로 정렬에 필요한 총 시간은 O (n log n)이고 첫 번째 벡터의 요소 당 O (log n)), 삭제를위한 O (n) 시간으로 총 O (n log n)을 준다.

희망이 도움이됩니다.

Answer 2

도 용기를 정렬하고 정렬이 실제로 너무 비싸거나 메모리가 부족이라고 가정 : 또는

v1.erase(std::remove_if(v1.begin(), v1.end(), 
         [&v2](int i) { 
         return std::find_if(v2.begin(), v2.end(), 
              [](const std::pair<int, float>& p) { 
               return p.first == i; }) 
           != v2.end() }), v1.end()); 

first에 일종의 v2 대신 이진 검색을 사용합니다. 메모리가 충분하면 unordered_set을 사용하여 first을 v2으로 정렬합니다.

완전한 C++ 03 버전 :

#include <iostream> 
#include <vector> 
#include <utility> 
#include <algorithm> 

struct find_func { 
    find_func(int i) : i(i) {} 

    int i; 
    bool operator()(const std::pair<int, float>& p) { 
    return p.first == i; 
    } 
}; 

struct remove_func { 
    remove_func(std::vector< std::pair<int, float> >* v2) 
    : v2(v2) {} 
    std::vector< std::pair<int, float> >* v2; 
    bool operator()(int i) { 
    return std::find_if(v2->begin(), v2->end(), find_func(i)) != v2->end(); 
    } 
}; 


int main() 
{ 
    // c++11 here 
    std::vector<int> v1 = {5, 3, 2, 4, 7, 8}; 
    std::vector< std::pair<int, float> > v2 = {{2,8}, {7,10}, {5,0}, {8,9}}; 
    v1.erase(std::remove_if(v1.begin(), v1.end(), remove_func(&v2)), v1.end()); 

    // and here 
    for(auto x : v1) { 
    std::cout << x << std::endl; 
    } 

    return 0; 
}