Home
About
- CodingGom's dev blog
  
  CodingGom의 개발 발자취
- Learn More
- Email
Posts
- All Posts
- All Tags
Projects

[Programming] STL 컨테이너

29 Jul 2018

Reading time ~5 minutes

##Hash와 Map 컨테이너

과거 취업활동을 위하여 면접을 보러 다닐때 많이 들었던 질문이 있다.

“STL ( … ) container에 대해서 설명해주세요.”

그것이 vector이든 list이든 map이든… 한번씩은 꼭 물어봤던거 같다. 지금와서 생각해보면 자료구조에 대한 기본적인 이해와 알고리즘, 메모리등 종합적으로 수준을 알 수 있는 참 좋은 질문이라고 생각한다. 역시, 괜히 물어보는게 아니었다.

실제 본인이 면접에서 들었던 컨테이너들에 관해 살펴보기로 하겠다.

#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는 강력 보장 의 예외 안전성을 가진다고 한다. 뭐… 구현자체가 그리 되있다고 한다.

#std::set 과 std::map

map ○ 레드 - 블랙 트리 기반 ○ Key값과 데이터를 한쌍의 원소로 관리하는 컨테이너 ○ Key값의 중복을 허용하지 않음 (multmap의 경우 key 부분의 중복을 허용함) ○ Key값은 int이외에 다른 타입을 가질수 있음 ○ 연관 배열처럼 사용됨

set ○ 연관 컨테이너, 균형 바이너리 트리구조로 양방향 반복자를 갖는다 ○ 레드 - 블랙 트리 기반 ○ Key만을 저장, 중복을 허용하지 않음 (multset의 경우 중복을 허용함) ○ 원소값 변경을 권하지 않음 => 연관 컨테이너인 set은 원소가 정렬된 상태이기 때문에 원소 값 자체를 바꾼다는 것은 규칙을 깨는 행위 ○ 정렬 알고리즘등 랜덤 액세스를 요구하는 알고리즘을 사용할수 없다 ○ 삽입시 자동으로 정렬된 상태가 됨 (기본 정렬자 : less, 내림 차순) ○ 삽입 성공여부가 pair로 반환됨 (first : 값 위치의 반복자 / second : bool 성공여부)

위의 두 컨테이너는 기능상으로는 매우 유사하다. 차이라고 한다면 map은 key 와 그 키의 값에 해당하는 value가 함께 저장되고, set은 key값만 저장되는 구조이다. 사실 이 두 컨테이너의 차이보다 map과 hash와의 차이를 많이 물어봤던거 같다. 일단 Hash map이란 무엇일까?

Hash map역시 key와 value의 쌍을 이루는 구조이다. 음? 같은거 아닌가? 일단 내부에 사용된 자료구조가 다르다. Hash map은 Hash table 자료구조를 이용한다. 즉, key값을 해쉬함수에 대입하여 테이블의 버켓번호를 분포시키고 이 분포가 어떠냐에 따라 성능에 영향을 받는다. 잘 구현된 해쉬함수(중복없는 고른 분포를 만들어주느냐)에서는 검색 속도가 O(1)의 시간 복잡도를 가진다. O(logN)의 Map보다 빠르다고 한다.

아니 그러면 Hash map을 쓰는게 좋지 않느냐하는 의문을 가지게 된다. 본인의 생각은 ‘글쎄’이다. 일반적으로 Hash map을 쓰는게 빠른게 맞다. 하지만 해쉬함수가 어떠냐에 따라 성능은 천차만별이다. 이러한 이유로 STL의 표준으로 등록되지도 않았다.(물론 unodered_map이라고 해쉬테이블을 사용하는 컨테이너가 표준으로 등록되어 있다) 뭐… 어떤걸 사용하냐는 이것 또한 사용자의 취향이라고 생각한다.

여담으로 set과 map의 삽입 삭제가 빈번하면 좋지 않은 이유는 O(logN)의 시간 복잡도를 가지지만, 레드-블랙 트리의 구조를 내포하고 있기에 밸런싱(트리의 균형을 유지하는 작업)을 삽입과 삭제시 수행하기 때문 이다.

#std::deque

deque ○ 자료구조 큐 + 스택 기반의 컨테이너 ○ 데이터의 삽입 삭제가 양끝에서 일어날 수 있다 ○ vector 컨테이너의 단점을 보안하기 위하여 여러개의 블록을 할당하고 하나의 블록처럼 사용하는 기능 제공 ○ 연속된 메모리 공간이 아니여서, 원소간들간의 포인터 연산이 불가능함 ○ Capacity = Size

이것은 면접때 한번도 안물어봤지만, 심심치 않게 나오기도 한다기에 간단한 설명만 하겠다.

C C++ Share Tweet +1