요소의 일부 속성을 기반으로 std :: vector 요소를 어떻게 제거 하시겠습니까?

Question

예를 들어 std::vector<MyClass> 인 경우 MyClass에 공개 메서드가있는 경우 : bool isTiredOfLife(), true를 반환하는 요소는 어떻게 삭제합니까?

v.erase(remove_if(v.begin(), v.end(), 
       mem_fun_ref(&MyClass::isTiredOfLife)), 
     v.end()); 

remove_if 시퀀스에서 아직 마지막 요소 다음의 반복자를 가리키는 반환 remove_if

Answer 1

나는 좋아한다. erase은 처음부터 마지막 ​​인수 (두 반복자 모두)를 지 웁니다.

Answer 2

remove_if를 사용하면이를 수행하는 "올바른 방법"입니다. 항목을 제거하면 반복기가 무효화되므로 반복기를 사용하여 순환하고 지우지 않도록주의하십시오. 사실, erase()를 기본 방법으로 사용하는 모든 예제는 벡터에 대한 나쁜 생각입니다. 지우기는 O (n)이므로 알고리즘 O (n^2)가됩니다. 이것은 O (n) 알고리즘이어야합니다.

아래에 나와있는 방법은 remove_if보다 빠르지 만 remove_if와는 달리 요소의 상대적 순서는 유지되지 않습니다. 주문 유지 (예 : 벡터 정렬)에 신경 쓰면 위의 대답과 같이 remove_if를 사용합니다. 주문에 신경 쓰지 않고 삭제할 항목 수가 일반적으로 벡터의 4 분의 1 미만인 경우이 방법이 더 빠를 수 있습니다.

for(size_t i = 0; i < vec.size();) 
    if(vec[i].isTiredOfLife()) 
    { 
     vec[i] = vec.back(); 
     vec.pop_back(); 
    } 
    else 
     ++i;