39-3-다.역방향 반복자

역방향 반복자는 순회 방향이 거꾸로 되어 있는 반복자이다. 양방향 반복자나 임의 접근 반복자에 어댑터를 적용하여 구현되며 ++, -- 연산이 반대 방향으로 정의되어 있다. 각 컨테이너는 다음 두 개의 역방향 반복자 타입을 제공하므로 이 타입의 반복자를 선언하기만 하면 된다. 상수, 비상수 버전이 따로 준비되어 있다.

 

reverse_iterator

const_reverse_iterator

 

컨테이너로부터 역방향 반복자를 얻을 때는 rbegin, rend 멤버 함수를 사용한다. 역방향 반복자로 컨테이너를 순회하면 끝에서부터 앞쪽으로 순회할 수 있다. 이 두 멤버 함수가 가리키는 위치는 다음과 같은데 단순히 begin, end의 맞은편 반대쪽을 가리키는 것은 아니다.

범위의 원칙에 의해 구간의 처음은 포함되며 끝은 항상 제외되어야 하므로 rbegin ~ rend로 역방향 순회를 하려면 rbegin은 끝요소를 가리키고 rend는 첫 요소보다 하나 더 앞쪽을 가리켜야 한다. 물론 rend위치는 실제로 컨테이너의 내부도 아니며 처리 대상에도 포함되지 않는다. 다음 예제는 벡터를 역순으로 순회하며 요소들을 출력한다.

 

: revit

#include <iostream>

#include <vector>

using namespace std;

 

void main()

{

     int ari[]={1,2,3,4,5};

     vector<int> vi(&ari[0],&ari[5]);

 

     vector<int>::reverse_iterator rit;

     for (rit=vi.rbegin();rit!=vi.rend();rit++) {

          printf("%d\n",*rit);

     }

}

 

reverse_iterator 타입의 rit를 선언하고 rbegin으로 초기화하면 벡터의 제일 끝 요소를 가리킬 것이다. 이 요소를 출력하고 rit를 1 증가시키면 ++ 연산자가 반복자를 벡터의 선두쪽으로 이동시킨다. 이 과정을 rend가 아닐 때까지, 즉 첫 요소보다 앞에 이르기 직전까지 반복하므로 첫 번째 요소를 출력한 후 루프를 탈출하게 된다. 출력 결과는 5, 4, 3, 2, 1인데 다음처럼 순회하는 것과 사실상 동일하다.

 

     vector<int>::iterator it;

     for (it=vi.end()-1;;it--) {

          printf("%d\n",*it);

          if (it==vi.begin()) break;

     }

 

순방향 반복자를 사용하여 직접 반대로 순회했다. 이때 시작 지점은 end보다 하나 더 앞쪽이어야 하며 begin 위치도 출력 대상에 포함되므로 일단 출력한 후 begin에 이르렀으면 루프 중간에서 탈출해야 한다. 순방향 반복자로도 역방향 순회가 가능하기는 하지만 보다시피 직관적이지 못하고 불편하다.

알고리즘 함수들은 구현을 위해 항상 순방향 순회를 하도록 되어 있는데 반복자를 이동시키기 위해서 늘상 ++ 연산자를 사용한다. 역방향 반복자를 알고리즘으로 전달하면 ++ 연산의 의미가 바뀌므로 알고리즘의 순회 방향을 변경할 수 있다. find는 반복자를 앞으로 이동하며 값을 찾지만 역방향 반복자를 전달하면 뒤쪽으로 이동하므로 역방향에서 검색할 수 있다.

 

: revfind

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     int ari[]={6,2,9,2,7};

     vector<int> vi(&ari[0],&ari[5]);

 

     puts(find(vi.begin(),vi.end(),2)==vi.end() ? "없다.":"있다.");

     puts(find(vi.rbegin(),vi.rend(),2)==vi.rend() ? "없다.":"있다.");

}

 

vi 벡터에 두 개의 2가 포함되어 있는데 순방향으로 찾을 때와 역방향으로 찾을 때 검색되는 값이 다르다. 이 경우는 둘 다 같은 2의 값을 가지지만 위치에 따라 요소의 의미가 달라질 수도 있다. 어떤 요소가 끝에서 어디쯤에 있는지를 검색하고 싶을 때 역방향 반복자를 사용한다.

역방향 반복자에는 원래의 순방향 반복자를 리턴하는 base 멤버 함수가 정의되어 있다. 삽입, 삭제 함수들은 역방향 반복자를 받아들이지 않기 때문에 역방향 검색한 위치에 대고 어떤 작업을 하고 싶을 때는 순방향 반복자로 바꾸어야 한다. 또한 역방향 검색 후에 다시 순방향으로 검색하고 싶을 때 base로 언제든지 순방향 반복자를 구할 수 있다. base로 구한 순방향 반복자는 역방향 반복자보다 항상 하나 더 큰 값을 가진다.

이렇게 되어 있는 이유는 순방향 반복자가 역방향 반복자보다 한칸 더 오른쪽에 있으며 이렇게 해야 rbegin의 base가 end가 되기 때문이다. 다음은 역방향 검색 후 다시 순방향으로 검색한다.

 

: revbase

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void main()

{

     const char *str="c++ standard template library";

     vector<char> vc(&str[0],&str[strlen(str)]);

 

     vector<char>::reverse_iterator rit;

     vector<char>::iterator bit,it;

     rit=find(vc.rbegin(),vc.rend(),'t');

     bit=rit.base();

     it=find(bit,vc.end(),'a');

     if (it!=vc.end()) {

          printf("검색 결과 = %c\n",*it);

     }

}

 

문자열 끝에서부터 't'를 찾기 위해 역방향 검색을 했으며 't' 이후 최초로 나타나는 a를 찾기 위해 순방향 반복자 bit를 rit.base로 구하여 bit이후부터 검색했다.