반복자(iterator)_2

7. 삽입 반복자(insert iterator)

삽입 반복자는 보통의 경우 "덮어쓰기 모드(overwrite  mode)"로 동작하는 제네릭 알고리즘을 "삽입 모드(insert mode)"로 바꿔준다. 다시 말해서, 삽입 반복자의 경우, *i = ... 을 사용하면 i 자리에 위치한 객체를 덮어쓰는 것이 아니라 삽입을 하게 되며, 이는 컨테이너의 삽입 멤버 함수를 이용하여 이루어진다. 삽입 반복자는 길이를 모르는 데이터 시퀀스를 입력 스트림이나 컨테이너에서 다른 컨테이너로 옮길 때 매우 유용하다. STL은 다음 세 가지 종류의 삽입 반복자를 제공한다.

각각의 삽입 반복자는 Container 타입을 템플릿 인자로 사용한다.

- back_insert_iterator<Container>   : Container의 push_back 멤버 함수를 사용 - front_insert_iterator<Container>   : Container의 push_front 멤버 함수를 사용 - insert_iterator<Container>   : Container의 insert 멤버 함수를 사용

삽입 연산을 수행한 뒤에는 컨테이너에 할당된 공간이 자동으로 더 늘어나게 한다. 반면에, 대입 연산에서는 대입이 필요한 공간을 미리 확보하고 있어야 한다.

 

STL은 삽입 반복자를 쉽게 사용할 수 있도록, 제네릭 함수 템플릿인 back_inserter를 정의해 두었다.

template<typename Container> inline back_insert_iterator<Container> // 이것은 리턴 타입 back_inserter(Container& x) {     return back_insert_iterator<Container>(x); }

insert_iterator와 insert 함수는 컨테이너의 insert 멤버 함수인 insert(iterator, value)를 사용한다. STL 컨테이너들은 모두 이 함수를 가지고 있기 때문에, insert는 (정렬 연관 컨테이너를 비롯한) 모든 컨테이너 타입과 함께 사용이 가능하다.

 

 

8. 입력, 출력 다시 보기 : 스트림 반복자

입력 반복자 부류와 출력 반복자 부류에 관해 좀 더 세부적으로 살펴보기로 하자. 입력  반복자 부류와 출력 반복자 부류를 STL에 포함시킨 가장 큰 이유는 I/O 스트림에 연결된 반복자를 얻으려면, istream_iterator 클래스(입력에 사용)와 ostream_iterator 클래스(출력에 사용)를 이용하면 된다. istream_iterator가 생성하는 반복자는 출력 반복자가 아니라 입력 반복자이다. 이는 istream_iterator 객체가 한쪽 방향으로만 데이터를 읽어나갈 수 있으며, 입력 스트림 반복자 객체를 사용하여 데이터를 출력할 수는 없다는 것을 의미한다.

 

istream_iterator<T> 타입이 제공하는 생성자 istream_iterator(istream&)는 주어진 입력 스트림(예를 들어, 다음 예제에서 보게 될 표준 입력 스트림 cin)으로부터 읽어들인 T 타입의 값들을 가리키는 적용할 반복자를 만들어 낸다.

 

생성자 istream_iterator<T>( )는 입력 스트림 반복자를 위한 끝 표시기(end marker)의 역할을 하는 입력 반복자를 만들어 낸다. 이 반복자는 입력 스트림 반복자가 스캐닝을 하다가 입력 스트림의 끝(end-of-stream)에 도달했을 때 반복자가 가지는 값이다.

 

 

9. STL 알고리즘이 준수해야 하는 반복자 부류에 관한 명세

이제는 STL 알고리즘의 인터페이스로부터, 주어진 알고리즘과 함께 사용할 수 있는 반복자를 알아내는 방법을 살펴보자.

STL 튜토리얼·레퍼런스 가이드 제2판 22장, "제네릭 알고리즘 레퍼런스 가이드"를 보면, merge의 인터페이스는 다음과 같이 되어 있다.

template<typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1,                              InputIterator2 first2, InputIterator2 last2,                              OutputIterator result);

 

STL 튜토리얼·레퍼런스 가이드 제2판 22장에서는 다음 두 가지 규칙을 따르고 있다.

- 템플릿 클래스 인자의 이름이 Iterator나 IteratorN(여기서 N은 정수)으로 끝나는 경우는 해당 템플릿 인자가 반드시 반복자 타입이어야 한다는 것을 의미한다. - 이름의 앞부분은 반복자가 어느 부류에 속한 것인지 알아볼 수 있도록 표기해야 한다.

이 두가지 규칙을 염두하고 위에 표시된 merge알고리즘의 인터페이스를 살펴보면, 이 인터페이스가 지니고 있는 의미를 알아낼 수 있을 것이다. 먼저 merge 알고리즘의 처음 두 개의 인자는 모두 동일한 타입의 입력 반복자이어야 한다. 그리고 세 번째와 네 번째 인자도 타입이 동일한 입력 반복자이어야 한다(하지만 처음 두 인자의 타입과는 다을 수 있다). 그리고 마지막 인자는 출력 반복자이어야 한다.

 

이번에는 find 알고리즘을 살펴보자. find 알고리즘은 다음과 같은 인터페이스를 가지고 있다.

template <typename InputIterator, typename T> InputIterator find(InputIterator first, InputIterator last, const T& value);

위 인터페이스에 따르면 find의 처음 두 개의 인자는 입력 반복자이어야 하고, 리턴 값은 입력 반복자 타입이어야 한다는 것을 알 수 있다. 이는 결과적으로 find가 출력 반복자를 제외한 모든 반복자 즉, 입력 반복자, 순방향 반복자, 양방향 반복자, 임의 접근 반복자와 함께 사용할 수 있다는 것을 의미한다.

 

이번에는 search 알고리즘의 인터페이스를 살펴보자. search는 함께 사용할 수 있는 반복자가 find보다 좀 더 제한적이라는 것을 알 수 있다. search 알고리즘은 주어진 시퀀스에서 원하는 서브 시퀀스를 검색해 내는 알고리즘이며, strstr과 같은 서브 스트링 매칭 알고리즘을 보다 일반화한 것이라고 보면 된다.

template<typename ForwardIterator1, typename ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,                                   ForwardIterator2 first2, ForwardIterator2 last2);

위 인터페이스에 따르자면, search 알고리즘은 인자들이 모두 순방향 반복자이어야 함을 알 수 있다. 그렇다면, 왜 search 알고리즘에서는 입력 반복자를 인자로 사용하지 않는 것일까? 이유는 간단하다. search 알고리즘은 멀티 패스 알고리즘이기 때문이다. 즉, 슼닝을 여러 번 한다는 것이다. search 알고리즘은 반복자들을 저장해 두었다가 다음에 스캔할때 저장해둔 반복자를 다시 사용한다. 따라서, 이 알고리즘은 istream_iterator와 함께 사용할 수 없다.

 

 

10. 제네릭 알고리즘 설계하기

앞에서 알고리즘의 인터페이스 명세를 통해 주어진 알고리즘과 함께 사용할 수 있는 반복자가 무엇인지 알아낼 수 있다는 것을 살펴보았다. 따라서, 이제는 알고리즘의 세부적인 구현에 관해서는 자세히 알 필요가 없지만, 반복자 부류에 관한 이해를 더욱 공고히하기 위해서는 알고리즘 내부를 직접 들여다 보고, 효율성의 유지와 최대한의 범용성 확보를 목표로 하는 STL이 이를 위해 알고리즘에서 채택한 결정 사항들을 살펴볼 필요가 있는 것이다. 이쯤에서 전에도 한 번 소개했던 STL의 제네릭 find 알고리즘의 정의를 다시 살펴보도록 하자.

template<typename InputIterator, typename T> InputIterator find(InputIterator first, InputIterator last, const T& value) {     while(first != last && *first != value)         ++first;     return first; }

find 알고리즘을 위와 같이 구현하면 모든 입력 반복자와 함께 사용할 수 있도록 되어 있으며, 그 이유는 다음과 같다.

- 인자로 넘겨받은 반복자에 적용되는 연산자들은 !=, *, ++이 전부이다. - * 연산자를 통해 얻어낸 객체에 대입 연산을 수행하지 않는다. - 단일 패스 알고리즘이다.

따라서, find 알고리즘을 최대한 제네릭하게 만들려면 위와 같이 구현해야 하며, 만약 다른 방식으로 구현한다면 find를 이처럼 제네릭한 알고리즘으로 되도록 만들 수 없다.

 

설계 측면에서 STL이 거둔 가장 큰 성과 중 하나는 find를 비롯한 여러 알고리즘들을 작성할 때, 데이터 접근에 관련된 요구 사항들을 최소화하여 코딩함으로써 보다 더 제네릭한 알고리즘을 만들 수 있도록 한 것이다.

 

 

11. 일부 알고리즘에서 더 강력한 반복자를 필요로 하는 이유

STL 알고리즘 중에는 입력, 출력, 순방향 반복자들이 제공하는 기능보다 더 많은 기능을 가진 양방향 반복자 부류나 임의 접근 반복자 부류를 인자로 사용해야 하는 알고리즘들이 있다. 이러한 알고리즘을 다른 종류의 반복자와 함께 사용하면 컴파일이 되지 않는다. 예를 들어, 다음 sort 알고리즘의 인터페이스를 살펴보자.

template<typename RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);

이 인터페이스 명세에 따르자면, sort 알고리즘은 두 개의 반복자를 필요로 하며, 이 두 개의 반복자 모두 임의 접근 반복자 부류이어야 한다는 것을 알수 있다. 따라서, 다음과 같은 코딩이 가능하다.

vector<int> vector1; // ... vector1에 값을 삽입하는 코드   sort(vector1.begin(), vector1.end());

 

sort 알고리즘을 아래와 같이 list에 적용하는 것은 불가능하다.

list<int> list1; // ... list1에 값을 삽입하는 코드 sort(list1.begin(), list1.end()); // 잘못되었음

list1.begin()과 list1.end()는 양방향 반복자이기 때문에, sort에서 사용되는 += 연산자라든지 기타 연산자들은 모두 다 제공하지는 못한다. 따라서, 이 코드는 컴파일이 되지 않는다.

 

list 반복자나 기타 다른 컨테이너 부류와 관련된 반복자들을 확장하여 +=, < 연산자들과 임의 접근 반복자들이 가지고 있는 다른 연산자들을 제공 할 수 있게 하면 좋을 것 같은데 왜 그렇게 하지 않는 것일까? 그렇게 하면 반복자에 적용할 수 있는 연산자들이 어떠한 것인지에 관해 크게 신경 쓰지 않아도 되고, 결과적으로 제네릭 알고리즘을 구현하는 작업이 간단해질 것 같은데 말이다. 이번에도 정답은 효율성 때문이다. list에서는 list1.begin() + n과 같은 표현식을 상수 시간내에 수행 할 수 없다. 그저 리스트 노드를 한 개씩 차례로 순회하는 방법 밖에 없으며, 이에 소요되는 시간은 n에 비례한다(즉, 선형 시간). 그렇기 때문에, 이러한 메쏘드를 작성하여 그것을 + 연산자로 사용한다면, 이는 임의 접근을 구현한 것이 아니다. 따라서, 이런식으로 구현한 sort 알고리즘은 리스트만의 특성을 이용하는 다른 정렬 알고리즘보다 훨씬 더 느린 알고리즘이 될 것이다.

 

 

12. 최적의 알고리즘 선택하기

알고리즘/컨테이너 호환성에 관해 명심하고 있어야 할 사항이 한 가지 있다. 즉, STL에서 분류해 놓은 다양한 반복자 부류를 통해, 알고리즘과 컨테이너간의 다양한 조합들 중에서 효율적인 조합은 권장되고, 비효율적인 조합은 생기지 않도록 해두었지만, 그렇다고 해서 비효율적인 조합이 발생하는 것을 완전히 막을 수는 없다. 즉, 주어진 제네릭 알고리즘을 컴파일 에러없이 특정 컨테이너에 적용할 수 있다고 해서 그것이 반드시 바람직한 조합이라고 말할 수는 없다는 것이다.

 

 

13. 상수 반복자 타입과 뮤터블 반복자 타입

순방향, 양방향, 임의 접근 반복자에 적용되는 또 하나의 분류 방법이 있다. 즉, 반복자를 뮤터블(mutable) 반복자와 상수(constant) 반복자로 나누는 것이다. 이것은 operator*의 결과 값이 레퍼런스인지 상수 레퍼런스인지에 따라 결정된다.

모든 STL 컨테이너 타입은 iterator 뿐만 아니라 const_iterator를 식별자로 제공하고 있다.

 

아래 표는 STL 컨테이너가 제공하는 반복자가 속한 반복자 부류이다.

 

 

14. STL 컨테이너가 제공하는 반복자 부류

위 표는 STL 컨테이너가 제공하는 반복자 타입들이 어느 반복자 부류에 속해 있는가를 보여주고 있다. 여기서 주목해야 할 것은 set과 multiset의 iterator와 const_iterator는 모두 상수 양방향 반복자 타입이라는 점이다. 따라서, 이 두 가지 반복자가 실제로는 동일한 타입이다. 이렇게 만든 이유는 다음과 같다. 셋과 멀티셋에서 저장된 키 값을 변경하려면, 일단 키 값을 삭제(erase 멤버 함수를 사용)한 뒤에, 다른 키 값을 삽입(insert 멤버 함수를 사용)하는 것이 유일한 방법이다. 셋과 멀티셋 반복자를 상수 반복자로 해두지 않으면, erase와 insert 멤버 함수를 사용하지 않고도 키 값을 변경할 수 있게 되며, 이런 식으로 키 값을 변경하게 되면, 셋과 멀티셋에 담긴 원소들이 정렬 상태를 유지할 수 없게 된다.

 

 

 

 

- STL 튜토리얼·레퍼런스 가이드 제2판 中 -