[C++] 표준 템플릿 라이브러리 (STL)

세 개의 라이브러리를 이야기한다.

 

• 컨테이너 (container) = 임의 타입의 객체를 보관
• 반복자 (iterator) = 컨테이너에 보관된 원소에 접근
• 알고리즘 (algorithm) = 반복자들을 가지고 일련의 작업을 수행

반복자를 이용해서 컨테이너를 추상화 시켜서 접근, 하나의 알고리즘 코드가 모든 종류의 컨테이너들을 지원

 

컨테이너

시퀀스 컨테이너 (sequence container) =  객체들을 순차적으로 보관   ->  vector, list, deque

연관 컨테이너 (associative container) = 키를 바탕으로 대응되는 값을 찾아줌  -> 셋(set), 맵(map), unordered_set, unordered_map

 

벡터 (vector) = 가변길이 배열

원소들이 메모리 상에서 실제로 순차적으로 저장, 임의의 위치에 있는 원소를 접근하는 것이 매우 빠름

 

[], at = 임의의 위치에 있는 원소에 접근 - O(1)

push back / push_pop = 맨 뒤에 새로운 원소를 추가 or 제거

- 일반적으로 O(1) , 원소 추가 시 매우 드물게  할당된 공간을 다 채웠을 때는 O(n) -> 이를 amortized O(1)라고 표현

insert, erase = 중간에 원소 추가 or 제거 - O(n)

 

 

리스트 (list) = 양방향 연결 구조를 가진 자료형

 

덱 (deque - double ended queue) 

 

여러개의 메모리 블록을 할당하고하나의 블록처럼 여기는 기능을 제공

메모리가 부족할때 마다 새로운 메모리 블록을 할당하여 이전 원소를 복사하는 수고를 하지 않는다.

원소들이 어디에 저장되어 있는지에 대한 정보를 보관하기 위해 추가적인 메모리가 더 필요하다.

실행 속도를 위해 메모리를 희생하는 컨테이너.

 

• 일반적인 상황에서는 그냥 벡터를 사용
• 중간에 원소들을 추가하거나 제거하는 일을 많이 하고, 원소들을 순차적으로만 접근 한다면 리스트를 사용
• 맨 처음과 끝 모두에 원소들을 추가하는 작업을 많이 하면 덱을 사용