반복자 무효화 규칙
C ++ 컨테이너에 대한 반복자 무효화 규칙은 무엇입니까?
바람직하게는 요약리스트 형식으로되어있다.
(참고 : 이것은 Stack Overflow의 C ++ FAQ에 대한 항목 입니다.이 양식으로 FAQ를 제공한다는 아이디어를 비판하려면이 모든 것을 시작한 메타에 게시 하면됩니다. 이 질문은 C ++ 대화방 에서 모니터링되며 여기서 FAQ 아이디어는 처음부터 시작되었으므로 아이디어를 얻은 사람들이 귀하의 답변을 읽을 가능성이 큽니다.)
C ++ 17 (모든 참조는 CPP17- n4659 의 최종 작업 초안에서 가져온 것임 )
삽입
시퀀스 컨테이너
vector: 기능insert,emplace_back,emplace,push_back원인 재 할당 새 크기가 기존의 용량보다 큰 경우. 재 할당은 시퀀스의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화합니다. 재 할당이 발생하지 않으면 삽입 점 이전의 모든 반복자와 참조가 유효한 상태로 유지됩니다. [26.3.11.5/1] 함수
와 관련하여reserve재 할당은 시퀀스의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화합니다. 삽입 후reserve()벡터 크기가의 값보다 커질 때까지 호출 후 발생하는 삽입 중에 재 할당이 발생하지 않습니다capacity(). [26.3.11.3/6]deque: deque 중간에 삽입하면 모든 반복자와 deque 요소에 대한 참조가 무효화됩니다. deque의 양쪽 끝에 삽입하면 deque에 대한 모든 반복자가 무효화되지만 deque 요소에 대한 참조의 유효성에는 영향을 미치지 않습니다. [26.3.8.4/1]list: 반복자와 참조의 유효성에 영향을 미치지 않습니다. 예외가 발생하면 아무런 영향이 없습니다. [26.3.10.4/1].
는insert,emplace_front,emplace_back,emplace,push_front,push_back함수는이 규칙이 적용된다.forward_list: 과부하의insert_after어떤 것도 반복자와 참조의 유효성에 영향을 미치지 않아야한다 [26.3.9.5/1]array: 일반적으로 배열의 반복기는 배열 수명 동안 무효화되지 않습니다. 그러나 스왑하는 동안 반복자는 동일한 배열 요소를 계속 가리 키므로 값이 변경됩니다.
연관 컨테이너
All Associative Containers:insert및emplace구성원은 반복자의 유효성 및 컨테이너에 대한 참조에 영향을 미치지 않아야한다 [26.2.6 / 9]
정렬되지 않은 연관 컨테이너
All Unordered Associative Containers: 리 해싱은 반복자를 무효화하고 요소 간 순서를 변경하며 어떤 버킷 요소가 나타나는지 변경하지만 포인터 또는 요소에 대한 참조는 무효화하지 않습니다. [26.2.7 / 9] 및 부재는 컨테이너 요소에 대한 참조의 유효성에 영향을 미치지 아니하고 용기 모든 반복자를 무효화 할 수있다. [26.2.7 / 14] 하고 있으면 부재 반복자의 유효성에 영향을 미치지 아니한다 여기서, 삽입 작업 전에 용기의 원소의 개수, 삽입 요소의 개수이며, 상기 용기의 통 개수이고, 는 IS 컨테이너의 최대 하중 계수. [26.2.7 / 15]insertemplaceinsertemplace(N+n) <= z * BNnBzAll Unordered Associative Containers: 병합 작업 (예a.merge(a2):)의 경우 전송 된 요소를 참조하는 반복자와 참조하는 모든 반복자a는 무효화되지만 나머지 요소에 대한 반복자a2는 유효합니다. (표 91 — 정렬되지 않은 연관 컨테이너 요구 사항)
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
지워 없앰
시퀀스 컨테이너
vector: 지우기 시점 또는 이후 의 기능erase및pop_back무효화 반복자 및 참조를 무효화합니다. [26.3.11.5/3]deque: 마지막 요소를 지우는 지우기 작업deque은 과거 반복기 및 모든 반복기와 지워진 요소에 대한 참조 만 무효화합니다.deque마지막 요소가 아닌 a의 첫 번째 요소를 지우는 지우기 작업은 반복자 및 지워진 요소에 대한 참조 만 무효화합니다. 첫 번째 요소 나 마지막 요소를 지우지 않는 지우기 작업deque은 과거 반복자와 모든 반복자와의 모든 요소에 대한 참조를 무효화합니다deque. [참고 :pop_front및pop_back지우기 작업입니다. — 끝 노트] [26.3.8.4/4]list: 반복자 및 무효화 된 요소에 대한 참조 만 무효화합니다. [26.3.10.4/3]. 이 적용되는erase,pop_front,pop_back,clear기능.
remove및remove_if멤버 함수 : 목록 웁니다 모든 요소리스트 반복자 지칭i다음의 조건이 유지되는 경우 :*i == value,pred(*i) != false. 반복자와 무효화 된 요소에 대한 참조 만 무효화한다 [26.3.10.5/15].
unique멤버 함수-반복자i가 참조하는 동일한 연속 요소 그룹의 모든 연속 그룹에서 첫 번째 요소를 제외한 모든 요소[first + 1, last)를*i == *(i-1)(인수가없는 고유 버전의 경우) 또는pred(*i, *(i - 1))술어 인수가있는 고유 한 버전의 경우 보유합니다. 반복자와 무효화 된 요소에 대한 참조 만 무효화합니다. [26.3.10.5/19]forward_list:erase_after반복자와 무효화 된 요소에 대한 참조 만 무효화합니다. [26.3.9.5/1].
remove및remove_if멤버 함수-다음 조건이 충족되는 목록 반복자 i에서 참조하는 목록의 모든 요소를 지 웁니다.*i == value(forremove()),pred(*i)true (forremove_if()). 반복자와 무효화 된 요소에 대한 참조 만 무효화합니다. [26.3.9.6/12].
unique멤버 함수-반복자 i에 의해 참조 된 반복 요소 i가 참조하는 모든 연속 된 동일한 그룹의 그룹에서 첫 번째 요소를 제외한 모든 요소를 [*i == *(i-1)인수 + 1, 마지막) 범위 (인수가없는 버전의 경우) 또는pred(*i, *(i - 1))술어가있는 버전의 경우를 지 웁니다. 인수) 보유합니다. 반복자와 무효화 된 요소에 대한 참조 만 무효화합니다. [26.3.9.6/16]All Sequence Containers:clear의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화하고 과거 반복기를 무효화 할 수 있습니다 (표 87-시퀀스 컨테이너 요구 사항). 그러나 위해forward_list,clear과거 - 더 - 끝 반복자를 무효화하지 않습니다. [26.3.9.5/32]All Sequence Containers:assign컨테이너의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화합니다. 들어vector와deque, 또한 past-the-end 반복자를 무효화합니다. (표 87 — 시퀀스 컨테이너 요구 사항)
연관 컨테이너
All Associative Containers:erase멤버는 반복자 및 무효화 된 요소에 대한 참조 만 무효화해야한다 [26.2.6 / 9]All Associative Containers:extract멤버는 제거 된 요소에 대한 반복자 만 무효화합니다. 제거 된 요소에 대한 포인터와 참조는 유효하다 [26.2.6 / 10]
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
반복자 무효화와 관련된 일반적인 컨테이너 요구 사항 :
달리 명시되지 않는 한 (명시 적으로 또는 다른 함수로 함수를 정의하여) 컨테이너 멤버 함수를 호출하거나 컨테이너를 라이브러리 함수에 인수로 전달하면 컨테이너 내의 오브젝트에 대한 반복자를 무효화하거나 값을 변경해서는 안됩니다. . [26.2.1 / 12]
어떤
swap()함수도 스왑되는 컨테이너의 요소를 참조하는 참조, 포인터 또는 반복자를 무효화하지 않습니다 . [참고 : end () 반복자는 요소를 참조하지 않으므로 무효화 될 수 있습니다. — 끝 참고] [26.2.1 / (11.6)]
위 요구 사항의 예로 :
transform알고리즘 :op및binary_op함수는 반복자 또는 하위 범위를 무효화하거나 범위 [28.6.4 / 1]의 요소를 수정해서는 안됩니다.accumulate알고리즘 : [first, last] 범위에서binary_op요소를 수정하거나 반복자 또는 하위 범위를 무효화하지 않아야합니다 [29.8.2 / 1]reduce알고리즘 : binary_op는 반복자 또는 하위 범위를 무효화하거나 [first, last] 범위의 요소를 수정하지 않아야합니다. [29.8.3 / 5]
등등...
C ++ 03 (출처 : 반복자 무효화 규칙 (C ++ 03) )
삽입
시퀀스 컨테이너
vector: 새로운 컨테이너 크기가 이전 용량보다 크지 않은 경우 삽입 지점 이전의 모든 반복자와 참조는 영향을받지 않습니다 (이 경우 모든 반복자와 참조가 무효화 됨) [23.2.4.3/1]deque: 삽입 된 멤버가 deque의 끝 (앞 또는 뒤)에 있지 않으면 모든 반복자와 참조가 무효화됩니다 (이 경우 모든 반복자가 무효화되지만 요소에 대한 참조는 영향을받지 않습니다) [23.2.1.3/1]list: 영향을받지 않는 모든 반복자와 참조 [23.2.2.3/1]
연관 컨테이너
[multi]{set,map}: 영향을받지 않는 모든 반복자와 참조 [23.1.2 / 8]
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
지워 없앰
시퀀스 컨테이너
vector: 소거 시점 이후의 모든 반복자와 참조가 무효화 됨 [23.2.4.3/3]deque: 지워진 멤버가 deque의 끝 (앞 또는 뒤)에 있지 않으면 모든 반복자와 참조가 무효화됩니다 (이 경우 지워진 멤버에 대한 반복자와 참조 만 무효화 됨) [23.2.1.3/4]list: 소거 된 요소에 대한 반복자와 참조 만 무효화 됨 [23.2.2.3/3]
연관 컨테이너
[multi]{set,map}: 삭제 된 요소에 대한 반복자와 참조 만 무효화 됨 [23.1.2 / 8]
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
크기 조정
vector: 삽입 / 삭제에 따른 것 [23.2.4.2/6]deque: 삽입 / 삭제에 따른 것 [23.2.1.2/1]list: 삽입 / 삭제에 따른 것 [23.2.2.2/1]
참고 1
달리 명시되지 않는 한 (명시 적으로 또는 다른 함수로 함수를 정의하여) 컨테이너 멤버 함수를 호출하거나 컨테이너를 라이브러리 함수에 인수로 전달하면 컨테이너 내의 오브젝트에 대한 반복자 를 무효화 하거나 값을 변경 해서는 안됩니다. . [23.1 / 11]
노트 2
C ++ 2003에서는 "end"반복자가 위의 규칙을 따르는 지 여부는 명확하지 않습니다 . 어쨌든 그것들은 (실제로 그러하기 때문에) 있다고 가정해야합니다.
노트 3
포인터 무효화 규칙은 참조 무효화 규칙과 동일합니다.
C ++ 11 (출처 : 반복자 무효화 규칙 (C ++ 0x) )
삽입
시퀀스 컨테이너
vector: 새로운 컨테이너 크기가 이전 용량보다 크지 않은 경우 삽입 지점 이전의 모든 반복자와 참조는 영향을받지 않습니다 (이 경우 모든 반복자와 참조가 무효화 됨) [23.3.6.5/1]deque: 삽입 된 멤버가 deque의 끝 (앞 또는 뒤)에 있지 않으면 모든 반복자와 참조가 무효화됩니다 (이 경우 모든 반복자가 무효화되지만 요소에 대한 참조는 영향을받지 않습니다) [23.3.3.4/1]list: 영향을받지 않는 모든 반복자와 참조 [23.3.5.4/1]forward_list: 영향을받지 않는 모든 반복자와 참조 (에 적용insert_after) [23.3.4.5/1]array: (없음)
연관 컨테이너
[multi]{set,map}: 영향을받지 않는 모든 반복자와 참조 [23.2.4 / 9]
분류되지 않은 연관 컨테이너
unordered_[multi]{set,map}: 리 해싱 발생시 모든 반복자가 무효화되었지만 영향을받지 않는 참조 [23.2.5 / 8]. 삽입은 컨테이너의 사이즈가 초과하지 않도록 유발하는 경우가 발생하지 않고 다시 해싱z * B여기서z최대 하중 인자이며B버킷 수. [23.2.5 / 14]
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
지워 없앰
시퀀스 컨테이너
vector: 소거 시점 이후의 모든 반복자와 참조가 무효화 됨 [23.3.6.5/3]deque: 마지막 요소를 지우면 이터레이터 만 무효화되고 지워진 요소와 과거의 이터레이터에 대한 참조 만 무효화됩니다. 첫 번째 요소를 지우면 반복자 및 지워진 요소에 대한 참조 만 무효화됩니다. 다른 요소를 지우면 모든 반복자와 참조가 무효화됩니다 (과거의 반복자를 포함) [23.3.3.4/4]list: 삭제 된 요소에 대한 반복자와 참조 만 무효화 됨 [23.3.5.4/3]forward_list: 삭제 된 요소에 대한 반복자와 참조 만 무효화 됩니다 (적용erase_after) [23.3.4.5/1]array: (없음)
연관 컨테이너
[multi]{set,map}: 삭제 된 요소에 대한 반복자와 참조 만 무효화 됨 [23.2.4 / 9]
정렬되지 않은 연관 컨테이너
unordered_[multi]{set,map}: 삭제 된 요소에 대한 반복자와 참조 만 무효화 됨 [23.2.5 / 13]
컨테이너 어댑터
stack: 기본 컨테이너에서 상속queue: 기본 컨테이너에서 상속priority_queue: 기본 컨테이너에서 상속
크기 조정
vector: 삽입 / 삭제에 따른 것 [23.3.6.5/12]deque: 삽입 / 삭제에 따른 것 [23.3.3.3/3]list: 삽입 / 삭제에 따른 것 [23.3.5.3/1]forward_list: 삽입 / 삭제에 따른 것 [23.3.4.5/25]array: (없음)
참고 1
달리 명시되지 않는 한 (명시 적으로 또는 다른 함수로 함수를 정의하여) 컨테이너 멤버 함수를 호출하거나 컨테이너를 라이브러리 함수에 인수로 전달하면 컨테이너 내의 오브젝트에 대한 반복자 를 무효화 하거나 값을 변경 해서는 안됩니다. . [23.2.1 / 11]
노트 2
swap () 함수 는 스왑되는 컨테이너의 요소를 참조하는 모든 참조, 포인터 또는 반복자를 무효화하지 않습니다 . [참고 : end () 반복자 는 어떤 요소도 참조하지 않으므로 무효화 될 수 있습니다 . — 끝 노트] [23.2.1 / 10]
노트 3
위의주의가에 대한보다 다른 swap(), 그것은 "끝"반복자는 위에 나열된 당 컨테이너 규칙 적용 여부를 명확하지 않다 ; 어쨌든 당신은 그들이 있다고 가정해야합니다.
참고 4
vector그리고 정렬되지 않은 모든 연관 컨테이너 지원 reserve(n)은 컨테이너의 크기가 커질 때까지 자동 크기 조정이 발생하지 않도록합니다 n. 차후 제안에서는 최소 하중 계수를 지정할 수 있으므로 충분한 작업으로 컨테이너 크기를 최소값 이하로 줄이면 재해 싱이 발생할 수 있으므로 순서 가 지정되지 않은 연관 컨테이너에 주의해야합니다 . 보증은 .inserteraseerase
그것은 어떤 종류의 삽입 반복자 (덧붙였다 아마 가치가있다 std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator모든 삽입이 반복자를 통해 수행하고 다른 독립적 인 반복자-무효화 이벤트가 발생하지 않기 때문에) 길이로 유효 보장됩니다.
예를 들어, std::vector를 사용하여 일련의 삽입 작업을 수행하는 경우 std::insert_iterator이러한 삽입이 벡터 재 할당을 트리거하여 해당 벡터를 "지정"하는 모든 반복자가 무효화 될 수 있습니다. 그러나 해당 삽입 반복기는 유효하게 유지됩니다. 즉, 삽입 순서를 안전하게 계속할 수 있습니다. 벡터 재 할당 트리거에 대해 전혀 걱정할 필요가 없습니다.
이는 다시 삽입 반복자 자체를 통해 수행 된 삽입에만 적용됩니다. 컨테이너에 대한 일부 독립적 인 조치로 반복자 무효화 이벤트가 트리거되면 삽입 규칙이 일반 규칙에 따라 무효화됩니다.
예를 들어,이 코드
std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);
for (unsigned n = 20; n > 0; --n)
*it_ins++ = rand();
벡터가이 프로세스의 중간에 어딘가에 재 할당하기로 결정하더라도 벡터에 유효한 삽입 시퀀스를 수행하도록 보장됩니다. 반복자 it는 분명히 유효하지 않지만 it_ins계속 유효합니다.
이 질문은 너무 많은 투표를하고 FAQ가되기 때문에 C ++ 03과 C ++ 11 std::vector의 삽입 작업이에 대한 영향에 관한 C ++ 03과 C ++ 11의 중요한 차이점에 대해 별도의 답변을 작성하는 것이 좋습니다 . 에 대한 반복자와 참조의 유효성 reserve()과 capacity()가장 upvoted 답변을 통지하지 못했습니다.
C ++ 03 :
재 할당은 시퀀스의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화합니다. 삽입이 벡터 의 크기를 가장 최근의 reserve () 호출에 지정된 크기보다 크게 할 때까지 reserve () 호출 후 발생하는 삽입 중에 재 할당이 발생하지 않는 것이 보장됩니다 .
C ++ 11 :
재 할당은 시퀀스의 요소를 참조하는 모든 참조, 포인터 및 반복자를 무효화합니다. 삽입이 벡터의 크기 를 capacity () 값보다 크게 할 때까지 reserve () 호출 후 발생하는 삽입 중에 재 할당이 발생하지 않는 것이 보장됩니다 .
따라서 C ++ 03에서는 unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)다른 답변에서 언급 한 " " 가 아니라 " " 가 아닙니다 greater than the size specified in the most recent call to reserve(). 이것이 C ++ 03이 C ++ 11과 다른 점입니다. C ++ 03 insert()에서 벡터의 크기가 이전 reserve()호출에 지정된 값에 도달하면 ( 요청한 것보다 더 큰 결과가 발생할 수 capacity()있기 때문에 현재보다 작을 수 있음) 이후에 재 할당 및 무효화 될 수 있습니다. 모든 반복자와 참조. C ++ 11에서는 이런 일이 발생 하지 않으며 크기가 초과되기 전에 다음 재 할당이 발생하지 않는다는 것을 확실하게 알 수 있습니다 .reserve()capacity()insert()capacity()capacity()
결론적으로 C ++ 03 벡터로 작업하고 삽입을 수행 할 때 재 할당이 발생하지 않도록하려면 이전에 전달한 인수의 값이 reserve()아니라 크기를 확인해야합니다. 에 대한 호출의 반환 값입니다. capacity()그렇지 않으면 " 조기 "재 할당에 놀랄 수 있습니다 .
참고 URL : https://stackoverflow.com/questions/6438086/iterator-invalidation-rules
'Programing' 카테고리의 다른 글
| 'mutable'키워드는 const 함수로 변수를 수정하는 것 이외의 다른 목적을 가지고 있습니까? (0) | 2020.02.12 |
|---|---|
| malloc 후에 해방되지 않으면 어떻게 되나요? (0) | 2020.02.12 |
| Node.js은 (는) 무엇 이죠? (0) | 2020.02.12 |
| 커맨드 라인의 Node.js 버전? (0) | 2020.02.12 |
| Bash에서 해시 테이블을 정의하는 방법은 무엇입니까? (0) | 2020.02.12 |