pop_back()이 실제로 std::벡터의 *모든* 반복자를 무효화합니까?
https://stackoverflow.com/questions/62340
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
std::vector<int> ints;
// ... fill ints with random values
for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
if(*it < 10)
{
*it = ints.back();
ints.pop_back();
continue;
}
it++;
}
이 코드는 다음과 같은 이유로 작동하지 않습니다. pop_back() 라고, it 무효화됩니다.그러나 반복자의 무효화에 대해 이야기하는 문서를 찾을 수 없습니다. std::vector::pop_back().
그것에 대한 링크가 있나요?
해결책
에 대한 호출 pop_back() 벡터의 마지막 요소를 제거하므로 해당 요소에 대한 반복자가 무효화됩니다.그만큼 pop_back() 전화는 ~ 아니다 마지막 요소 이전 항목에 대한 반복자를 무효화합니다. 재할당만이 이를 수행합니다.Josuttis의 "C++ 표준 라이브러리 참조"에서:
요소 삽입 또는 제거는 다음 요소를 참조하는 참조, 포인터 및 반복자를 무효화합니다.삽입으로 인해 재 할당이 발생하면 모든 참조, 반복자 및 포인터가 무효화됩니다.
다른 팁
다음은 The Holy Standard에서 직접 제공한 답변입니다.
23.2.4.2 벡터는 선택적 시퀀스 요구 사항(23.1.1)의 대부분을 포함하여 컨테이너와 가역 컨테이너(23.1의 두 표에 제공) 및 시퀀스의 모든 요구 사항을 충족합니다.
23.1.1.12 표 68 Expressiona.pop_back () 반환 Typevoid Operational Semanticsa.erase(--a.end())컨테이너벡터, 목록, 데크
a.pop_back은 a.erase(--a.end())와 동일합니다.삭제에 대한 벡터의 세부 사항을 살펴보면 다음과 같습니다.
23.2.4.3.3 - 반복자 삭제(반복자 위치) - 효과 - 삭제 지점 이후의 모든 반복자와 참조를 무효화합니다.
따라서 pop_back을 호출하면 이전 최종 요소(현재는 더 이상 존재하지 않음)에 대한 모든 반복자가 무효화됩니다.
코드를 보면 문제는 마지막 요소를 제거하고 목록이 비어 있어도 여전히 요소를 증가시키고 목록 끝에서 벗어나는 것입니다.
(저는 C++0x 작업 초안에서 사용된 번호 매기기 체계를 사용합니다. 여기서 구할 수 있는
732페이지의 표 94에서는 pop_back(시퀀스 컨테이너에 있는 경우)이 다음과 같은 효과를 갖는다고 나와 있습니다.
{ iterator tmp = a.end();
--tmp;
a.erase(tmp); }
23.1.1, 12번 항목은 다음과 같이 명시합니다.
달리 지정되지 않는 한 (명시 적으로 또는 다른 함수 측면에서 함수를 정의하여), 컨테이너 멤버 함수를 호출하거나 컨테이너를 라이브러리 함수로 인수로 전달하는 경우 해당 컨테이너 내의 객체를 무효화하거나 값을 변경하지 않아야합니다. .
접두사를 적용하여 end()에 액세스하는 것은 모두 그러한 효과가 없습니다. 그러나 erasure()는 다음과 같습니다.
23.2.6.4 (Vector.erase() 포인트 4에 관하여):
효과:삭제 지점이나 그 이후의 반복자와 참조를 무효화합니다.
결론적으로:pop_back()은 표준에 따라 마지막 요소에 대한 반복자만 무효화합니다.
다음은 SGI의 STL 문서에서 인용한 내용입니다(http://www.sgi.com/tech/stl/Vector.html):
[5] 벡터의 반복자는 메모리가 재할당되면 무효화됩니다.또한 벡터 중간에 요소를 삽입하거나 삭제하면 삽입 또는 삭제 지점 뒤의 요소를 가리키는 모든 반복기가 무효화됩니다.따라서 벡터가 사용할 만큼의 메모리를 사전 할당하기 위해 Reserve()를 사용하고 모든 삽입과 삭제가 벡터의 끝에 있는 경우 벡터의 반복자가 무효화되는 것을 방지할 수 있습니다.
나는 pop_back이 마지막 요소를 가리키는 반복자와 end() 반복자를 무효화한다고 생각합니다.우리는 코드가 실패한 데이터와 무슨 일이 일어나고 있는지 결정하지 못하는 방식을 실제로 확인해야 합니다.내가 알 수 있는 한, 코드는 작동해야 합니다. 이러한 코드의 일반적인 문제는 @mikhaild가 지적한 대로 반복자의 요소 및 ++ 제거가 동일한 반복에서 발생한다는 것입니다.그러나 이 코드에서는 그렇지 않습니다.pop_back이 호출되면 it++는 발생하지 않습니다.
마지막 요소를 가리키고 마지막 요소가 10보다 작은 경우 여전히 문제가 발생할 수 있습니다.우리는 지금 비교하고 있습니다. 무효화 그것과 끝().여전히 작동할 수는 있지만 보장할 수는 없습니다.
반복자는 스토리지 재할당 시에만 무효화됩니다.Google은 당신의 친구입니다. 각주 5 참조.
다른 이유로 인해 코드가 작동하지 않습니다.
pop_back() 마지막 요소를 가리키는 반복자만 무효화합니다.C++ 표준 라이브러리 참조에서:
요소 삽입 또는 제거는 다음 요소를 참조하는 참조, 포인터 및 반복자를 무효화합니다.삽입으로 인해 재 할당이 발생하면 모든 참조, 반복자 및 포인터가 무효화됩니다.
따라서 귀하의 질문에 대답하려면 아니요, 무효화되지 않습니다. 모두 반복자.
그러나 코드 예제에서는 무효화될 수 있습니다. it 마지막 요소를 가리키고 값이 10 미만인 경우.이 경우 Visual Studio 디버그 STL은 반복자를 무효화된 것으로 표시하고 end()와 같지 않은지 추가로 확인하면 어설션이 표시됩니다.
반복자가 순수 포인터로 구현되면(디버그가 아닌 모든 STL 벡터 사례에서와 마찬가지로) 코드가 제대로 작동해야 합니다.반복자가 포인터보다 크면 코드는 마지막 요소를 올바르게 제거하는 경우를 처리하지 못합니다.
오류는 "it"이 벡터의 마지막 요소를 가리킬 때 이 요소가 10보다 작으면 이 마지막 요소가 제거된다는 것입니다.그리고 이제 "it"은 ints.end()를 가리키고, 다음 "it++"는 포인터를 ints.end()+1로 이동합니다. 이제 "it"은 ints.end()에서 도망가고 모든 코드를 스캔하는 무한 루프가 발생합니다. 메모리 :).
"공식 사양"은 C++ 표준입니다.C++03 사본에 접근할 수 없는 경우 위원회 웹사이트에서 C++0x의 최신 초안을 얻을 수 있습니다. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf
컨테이너 요구 사항의 "작동 의미" 섹션에서는 pop_back()이 { iterator i = end();--나;지우기(i);}.삭제를 위한 [Vector.modifiers] 섹션에 "효과:삭제 지점이나 그 이후의 반복자와 참조를 무효화합니다."
직관 인수를 원할 경우 pop_back은 실패하지 않습니다(표준 컨테이너의 value_types 파괴는 예외 발생이 허용되지 않기 때문에). 따라서 복사나 할당을 수행할 수 없습니다(발생할 수 있으므로). 지워진 요소에 대한 반복자와 끝 반복자는 무효화되지만 나머지는 무효화되지 않습니다.
pop_back()은 무효화만 됩니다. 그것 만약에 그것 벡터의 마지막 항목을 가리키고 있었습니다.따라서 다음과 같이 벡터의 마지막 int가 10보다 작을 때마다 코드가 실패합니다.
*it = ints.back();// *it를 이미 가지고 있는 값으로 설정합니다.
ints.pop_back();// 반복자를 무효화합니다.
계속하다;// 라운드를 반복하고 잘못된 반복자에 액세스합니다.
뒤로 요소를 삭제된 위치로 교체하는 대신에 erasure의 반환 값을 사용하는 것을 고려할 수 있습니다.시퀀스 삭제의 경우 삭제되는 요소 다음의 요소를 가리키는 반복자를 반환합니다.이 방법을 사용하면 원래 알고리즘보다 더 많은 복사가 발생할 수 있습니다.
for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
if(*it < 10)
it = ints.erase( it );
else
++it;
}
std::remove_if 대안적인 해결책이 될 수도 있습니다.
struct LessThanTen { bool operator()( int n ) { return n < 10; } };
ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );
std::remove_if (내 첫 번째 알고리즘과 마찬가지로) 안정적이므로 이 작업을 수행하는 가장 효율적인 방법은 아니지만 간결합니다.
정보를 확인해보세요 여기(cplusplus.com):
마지막 요소 삭제
벡터의 마지막 요소를 제거하여 벡터 크기를 효과적으로 1씩 줄이고 이에 대한 모든 반복기와 참조를 무효화합니다.
