STL의 map에서 erase 관련 질문입니다.

canuyes의 이미지

안녕하세요.

알고리즘을 공부하던 도중에 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의 값이 쓰레기값이 되지 않는지 궁금합니다.

답변 기다립니다.

klyx의 이미지

반복자 무효화에 대한 질문같습니다. 컨테이너에 따라서 삽입삭제에의해 반복자가 무효화되는지 안되는지는 표준라이브러리명세를 보면 나와있습니다. iterator invalidation이라로 하니, 한번 찾아보시는게 좋을듯하네요. 표준에서는 구체적인 구현물을명시하지 않습니다. 만약 RBTree로는 무효화규칙을 지킬수없다면 그건 map 의 올바른 구현물이 아닌거지요.

kukyakya의 이미지

map의 경우 erase되는 원소에 대한 레퍼런스와 이터레이터만 무효화됩니다.

지금 표준문서를 갖고 있지 않아 표준문서의 내용을 찾아드리긴 힘들 것 같고, cppreference.com의 map::erase()에 다음과 같이 설명되어 있습니다.

'References and iterators to the erased elements are invalidated. Other references and iterators are not affected.'

따라서 올리신 코드는 그대로 사용하셔도 됩니다.

좀 더 간단히 표현하자면

TREE.erase(it--);

와 같이 한줄로 사용하시는 게 더 가독성에 좋을 것 같습니다.

canuyes의 이미지

답변 정말 감사드립니다.
조금은 주제에서 벗어난 질문이지만 앞으로 필요할 것 같아 질문드립니다.
항상 질문을 올리기 전에 cppreference.com을 들어가서 찾아보고는 하는데요.
솔직히 말씀드리면 아직 학부생이라 그런지 알아보기가 어렵습니다.
탄탄한 기초가 없기때문이라고 생각되는데요.
STL의 리퍼런스만 보고도 알아볼 수 있을정도로만 기초를 쌓고 싶은데
어떻게 공부해야하나요?

실례가 안된다면 서적이나, 웹사이트를 추천 받고 싶습니다.

kukyakya의 이미지

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 여기가 좀 더 설명이 상세하고 현행 표준이 많이 반영되어있는 것 같아요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.