std :: vector에서 여러 객체 지우기?

Question

여기 내 문제가 있습니다, 내가 std :: vector ints 함께 말할 수 있습니다.

50904090806080이라고 가정 해 봅시다.

두 번째, 다섯 번째 및 세 번째 요소를 제거해야한다는 것을 알고 있습니다. 필자는 제거 할 요소의 순서와 횟수를 항상 알 필요가 없습니다. 문제는 요소를 지우는 것입니다. 그러면 다른 요소의 색인이 변경됩니다. 따라서 어떻게 이들을 지우고 인덱스 변경을 보상 할 수 있습니까?

1. 요소의 원래 순서를 유지하지 않는 빠른 방법 :

감사

Answer 1

나는 여러 가지 방법을 제공하고 (오프셋 (offset)와 지우기 선형 다음 옵션을하지 않는 정렬)

지울 요소에 벡터의 현재 마지막 요소를 할당 한 다음 마지막 요소를 지 웁니다. 이렇게하면 큰 움직임을 피할 수 있고 마지막 색인을 제외한 모든 색인은 일정하게 유지됩니다. 뒤에서 지우기를 시작하면 사전 계산 된 모든 색인이 정확합니다. I이 표시

void quickDelete(int idx) 
{ 
    vec[idx] = vec.back(); 
    vec.pop_back(); 
} 

본질적 ... 소거 제거 관용구의 자필 버전 Klaim으로 지적되고

2 요소의 원래 순서를 유지하는 느린 방법

1 단계 : 삭제할 벡터 요소를 모두 표시합니다 (예 : 특수 값 사용). O (삭제할 색인 |)이 있습니다.

2 단계 : v.erase(remove (v.begin(), v.end(), special_value), v.end());을 사용하여 표시된 모든 요소를 ​​지 웁니다. 이것은 O (| v |)를 가진다.

따라서 인덱스 목록이 벡터보다 짧은 경우 총 실행 시간은 O (| vector v |)입니다.

3 요소의 원래 순서 보유 느린 다른 방법

사용 술어 및 https://stackoverflow.com/a/3487742/280314에 기재된 경우 삭제한다. 이것을 효율화하고 의 요구 사항을 존중하려면 "정렬로 선형 적으로 지우기"를 선택하지 말아야합니다. 제 생각은 해시 테이블을 사용하여 술어를 구현하고 해시 테이블에 저장된 색인을 조정하여 삭제가 true를 반환 할 때 진행되도록하는 것입니다. Klaim은 제안했다.

http://www.cplusplus.com/reference/algorithm/remove_if/이 (remove-erase idiom 참조) 항목을 삭제하는 것을 잊지 마세요 참조 : 술어 당신은 당신이 원하는 것을 달성 할 수 remove_if 알고리즘을 사용하여

Answer 2

.

당신의 술어는 단순히 각 값의 idx를 유지하여 true를 반환 할 때마다 유지하는 모든 색인을 제거하고 줄입니다.

그렇다면 제거 삭제 관용구를 사용하여 각 객체를 제거 할 수 있다면 간단하게 작업을 수행하면됩니다.

Answer 3

나는 이 아닌 요소를 이동합니다은 임시 벡터로 지우고 원래의 벡터로 바꾸고 싶습니다.

Answer 4

항목을 뒤로 지 웁니다. 즉, 가장 높은 인덱스를 먼저 지운 다음 가장 높은 인덱스를 지우십시오. 이전의 반복기 또는 인덱스를 무효화하지 않으므로 다중 지우기 호출의 명백한 접근 방식을 사용할 수 있습니다.

Answer 5

겠습니까이 작품 :

void DeleteAll(vector<int>& data, const vector<int>& deleteIndices) 
{ 
    vector<bool> markedElements(data.size(), false); 
    vector<int> tempBuffer; 
    tempBuffer.reserve(data.size()-deleteIndices.size()); 

    for (vector<int>::const_iterator itDel = deleteIndices.begin(); itDel != deleteIndices.end(); itDel++) 
     markedElements[*itDel] = true; 

    for (size_t i=0; i<data.size(); i++) 
    { 
     if (!markedElements[i]) 
      tempBuffer.push_back(data[i]); 
    } 
    data = tempBuffer; 
} 

그것은 상관없이 삭제 얼마나 많은 요소, 오 (n)이 작동 없습니다. 벡터 인라인 순서를 재정 의하여 효율성을 얻을 수 있습니다 (하지만이 방법은 더 읽기 쉽습니다).