[C++] vector와 deque

vector는 동적 배열이다.
일반 배열이나 std::array처럼 길이가 정해지는 것이 아니라, 실시간으로 필요한 만큼 길이가 늘어난다.

그리고 배열답게 O(1) 시간에 즉시 완수되는 인덱싱이 가능한데다, 실제 메모리 상의 시퀀스(연속성)이 보장이 되기 때문에 더욱 빠르다.

하지만 그렇기 때문에 확장에는 약간의 단점이 따른다.
push_back 등으로 길이를 늘일 때 벡터는 어떻게 동작을 할까? 메모리를 다시 재할당해야한다.
(실제로는 미리 어느정도의 여분 공간을 할당해두어서, 재할당이 매번 일어나진 않는다.)
필요한 공간만 할당해서 그대로 이어붙이면 안되냐고? 그럼 메모리 상의 시퀀스를 유지할 수가 없다.

그래서 벡터는 공간이 부족하면 더 큰 공간을 새로 할당해서 전부 거기로 옮긴다.
원래 이 부분에서 적지 않은 오버헤드가 있었다.
그래서 성능의 병목을 reserve라는 함수로 미리 할당해서 재할당을 방지해야 했는데, 다행스럽게도 C++11부터 Move Semantic이 등장해서 이 동작의 비용이 크게 감소했다고 한다.

그래서 갱신이 안되는 구식 레퍼런스 사이트에서 push_back의 복잡도를 보면 이렇게 나온다.

"상수 시간이 걸린다. 하지만 재할당이 일어나면 선형시간이 걸린다."

그리고 최신 레퍼런스 사이트에서는

그냥 상수라고 해준다.

deque는 더블-엔디드-큐다.
원래는 앞과 뒤에서만 접근이 되는 구조여야 하는데, c++에서는 좀 변화를 줬다.
인덱싱이 되게 한 것이다.
그래서 deque는 앞에서도 빠른 추가와 삭제가 가능한 vector가 되었다.
물론 이것 말고도 차이는 있다.

벡터는 공간이 부족하면 재할당을 하지만 deque는 그냥 새 '청크'를 생성한다. 이 청크들은 전부 동일한 크기를 가지는 배열이다.
그리고 청크에 대한 인덱싱 테이블을 두어서 바로바로 접근을 할 수 있게 한다.
구조는 아래와 같은데, 스택오버플로에서 퍼온거다.
https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

그래서 deque 자체는 시퀀스가 보장되지 않으나, 보다 균일한 성능을 보장할 수 있었다. C++11부턴 달라진 것 같지만 말이다.

이대로 끝나긴 심심하니 성능 측정이나 해본다.

순서대로 돌면서 삽입하는 코드다.

컴파일 환경은 릴리즈 모드에 x86이고, 측정 단위는 나노초다.

우리 모두 벡터를 쓰자.