※ 본 글은 제 네이버 블로그에 올렸던 내용을 기반으로 조금 더 갈고 닦은 글입니다!
뒤늦게 PS에 재미들려 하라는 공부는 안하고 PS문제만 풀고 있습니다.. 너 졸업하고 뭐할꺼니 대체.. ㅋㅋㅋㅋㅋㅋㅋㅋ
좀 더 어렸을 때, 대학교 1학년 때라도 시작했으면 어땠을까 하는 아쉬움이 들지만 뭐 어쩌겠습니까! 지금부터라도 열심히 하는거죠 ㅎㅎ (서울캠퍼스에 컴공만 있었어도 ㅂㄷㅂㄷ)
다들 그렇듯 저도 프로그래밍 언어를 학교 파이썬수업으로 시작했지만(물론 정확하게는 대학교 1학년때 프로그래밍 동아리에서 배운 Ruby이지만, 군대를 다녀와서 거의 다 까먹었으므로.. ㅠㅠ) 자료구조를 듣다보니 메모리까지 컨트롤해버리는 C++의 매력에 꽂혀 되도록 C++로만 문제를 해결하고 있습니다.물론 다른 언어에 비하면 로우레벨에 가깝기 때문에 샷건 여러번 쳤습니다...
C++로 문제를 풀 때 본인이 자료구조를 하나하나 만들어서 사용하는 것은 시간적으로 굉장히 비효율적입니다. 남들 다 빠르게 빠르게 문제 푸는데 나만 '1+1은 도대체 어떻게 계산되는거지?' 하며 고민하고 있을 순 없잖아요?
간단하게 말해 이런 자료구조를 담은 친구들을 STL이라고 합니다. 아래에서 좀 더 자세하게 알아보겠습니다!
목차
0. STL이란?
STL(Standard Template Library)는 표준 템플릿 라이브러리의 약자입니다.
엄밀하게 말하면 C++에서 이렇게 이미 만들어진 템플릿을 이용하기 위해 불러와서 사용하는 것은 C++ Standard Library라고 하는 것이 맞지만, 예전부터 STL이라고 불러왔기 때문에 지금도 STL이라고 많이들 부르곤 합니다. (CSL이라고 부르기는 좀 그랬나봅니다 ㅋㅋㅋㅋ)
STL의 종류는 굉장히 다양합니다. 아마도 여러분이 컴공, 컴과, 혹은 소프트웨어학과 학부생이라면 자료구조 라는 수업때 직접 하나하나 구현을 해 봤을 것이라고 생각됩니다.(저도 저번 학기 수업들으며 죽어라 만들었습니다 ㅋㅋㅋㅋㅋ) 이것들을 한데 모아서 라이브러리로 모으면 STL이 되는 것이죠.
EA에서 만든 STL인 EASTL(그 피파 게임사인 EA 맞습니다!), STLPort, TSTL(TypeScript에 포팅된 STL입니다!), SGI STL 등 다양한 종류가 있습니다. 원하면 가져와서 쓸 수도 있고 필요에 따라 만들 수도 있는 것이 바로 STL이죠.
STL은 크게 컨테이너, 반복자, 알고리즘 총 3가지로 나눌 수 있습니다. 하나하나 살펴보죠!
0.0. 컨테이너 (Container)
컨테이너는 자료를 저장하는 클래스 템플릿들의 집합입니다.
big-O Notation을 배우셨다면 이 big-O가 가장 최소화될 수 있는 자료형을 골라서 그걸로 컨테이너를 선택해서 만들면 성능을 극대화 할 수 있습니다.
- pair : 간단한 연관 컨테이너로, 순서에 따라 first, second로 불리는 객체로 구성되어 배치, 복사, 비교될 수 있습니다. 여기서 first 요소가 컨테이너 내 유니크 키로 작동합니다. 이 pair는 map이나 hash_map(C++11부터는 unordered~)에 기본값으로 쓰입니다.
- vector : C의 배열과 거의 비슷하게 사용할 수 있는 컨테이너입니다. 맨 끝에 삽입과 삭제, 그리고 위치 참조시 O(1)이라 매우 효율적입니다. 다만 삽입하고 삭제하는데가 끝이 아니라면 O(n)이 걸립니다.
- deque : 맨 앞, 맨 뒤에서 모두 O(1)로 삽입과 삭제가 가능합니다. 다만 메모리 상에서 연속적으로 저장하지는 않기 때문에 반복자를 사용할 때 유효성을 보장하지 않습니다.
- list/forward_list : 연결 리스트로, 검색과 접근에 있어서 느리지만 위치만 안다면 빠르게 삽입하고 제거할 수 있습니다. (forward가 붙으면 단방향 연결리스트로 찾을 때 후진이 불가능합니다!!)
- set/multiset : 트리구조로 만들어져 삽입할 때부터 정렬됩니다. 각종 집합 연산이 가능하고 set의 경우 정렬시 사용되는 값이 유일해야 합니다. (multiset은 정렬 시 사용되는 값이 유일하지 않아도 됩니다!!)
- map/multimap : set과 굉장히 유사하지만 key값에 더해서 value값이 존재합니다. (pair 형태로!!) key값은 유일해야 하지만 value 값은 유일할 필요는 없습니다.(multimap은 key값이 유일하지 않아도 됩니다!!)
- unordered_set/unordered_map/unordered_multiset/unordered_multimap : 위의 set과 map와 개념적으로는 동일하지만 트리 대신 hash를 이용하여 구현한 컨테이너입니다. (C++11 이전에는 hash_set 등의 hash가 붙은 이름으로 사용되었습니다!!) 그래서 삽입, 삭제, 검색시 시간복잡도 역시 트리가 아니라 해시의 특성을 따릅니다.(삽입, 검색, 삭제시 최적 O(1), 최악 O(n))
- stack : LIFO(Last in first out)형식으로 구성된 자료구조입니다. 마지막으로 삽입된 요소가 top에 존재합니다.
- queue : FIFO(First in first out)형식으로 구성된 자료구조입니다.
- priority queue : queue인데, 높은 우선순위를 가진 요소가 상위에 위치합니다.
※ 이런 컨테이너들에 대해서 더 자세히 알고 싶다면 인터넷이나 학교에서 열리는 자료구조 수업을 들으시면 이해에 도움이 됩니다! 또한 컨테이너들을 사용하는 방법은 각 컨테이너별로 포스팅할 예정입니다!
0.1. 반복자(Iterator)
반복자는 컨테이너 원소를 순회하는 방법을 추상화한 객체들을 뜻합니다.
반복자를 이용하면 STL 내부의 자료에 접근하는 방법을 표준화할 수 있습니다.
다르게 말하면 이런 반복자를 사용해서 컨테이너 내 원소들에 접근할 수 있습니다.
- input iterators : 값들의 시퀀스를 읽는 데 사용됩니다.
- output iterators : 값들의 시퀀스를 쓰는 데 사용됩니다.
- forward iterators : 읽고 쓸 수 있으며 앞으로 움직일 수 있습니다.
- bidirectional iterators : forward iterators의 특징을 가지며 앞뒤로 다 움직일 수 있습니다.
- random access iterators : 자유롭게 움직일 수 있습니다.
0.2. 알고리즘(Algorithm)
알고리즘은 정렬, 삭제, 검색, 연산등의 활동을 수행하는 작업을 정의해 놓은 템플릿 함수를 말합니다.
- sort : 정렬하는 함수
- find : 검색하는 함수
- transform : 변경하는 함수
- for_each : first부터 last까지 원소들의 각각에 대해서 함수를 실행하는 함수
- generate : 생성하는 함수
- binary_search : 이진탐색법으로 검색하는 함수
1. STL의 특징
STL의 종류가 매우매우 다양한 만큼 STL의 특징은 각 STL마다 다릅니다.
어떤 STL의 경우 검색할 때 효율적일 수 있고, 어떤 STL의 경우 삽입할 때 효율적일 수 있는 것이죠. 이러한 효율성은 어떻게 STL을 만드냐에 따라 달라집니다.
그리고 STL은 컨테이너들에 독립적이기 때문에 라이브러리의 복잡성을 굉장히 줄여주었습니다.
또한 템플릿의 사용을 통해 기존 런타임 다형성(실행시간 다형성)에 비해 효과적인 컴파일 타임 다형성을 제공합니다. (런타임(Run time)은 응용프로그램이 동작되는 때, 컴파일타임(Complie time)은 기계어 코드로 변환되는 때를 의미합니다)
무엇보다도 우리가 따로 자료구조를 담은 함수를 만들어 놓지 않아도 미리 라이브러리만 include해서 쓸 수 있다면 시간도 절약되고 간편하죠. 얼마나 좋습니까!!
지금까지 STL에 대한 기본적인 정보에 대해서 알아보았습니다.
초창기 STL은 C++ 표준 라이브러리에 큰 영향을 미쳤고, 계속 발전해오면서 현재 2021년에 아주 편리하게 라이브러리를 불러와서 사용할 수 있다고 생각하면 STL의 기본은 이해하고 있다고 볼 수 있을 겁니다 ㅎㅎ
다음 포스팅부터는 위에서 언급했던 컨테이너들을 하나하나 살펴보고 어떻게 사용할 수 있는 지에 대한 방법과 간단한 설명을 해 보도록 하겠습니다. 감사합니다 :)
최근댓글