STL의 map에서 erase 관련 질문입니다.
글쓴이: canuyes / 작성시간: 목, 2014/07/31 - 11:23오전
안녕하세요.
알고리즘을 공부하던 도중에 stl의 map을 사용하다 궁금한 점이 생겨 질문 드립니다.
아래와 같이 map을 선언하였습니다.
map<int,int> TREE;
아래와 같이 TREE에 여러 값을 삽입한 상태에서 (k3,v3)를 가리키는 반복자 it를 가지고 있다고 할때,
(k1 != k2 != k3 != k4 != k5, v1!=v2!=v3!=v4!=v5 입니다.)
TREE.insert(map<int,int>::value_type(k1,v1)); TREE.insert(map<int,int>::value_type(k2,v2)); TREE.insert(map<int,int>::value_type(k3,v3)); TREE.insert(map<int,int>::value_type(k4,v4)); TREE.insert(map<int,int>::value_type(k5,v5)); map<int,int>::iterator it=TREE.lower_bound(k3);
다음과 같이 erase연산을 사용하면 반복자 it는 (k2,v2)를 가리키고 있는것이 보장되나요?
map<int,int>::iterator temp=it; temp--; TREE.erase(it); it=temp;
우선 제가 넣어본 테스트케이스로는 올바르게 작동하기는 합니다.
그런데 이전에 red black tree를 구현해 볼 때, 값이 삭제되는 경우 모양이 많이 바뀌는 것을 본적이 있습니다.
그래서 트리가 red black tree의 규칙에 의해 재구성 되면서 it의 값이 쓰레기값이 되지 않는지 궁금합니다.
답변 기다립니다.
Forums:
반복자 무효화에 대한 질문같습니다. 컨테이너에 따라서
반복자 무효화에 대한 질문같습니다. 컨테이너에 따라서 삽입삭제에의해 반복자가 무효화되는지 안되는지는 표준라이브러리명세를 보면 나와있습니다. iterator invalidation이라로 하니, 한번 찾아보시는게 좋을듯하네요. 표준에서는 구체적인 구현물을명시하지 않습니다. 만약 RBTree로는 무효화규칙을 지킬수없다면 그건 map 의 올바른 구현물이 아닌거지요.
map의 경우 erase되는 원소에 대한 레퍼런스와
map의 경우 erase되는 원소에 대한 레퍼런스와 이터레이터만 무효화됩니다.
지금 표준문서를 갖고 있지 않아 표준문서의 내용을 찾아드리긴 힘들 것 같고, cppreference.com의 map::erase()에 다음과 같이 설명되어 있습니다.
'References and iterators to the erased elements are invalidated. Other references and iterators are not affected.'
따라서 올리신 코드는 그대로 사용하셔도 됩니다.
좀 더 간단히 표현하자면
와 같이 한줄로 사용하시는 게 더 가독성에 좋을 것 같습니다.
답변감사합니다.
답변 정말 감사드립니다.
조금은 주제에서 벗어난 질문이지만 앞으로 필요할 것 같아 질문드립니다.
항상 질문을 올리기 전에 cppreference.com을 들어가서 찾아보고는 하는데요.
솔직히 말씀드리면 아직 학부생이라 그런지 알아보기가 어렵습니다.
탄탄한 기초가 없기때문이라고 생각되는데요.
STL의 리퍼런스만 보고도 알아볼 수 있을정도로만 기초를 쌓고 싶은데
어떻게 공부해야하나요?
실례가 안된다면 서적이나, 웹사이트를 추천 받고 싶습니다.
C++ 문법이 아니라 STL에 대한 개념을
C++ 문법이 아니라 STL에 대한 개념을 말씀하시는거라면 http://www.sgi.com/tech/stl/stl_index.html 를 추천합니다.
오래된 문서라 현행 표준과는 차이가 좀 있지만 Forward Iterator라던지 Strict Weak Ordering이라던지 하는 STL에서 사용되는 개념들이 잘 정리되어 있습니다.
차근차근 모르는 개념에 대해선 링크 타고 다니시면서 공부하신 다음에 표준 문서를 보시면 좀 더 이해하기 편할 거예요.
----
지금 보니 cppreference.com에도 괜찮은 페이지가 있네요. http://en.cppreference.com/w/cpp/concept 여기가 좀 더 설명이 상세하고 현행 표준이 많이 반영되어있는 것 같아요.
댓글 달기