반복자 무효화(Iterator Invalidation)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

반복자는 내부적으로 포인터로 구현되어 있다.

 

그러므로 특정 노드 또는 원소의 주소가 바뀌면 그 주소를 갖는 반복자는 무효화될 수 있고 Crash로 이어질 수 있다.

 

std::vector에서의 반복자 무효화

• 삽입 시 용량 부족으로 메모리가 재할당 된 경우 발생할 수 있다.
• 중간에 원소를 삽입하여 뒤 원소들의 위치가 밀린 경우 발생할 수 있다.
  (용량이 충분하더라도 기존 주소를 포인터가 아닌 값으로 직접 참조하는 것으로 인식하여 오류 발생)

 

std::list에서의 반복자 무효화

• 삽입/삭제 시에는 원소의 이동이 필요치 않으므로 발생하지 않는다.
• 할당 해제된 주소를 참조하는 경우만 주의하면 된다.

 

#include <iostream>
#include <vector>
#include <list>

using namespace std;

void main()
{
    vector<int> v = {1, 2, 3, 4, 5};

    // 용량을 10으로 변경
    v.reserve(10);

    // it는 5의 위치를 가리킨다.
    vector<int>::iterator v_it = v.begin() + 4;

    cout << *v_it << endl;

    // 3번째 위치에 0 추가
    v.emplace(v.begin() + 2, 0);

    // 오류 발생!!
    // 주소가 유효하더라도 값으로 직접 접근하는 것으로 인식한다.
    // cout << *v_it << endl;

    // 오류가 발생하지 않는다.
    cout << *(v.begin() + 4) << endl;



    list<int> lst = {1, 2, 3, 4, 5};

    list<int>::iterator lst_it = next(lst.begin(), 4);

    cout << *lst_it << endl;

    // 3번째 위치에 0 추가
    lst.emplace(prev(lst_it, 1), 0);

    // 오류가 발생하지 않는다.
    cout << *lst_it << endl;
}