[C++ STL] 2. STL 구성요소 간략정리

공부 내용을 정리하는 목적 이므로 참고용으로만 읽어 주시기 바랍니다. 틀린 부분에 대한 지적은 감사합니다.

1. 컨테이너(container)란?

STL의 구성요소로 컨테이너, 반복자, 알고리즘이 존재한다. 그중 하나인 컨테이너에 대해 먼저 정리하자.

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

 

2. 컨테이너 종류

컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라 여러 가지 형태로 나뉠 수 있다.

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

시퀀스 컨테이너의 경우 요소가 언제 삽입되는지에 따라 배열안에서 요소의 순서가 결정된다. 즉, 연속되게 저장하는 배열같은 구조이다. 하지만 특이하게 list는 다음 요소의 주소를 가르키는 노드구조를 가지고 있다.
연관 컨테이너의 경우 작으면 왼쪽을 가르키고 크면 오른쪽을 가르키는등 어떤 기준에 따라 정렬된다. 따라서 순서가 없고 기준에 따라 다음 요소의 메모리 주소를 가르키는 노드구조이다.

 

따라서 저장 방식에 따라 분류해 보면
-배열(연속된 메모리)기반의 컨테이너 : 데이터 여러개가 하나의 메모리 단위에 저장된다. (vector, deque)
-노드기반의 컨테이너 : 데이터 하나를 하나의 메모리 단위에 저장된다. (list, set, multiset, map, multimap)

 

3. 반복자 란?

반복자(Iterator)는 컨테이너에 저장된 요소를 반복적으로 순회하여 요소를 가리키고, 그 요소에 접근해서 다음 요소를 가리키게 하는 기능을 갖고 있는 포인터와 비슷한 개념의 객체이다. 

즉, 컨테이너의 구조나 요소의 타입과 상관없이 독립적으로 여러 컨테이너와 결합해서 데이터를 순회하는 과정을 수행할 수 있다.

 

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

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

반복자의 종류는 다음과 같다.

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

 

4. 알고리즘 이란?

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

 

알고리즘의 종류는 다음과 같다.

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