STL(Standard Template Library)
C++이 가지는 프로그래밍 언어로서의 특징 중 하나로 일반화 프로그래밍(generic programming)을 들 수 있습니다.
이러한 일반화 프로그래밍은 데이터를 중시하는 객체 지향 프로그래밍과는 달리 프로그램의 알고리즘에 그 중점을 둡니다.
C++ 표준 템플릿 라이브러리인 STL도 이러한 일반화 프로그래밍 패러다임의 한 축을 담당하고 있습니다.
STL은 알고리즘을 일반화한 표현을 제공하여, 데이터의 추상화와 코드를 재활용할 수 있게 합니다.
STL은 1994년 휴렛팩커드연구소의 알렉스 스테파노프(Alex Sepanov)와 멩 리(Meng Lee)가 처음으로 그 구현을 발표합니다.
그 후 STL은 ISO/ANSI C++ 표준 위원회에 의해 C++ 표준 템플릿 라이브러리로 포함되게 됩니다.
STL의 구성 요소
C++ 표준 템플릿 라이브러리인 STL은 다음과 같은 구성 요소로 이루어진 템플릿을 제공합니다.
1. 반복자(iterator)
2. 컨테이너(container)
3. 알고리즘(algorithm)
컨테이너(container)
STL에서 컨테이너(container)는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있습니다.
컨테이너는 클래스 템플릿으로, 컨테이너 변수를 선언할 때 컨테이너에 포함할 요소의 타입을 명시할 수 있습니다.
반복자(iterator)
반복자(iterator)란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여, 각각의 요소에 대한 접근을 제공하는 객체입니다.
즉, 컨테이너의 구조나 요소의 타입과는 상관없이 컨테이너에 저장된 데이터를 순회하는 과정을 일반화한 표현입니다.
템플릿이 타입과 상관없이 알고리즘을 표현할 수 있게 해준다면, 반복자는 컨테이너와 상관없이 알고리즘을 표현할 수 있게 해주는 것입니다.
반복자가 가져야 할 요구 사항과 정의되어야 할 연산자는 다음과 같습니다.
1. 가리키는 요소의 값에 접근할 수 있어야 합니다. 따라서 참조 연산자(*)가 정의되어야 합니다.
2. 반복자 사이의 대입 연산, 비교 연산이 가능해야 합니다. 따라서 대입, 관계 연산자가 정의되어야 합니다.
3. 가리키는 요소의 주변 요소로 이동할 수 있어야 합니다. 따라서 증가 연산자(++)가 정의되어야 합니다.
위와 같은 요구 사항을 모두 갖춰야만 STL 알고리즘에서 반복자로 사용될 수 있습니다.
반복자는 포인터를 일반화한 것으로, 포인터는 반복자가 가져야 할 모든 요구 사항을 만족합니다.
반복자의 종류
STL은 제공하는 기능에 따라 반복자를 다음과 같이 다섯 가지로 분류하고 있습니다.
1. 입력 반복자(input iterator)
2. 출력 반복자(output iterator)
3. 순방향 반복자(forward iterator)
4. 양방향 반복자(bidirectional iterator)
5. 임의 접근 반복자(random access iterator)
입력 반복자(input iterator)
입력 반복자(input iterator)는 가장 단순한 형태의 반복자로, 컨테이너로부터 값을 읽는 데 사용됩니다.
입력 반복자를 사용하면 컨테이너로부터 값을 읽을 수는 있지만, 프로그램이 그 값을 변경할 수는 없습니다.
따라서 이 반복자는 읽기 전용 알고리즘에 사용할 수 있습니다.
입력 반복자는 증가 연산자(++)를 사용하여 순방향으로만 이동할 수 있습니다.
또한, 참조 연산자(*)를 사용하여 반복해서 요소를 참조할 수 있습니다.
다음 예제는 순차 검색을 통해 컨테이너에 포함된 특정 값을 찾아내는 Find() 함수의 원형을 보여줍니다.
예제
template<class InputIterator, class T>
InputIterator Find(InputIterator first, InputIterator last, const T& value);
출력 반복자(output iterator)
출력 반복자(output iterator)는 입력 반복자와는 반대로 컨테이너의 값을 변경하는 데 사용됩니다.
출력 반복자를 사용하면 컨테이너의 값을 변경할 수는 있지만, 프로그램에서 값을 읽을 수는 없습니다.
따라서 이 반복자는 쓰기 전용 알고리즘에 사용할 수 있습니다.
출력 반복자는 증가 연산자(++)를 사용하여 순방향으로만 이동할 수 있습니다.
또한, 참조 연산자(*)를 사용하여 단 한 번만 요소에 값을 쓸 수 있습니다.
다음 예제는 한 컨테이너에서 다른 컨테이너로 값을 복사하는 Copy() 함수의 원형을 보여줍니다.
예제
template<class InputIterator, class OutputIterator>
OutputIterator Copy(InputIterator first, InputIterator last, OutputIterator result);
입력 반복자와 출력 반복자는 입출력 스트림에만 적용됩니다.
순방향 반복자(forward iterator)
순방향 반복자(forward iterator)는 입출력이 모두 가능한 반복자입니다.
따라서 이 반복자는 다중 패스 알고리즘에 사용할 수 있습니다.
순방향 반복자는 증가 연산자(++)를 사용하여 순방향으로만 이동할 수 있습니다.
또한, 참조 연산자(*)를 사용하여 몇 번이고 반복해서 같은 요소를 참조하거나, 그 값을 변경할 수 있습니다.
즉 순방향 반복자는 입력 반복자와 출력 반복자의 기능을 모두 포함하고 있습니다.
다음 예제는 특정 값을 찾아 다른 값으로 변경하는 Replace() 함수의 원형을 보여줍니다.
예제
template<class ForwardIterator, class T>
void Replace(ForwardIterator first, ForwardIterator last, const T& target, const T& replacement);
양방향 반복자(bidirectional iterator)
양방향 반복자(bidirectional iterator)는 입출력이 모두 가능한 반복자입니다.
양방향 반복자는 증가 연산자(++)를 사용하면 순방향으로, 감소 연산자(--)를 사용하면 역방향으로도 이동할 수 있습니다.
또한, 참조 연산자(*)를 사용하여 몇 번이고 반복해서 같은 요소를 참조하거나, 그 값을 변경할 수 있습니다.
즉 양방향 반복자는 순방향 반복자의 기능을 모두 포함하고 있습니다.
다음 예제는 특정 컨테이너의 모든 값을 거꾸로 새로운 컨테이너에 옮기는 Reverse() 함수의 원형을 보여줍니다.
예제
template<class BidirectionalIterator, class OutputIterator>
OutputIterator Reverse(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);
임의 접근 반복자(random access iterator)
임의 접근 반복자(random access iterator)는 최상위 레벨의 반복자로서 가장 많은 기능을 제공합니다.
임의 접근 반복자는 양방향 반복자의 모든 기능을 포함하고 있으며, 첨자 연산자([])를 통해 임의의 요소에 접근할 수 있습니다.
또한, 증감 연산자를 통해 양방향으로 이동할 수 있으며, 요소의 순서를 결정하기 위해 관계 연산자를 사용할 수 있습니다.
즉 임의 접근 반복자는 양방향 반복자의 모든 기능과 함께 기존의 일반 포인터가 하는 거의 모든 일을 할 수 있습니다.
다음 예제는 특정 컨테이너의 모든 값을 정렬시키는 Sort() 함수의 원형을 보여줍니다.
예제
template<class RandomAccessIterator>
void Sort(RandomAccessIterator first, RandomAccessIterator last);
반복자 계층
STL의 반복자(iterator)는 계층적으로 분류됩니다.
예를 들어, 순방향 반복자는 입력 반복자와 출력 반복자의 모든 기능을 포함하고 거기에 자신만의 기능을 추가합니다.
이렇게 다양한 반복자를 사용하는 이유는 알고리즘의 적용 조건을 제한하기 위해서입니다.
즉, 양방향 반복자는 임의 접근 반복자에 기초하는 알고리즘은 사용할 수 없지만, 자신보다 하위 계층의 반복자에 기초하는 알고리즘은 사용할 수 있는 것입니다.
다음 표는 STL 주요 반복자의 기능을 계층 순으로 정리한 것입니다.
|
반복자의 기능 |
입력 |
출력 |
순방향 |
양방향 |
임의 접근 |
|
접근(->) |
○ |
X |
○ |
○ |
○ |
|
읽기(*) |
○ |
X |
○ |
○ |
○ |
|
쓰기(*) |
X |
○ |
○ |
○ |
○ |
|
증가 연산자(++) |
○ |
○ |
○ |
○ |
○ |
|
감소 연산자(--) |
X |
X |
X |
○ |
○ |
|
첨자 연산자([]) |
X |
X |
X |
X |
○ |
|
산술 연산자(+, -) |
X |
X |
X |
X |
○ |
|
산술 대입 연산자(+=, -=) |
X |
X |
X |
X |
○ |
|
관계 연산자(<, <=, >, >=) |
X |
X |
X |
X |
○ |
iterator 헤더 파일
STL은 iterator 헤더 파일을 통해 미리 정의된 몇 가지 반복자를 제공합니다.
이 헤더 파일은 미리 정의된 반복자뿐만 아니라 스트림 반복자, 반복자의 원형 그리고 여러 지원 템플릿을 포함하고 있습니다.
스트림 반복자(stream iterator)
스트림 반복자(stream iterator)는 반복자 연산을 통해 알고리즘이 입출력 스트림에 보다 쉽게 접근할 수 있도록 해줍니다.
이때 STL은 입력과 출력 스트림을 각각 입력과 출력 반복자로 변환하는 방식으로 제공합니다.
입력 스트림 반복자는 istream_iterator, 출력 스트림 반복자는 ostream_iterator 클래스 템플릿에서 제공합니다.
istream_iterator 클래스 템플릿은 다음과 같이 정의됩니다.
문법
template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
class istream_iterator : public iterator<input_iterator_tag, T, Distance, const T*, const T&> { ... }
ostream_iterator 클래스 템플릿은 다음과 같이 정의됩니다.
문법
template <class T, class charT = char, class traits = char_traits<charT> >
class ostream_iterator : public iterator<output_iterator_tag, void, void, void, void> { ... }
istream_iterator와 ostream_iterator 클래스 템플릿은 첫 번째를 제외한 인수에 모두 디폴트 인수를 명시하고 있습니다.
따라서 사용자는 입출력하고자 하는 데이터의 타입만을 인수로 전달하여 간편하게 사용할 수 있습니다.
다음 예제는 copy() 함수를 사용하여 vertor 객체의 첫 요소부터 마지막 요소까지를 모두 출력하는 예제입니다.
예제
vector<int> vc = {1, 2, 3, 4, 5};
copy(vc.begin(), vc.end(), ostream_iterator<int>(cout));
cout << endl;
copy(vc.begin(), vc.end(), ostream_iterator<int>(cout, " "));
위의 예제에서는 C++ 표준 출력 객체인 cout 객체를 ostream_iterator 클래스 템플릿의 인수로 전달하여 모니터에 대한 출력을 수행합니다.
삽입 반복자(insert iterator)
알고리즘에서 출력 반복자를 사용하면 반복자가 가리키는 요소의 값을 덮어쓰게 됩니다.
하지만 삽입 반복자(insert iterator)는 값을 덮어쓰지 않고, 그 요소의 위치에 새로운 값을 삽입할 수 있게 해줍니다.
즉, 삽입 반복자는 반복자의 복사 연산을 삽입 연산으로 변환해 주는 역할을 합니다.
STL에서 제공하는 삽입 반복자는 다음과 같습니다.
1. insert_iterator
2. back_insert_iterator
3. front_insert_iterator
|
삽입 반복자 |
설명 |
사용 멤버 함수 |
사용가능 컨테이너 |
|
insert_iterator |
해당 컨테이너의 특정 위치에 삽입함. |
insert() |
모든 컨테이너 |
|
back_insert_iterator |
해당 컨테이너의 뒤쪽에 삽입함. |
push_back() |
시퀀스 컨테이너 (vector, list, deque) |
|
front_insert_iterator |
해당 컨테이너의 앞쪽에 삽입함. |
push_front() |
list, deque |
다음 예제는 push_back() 함수와 push_front() 함수의 삽입 반복자를 사용하여 리스트에 요소를 삽입하는 예제입니다.
예제
list<int> ls = {10};
ls.push_back(20); // back_insert_iterator를 사용함.
ls.push_front(30); // front_insert_iterator를 사용함.
copy(ls.begin(), ls.end(), ostream_iterator<int>(cout, " "));
역방향 반복자(reverse iterator)
역방향 반복자(reverse iterator)는 순방향 반복자와는 반대 방향으로 동작하는 반복자입니다.
즉, 역방향 반복자의 증가 연산자(++)는 순방향 반복자의 역방향으로 이동하게 됩니다.
rbegin()과 rend() 멤버 함수를 사용하면 자동으로 reverse_iterator를 반환합니다.
다음 예제는 rbegin()과 rend() 함수의 역방향 반복자를 사용하여 리스트의 요소를 역순으로 출력하는 예제입니다.
예제
list<int> ls = {10, 20, 30};
copy(ls.rbegin(), ls.rend(), ostream_iterator<int>(cout, " "));
상수 반복자(constant iterator)
앞서 살펴본 것처럼 반복자를 동작 방식으로 분류하는 것 외에도 반복자가 가리키는 값의 변경이 가능한가로 분류할 수도 있습니다.
이때 반복자가 가리키는 값의 변경이 불가능한 반복자를 상수 반복자(constant iterator)라고 합니다.
단, 상수 반복자란 반복자가 가리키는 요소를 상수화시킨 것이지 반복자 그 자체를 상수화시킨 것은 아닙니다.
따라서 양방향 상수 반복자라면 앞뒤로 이동하며 다른 요소를 가리키는 것이 가능합니다.
이러한 상수 반복자의 타입은 const_iterator 타입으로 정의됩니다.
다음 예제는 반복자를 사용하여 리스트의 첫 번째 요소의 값을 변경하는 예제입니다.
예제
list<int> ls = {10, 20, 30};
list<int>::iterator iter;
list<int>::const_iterator citer;
iter = ls.begin();
*iter = 100;
citer = ls.end();
// *citer = 300; // 상수 반복자이므로 값의 변경은 불가능함.
for(citer = ls.begin(); citer != ls.end(); citer++)
{
cout << *citer << " ";
}
위의 예제에서 상수 반복자로 선언된 citer는 가리키는 값의 변경이 불가능하며, 값을 읽는 작업에만 사용할 수 있습니다.
'C++' 카테고리의 다른 글
| C++ STL알고리즘 (0) | 2020.07.05 |
|---|---|
| C++ STL컨테이너 (0) | 2020.07.05 |
| C++ 템플릿 (0) | 2020.07.05 |
| C++ OOP다형성 (0) | 2020.07.05 |
| C++ OOP상속성 (0) | 2020.07.05 |
댓글