STL ( Standard Template Library ) 컨테이너

• STL 컨테이너 종류로는 시퀀스 컨테이너, 어댑터 컨테이너, 연관 컨테이너가 있습니다.

시퀀스 컨테이너

list

• list 는 이중 링크드 리스트로 구현된 컨테이너입니다.

장점

• 정렬이 가능합니다.
• 중간에 데이터를 삽입하거나 삭제할 때 새롭게 연결만 해주면 되기 때문에 오버헤드가 적습니다.
• 저장할 요소의 개수를 미리 알 수 없을 때 사용하기에 적합합니다.

단점

• 랜덤 액세스가 불가능합니다.
• 순회할 때 스페이셜 로컬리티의 이점을 얻을 수 없습니다.

사용하기 적합한 경우

• 저장한 요소의 개수가 빈번하게 변화할 때
• 삽입, 삭제가 빈번하게 발생될 떄
• 랜덤 액세스가 필요하지 않을 때

vector

• vector 는 배열로 구현된 컨테이너입니다.
• 저장할 요소의 개수가 최대 크기를 넘어설 경우 현재 크기의 *2 만큼의 배열을 새로 확보한다.

장점

• 정렬이 가능합니다.
• 인덱스를 이용한 랜덤 액세스가 가능합니다.
• 순회할 때 스페이셜 로컬리티의 이점을 얻을 수 있습니다.

단점

• 중간에 데이터를 삽입하거나 삭제할 때 복사 오버헤드가 발생합니다.
• 저장할 요소의 개수가 현재 컨테이너 크기보다 클 경우 새롭게 메모리를 확보하고 복사하는 오버헤드가 발생합니다.

사용하기 적합한 경우

• 저장할 요소의 개수가 일정할 때
• index를 이용한 랜덤 액세스가 필요할 때
• 잦은 순회가 필요할 때

어댑터 컨테이너

stack

• LIFO ( Last in first out ) 의 특징을 가진 컨테이너입니다.

queue

• FIFO ( First in first out ) 의 특징을 가진 컨테이너입니다.

priority_queue

• 힙 자료구조의 컨테이너입니다.

연관 컨테이너

map, set

• 자가 균형 이진 탐색트리인 레드-블랙 트리로 구현된 컨테이너입니다.
• key, value 를 한 쌍으로 저장하는 컨테이너입니다.
• multimap, multiset 을 이용하면 중복 key 저장이 가능합니다.

장점

• key를 기준으로 정렬이 가능합니다.
• 랜더 액세스가 가능합니다.

단점

• 시간 복잡도가 O(log N) 으로서 저장하는 데이터가 많아질 수록 검색 성능이 떨어집니다.

사용하기 적합한 경우

• key를 이용한 랜덤 액세스가 필요할 때
• key를 기준으로 정렬이 필요할 때

unordered_map, unordered_set

• 해쉬 테이블로 구현된 컨테이너입니다.
• key, value 를 한 쌍으로 저장하는 컨테이너입니다.
• unordered_multimap, unordered_multiset 을 이용하면 중복 key 저장이 가능합니다.

장점

• key 해쉬를 이용한 랜덤 액세스가 가능하기 때문에 저장할 요소의 개수의 상관없이 일정한 검색 시간 복잡도를 가집니다.

단점

• 정렬이 불가능합니다.
• 저장할 요소의 개수가 적다면은 오히려 해쉬 함수로 인해 성능이 떨어질 수 있습니다.
• 해쉬 충돌이 발생될 경우 그만큼 검색 시간 복잡도가 증가합니다.

사용하기 적합한 경우

• key를 이용한 랜덤 액세스가 필요할 때
• 정렬이 필요하지 않을 때
• 많은 양의 데이터를 저장해야 할 때
• 많은 양의 데이터를 저장해도 일정한 검색 시간 복잡도를 원할 때

STL 컨테이너 비교

STL ( Standard Template Library ) 이란?

• STL은 일반적으로 많이 사용되는 자료구조와 알고리즘을 모은 표준 템플릿 라이브러리입니다.
• STL은 반복자, 알고리즘, 함수자, 컨테이너라고 불리는 네 가지의 구성 요소를 제공합니다.

Template 과 Generic Programming

• 데이터 형식에 의존하지 않고, 하나의 값이 여러 다른 데이터 타입들을 가질 수 있도록 하여 코드의 재사용성 및 다형성의 이점을 얻을 수 있는 프로그래밍 기법입니다.

Template

• Template 은 C++ 에서 Generic Programming 기법을 사용할 수 있는 기능입니다.

STL 반복자 ( iterator )

• STL 은 일관적으로 STL 컨테이너를 접근할 수 있는 iterator 라고 불리는 반복자를 제공합니다.

iterator 를 사용하는 이유

• iterator 를 통해서 STL이 제공하는 컨테이너를 일관적인 방법으로 접근할 수 있습니다.

STL 알고리즘

• STL 은 min_elementPermalink ( 최솟값 ), max_elementPermalink ( 최댓값 ), sort ( 정렬 ), find ( 요소 찾기 ), erase ( 요소 삭제 ) 등의 STL 컨테이너를 대상으로 사용할 수 있는 알고리즘 함수들을 제공합니다.

STL 함수자 ( functor )

• STL은 plus, minus, multiplies, divides 와 같은 산술 연산 함수자 그리고 equal_to, not_equal_to, greater, less 등과 같은 비교 연산 함수자를 제공합니다.

사용 예시

• priority_queue<int, vector<int>, greater<int>> pq; 와 같이 사용해서 낮은 숫자가 가장 먼저 pop 될 수 있도록 할 수 있습니다.

STL 컨테이너

• STL은 시퀀스, 연관, 어뎁터 컨테이너를 제공합니다.

시퀀스 컨테이너

• 시퀀스 컨테이너는 데이터를 선형을 저장하고 관리하는 형태의 컨테이너를 말합니다.
• list, vector, deque, forward_list, array 등이 있습니다.

어뎁터 컨테이너

• 기존 컨테이너를 랩핑하여 스택과 큐 같은 인터페이스의 제한을 둔 컨테이너를 말합니다.
• stack, queue, priority_queue 등이 있습니다.

연관 컨테이너

• key 와 value 를 묶어 데이터를 하나의 쌍으로 저장하는 컨테이너를 말합니다.
• map, multimap, set, multiset, unordered_map, unordered_multimap, unordered_set, unordered_multiset 등이 있습니다.

C++ 캐스트를 사용해야 하는 이유

• 코드만 보고 캐스트를 사용한 목적을 확실히 알 수 있습니다.
• 일부 캐스트는 컴파일 단계에서 에러를 확인할 수 있습니다.

C++ 캐스팅의 종류 및 사용방법

const_cast

• const, volatile 특성을 제거할 때 사용하는 캐스트입니다.

dynamic_cast

• 상속관계에 있는 사용자 정의 데이터 타입간에 업 캐스팅할 때 사용합니다.
• 가상 함수를 가진 상속관계에 타입간에 캐스팅시에는 다운 캐스팅도 가능합니다.
• 다운 캐스팅시 실제로 상속관계에 있는 타입인지 런 타임에 RTTI를 통해 검사하기 때문에 안전성 측면에서는 이점이 있지만, 검사하는 코드로 인해 성능상 좋지 못한 캐스트입니다.

reinterpret_cast

• 어떠한 타입이든 캐스팅이 가능합니다.
• 강력한 캐스트이지만, 컴파일러마다 캐스팅 결과가 다르기 때문에 이식성이 좋지 못합니다.

static_cast

• 일반 데이터 타입간에 캐스팅을 허용합니다.
• 일반 데이터 타입을 void*로 캐스팅이 가능합니다.
• 상속관계에 있는 사용자 정의 데이터 타입간의 업, 다운 캐스팅이 가능합니다.