Tutorial: STL Set 2 timer 1초 memory 256MB

이전 문제에서는 STL Set의 맛보기 단계를 거쳐 보았다.

Set(을 포함한 여러 STL 자료구조)의 강력한 기능을 쓰기 위해서는 

먼저 반복자(iterator)라는 게 무엇인지 알아야 한다.

왜냐 하면, Set의 기능을 이루는 함수들은 반복자(iterator)를 리턴하기 때문이다. 

그럼 반복자라는 것은 무엇일까? 

반복자(iterator)

​

정확한 정의를 가져와서 쓰는 것 보다는, 예를 들어서 설명을 들어보도록 하자.

현재 s라는 이름의 set<int>를 만들고, s에는 [2 5 7 10]이 들어있다고 하자.

여러분은 전 시간에 배웠던 for문을 이용하여, s에 들어있는 모든 원소를 순회하도록 시켰다..

그렇다면, 어떤 장치에 의해 다음과 같이 처음에 2를 가리키는 “화살표”가 필요할 것이다.

다음 반복에는 이 화살표가 5를 가리키게 해야 할 것이다.

다음 두 반복은 각각 다음과 같은 과정에 의해 이루어질 것이다.

그렇다. (어떤 식으로든) 모든 원소를 순회하기 위해선, 적어도 그 원소가 있는 위치를 가리키는 특별한 화살표가 필요하다. 이 화살표를 부르는 말이 바로 반복자이다.

아직도 와 닿지 않는다면, Set 대신 배열을 순회한다고 생각해보자.

아 이건 너무 쉽지! 배열을 순회하기 위해서 어떤 행동을 하는가? 벌써부터 키보드가 근질근질 할 것이다. 아래 문장은 여러분이 여기까지 오면서 적어도 1천번은 썼을 법한 문장이다.

이 아래 문장을 치는 순간만큼은 여러분의 타자 속도가 500타 이상으로 측정되지 않을까?

for(int i = 0 ; i < n ; i++) // n은 배열 arr[] 의 크기.

이 습관적으로 썼던 반복 변수 i! i가 바로 배열이라는 자료구조의 “반복자”인 것이다. 배열의 “i번째” 만 알면, 그 배열의 원소를 알 수 있으며, 추가적으로 다음 반복에 어디를 가리킬지 ((i+1)번째)를 알 수가 있다. 반복자 i가 있기 때문에, 우리는 배열이라는 순회를 할 수 있기 때문이다.

참고로 문법을 처음 배우면 언어 불문하고 반복 변수를 i라는 이름으로 지으라고 반강제적으로 가르치는데, 이 i라는 이름도 반복자(iterator)의 약자인 i에서 온 것이다.

자 다시 set으로 돌아오자. set의 반복자는 정수 i로 간단하게 나타낼 수 있는 것이 아니라, 특정한 형식이 있다. 전 문제에서 크게 바뀌지 않은 아래 예제를 보며 연습해보도록 하자.

#include <stdio.h>
#include <algorithm>
 
#include <set> //set을 사용하려면 이 헤더파일이 필요하다.
 
 
using namespace std; 
 
int main()
{
 
   set<int> s;  /// int형 자료를 넣을 수 있는 집합 s를 하나 만든다.
   s.insert(3);  /// 집합 s에 3을 넣는다.
   s.insert(5);
   s.insert(3);  /// 3이 이미 있으므로, 이 삽입작업은 아무 효과가 없다.
   s.insert(6);
   s.insert(9);
   s.insert(2); 
 
   s.erase(3); ///집합에서 3을 삭제.
   s.erase(10); ///집합에 10이 없으므로 이 삭제작업은 무효하다.
 
 
   set<int>::iterator iter; // int자료형을 관리하는 set을 순회하는 반복자 iter를 선언한다. 
 
   for(iter = s.begin() ; iter != s.end() ; iter=next(iter)/* 보통 ++iter로 대체한다 */ )
   {
 
       printf("%d " , *iter);
   }
   return 0;
}

s.begin() 메소드를 호출하면, s의 가장 앞을 가리키는 화살표, 즉 반복자를 반환한다. 

for문에서 iter에 s.begin()을 대입하면서 반복문을 시작하는 것은, 배열을 순회할 때 i에 0을 대입하고 시작하는것과 같은 이치이다.

s.end() 메소드를 호출하면, s의 가장 뒤를 가리키는 화살표(반복자)를 반환한다. 

주의할 점은 s.begin()과 달리, s.end()는 가리키는 원소가 없기 때문에, 화살표가 s.end()를 가리키게 되는 순간 반복을 종료해야 한다는 점이다.

어떤 반복자던지, next()함수와 prev()함수를 적용할 수 있으며, next()함수를 쓰면 화살표(반복자)의 다음 위치(오른쪽 화살표)를 반환하고 prev()함수를 쓰면 화살표의 이전 위치를 반환한다. 

인자로 보내는 iter가 s.begin()일 때 prev()함수를 호출하거나, s.end()일 때 next()함수를 호출하지 않도록 주의한다. 

보통 iter = next(iter) 는 ++iter로 줄여서 쓰며, iter = prev(iter)의 경우 --iter로 줄여서 쓴다.

화살표가 가리키는 원소를 가져오는 방법은, 인디렉션(*)연산자를 반복자 앞에 붙이면 된다. 이는 주소값을 저장한 포인터가 가리키는 원소를 얻고 싶을 때 쓰는 표현과 상당히 유사하다.

설명이 길어지므로 여기서 끊고, 반복자에 관련한 간단한 연습문제 하나를 풀어보고 다음으로 넘어가도록 하자.

연습문제

정수형 자료를 저장할 수 있는 집합(set)을 선언한 후, 다음 2가지 작업을 순서대로 처리한 후에 남아있는 자료들 중 앞에서부터 x번째(맨 앞: 1번째) 자료를 출력하는 프로그램을 작성하라

• i □ : □가 없다면 집합에 추가한다.

• r □ : 집합 내에 □가 있다면 삭제한다. 없다면 아무 것도 하지 않는다.

Set Tutorial 1의 연습문제에서 썼던 100점짜리 코드를 그대로 수정해도 좋다.

 ​