vector와 deque는 연속적인 메모리 공간을 사용하는 동적배열?
글쓴이: dltkddyd / 작성시간: 금, 2014/02/21 - 2:15오후
vector가 어떻게 구현되는지를 생각해봤는데, 내부에 역참조할 수 있는 포인터를 하나 갖는 동적배열이라는 잠정적인 결론을 내리게 됐습니다. 맞나요?
그리고 그 포인터가 가리키는 일련의 공간(하나로 연이어진)을 사용합니다. 이것도 맞는지 궁금하네요?
그리고 deque도 vector와 같이 역참조할 수 있는 포인터를 하나 갖고 있으며 구현된 원리는 vector와 같다. 즉 일련의 공간(하나로 연이어진)을 사용한다. 단 앞에서 삽입, 삭제가 가능하다는 점에서만 vector와 다르다. 이 설명도 맞는지 궁금합니다.
vector는 직접 만들어봤습니다. deque도 한 번 직접 만들어보려고요? vector와 유사한 구조인지 궁금합니다.
Forums:
C++11 이전의 표준에서는 vector가 꼭 연속된
C++11 이전의 표준에서는 vector가 꼭 연속된 공간을 사용할 의무가 없었고, C++11에 와서야 연속된 공간을 사용해야 한다는 내용이 추가되었습니다.
대부분의 구현체가 연속된 공간을 사용하도록 구현되어 있긴 하지만 기존의 표준에서는 vector가 꼭 연속된 공간을 사용하리란 보장을 할 수 없습니다.
deque는 C++11을 포함한 모든 표준에서 연속된 공간으로 구현해야할 의무가 없습니다.(물론 연속된 공간으로 구현하는 것이 가장 편하겠죠.)
deque는 그럴만한 이유가 있는거네요.
처음에는 deque가 vector와 같을 것이라고 생각했는데, 어제 하루, 그리고 오늘 생각해보니 많이 다르네요. deque는 vector보다 더 진일보한 것이며 vector의 단점을 보완하기 위한 컨테이너 같다는 생각을 했습니다. 각종 연산자는 물론 begin(), end()의 구현도 vector와는 다를 것이라는 판단을 내렸습니다. 물리적으로 독립적인 공간을 사용하는 것이 분명할 것이라 생각하는데요. 그렇지 않으면 push_front를 연속으로 사용할 때 부하가 많이 걸리더군요. 표준의 경우는 아무리 수천 만 번을 push_front로 값을 집어넣어도 속도가 전혀 줄어들지 않습니다. 이로 추정컨데 분명 gcc의 deque는 두 개의 물리적인 공간을 사용할 겁니다. deque가 말 그대로 double ended que니까요. 즉 두 개로 끝나는 큐라는 것이죠.
맞는지 모르겠네요?
본인 맞습니다.
인증샷
우헤헤헤... 로 대신합니다.
그냥 벡터에서 뒤에 미리 할당해놓듯이 앞에도 미리
그냥 벡터에서 뒤에 미리 할당해놓듯이 앞에도 미리 할당하고 유효한 데이터가 시작되는 오프셋만 조절하면 됩니다.
단점을 보완할려고 시작한 것 같기는 하지만...
실제로는 더 쓸모가 없는 것 같습니다.
http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/
뭐랄까.... 콩라인?
과거 표준을 구하기는 어렵지만 vector 는 C++98 도 연속공간을 보장하는 것으로 알고 있습니다.
주소추출연산자를 사용한 표현식은 확실히 C++11 에 추가된 것 같은데 좀더 명확히 하기 위해서 들어간 것으로 알고 있습니다.
그리고 deque 는 표준이 요구하는 바를 구현할려면 전체공간을 연속공간으로 만들 수가 없습니다.
http://stackoverflow.com/questions/5345152/why-would-i-prefer-using-vector-to-deque
무엇보다 container 에 삽입, 삭제가 일어나도 요소참조는 무효화되지 않는다는 규정이 있기 때문입니다.
vector의 연속공간 보장은 C++11이 아니라
vector의 연속공간 보장은 C++11이 아니라 C++03부터 추가된 내용이었네요.
deque에 레퍼런스 invalidation에 관한 내용이 있었군요. 개인적으로 거의 안쓰는 컨테이너라 iteration validation에 대해서만 기억하고 있어서 잘못된 답변을 달았네요. 죄송합니다.
댓글 달기