STL는 일반화 프로그래밍(generic programming)의 한 예입니다.
객체 지향 프로그래밍은 프로그래밍의 데이터 측면을 중시하지만, 일반화 프로그래밍은 알고리즘에 중점을 둡니다.
두 프로그래밍 패러다임에 공통적인 것은, 데이터의 추상화와 재활용이 가능한 코드의 작성입니다.
추구하는 철학은 완전히 다른데, 일반화 프로그래밍의 목적은 데이터형과 무관한 코드를 작성하는 것입니다.
템플릿은 일반화 프로그램을 작성하는 C++의 도구입니다.
이터레이터가 필요한 이유
이터레이터를 이해하는 것이 STL을 이해하는 열쇠입니다.
템플릿이 알고리즘을 저장할 데이터형과 무관하게 만드는 것처럼, 이터레이터는 알고리즘을 사용할 컨테이너형과 무관하게 만듭니다.
이터레이터는 STL의 일반화 접근에 필수 구성 요소입니다.
예시
int형 배열에서 특정한 값을 찾는 함수를 만들어 봅시다.
int* find(int Array[], int N,int Length) {
for (int i = 0; i < Length; i++) {
if (Array[i] == N) {
return &Array[i];
}
}
return nullptr;
}이 함수는 배열에서 값을 찾으면 값이 발견된 주소를 리턴합니다. 찾지 못하면 널포인터를 리턴합니다.
만약 템플릿을 사용하면 ==연산자를 지원하는 모든 데이터형의 배열에까지 이것을 일반화할 수 있습니다.
그러나 이 알고리즘은 여전히 배열이라는 특정한 데이터 구조에 매여 있습니다.
이 경우에 일반화 프로그래밍의 목적은 배열, 링크드 리스트, 또는 그 밖의 다른 컨테이너형 데이터 구조에 두루 사용할 수 있는 하나의 find함수를 확보하는 것입니다.
즉 함수는 컨테이너에 저장되는 데이터형에 얾매이지 않을 뿐만 아니라, 컨테이너의 구조 자체에도 얽매이지 않아야 합니다.
필요한 것은 컨테이너에 저장된 값들을 훑고 지나가는 과정의 일반화 표현입니다.
이터레이터가 바로 그 일반화 표현입니다.
find함수를 구현하기 위해 이터레이터가 가져야 하는 최소한의 특성
- 이터레이터가 참조하는 값에 접근하기 위해 내용 참조(dereference)를 할 수 있어야 한다.(*ptr)
- 한 이터레이터를 다른 이터레이터에 대입할 수 있어야 한다. (ptr1 = ptr2)
- 한 이터레이터가 다른 이터레이터와 같은 것인지 비교할 수 있어야 한다.( ptr1 == ptr2 또는 ptr1 != ptr2)
- 이터레이터가 컨테이너에 들어 있는 모든 원소들을 훑고 지나갈 수 있어야 한다.(ptr1++ 또는 ++ptr1)
STL의 컨테이너 클래스들은 그 클래스에 맞는 이터레이터형을 정의합니다.
어떤 컨테이너 클래스는 포인터가 이터레이터가 될 수 있고, 객체가 이터레이터가 될 수 있습니다.
그리고 *나 ++같은 필요한 연산을 제공합니다.
그다음에, 각 컨테이너 클래스는 컨테이너에 있는 마지막 값 바로 다음으로 증가되었을 때 이터레이터에 대입되는 값 past-the-end 마커를 가집니다.
각 컨테이너 클래스는 컨테이너에 들어 있는 첫 번째 원소를 지시하는 이터레이터와
past-the-end 위치를 지시하는 이터레이터를 각각 리턴하는 begin 멤버 함수와 end 멤버 함수를 가집니다.
그리고 각 컨테이너 클래스는 첫 번째 원소부터 past-the-end까지 훑고 지나가는 하나의 이터레이터를 선택하여 컨테이너에 있는 모든 원소들을 빠짐없이 방문하는 ++연산을 가집니다.
#include <iostream>
#include <list>
int main(void) {
std::list<int> List = std::list<int>();
List.push_back(1);
List.push_back(2);
List.push_back(3);
for (std::list<int>::iterator it = List.begin(); it != List.end(); ++it) {
std::cout << *it << std::endl;
}
}각 클래스를 위한 적절한 이터레이터를 정의하고 클래스들을 일관된 방식으로 설계하면, STL을 사용하여 내부적인 표현이 전혀 다른 여러 컨테이너들에 대해 동일한 코드를 작성할 수 있습니다.
begin 멤버 함수로 인해 자동으로 타입 추론이 가능하기 때문에 명시적으로 자료형을 쓰는 대신 auto를 사용해도 됩니다.
또한 C++11의 range에 기초한 루프를 사용해도 됩니다.
#include <iostream>
#include <list>
int main(void) {
std::list<int> List = std::list<int>();
List.push_back(1);
List.push_back(2);
List.push_back(3);
for (auto item : List) {
std::cout << item << std::endl;
}
}
이터레이터의 종류
알고리즘이 다르면 이터레이터들에 대한 요구 사항이 달라집니다.
첫번째 예
검색 알고리즘은 이터레이터가 컨테이너 속의 전체를 훑고 지나갈 수 있도록 ++연산자를 정의할 것을 요구합니다.
이 경우에는 데이터에 대한 쓰기 접근은 금지하고 읽기 접근만 허용해야 합니다.
두 번째 예
정렬 알고리즘은 서로 인접해 있지 않은 두 원소를 교환할 수 있도록 임의 접근을 허용해야 합니다.
+연산자를 정의하여 임의 접근을 허용하고, 데이터 읽기/쓰기 접근을 모두 허용해야 합니다.
STL은 다섯 가지 이터레이터를 정의하고, 알고리즘을 필요한 이터레이터의 종류로 서술합니다.
-
입력 이터레이터(input iterator)
-
출력 이터레이터(output iterator)
-
전방 이터레이터(forward iterator)
-
전후방 이터레이터(bidirectional iterator)
-
임의 접근 이터레이터(random access iterator)
다섯 가지 이터레이터의 공통점은
-
내용 참조(dereference)를 할 수 있다. (* 연산자)
-
서로 같은지, 다른지 비교할 수 있다. (!=,== 연산자)
입력 이터레이터
"입력"이라는 용어는 프로그램의 관점에서 사용하는 말입니다. (컨테이너에서 프로그램으로 들어가는 정보를 입력이라고 생각함)
따라서 입력 이터레이터는, 컨테이너로부터 값을 읽기 위해 프로그램이 사용할 수 있다.
하지만 해당 이터레이터는 읽기만 가능하고 쓰기는 불가능합니다.
따라서 입력 이터레이터를 필요로 하는 알고리즘들은, 컨테이너에 저장된 값을 변경하지 않는 알고리즘들입니다.
입력 이터레이터를 사용하여 다시 한번 그 컨테이너를 훑을 때 동일한 순서로 값들을 훑고 지나간다는 보장은 없습니다.
또한 입력 이터레이터가 이미 증가된 후에 증가되기 전 값을 여전히 내용 참조를 할 수 있다는 보장은 없습니다.
즉 입력 이터레이터에 기초를 둔 알고리즘은 일회성 알고리즘입니다.
즉 입력 이터레이터는 일방향 이터레이터고 증가시킬 수는 있지만 되돌릴 수는 없습니다.
출력 이터레이터
STL 사용에서 "출력"이라는 용어는 프로그램에서 컨테이너로 정보를 보내기 위해 이터레이터가 사용된다는 것을 의미합니다.
출력 이터레이터는 입력 이터레이터와 비슷하지만 출력 이터레이터는 내용 참조를 통해 프로그램이 컨테이너에 있는 값을 읽는 것이 아니라 변경하는 것을 허용합니다.
즉 읽지는 못하지만 쓰기는 가능합니다.
출력 이터레이터는 일회성 쓰기 전용 알고리즘에 사용할 수 있습니다.
전방 이터레이터
입력, 출력 이터레이터와 마찬가지로 전방 이터레이터도 컨테이너 속을 훑고 지나가기 위해 ++ 연산자만 사용합니다.
그래서 전방 이터레이터는 컨테이너 속을 한 번에 한 원소씩 전방으로만 진행할 수 있습니다.
입력, 출력 이터레이터와 달리 전방 이터레이터는 그것을 사용할 때마다 연속된 값들을 반드시 같은 순서로 훑고 지나갑니다.
전방 이터레이터는 읽기/쓰기 둘 다 가능하고 읽기만 할 때에도 전방 이터레이터를 사용할 수 있습니다.
전후방 이터레이터
전후방 이터레이터는 전방 이터레이터가 가지고 있는 모든 기능에, 두 감소 연산자(접두어, 접미어 버전)에 대한 기능을 추가한 것입니다.
즉 reverse함수로 예시를 들 수 있습니다.
임의 접근 이터레이터
임의 접근 이터레이터는 전후방 이터레이터가 가지고 있는 모든 기능에, 임의 접근을 지원하는 (포인터 덧셈과 같은) 연산과, 원소들의 순서를 매기는 데 사용할 관계 연산자들을 추가합니다.
임의 접근이 필요한 표준 정렬이나, 이진 탐색 같은 알고리즘은 임의 접근이 가능해야 하므로 이런 알고리즘에 쓰입니다.
임의 접근 이터레이터 연산표
a와 b는 이터레이터의 값
n은 정수
|
식 |
설명 |
|
a+n |
a가 지시하는 원소로부터 n번째 뒤에 원소를 지시함 |
|
n + a |
a + n과 같다 |
|
a - n |
a가 지시하는 원소로부터 n번째 앞의 원소를 지시함 |
|
r += n |
r = r+n과 같다 |
|
r -= n |
r = r-n과 같다 |
|
a[n] |
*(a+n)과 같다 |
|
b - a |
b = a + n과 같은 경우에 n의 값 |
|
a < b |
b = a > 0이면 true |
|
a > b |
b < a 이면 true |
|
a >= b |
!(a < b)면 true |
|
a <= b |
!(a > b)면 true |
이터레이터 정리표
아래 다섯 가지의 이터레이터들의 특징을 표로 정리한 것들입니다.
|
이터레이터 기능 |
입력 |
출력 |
전방 |
전후방 |
임의 접근 |
|
내용 참조하여 읽기 |
O |
X |
O |
O |
O |
|
내용 참조하여 쓰기 |
X |
O |
O |
O |
O |
|
고정 반복 가능한 순서 |
X |
X |
O |
O |
O |
|
++i i++ |
O |
O |
O |
O |
O |
|
--i i-- |
X |
X |
X |
O |
O |
|
i[n] |
X |
X |
X |
X |
O |
|
i+n |
X |
X |
X |
X |
O |
|
i-n |
X |
X |
X |
X |
O |
|
i+=n |
X |
X |
X |
X |
O |
|
i-=n |
X |
X |
X |
X |
O |
특별한 종류의 이터레이터로 서술된 알고리즘은, 그 종류의 이터레이터나 필요한 기능을 가진 다른 이터레이터를 사용할 수 있습니다.
예를 들어 임의 접근 이터레이터를 가진 컨테이너는 reverse(전후방 이터레이터) 함수를 사용할 수 있습니다.
임의 접근 이터레이터는 전후방 이터레이터의 모든 기능을 사용할 수 있습니다.
그러니까 기능만 충족한다면, 어떠한 이터레이터를 써도 된다는 것입니다.
여러가지 이터레이터가 존재하는 이유
요구 사항이 가장 적은 이터레이터를 사용하여 알고리즘을 작성함으로써, 가장 넓은 범위의 컨테이너들에 사용할 수 있도록 하자는 것이 그 목적입니다.
따라서 계층이 낮은 입력 이터레이터를 사용함으로써 find() 함수는, 읽을 수 있는 값들이 들어 있는 어떠한 컨테이너에도 사용할 수 있습니다.
그러나 임의 접근 이터레이터를 요구하는 sort() 함수는, 그러한 종류의 이터레이터를 지원하는 컨테이너에만 사용이 가능합니다.
다양한 종류의 이터레이터들은 정의된 데이터형이 아니고 개념적 특성화입니다.
각 컨테이너 클래스는 iterator라는 클래스 사용 범위의 typedef 이름을 정의합니다.
그래서 vector<int> 클래스는 vector<int>::iterator형의 이터레이터를 가집니다.
개념, 개량, 모델
이터레이터는 데이터형이 아니라 요구 사항들의 집합이기 때문에 이터레이터의 특성을 갖는 클래스를 설계할 수 있지만, 컴파일러가 그 클래스만 사용하도록 제한할 수 없습니다.
사용자가 설계한 이터레이터 클래스를 통해 그 요구 사항들을 충족시킬 수 있습니다.
그러나 단순 포인터를 가지고도 그 요구 사항들을 충족시킬 수 있습니다.
STL을 설명하는 문건들은 그러한 요구 사항들의 집합을 개념(concept)이라는 단어로 표현하고 있습니다.
따라서 입력 이터레이터 개념, 전방 이터레이터 개념 등으로 표현합니다.
설계하려는 컨테이너 클래스가 이터레이터가 필요하면, 표준 이터레이터 템플릿들을 포함시킬 수 있습니다.
개념은 상속과 비슷한 관계를 가질 수 있는데, 예를 들어 전후방 이터레이터는 전방 이터레이터의 기능을 상속합니다.
그러나 이터레이터에는 C++의 상속 메커니즘을 적용할 수 없습니다.
(전방 이터레이터는 클래스, 전후방 이터레이터는 단순 포인터로 구현한다면 전후방 이터레이터는 내장 데이터형이기 때문에 클래스로부터 파생시킬 수 없지만 '개념'적으로 기능을 상속한다.)
어떤 STL 문건에서는 개념적인 상속을 개량(refinement)이라는 단어로 표현합니다.
따라서 전후방 이터레이터는 전방 이터레이터 개념의 '개량'입니다.
어떤 개념의 특별한 한 구현을 모델(model)이라고 하는데 int를 지시하는 단순 포인터는 임의 접근 이터레이터 개념의 한 모델의 예시로 들 수 있습니다.
이터레이터와 포인터
이터레이터는 포인터를 일반화한 것이고, 포인터는 이터레이터의 모든 요구 사항을 충족합니다.
이터레이터는 STL 알고리즘을 위한 인터페이스를 구성합니다.
따라서 STL 알고리즘은 포인터에 기초를 두고 있는 STL이 아닌 컨테이너들에 포인터를 적용할 수 있습니다.
#include <iostream>
#include <algorithm>
int main(void) {
int Array[5] = { 5,3,2,1,0 };
std::sort(Array, Array + 5);
}C++는 포인터들을 위한 "마지막 원소 바로 다음"이라는 개념을 배열에도 지원합니다.
이것이 STL 알고리즘을 일반 배열에 적용하는 것을 가능하게 만듭니다.
포인터가 이터레이터이고, 알고리즘들이 이터레이터에 기초하고 있기 때문에 알고리즘을 일반 배열에 적용할 수 있는 겁니다.
댓글