STL 기초적인 질문..
글쓴이: seldom / 작성시간: 금, 2004/04/30 - 11:50오후
C++ Standard Library 책을 보고 공부하기 시작한지 얼마 안되었습니다.
vector 나 deque 에서 원소의 삽입과 제거는 재할당을 유발하기에
반복자를 무효화 시킨다라고 책에 나와있습니다.
예를들어, 1~10 의 숫자를 vector 에 집어넣은 후에
반복자를 통해 모든 원소를 액세스하면서 값을 검사해 소수가 아니라면
삭제해서 결국 컨테이너에 소수만 남기게 하고 싶다라고 할때..
삭제하는것은 반복자를 무효화하기 때문에 이것은 불가능한 시나리오 입니까?
Forums:
Re: STL 기초적인 질문..
새로운 컨테이너를 하나 만든후, 기존의 컨테이너에서 조건을 만족하는 원소를 새 컨터이너에 복사하는 방법도 있습니다.
그리고 꼭 기존의 컨테이너를 사용해야 한다면 마지막에 swap를 사용하면 될것 같습니다.
#include <vector> #include <iostream> #include <iterator> using namespace std; bool isPrime(int v){ for (int i=2; i<v; i++){ if (v%i==0) return false; } return true; } int main(int argc, char* argv[]){ vector<int>v; vector<int>prime; vector<int>::iterator iter; for (int i=0; i<10; i++){ v.push_back(i+1); } for (iter=v.begin(); iter!=v.end(); iter++){ if (isPrime(*iter)){ prime.push_back(*iter); } } cout << "기존: " ; copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); cout << endl << "계산 결과: " ; copy(prime.begin(), prime.end(), ostream_iterator<int>(cout, " ")); swap(v, prime); cout << endl << "swap 수행후: " ; copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); }아마도 이펙티프 STL을 보시는거 같은데, 위의 내용을 보고 저는 그냥 "컨테이너를 순회하는 루프 내에선 컨테이너의 삽입 삭제를 하지 말자" 머 이정도로
기억하고 넘어간듯 합니다.
그런데 STL을 사용할 하려면 위와 같은 반복문 보다는 for_each, count, copy 등을 사용하라고 하더군요.
erase가 현재 반복자를 무효화시켜서 그러시는 것이라면 걱정할 필요가
erase가 현재 반복자를 무효화시켜서 그러시는 것이라면 걱정할 필요가 없지 않나 생각합니다.
erase는 삭제된 자료 다음을 가리키는 새 반복자를 반환합니다. 삭제하고 새롭게 받은 반복자부터 다음 내용을 검색해나가시면 될겁니다.
자세한 알고리즘을 안 적어주셔서 더 구체적으로는 모르겠군요.
- 죠커's blog / HanIRC:#CN
Re: STL 기초적인 질문..
원소의 제거시에는 재할당이 일어나지 않습니다. (e. vector의 경우)
제거되는 원소의 반복자가 무효화 되기는 하겠지만 재할당은 일어나지 않습니다.
책 어디에서 재할당이 일어난다고 나와 있던가요?
...
p.205 에 그렇게 나와 있습니다.
니콜라이 M.조슈티스 가 쓴 STL Standard Library 입니다.
제가 이해한 바에 따라도 그게 맞는 것 같은데요?
vector 의 경우 push_back() 이면서 메모리가 충분한 경우와
끝부분의 원소를 삭제하는 연산 외에는 전부 재할당이 일어나는 듯하고
deque 도 비슷한 경우 빼고는 대부분 재할당이 일어나는 것으로 이해하고 있는데요..
어쨌거나 제가 원한 정보는 "컨테이너를 순회하는 루프 내에선 컨테이너의 삽입 삭제를 하지 말자"
이었습니다.
이펙티브 STL 어느 부분인지 알려주시면 감사하겠습니다.
서점가서 살짝 봐야겠군요.
성능을 위해서는 CN 님 답변대로 하는 것이 좋을 듯 싶고요..
ps.. 책 제목을 착각했습니다. C++ Standard Library 입니다.
순차적으로 구현된 컨테이너라면 중간에 삽입과 삭제가 일어난다면 복사가 이
순차적으로 구현된 컨테이너라면 중간에 삽입과 삭제가 일어난다면 복사가 이루어지는 것은 맞습니다. ABCDE에서 C가 삭제된다면 ABXDE를 만들지 않고 ABDE를 만드는데 DE를 앞으로 복제하고 end를 앞으로 당겨서 구현한다고 알고 있습니다. 반대의 경우도 그렇구요.
재할당이란 말을 가지고 Testors님과 seldom님이 이견을 가지시는 것은 서로가 정의한 용어가 다르기 때문이지 않나 생각합니다. 처음에 제가 재할당이라는 말을 들었을때는 벡터등의 자료형에서 처음 할당된 사이즈를 초과해서 새롭게 2배의 메모리 공간으로 복제되는 것을 의미하는 줄 알았습니다.
하지만 링크로 구현된 컨테이너라면 중간에 삽입과 삭제가 일어난다고 하더라도 링크만 바꿔주면 해결되는 문제입니다. (그럴경우 반복자는 포인터 흉내를 내는 객체 혹은 템플릿 객체로 구현되어 있겠지요.)
중간에 삽입, 삭제를 빈번하게 한다면 다른 컨테이너를 찾는 것이 가장 좋은 정답이겠지요.
- 죠커's blog / HanIRC:#CN
Re: ...
그것은 deque 에 한정된 이야기일 것입니다.
vector 의 경우는 erase() 시에 재할당이 일어나지 않습니다.
표준에는 아래와 같이 "재할당은 모든 반복자를 무효화 한다" 라고 명시되어 있습니다.
그리고 vector 의 erase() 의 경우 "지워진 지점 이후의 반복자가 무효화 된다" 라고 명시되어 있지요.
이는 이후의 반복자가 무효화되기는 하지만 "재할당" 이 일어나지는 않는다는 의미입니다.
실제로 vector 의 경우 원소가 추가되어야 하는데 capacity 가 모자랄 경우나 swap() 이 불리는 경우가 아니라면 재할당이 일어나지 않습니다.
만약 erase() 가 재할당을 일으킨다면 erase() 는 vector 의 capacity 를 줄이는 방법이 될 수 있을 것입니다.
하지만 vector 의 capacity 를 줄이는 것은 swap() 이 유일한 방법이라고 Scott Meyers 아저씨가 Effective STL 에서 언급하고 있지요.
(사실은 소멸자와 생성자를 연달아 불러주는 방법이 있기는 합니다 - http://gpgstudy.com/forum/viewtopic.php?t=3332 )
이전에 다른 커뮤니티에서 vector 컨테이너의 재할당에 관해 논의한 적이 있습니다.
C++ 표준의 해석과 관련해 이 주제와 관련이 있는듯 하여 덧붙입니다.
http://gpgstudy.com/forum/viewtopic.php?t=2798
...
CN 님이 언급하셨더시피 '원소의 재할당'을 의미했던 것인데 님이
언급한 문서의 reallocation 은 원소 전체의 내부 메모리 교체를
의미하는 듯 합니다.
원소의 재할당이란 assignment 연산자를 이용한 노가다 이사 작업이겠죠?
어쨌거나 번역본에는 재할당이라는 용어를 사용하고 있는데
좀 혼돈을 줄 수도 있겠군요.
원서에는 어떤 단어로 씌였는지 궁금합니다.
'대입/복사' 와 '재할당' 은 혼동하기에는 거리가 있는 용어가 아닐까
'대입/복사' 와 '재할당' 은 혼동하기에는 거리가 있는 용어가 아닐까 생각합니다.
저도 책을 찾아 보았는데요, 아래는 본문 내용입니다.
위의 문장은 deque 챕터의 글이고, "deque 의 다른 원소를 참조하는 반복자를 무효화 시킨다." 라는 구절이 있으므로 이는 deque 에 한정되는 내용이라는 것을 알 수 있을 것입니다. "vector의 erase() 시에 재할당이 일어난다" 라는 언급은 책에는 없습니다.
그리고 같은 챕터 202 페이지 "6.3.1 deque의 능력" 부분을 보면 아래와 같은 구절이 있습니다.
이와같이 책은 '복사' 와 '재할당' 이라는 용어를 구분해서 사용하고 있습니다.
이는 deque 챕터 뿐만 아니라 책의 모든 부분에서 마찬가지 인데요,
제가 보기에는 책이 의미한 바도 '컨테이너 내의 메모리 블럭의 재할당' 이고
원문에도 reallocation 이라는 단어가 사용되었을거라고 생각 합니다.
( 혹시 원서 갖고 계신분? :wink: )
vector 의 erase() 가 재할당을 유발한다고 하셔서 그렇지 않다는것을 지적하려 한것인데 쓰레드가 요상하게 길어졌네요. : )
제가 사용한 경험으로는 vector의 경우는 삽입,삭제시데이터의 선형적이
제가 사용한 경험으로는 vector의 경우는 삽입,삭제시데이터의 선형적이라는걸 보장해 주는거 같습니다.
흔히 생각하는 배열과 가장 가까운 자료구조라고 생각이 됩니다.
deque같은 경우는 vector와 비슷한 선형적인 자료구조를 가지고 있지만, 추가시에 일어나는 처리 방법은 vector와는 좀 다른 거 같더군요.
vector와 같이 추가시 메모리에 여유가 없으면 크기가 맞는 영역을 찾아 전부 재할당을 하지만, deque같은 경우는 다른 영역에 추가된 부분의 여유공간이 없으면, 전부를 재할당 하는게 아니라 추가된 부분만 뒤에 링크를 거는 식인거 같더군요.
begin반복자를 가지고 직접 메모리 조작을 하니 선형 계산은 문제가 생기더군요.
루프내부에서 데이터를 삭제할수는 있지만 stl같은 경우는 썩 좋은 방법은 아닌거 같더군요.
earse( it++ ) 머 이런식으로 제거자에게는 it의 현제 복사본을 넘기고 미리 다음의 반복자로 넘기는 방법도 있지만... 역시 별로.... 제거를 시킨다고해도 여전히 데이터가 연결되있을수도 있습니다.
아 참고로 제거시 이동은 제거된 부분에서 잛은쪽을 재할당 시킴니다.
항상 반복자의 유효성을 잘 생각하셔서 관리하세요.
Simple is best, all of the time...
저거 맞나...
...
Testors 님이 지적하신 내용이 맞습니다.
서점에가서 확인했더니 재할당은 reallocation 이더군요.
저는 삽입과 제거시에 재할당을 유발한다고 하기에
당연히 re-assignment 로 생각했습니다.(assignment 연산자를 할당 연산자로 부르니까..)
하지만 왜 deque 에서는 제거시에도 reallocation 이 발생할수 있다는 것인지는 잘 모르겠군요.
shrink 되는 것을 reallocation 의 의미로 사용한 것도 아닌듯 한데 말입니다.
번역본의 번역이 꽤 잘되었다고 생각했는데 한국어 자체가 그리 논리적이지 못한건지
애매했던 여러부분들이 원서를 보니 명쾌하게 이해가 되더군요.
Re: ...
deque 같은 경우 배열을 여러개 사용합니다
그래서 erase 를 사용하다가 어느 배열을 사용할 필요가 없으면 그 배열을 제거 할수 있는것으로 알고 있습니다
따라서 재할당?의 개념이 될수 있을거라 생각합니다
vector같은 경우 위에서 말씀하신 이펙티브 STL에서 보면 한번 늘어나면 줄어들지는 않습니다 swap 방법을 제외 하면요
그리고 삭제로 반복자가 무효화되지 않는건 list 밖에 없는것으로 알고 있지만
이것도 100% 보장을 하지 않습니다
list 경우 반복자가 특별한 경우 무효화 되는 경우도 있다고 알고 있는데
기억이 잘 나지 않습니다 --;
승자는 자기보다 우월한 사람을 보면 존경심을 갖고 그로부터 배울 점을 찾지만 패자는 자기보다 우월한 사람을 만나면 질투심을 갖고 어디 구멍난 곳이 없는지 찾는다.
- 하비스
댓글 달기