[C++] vector & deque

Vector

 

vector.size() 는 실제 벡터에 들어있는 item의 수를 나타낸다.

반면, vector.capacity()는 벡터에 할당된 메모리 크기를 나타낸다.

따라서 size != capacity

capacity grows exponentially.

 

ex)

vector<int> v = {1,2,3,4};
// v.size() == v.capacity() == 4

v.push_back(5);
// v.size() == 5;
// v.capacity() == 8

 

여기서 v.capacity() == 8 인 이유는?

4 다음엔 8로 메모리 공간이 할당되기 때문이다.

 

이번엔 다음 예를 살펴보자.

// EX1
vector<int> v(5); // 선언과 동시에 초기화
// v.size() == 5, v.capacity() == 5

// EX2
vector<int> v2; // 선언
v2.resize(5); // 초기화
// v2.size() == 5, v2.capacity() == 5

// EX3
vector<int> v3;
v3.reserve(5);
// v3.size() == 0, v3.capacity() == 5

EX3를 살펴보면,

reserve() 함수를 통해 size()는 0이지만 capacity는 5임을 알 수 있다.

 

따라서, 최대 개수를 안다면 reserve(N)을 사용하면 좋다.

 

Deque

: 동적 배열, 임의의 위치에 있는 원소 접근과, 앞과 뒤에서 원소를 추가하는 연산은 O(1)을 보장

1.  deque는 재할당이 없다. 즉, reserve()와 capacity()가 없다.

2. vector는 한방향인데, deque는 양방향성을 띈다.