vector :: erase를 사용할 때 무엇이 ​​충돌 할 수 있습니까?

Question

벡터에서 일부 작업을 수행하려고합니다. 어떤 경우에는 벡터에서만 지우기를 호출합니다.

여기 내 코드

while(myQueue.size() != 1) 
{ 
    vector<pair<int,int>>::iterator itr = myQueue.begin(); 
    while(itr != myQueue.end()) 
    { 
     if(itr->first%2 != 0) 
      myQueue.erase(itr); 
     else 
     { 
      itr->second = itr->second/2; 
      itr++; 
     } 
    } 
} 

나는 호환되지 않는 메시지 벡터 반복자이 충돌을 얻고 2 iteration.And에서 충돌을 얻고있다.

충돌의 원인은 무엇일까요? erase() 만약

Answer 1

이 무효화 반복자라고하며 그 반복자는 다음 루프의 다음 반복에 액세스 할 수 있습니다. std::vector::erase() 다음 반복자 삭제 된 반복자 후 반환

itr = myQueue.erase(itr); 

Answer 2

감안할 때 b의 범위 어딘가에 반복자 i의 시작과 벡터 범위의 끝 과거 e 하나의 소거 동작입니다 반복자 범위 [b, e)i부터 e까지 모든 반복기를 무효화합니다. 그래서 erase에 전화 할 때 매우 신중해야합니다.

itr = myQueue.erase(itr); 

또 다른 방법은 i 요소와 마지막 요소를 교체 한 후 마지막을 삭제하는 것 다음 erase 회원은 후속 작업을 위해 할 수 있습니다 당신이 해야지 그것을 사용하는 새로운 반복자를 반환한다. i 이상의 요소 이동 횟수가 적기 때문에 더 효율적입니다.

또한

myQueue.swap(i, myQueue.back()); 
myQueue.pop_back(); 

, 그것의 모양에서, 당신은 왜 vector을 사용하고 있습니까? queue이 필요한 경우 std::queue을 사용할 수도 있습니다.

Answer 3

이것은 정의되지 않은 동작입니다. 특히, 반복자를 지우면 무효화되고 더 이상 사용할 수 없습니다. 다시 다음

for (auto it = v.begin(); it != v.end();) { 
    if (it->first % 2 != 0) 
     it = v.erase(it); 
    else { 
     it->second /= 2; 
     ++it; 
    } 
} 

그러나, 자신의 루프 롤 오히려 알고리즘을 사용하지보다 효율적이고 관용적 될 것입니다 : 루프를 줄이기의 관용적 인 방법은 무엇인가 같은 것

v.erase(std::remove_if(v.begin(), 
         v.end(), 
         [](std::pair<int,int> const & p) { 
          return p.first % 2 != 0; 
         }), 
     v.end()); 
std::transform(v.begin(), v.end(), v.begin(), 
       [](std::pair<int,int> const & p) { 
        return std::make_pair(p.first, p.second/2); 
       }); 

이 방법의 장점은 지우는 동안 요소의 복사본 수가 적다는 것입니다. (범위에 남아있는 각 유효한 요소는 한 번만 복사됩니다.) 잘못 입력하는 것이 더 어렵습니다. 즉, 무효화 된 반복기를 잘못 사용합니다 ...) 단점은 remove_if_and_transform이 없기 때문에 2 패스 알고리즘이며,있을 경우 효율성이 떨어질 수 있습니다. 많은 수의 요소들.

Answer 4

루프를 수정하면서 반복을 반복하는 것은 일반적으로 까다 롭습니다. 소거 제거 관용구 :

따라서 비 연관 시퀀스 가능한 관용구 ++ 특정 C가있다.

IT는 erase 방법의 범위 과부하와 remove_if 알고리즘의 사용을 결합 :

술어 어느 전형적인 펑 객체 또는 새로운 C++ 11 람다 구문을 사용하여 표현된다

myQueue.erase(
    std::remove_if(myQueue.begin(), myQueue.end(), /* predicate */), 
    myQueue.end()); 

.

// Functor 
struct OddKey { 
    bool operator()(std::pair<int, int> const& p) const { 
     return p.first % 2 != 0; 
    } 
}; 

/* predicate */ = OddKey() 

// Lambda 
/* predicate */ = [](std::pair<int, int> const& p) { return p.first % 2 != 0; } 

람다 형식은 더 간결하지만 덜 문서화 될 수 있으며 (이름 없음) C++ 11에서만 사용할 수 있습니다. 당신의 취향과 제약에 따라, 가장 적합한 것을 골라주십시오.

---

코드 작성 방법을 향상시킬 수 있습니다 : Boost.Range을 사용하십시오.

typedef std::vector< std::pair<int, int> > PairVector; 

void pass(PairVector& pv) { 
    auto const filter = [](std::pair<int, int> const& p) { 
     return p.first % 2 != 0; 
    }; 
    auto const transformer = [](std::pair<int, int> const& p) { 
     return std::make_pair(p.first, p.second/2); 
    }; 

    pv.erase(
     boost::transform(pv | boost::adaptors::filtered(filter), 
         std::back_inserter(pv), 
         transformer), 
     pv.end() 
    ); 
} 

당신은 많은 다른 사람들과 함께 transform 및 설명서의 filtered adaptor을 찾을 수 있습니다.