STL:Container, Iterator, Algorithm 개념

오늘은 컨테이너, 이터레이터, 알고리즘이란 무엇이며, 무엇이 있는지 학습한 결과를 기록한다.

Container

컨테이너는 뜻 그대로 그릇, 무언가 담을 수 있는 역할을 한다. 즉, 자료 및 값을 저장하는 역할을 한다. 이 그릇의 모양이나 크기에 따라 담기를 권장되는 내용물이 다르고 취급 방법이 다르다.(컵이라는 그릇에 라면을 담을 수는 있지만 효율적이지 못한 것처럼.)

먼저, 컨테이너에는 순차 컨테이너, 연관 컨테이너, 컨테이너 어댑터 등이 있다. 

이게 무슨 소리인가? 

순차 컨테이너 : 뭔가 자료들이 순차적으로 들어가는거..?
연관 컨테이너 : 연관되어서 들어가는거..? 쌍으로 연관되어서 들어가는 것인가?
컨테이너 어댑터 : 어댑터란 다른 전기나 기계 장치를 서로 연결해서 작동할 수 있도록 만들어 주는 결합 도구 라는 정의가 있는 것으로 보아, 컨테이너와 컨테이너를 변환할 수 있는 그런게 아닐까?

나는 리얼로 위와 같이 생각했다. 내가 조사해 본 컨테이너들은 다음과 같다.

순차 컨테이너 

말 그대로 순차적으로 자료를 저장한다. 내 예측이 맞았다! 순차 컨테이너에서는 자료의 추가가 빠르지만 탐색할 때에는 시간이 많이 걸린다. 왜냐하면 순차적으로 접근하기 때문에!

이러한 순차 컨테이너에는 vector, deque, list 가 있다. 그렇게 벡터, 벡터했던게 바로 여기서 나오는 개념이었구나~

1. Vector : 동적 배열 처럼 동작하며, 자료는 뒤 쪽에서 추가된다.
2. Deque : 벡터와 유사하지만 앞에서도 자료들이 추가될 수 있다.
3. List : 벡터와 유사하지만 중간에서 자료를 추가하는 연산이 효율적이다.

연관 컨테이너

다음은 연관 컨테이너이다. 연관 컨테이너는 조사해 본 결과 사전과 같은 구조로 자료를 저장한다고 한다. 즉, 키와 값의 형태로 데이터가 저장되고, 자료들은 정렬되어 있으며 이러한 정렬 때문에 자료 추가에는 시간이 걸리지만 탐색은 키를 통하여 한 번에 뽑아내니 빠르다. 

이러한 연관 컨테이너에는 Set, Map, MultiSet, MultiMap 등이 있다

1. set : 집합이라고 하며, 중복이 없는 자료들이 정렬되어 저장된다.
2. map : 맵이라고 하며, key - value 형태로 저장된다.
3. multiset : 다중 집합이라고 하며, 집합과 유사하지만 자료의 중복을 허용한다.
4. multimap : 다중 맵이라고 하며, 맵과 유사하지만 키가 중복될 수 있다.

컨테이너 어댑터

드디어 컨테이너 어댑터이다!

컨테이너 어댑터는 기존 컨테이너의 인터페이시를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다고 한다. 이게 무슨 말일까 싶어서 좀 더 확인해보았는데

컨테이너 어댑터에는 Stack이 있다. 이를 예로 들자면, 기본 컨테이너인 벡터는 vector 클래스를 사용하는데 이 클래스의 인터페이스를 제한하고(벡터의 여러 기능들을 제한하고) 특정 형태(스택에 관련된 연산)의 동작 만을 수행하도록 한다.

그러니까 한 마디로 내가 어떤 자료구조를 구현할 것 인데 그냥 밑 바닥부터 구현하기 힘들고 귀찮은데 마침 기가 막히고 검증된 기존의 컨테이너가 있으니 이를 활용하여 확장 및 축소 등의 적용(Adapt)을 하는 것이라고 보면 될 것 같다. 그런데 뭔가 계속 제한한다고 하는데 이는 기존의 컨테이너에서 필요없는 부분은 사용하지 못하도록 하는 의미의 제한인 것 같다.

아무튼, 이러한 컨테이너 어댑터에는 Stack, Queue, Priority queue이 제공된다.

Iterator

이제는 반복자(Iterator)의 개념이다.

이 반복자는 각 컨테이너의 자료구조에 맞는 액세스를 할 수 있도록 도와준다. 예를 들어 순회를 한다거나, 원하는 값이 있는 메모리에 접근 가능하도록. 검증되었기 때문에 안심하고 사용해도 된다.

일종의 포인터와 비슷한 객체이다. 기존의 자료구조에서 보면 링크드 리스트에서만 보더라도 노드를 순회하기 위해서는 포인터의 값을 증가 혹은 감소시키고 여러 검사를 하는 등 작업을 했는데 반복자가 이를 대신해준다고 보면 된다. 

알고리즘마다 각기 다른 방식으로 컨테이너 요소들에 접근하기 때문에 반복자에도 여러 종류들이 존재한다. 그렇기 때문에 컨테이너를 사용한다면 꼭 반복자를 사용해야 한다.

반복자에는 몇 가지 예를 들자면 input iterator, output iterator, forward iterator, bidirectional iterator, random access iterator 등이 있다.

Algorithm

알고리즘은 문제 해결하기 위해서 그 절차나 방법의 공식화를 의미한다.

탐색, 정렬, 반전, 삭제, 변환 등이 있다.

 

위와 같이 3가지 요소로 구성된 것이 C++ STL이라는 것을 학습했고, 대충 개념을 잡게 되었다.