[C/C++]STL 컨테이너 - std::vector 와 std::list

이 글은 이전에 운영하던 깃 블로그에서 옮겨온 글입니다.

 

서론

과거 취업활동을 위하여 면접을 보러 다닐 때 많이 들었던 질문이 있습니다. STL 컨테이너뿐 아니라 C#의 컬렉션 등 각 언어별 개체(데이터)의 그룹을 다루는 기술은 내부적으로 고유의 자료구조가 있습니다. 이 때문에 자료구조에 대한 이론적인 내용이나 알고리즘, 메모리 최적화는 물론 이를 적절하게 활용할 수 있는지 보는 단골 질문입니다. 오늘은 개인적으로 많이 쓰인다고 생각하는(면접에서 가장 많이 물어보았던 것 위주) C++ STL의 표전 컨테이너들에 관하여 알아보려 합니다. 이번 글에서는 std::vector 와 std::list 에 관하여 알아보겠습니다.

---

std::vector

 

랜덤 액세스 iterator를 사용하는 배열 기반의 자료구조

• 배열처럼 하나의 메모리 블록에 원소가 연속적으로 저장됨
• 삽입과 삭제에 비용이 상당히 큼
  => 원소가 연속적으로 저장되는 구조이기 때문에 삽입과 삭제 시 메모리 재할당이 발생할 수 있음
• 중간 삽입의 경우에는 원소들을 이동하는 비용이 발생함
• 배열처럼 랜덤 액세스([ ] 접근)이기 때문에 STL의 모든 알고리즘을 사용할 수 있음
• Capacity >= Size : 실제 할당되는 크기와 원소가 담긴 크기의 차이

vector에 관한 설명중 "삽입과 삭제 비용이 크다"라는 부분이 있습니다. 이 부분은 왜 그럴까요?
그것은 vector가 그냥 배열구조가 아닌 '동적 배열' 구조를 가지기 때문이다.

아니 배열이면 배열이지 동적 배열구조는 뭐죠? 배열에 대해서는 익히 들 고있다시피, 공간이 미리 할당된 정적 메모리입니다. 이러한 배열을 동적 할당을 하여 사이즈를 점점 늘리는 구조라고 생각하시면 됩니다.

즉, 미리 할당된(정적으로) 배열이 꽉 차면 좀 더 크게 재할당 하여 기존에 있던 것을 복사하고 계속 이용한다는 것입니다. 그래서 Capacity(할당된 양) >= Size(실제 사용하고 있는 양) 이 되는 것이죠. Size가 Capacity를 초과하는 시점에서 재할당이 일어나기에 삽입이 빈번하면 그만큼 비용이 커집니다.

음? 그러면 삭제에는 왜 비용이 큰 것이냐? 그것은 배열 자체의 구조적인 문제입니다. 배열의 0번 인덱스부터 차례로 값이 할당되어 있다고 가정해보죠. 제일 끝부분에 삽입을 한다면 상관없겠지만 중간에 삽입을 하게 된다면? 그 자리부터 뒤에 있는 모든 데이터를 한 칸씩 뒤로 미루는 작업을 하게 됩니다. 그렇기에 삽입과는 별도로 뒤로 미는 비용이 추가되게 되는 것이죠.

아니, 삭제라면서 왜 삽입 이야기를 하느냐? 삽입과 같은 맥락이기 때문입니다. 삽입과는 반대로 특정 인덱스의 데이터를 삭제한다면 그 칸을 비워둘 수 없으니 뒤에 있는 데이터들을 앞으로 한 칸씩 끌어오는 비용이 들기 때문이죠.

결론, vector는 삽입과 삭제에 추가적인 비용이 들기 때문에 빈번하면 좋지 않다. 삽입과 삭제에 O(1) + O(1 ~ n) : O(n)인 선형 시간의 시간 복잡도를 가진다.

vector의 가장 큰 특징, 배열처럼 랜덤 액세스 가 가능하다는 것입니다. 방법은 두 가지, [] 연산자를 통한 접근과 at(index) 멤버 함수를 통한 접근입니다. 이 내용도 면접 질문으로 심심치 않게 등장한다고 합니다.

응? 왜 굳이 두가지 방법이 있지? 뭔가 차이가 있는 것인가? 어떤 차이가 있지? 하고 저도 at()를 뜯어본 적이 있습니다.
결과적으로 같지만 약간의 차이가 있었습니다.

at() 함수는 사이즈 체크를 한다!

[index] 접근은 index가 vector의 인덱스 범위를 오버플로우 혹은 언더플로우 했는지 검사하지 않습니다. 즉, 예외처리를 따로 해주어야 한다는 것이죠. 그에 반하여 at(index) 함수는 정의 부분에서 index의 범위 체크를 하고 범위를 넘어가면 예외를 발생시킵니다. [] 접근에 비해서 조금 더 시간이 걸릴지도 모르겠지만 그만큼 안정성이 확보되었다가 차이일 수 있겠네요. 어떤 것을 사용할지는 프로그래머의 취향이 아닐까 생각합니다.

 

참고 : 이 글은, 배열과 연결 리스트에 관한 기본 지식이 있다는 가정하에 적었습니다.

---

std::list

• 양방향 연결리스트 구조의 컨테이너
• 랜덤 액세스가 불가능하기 때문에 특정 원소를 찾는 작업은 처음부터(혹은 끝에서부터) 탐색
• 검색 작업이 빈번할 경우에는 용이하지 않음
• 포인터 이동만을 하기 때문에 삽입과 삭제 비용이 작음 (수행 시간이 상수 복잡도를 가짐)
• 원소 데이터를 위한 메모리 이외에 연결 정보를 위한 추가적인 메모리가 필요
• 컨테이너들 중 예외 안정성 이 가장 강함

vector와 다르게 list는 삽입과 삭제에 이득이 있습니다. 연결 리스트의 구조를 생각해보면 당연하겠네요. 단순히 포인터의 교체이기 때문에 추가로 메모리를 이동하는 등의 비용이 들지 않기 때문이죠.

vector와의 차이를 보면 랜덤 액세스가 불가능하다는 것이 있습니다. 연결 리스트 구조이기 때문에 특정 노드에 접근하려면 해당 위치를 기억하지 않는 이상 처음 혹은 끝에서부터 선형 탐색을 해야합니다. 어차피 처음부터(혹은 끝에서부터) 선형탐색을 통해 각각 원소를 갱신하는 등에 작업이 아니라 특정 원소에 접근하는 게 빈번하고, 삽입과 삭제가 빈번하지 않다면 vector를 쓰는 걸 추천합니다.

 

list의 경우 컨테이너들 중예외 안전성 이 가장 강하다는데.. 예외 안정성이란 무엇일까요?

• 예외 안정성 : 보장 정도에 따라 3가지로 분류됨
  1) 완전 보장 : 절대로 예외가 발생하지 않음
  
  2) 강력 보장 : 예외가 발생하지만, 예외를 catch 하면 해당 객체의 상태가 예외 catch 이전 상태로 보장되고, 해당 객체를 계속 사용하는 것이 가능
  
  3) 기본 보장 : 예외를 catch 할 경우 메모리의 누수 등의 문제는 없지만 객체의 상태를 알 수 없게 되고, 해당 객체를 계속 사용하는 것은 불가능

이중 list는 강력 보장의 예외 안전성을 가진다고 한다. 뭐… 구현 자체가 그리 돼있다고 합니다.