std :: vector :: end()에 대한 질문

Question

최근에 다음 함수에서 버그를 수정했는데 그 대답이 저를 놀라게했습니다. 나는 기능 다음 (나는 버그를 발견하기 전에 그것이로 작성) 한 :이 기능은 특정 위치가 '항목'에서 그들을 제거 '항목'벡터의 모든 Item 개체를 발견

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt) 
    { 
     vector<itemPtr>::iterator it; // itemPtr is a typedef for a std::tr1::shared_ptr<item::Item> 
     for(it=items.begin(); it!=items.end(); ++it) 
     { 
      if((*it)->getPosition() == pt) 
      { 
       item::Item item(**it); 
       items.erase(it); 
       vect.push_back(item); 
      } 
     } 
    } 

을하고, 그들을 'vect'에 넣는다. 나중에 putItemsAt이라는 함수는 그 반대를 수행하고 'items'에 항목을 추가합니다. 처음으로 getItemsAt이 정상적으로 작동합니다. 그러나 putItemsAt이 호출 된 후에는 getItemsAt의 for 루프가 '항목'의 끝에서 실행됩니다. '그것은'잘못된 Item 포인터를 가리키고 getPosition()은 segfaults입니다. 직감적으로, 나는 it!=items.end()을 it<items.end()으로 변경했다. 아무도 그 이유를 말할 수 있습니까? 주위를 둘러 보는 것은 반복자를 무효화하는 것이 포함될 수도 있지만 여전히 처음부터 어떻게 작동하는지 이해하지 못한다.

목록의 지우기가 더 효율적이기 때문에 벡터에서 목록으로 '항목'을 변경하려고하므로 궁금합니다. < 연산자가 없으므로 목록에 !=을 사용해야한다는 것을 알고 있습니다. 목록을 사용하여 동일한 문제가 발생합니까?

Answer 1

erase()를 호출하면 해당 반복기가 무효화됩니다. 루프 반복자이므로 무효화 한 후에 '++'연산자를 호출하면 정의되지 않은 동작이됩니다. erase()는 벡터의 다음 항목을 가리키는 새로운 유효한 반복자를 반환합니다.당신은 당신의 루프에 그 시점에서 그 새로운 반복자를 사용하는 즉, 필요

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt) 
{ 
    vector<itemPtr>::iterator it = items.begin(); 
    while(it != items.end()) 
    { 
     if((*it)->getPosition() == pt) 
     { 
      item::Item item(**it); 
      it = items.erase(it); 
      vect.push_back(item); 
     } 
     else 
      ++it; 
    } 
} 

Answer 2

정의되지 않은 동작이 호출됩니다. 벡터에 대한 모든 반복자는 해당 벡터에서 erase이라는 사실로 인해 무효화됩니다. 구현이 원하는 모든 작업을 수행하는 것은 완벽하게 유효합니다.

items.erase(it);으로 전화하면 it이 유효하지 않습니다. 표준을 준수하려면 it이 사망했다고 가정해야합니다.

vect.push_back에 대한 다음 호출에서 해당 유효하지 않은 반복기를 사용하여 정의되지 않은 동작을 호출합니다.

for 루프의 추적 변수로 it을 사용하여 정의되지 않은 동작을 다시 호출합니다.

std::remove_copy_if을 사용하여 코드를 유효하게 만들 수 있습니다.

class ItemIsAtPoint : std::unary_function<bool, item::Item> 
{ 
    Point pt; 
public: 
    ItemIsAtPoint(const Point& inPt) : pt(inPt) {} 
    bool operator()(const item::Item* input) 
    { 
     return input->GetPosition() == pt; 
    } 
}; 

void Level::getItemsAt(vector<item::Item>& vect, const Point& pt) 
{ 
    std::size_t oldSize = items.size(); 
    std::remove_copy_if(items.begin(), items.end(), std::back_inserter(vect), 
     ItemIsAtPoint(pt)); 
    items.resize(vect.size() - (items.size() - oldSize)); 
} 

당신이 boost::bind를 사용하는 경우에는이 훨씬 더 예쁘게 만들 수 있지만, 이것은 작동합니다.

Answer 3

반복기 무효화에 대한 Remy Lebeau의 설명과 함께 가서 코드 std::vector 대신 std::list을 사용하여 코드를 유효하고 점근 적으로 빠르게 (2 차 시간 대신 선형 시간) 만들 수 있다고 덧붙입니다. (std::list 삭제는 삭제 된 반복자 만 무효화하고 삽입은 반복자를 무효화하지 않습니다.)

또한 STL 구현의 디버그 모드를 활성화하여 디버깅 중에 반복자 무효화를 예측할 수 있습니다. GCC에서 컴파일러 플래그 -D_GLIBCXX_DEBUG을 사용합니다 (몇 가지주의 사항 참조).