벡터 크기를 조정하면 반복자가 무효화되나요?

StackOverflow https://stackoverflow.com/questions/1624803

  •  06-07-2019
  •  | 
  •  

문제

나는 이 C++ 코드를 발견했습니다:

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;

큰 난수를 인쇄합니다.하지만 추가하면 a.push_back(3) 세 번째와 네 번째 줄 사이에는 1이 인쇄됩니다.나에게 설명해 주실 수 있나요?

도움이 되었습니까?

해결책

보다 신중한 문구로 편집

예, 벡터를 크기로 조정하면 벡터를 가리키는 모든 반복자가 무효화 될 수 있습니다.

벡터는 데이터가 저장되는 배열을 내부적으로 할당하여 구현됩니다. 벡터가 자라면 해당 배열이 공간이 떨어질 수 있으며, 그렇다면 벡터는 새롭고 더 큰 배열을 할당하고 데이터를 그 위에 복사 한 다음 이전 배열을 삭제합니다.

따라서 이전 메모리를 가리키는 오래된 반복자는 더 이상 유효하지 않습니다. 벡터가 크기가 커지는 경우 아래쪽 (예를 들어 pop_back()) 그러나 동일한 배열이 사용됩니다. 배열의 크기는 자동으로 절대 크기가 없습니다.

이 재 할당 (및 포인터 무효화)을 피하는 한 가지 방법은 vector::reserve() 첫째,이 복사가 필요하지 않은 충분한 공간을 따로 설정하려면. 귀하의 경우에 전화 한 경우 a.reserve(3) 첫 번째 push_back() 작동, 그러면 내부 배열은 push_back배열을 재 할당하지 않고도 수행 할 수 있으므로 반복자가 유효합니다.

다른 팁

벡터 반복자는 벡터가 재 할당을 수행 할 때만 무효화됩니다.

전화 push_back(4) 벡터가 새로운 메모리 블록을 할당하게 만들고 있습니다. 이것이 반복기가 무효화되는 원인입니다. 당신이 사용할 때도 push_back(3), 재 할당은 수행되지 않습니다 push_back(4) 따라서 반복자는 유효합니다.

예, 벡터의 크기를 변경할 수있는 모든 동작은 반복자를 무효화 할 수 있습니다.

편집 : 여기에는 운영이 포함됩니다 (예 : erase(), resize()) 용기의 크기를 줄입니다. erase() 무효화되지 않습니다 모두 반복자이지만 지워진 요소 후에 모든 지점을 참조하는 반복자를 무효화합니다. resize() 측면에서 정의됩니다 insert() 그리고 erase(), 그래서 그것은 같은 잠재력을 가지고 있습니다.

반복자 무효화 규칙은 컨테이너마다 다릅니다.

이제 무효화는 벡터에서 두 가지 의미를 가질 수 있습니다.

  1. 무효화 = [begin,end]로 정의된 범위를 벗어난 지점
  2. 무효화 = 원래 객체와 다른 객체를 가리킴

보시다시피 두 번째는 훨씬 더 엄격합니다.

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

이 경우 항상 포함 범위 [begin,end]에 있으므로 myVector의 모든 작업에 안전하게 사용할 수 있다는 점에서 '유효'합니다.반면에 (*it) 표현식은 계속해서 변경됩니다.처음에는 0을 반환하고 그 다음에는 1을 반환하며 그 다음에는 정의되지 않은 동작이 발생합니다.

일반적으로 사람들은 두 번째 요구 사항에 대해 이야기하고 반복자를 무효화하는 것은 단순히 (*it)가 이전과 동일한 결과를 생성하지 않을 수 있음을 의미합니다.

이제 Vector의 반복자를 무효화하는 방법에는 여러 가지가 있습니다(사실 STL의 덜 안정적인 구조입니다).

요소를 추가하는 동안:

  • 이로 인해 재할당 (1) myVector.size() == myVector.capacity()인 경우 이를 확인하는 것은 오류가 발생하기 쉬우므로 일반적으로 추가하면 반복자가 무효화된다고 간주합니다.
  • '까다롭게' 하고 싶고 재할당이 실행되지 않는다는 것을 알고 있는 경우에도 다음 사항에 대해 걱정해야 합니다. insert.요소를 삽입하면 요소가 벡터 끝을 향해 한 단계 이동되므로 현재 위치를 가리키는 반복자와 모든 후속 위치를 가리키는 반복자가 무효화됩니다.

요소 제거 중:

  • 버퍼가 필요한 것보다 훨씬 커지더라도 재할당은 없습니다.하지만 다음을 사용하여 이를 강제로 적용할 수도 있습니다. 맞게 축소 관용구 (2).
  • 제거된 요소를 지나는 모든 반복자는 무효화됩니다.특히, 이전 'end' 반복자는 이제 [begin,end] 범위를 벗어났으며 예를 들어 STL 알고리즘 내에서 안전하게 사용할 수 없습니다.

(1) std::Vector의 내부 구조는 T의 배열입니다. 이는 C 프로그램과의 호환성(배열의 주소로 &myVector.front() 사용)과 연속성과 최소값을 보장하기 때문입니다. 공간 오버헤드(즉, 벡터 자체 데이터가 차지하는 공간의 양과 객체가 차지하는 공간의 양)

언제든지 .capacity() 메소드를 사용하여 벡터가 보유할 수 있는 객체 수를 알 수 있습니다.

객체를 삽입하려고 하는데 벡터에 필요한 용량이 없으면 .reserve(size_t) 메서드에 대한 호출이 트리거됩니다.이 방법은 필요한 항목 수가 현재 용량보다 많은 경우 재할당.

그런 다음 벡터는 요소의 새 배열을 할당하고(크기는 일반적으로 2*n+1이며 여기서 n은 현재 용량임) 현재 배열의 요소를 새 배열에 복사하고 현재 배열을 삭제합니다.

현재 배열을 삭제하기 때문에 벡터 반복자는 일반적으로 효율성을 위해 간단한 포인터이므로 반복자는 무효화됩니다.

반복자가 다음과 같이 구현된 경우에 유의하세요.벡터 + 카운트에 대한 참조 및 역참조는 실제로 *(&m_Vector.front() + n) 재할당으로 인해 무효화되지 않습니다.하지만 효율성은 떨어질 것입니다.

(2) 맞게 축소:경고, 이렇게 하면 요소의 COPY가 트리거되고 반복자가 무효화됩니다.

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

먼저 필요한 만큼의 메모리(라이브러리에 따라 최소량)만 할당하는 임시 벡터를 생성하고 myVector의 요소를 복사합니다.그런 다음 스왑 작업은 myVector와 이 복사본의 버퍼를 교환하므로 myVector는 이제 필요한 최소 메모리 양의 버퍼를 보유합니다.작업이 끝나면 임시 항목이 삭제되고 임시 항목이 보관된 메모리가 해제됩니다.

향후 참조를 위해 이와 같은 모든 STL 종류의 Tidbits는 SGI 웹 사이트에 있습니다. http://www.sgi.com/tech/stl/vector.html

컬렉션을 추가하거나 삭제 한 후 반복자가 유효한 상태를 유지 해야하는 경우 목록과 같은 다른 종류의 컬렉션을 살펴보십시오.

그래도 가장 좋은 방법은 컬렉션에서 원하는 기능의 매트릭스를 식별 한 다음 올바른 컨테이너를 선택하는 것입니다.

출발점은 Standard_Template_library 용기의 Wikipedia 기사를 참조하십시오. 현금이 있다면 Scott Meyer의 "Effective STL : 50 표준 템플릿 라이브러리 사용을 개선하는 50 가지 특정 방법"을 적극 권장합니다.

지원 링크 부족에 대한 사과는 여기에 초보자이며 둘 이상으로 게시 할 명성이 부족합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top