정체불명의 모모

[C++/STL] vector와 deque의 차이점 본문

프로그래밍(c++)

[C++/STL] vector와 deque의 차이점

정체불명의 모모 2021. 8. 10. 16:38
vector와 deque는 거의 동일한 인터페이스를 제공하고 대부분의 경우에 서로 바꾸어도 동작이 가능 할 정도로 유사하다.

"그럼 어떤 차이점이 있는 걸까?"


메모리

가장 중요한 차이점은 메모리에서의 연속성이다.
  • vector는 메모리가 연속적이다.
  • deque는 메모리가 연속되어 있지 않다.

Deque

Deque의 특징
  • Deque는 어느 방향으로도 iterate(참조) 가 가능하다.
    • DQ[2] 이런것이 가능하다.
  • vector와 다르게, 양쪽 끝 모두에서 원소 삽입, 삭제가 가능하다.
  • 그리고, 중간에 insert, erase도 가능하다.
  • 하지만 연속되어 있는것처럼 보이지만 연속되어 있지 않다.
    • 메모리에 쪼개서 보관한다 메모리(메모리 관리에 효율적)
      • 일관적인 성능을 보장한다.
    • 때문에 vector와는 다르게 capacity 와 reserve가 없다.
    • pointer 간 연산도 불가능 하다.

Vector

Vector의 특징
  • 메모리에 연속적으로 배치되어있다.
    • Cache Rate가 매우 높다.
  • 중간에 원소를 삽입하거나 삭제하는 작업은 오래걸린다.
  • 그리고 capacity는 기본적으로 , size보다 크게 할당 되어진다(약 2배 정도). 
    • 하지만 capacity가 부족한 경우 memory rellocate 작업이 필요해진다.

시퀀스 컨테이너간 차이점

vector
  • 개별 원소에 대한 접근이 잦을때 매우 유리
  • 중간 삽입 / 삭제시 매우 불리
  • 큰 데이터를 다룰 경우 불리
deque
  • 개별 원소에 대한 접근이 잦을때 유리
  • 중간에 삽입 / 삭제시 불리

1. deque의 push_front( ) 와 pop_front( )를 지원

: vector의 경우 push_back( ) , pop_back( ) 뒤에서 삽입, 삭제만을 제공한다. 

  하지만, deque는 'double-ended queue'에서 붙여진 이름답게 컨테이너 양쪽 끝에서 요소를 모두 삽입, 삭제가 가능하다.

  

2. vector의 capacity( ) 와 reserve( ) 

: deque 같은 경우에는 이런 함수가 필요없기 때문에 지원하지 않고 있는 것인데 이유를 알려면 각 형식이 메모리를

  어떻게 관리 하고 있는지 알 필요가 있다.

 

  ㅁ vector의 경우에는 연속된 메모리 구조를 사용한다.

  ex) 예를 들어 10MB의 vector는 연속된 10MB의 메모리를 사용하게 된다.

   ->하지만 경우에 따라서 연속된것이 아니라 10MB를 작은 블록으로 여러개 나누어서 사용하는 것이 성능이 더 좋을 수도 있다.

 

   ㅁ deque의 경우 작은 메모리 블럭을 연결하여 데이터를 구성한다.

 


 

 

Comments