[C++] STL - STL 구성 요소

STL 구성 요소에는 컨테이너, 반복자, 알고리즘이 존재한다.

 

컨테이너(container)

컨테이너는 같은 타입의 여러 객체를 저장하는 객체로 일종의 객체들의 집합이라고 할 수 있다. 컨테이너는 클래스 템플릿으로 작성되어 있어 컨테이너 변수를 생성할 때 템플릿 인자로 요소의 타입을 명시해야 한다. 따라서 대입할 수 있는 타입의 객체만을 저장해야하며 복사 생성 또한 가능하다. 또한 요소의 추가 및 제거를 포함해 다양한 기능을 수행하는 멤버 함수가 존재한다.

 

컨테이너 종류

종류	설명	컨테이너
시퀀스 컨테이너	특별한 규칙이 없는 일반적인 컨테이너. 순서가 있는 선형 구조	vector, deque, list, forward_list
연관 컨테이너	특정 규칙에 의해서 자동으로 정렬, 저장, 관리하는 컨테이너. 순서가 없는 비선형 구조	set, multiset, map, multimap
컨테이너 어댑터	간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형. 반복자를 지원하지 않아 STL 알고리즘에서 사용할 수 없다.	stack, queue, priority_queue

시퀀스 컨테이너의 경우 요소가 언제 삽입되는지에 따라 배열 안에서 요소의 순서가 결정된다. 즉, 연속되게 저장하는 배열같은 구조이다. 하지만 특이하게 list는 다음 요소의 주소를 가리키는 노드 구조를 가지고 있다.

연관 컨테이너의 경우 작으면 왼쪽을 가리키고 크면 오른쪽을 가리키는 등 어떤 기준에 따라 정렬된다. 따라서 순서가 없고 기준에 따라 다음 요소의 메모리 주소를 가리키는 노드 구조이다.

 

저장 방식에 따라 분류해 보면

- 배열(연속된 메모리) 기반의 컨테이너: 데이터 여러 개가 하나의 메모리 단위에 저장된다. (vector, deque)

- 노드 기반의 컨테이너: 데이터 하나가 하나의 메모리 단위에 저장된다. (list, set, multiset, map, multimap)

---

반복자(Iterator)

반복자는 컨테이너에 저장된 요소를 반복적으로 순회하여 요소를 가리키고, 그 요소에 접근해서 다음 요소를 가리키게 하는 기능을 갖고 있는 포인터와 비슷한 개념의 객체이다. 즉,  컨테이너의 구조나 요소의 타입과 상관없이 독립적으로 여러 컨테이너와 결합해서 데이터를 순회하는 과정을 수행할 수 있다.

 

반복자는 다음과 같은 특징을 가진다.

• 컨테이너 내부의 객체에 접근할 수 있어야 한다. 따라서 *(참조 연산자)가 정의되어야 한다. 
• 반복자는 다음 객체로 이동하고 컨테이너의 모든 객체를 순회할 수 있어야 한다. 따라서 ++같은 증가 연산자가 정의되어야 한다.
• 반복자의 위치를 판단할 수 있도록 =, ==, != 와 같은 반복자간의 대입, 비교 연산이 정의되어야 한다.

 

반복자의 종류

종류	설명
입력 반복자 (input iterator)	현재 위치의 객체의 값을 읽어 오는 반복자. 증가 연산자(++)를 사용하여 순방향으로만 이동할 수 있다.
출력 반복자 (output iterator)	현재 위치의 객체의 값을 변경할 수 있는 반복자. 증가 연산자(++)를 사용하여 순방향으로만 이동할 수 있다.
순방향 반복자 (forward iterator)	입력, 출력 반복자의 기능을 모두 가진 반복자. 순방향으로 이동(++) 가능하며 재할당이 가능하다.
양방향 반복자 (bidirectional iterator)	순방향 반복자 기능 + 역방향으로 이동(--) 이 가능한 반복자.
임의 접근 반복자 (random access iterator)	양방향 반복자 기능과 [ ]을 사용해 임의의 요소에 접근 가능한 반복자. 모든 컨테이너는 양방향 반복자와 임의 접근 반복자를 지원한다.

---

알고리즘

STL의 목적이 일반적인 알고리즘에 대한 효율적인 구현을 제공하는 것이다. 따라서 알고리즘에서는 컨테이너를 알고리즘을 통해 동작시키는 데에 필요한 많은 함수를 제공한다. 따라서 컨테이너는 STL 알고리즘 함수와 함께 사용되며 반복자를 통해 컨테이너에 적용시킨다.

 

알고리즘의 종류

알고리즘	설명	대표 함수
읽기 알고리즘	컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 특정 데이터를 읽기만 하는 알고리즘. algorithm 헤더에 존재	find(), for_each()
변경 알고리즘	컨테이너를 변경하지 않으며, 컨테이너의 지정된 범위에서 요소의 값만을 변경할 수 있는 알고리즘. algorithm 헤더에 존재	copy(), swap(), transform()
정렬 알고리즘	컨테이너의 지정된 범위의 요소들이 정렬되도록 컨테이너를 변경하는 알고리즘. algorithm 헤더에 존재	sort(), stable_sort(), binary_search()
수치 알고리즘	STL에 직접 속하지 않고 C++ 라이브러리로 분류된느 알고리즘. 수치적 해석을 위해 사용. numeric 헤더에 존재	accumulate()