41-1-나.셋

두 종류의 연관 컨테이너 중 상대적으로 간단한 셋부터 알아보자. 셋(Set)은 영어 단어 뜻 그대로 집합을 의미하는데 동일한 타입의 데이터를 모아 놓은 것이다. 저장하는 데이터 자체가 키로 사용되며 값은 저장되지 않는다. 동일 타입의 집합이라는 면에서는 벡터와 같지만 아무 위치에나 삽입되는 것이 아니라 정렬된 위치에 삽입된다는 점이 다르며 그래서 검색 속도가 아주 빠르다.

셋은 키의 중복을 허용하지 않으므로 같은 키를 두 번 넣을 수 없는 반면 멀티셋은 키의 중복을 허용하므로 같은 키를 여러 번 넣을 수 있다. 중복을 허용하는 집합인가 아닌가에 따라 두 컨테이너 중 하나를 선택해서 사용하면 된다. 예를 들어 주민 등록 번호의 집합이라면 중복을 허용해서는 안되며 사람 이름의 집합이라면 중복이 발생할 수도 있다.

셋 클래스

STL의 다른 컨테이너들과 마찬가지로 셋도 템플릿으로 정의되어 있다. 셋의 템플릿 정의는 다음과 같다.

template<class Key, class BinPred = less<Key>, class A = allocator<Key> >

class set { ... }

세 개의 템플릿 인수가 전달되는데 Key는 셋에 저장되는 키의 타입이다. 기본 타입은 물론이고 사용자 정의 타입에 대해서도 셋을 만들 수 있다. BinPred는 키를 정렬하기 위한 비교 함수 객체인데 디폴트는 less로 되어 있어 작은 값이 앞쪽에 배치되는 오름차순으로 정렬된다. 다른 함수 객체를 지정하면 정렬 방법을 변경할 수도 있지만 어차피 정렬 자체가 목적이 아니라 빠른 검색이 목적이므로 미만 비교만으로도 충분하다. 마지막 인수 A는 할당기인데 역시 디폴트가 있으므로 생략 가능하다.

비교 객체와 할당기는 대개의 경우 생략하므로 셋 타입을 만들기 위해 꼭 필요한 것은 키의 타입밖에 없는 셈이다. set<int>는 정수형의 집합이며 set<Time>은 Time 객체의 집합이다. 연관 컨테이너도 시퀀스와 마찬가지로 내부에서 사용하는 타입을 정의하는데 value_type, iterator, const_iterator, reference 등의 같은 이름을 사용한다. 이 외에 다음 세 개의 타입을 추가로 정의한다.

타입	설명
key_type	키의 타입이다. 셋은 키가 곧 값이므로 value_type과 동일하며 맵은 키와 값의 pair 타입으로 정의된다.
key_compare	키를 비교하는 함수 객체 타입이다. 디폴트는 less로 되어 있다.
value_compare	값을 비교하는 함수 객체 타입이다. 셋에서는 key_compare와 동일한 타입으로 정의되며 맵에서는 pair를 비교한다.

이중 value_compare는 사실상 셋에는 꼭 필요치 않은 타입인데 셋은 키만 저장되고 별도의 값이 없으므로 key_compare 대신 value_comapre도 쓸 수 있도록 동의어를 정의해 놓았을 뿐이다. 생성자는 세 개가 정의되어 있다.

explicit set(const BinPred& comp = BinPred());

set(const set& x);

set(InIt first, InIt last, const BinPred& comp = BinPred());

첫 번째 생성자가 디폴트 생성자인데 요소를 가지지 않는 빈 셋을 만든다. 두 번째 생성자는 복사 생성자이며 세 번째 생성자는 반복자 구간의 요소들로 셋을 생성한다. 이때 반복자 구간은 입력 반복자이기만 하면 되므로 다른 컨테이너의 구간을 가져올 수도 있다. 만약 중복된 키가 있다면 이때는 한 번만 삽입되며 멀티셋이라면 전부 삽입될 것이다. 조건자와 할당기는 원할 경우 변경할 수 있지만 대개의 경우 디폴트만 해도 무난하다.

멀티 셋은 키의 중복을 허용한다는 것만 빼고는 셋과 동일하다. 클래스 이름은 multiset이며 클래스 정의문이나 생성자도 셋과 완전히 동일하다. 키의 중복이 허용되므로 키를 삽입, 삭제하는 규칙이 조금 다른데 차이점은 개별 함수에서 설명하기로 한다.

삽입, 삭제

셋에 키를 삽입할 때는 insert 멤버 함수를 사용한다. 세 가지 버전이 제공된다.

pair<iterator, bool> insert(const value_type& val);

iterator insert(iterator it, const value_type& val);

void insert((iterator first, iterator last);

첫 번째 버전은 값 하나를 셋에 삽입하되 삽입 대상이 되는 값 val만 인수로 전달받으며 삽입 위치는 별도로 전달받지 않는다. 셋은 값이 주어지면 삽입 위치가 정렬 규칙에 의해 자동적으로 결정되므로 별도의 위치를 지정할 필요가 없다. 삽입한 결과로 삽입한 위치의 반복자와 삽입 성공 여부 두 개가 pair로 묶여 리턴된다. 셋은 중복을 허용하지 않으므로 val가 이미 존재할 경우 삽입에 실패할 수도 있다.

키 하나를 삽입하면 삽입된 위치와 성공 여부를 동시에 리턴해야 하며 그래서 pair 구조체가 리턴된다. 반복자에 실패를 뜻하는 특이값이 없기 때문에 반복자와 bool의 짝을 리턴할 수밖에 없다. insert를 호출한 후 성공 여부를 알고 싶다면 리턴된 pair의 second 멤버를 읽어 보고 이 값이 true이면 first 멤버에서 삽입된 반복자 위치를 구할 수 있다. 삽입 성공 여부나 삽입된 위치에 관심이 없다면 리턴값은 무시해도 상관없다.

셋에 비해 멀티셋은 중복이 허용되므로 첫 번째 insert 함수의 원형이 조금 다르다. 리턴 타입이 다른데 중복이 허용되므로 val이 셋에 이미 포함되어 있더라도 삽입은 항상 성공한다. 그래서 성공 여부는 리턴할 필요가 없으며 삽입된 위치를 가리키는 반복자만 리턴된다.

iterator insert(const value_type& val);

나머지 insert 함수는 셋과 멀티셋의 원형이 동일하다. 두 번째 버전의 insert는 삽입 위치를 지정하는 반복자가 인수로 전달되는데 이 반복자는 빠른 삽입을 위해 우선 검색할 시작 위치를 제공하는 힌트 역할을 할 뿐이다. 대충이라도 정렬되어 있는 컨테이너의 값을 셋에 추가한다면 매 요소에 대해 삽입 위치를 일일이 찾는 것보다 직전에 삽입된 곳에서 위치 선정을 시작하면 훨씬 더 빠를 것이다.

예를 들어 작은 값부터 큰 값을 차례대로 추가한다면 셋의 끝 부분에 배치될 확률이 높으므로 삽입 위치로 end()를 주는 것이 유리하다. 어디까지나 힌트 정보일 뿐이므로 아무 위치나 지정해도 삽입은 성공하며 제 위치를 찾아간다. 삽입할 값 val가 이미 셋에 존재한다면 삽입은 실패하며 이때는 셋 내에 이미 존재하는 val위치가 리턴된다. 물론 멀티셋은 무조건 성공한다. 삽입에 성공했으면 삽입된 위치가 리턴된다.

세 번째 버전의 insert는 반복자 구간의 값들을 한꺼번에 삽입한다. 하나씩 삽입하는 것보다는 훨씬 더 빠르게 삽입될 것이다. 셋에 이미 삽입된 값은 물론 삽입되지 않으며 멀티셋은 키의 존재 여부에 상관없이 전부 삽입한다. 다음 예제는 셋의 생성자와 삽입 함수들을 테스트한다.

예 제 : setcon

#include <iostream>

#include <set>

using namespace std;

template<typename C> void dump(const char *desc, C c) { cout.width(12);cout << left << desc << "==> ";

copy(c.begin(),c.end(),ostream_iterator<typename C::value_type>(cout," ")); cout << endl; }

void main()

{

int ar[]={1,4,8,1,9,6,3};

int i;

set<int> s;

for (i=0;i<sizeof(ar)/sizeof(ar[0]);i++) {

s.insert(ar[i]);

}

dump("원본",s);

set<int> s2=s;

dump("사본",s2);

const char *str="ASDFASDFGHJKL";

set<char> sc(&str[0],&str[13]);

dump("문자셋",sc);

}

셋과 멀티셋은 set 헤더 파일에 정의되어 있으므로 이 헤더 파일을 인클루드해야 한다. 실행 결과는 다음과 같다.

원본 ==> 1 3 4 6 8 9

사본 ==> 1 3 4 6 8 9

문자셋 ==> A D F G H J K L S

디폴트 생성자로 정수를 저장하는 set<int> 타입의 빈 셋 s를 생성하고 insert 함수로 ar배열의 값을 차례대로 셋에 삽입했다. ar배열에는 1이 두 개 있고 정렬되어 있지 않지만 셋이 중복을 허용하지 않으므로 1은 한 번만 들어가며 삽입할 때부터 정렬된 위치에 저장되므로 s는 항상 정렬 상태를 유지한다. for 루프에 의해 ar 배열의 값이 s에 삽입되는 과정은 다음과 같다.

s2는 복사 생성자로 s를 복사받은 것으므로 s와 똑같은 사본으로 생성될 것이다. 내부에서는 s의 모든 요소들을 s2로 깊은 복사하여 완전한 사본을 작성한다. 똑같은 동작을 하는 대입 연산자도 정의되어 있으므로 s2를 빈 셋으로 만든 후 s2=s; 로 대입을 해도 효과는 동일하다. 물론 생성 시점에만 같을 뿐이지 s와 s2는 별개의 셋이므로 이후 완전히 독립적으로 요소들을 관리한다.

sc는 문자형 셋인데 str 문자 배열의 전 구간을 삽입했다. 입력 반복자이기만 하면 되므로 벡터나 리스트 등의 다른 컨테이너의 값들로부터 셋을 생성할 수 있다. 중복되는 값은 제거되고 문자 크기 순으로 정렬된다. ASDF 문자들이 두 번씩 있지만 결과 셋에는 하나씩만 들어간다. 위 예제의 set 클래스 이름을 multiset으로 변경하면 결과는 다음과 같아진다.

원본 ==> 1 1 3 4 6 8 9

사본 ==> 1 1 3 4 6 8 9

문자셋 ==> A A D D F F G H J K L S S

정렬은 되지만 키가 중복될 수 있으므로 삽입된 회수만큼 키가 반복적으로 나타난다. 셋에서 요소를 삭제할 때는 erase 함수를 사용한다.

iterator erase(iterator it);

iterator erase(iterator first, iterator last);

size_type erase(const Key& key);

세 가지 방식으로 삭제할 수 있는데 각각 반복자가 지정하는 요소 하나, 반복자 구간의 모든 요소 또는 특정한 키를 가지는 요소를 찾아서 삭제한다. 키를 지정하는 erase의 경우 지정한 키가 셋에 포함되어 있지 않으면 아무 것도 하지 않으며 멀티셋의 경우 같은 키값을 가지는 모든 요소를 한꺼번에 삭제한다.

검색

셋에서 특정 키를 찾을 때는 다음과 같이 선언된 find 멤버 함수를 사용한다. 상수 버전과 비상수 버전이 중복 정의되어 있다.

iterator find(const Key& val);

const_iterator find(const Key& val) const;

인수로 찾고자 하는 키만 전달하면 된다. val 키가 발견되면 그 반복자를 리턴하며 없을 경우는 end()가 리턴된다. 간단하게 예제를 만들어 보자.

예 제 : setfind

#include <iostream>

#include <set>

#include <algorithm>

using namespace std;

void main()

{

set<int> s;

s.insert(1);

s.insert(2);

s.insert(3);

set<int>::iterator it;

it=s.find(2);

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

cout << *it << endl;

} else {

cout << "찾는 키가 없습니다." << endl;

}

}

1, 2, 3 세 개의 정수를 넣어 놓고 2를 찾았으므로 당연히 2가 출력될 것이다. 4나 5를 검색하면 키가 없다고 출력된다. find 멤버 함수 대신 전역 find 알고리즘 함수를 사용할 수도 있는데 다음과 같이 수정해도 결과는 일단 동일하다.

it=find(s.begin(),s.end(),2);

셋의 반복자가 임의 접근이 아니므로 전역 find 함수는 셋의 모든 요소를 순회하면서 순차적으로 검색하지만 find 멤버 함수는 정렬되어 있다는 특성을 이용하여 이진 트리 검색을 하므로 훨씬 더 빠르다. 이 예제의 경우 요소가 고작 세 개밖에 없어 아무 차이도 느낄 수 없겠지만 1000개 정도만 되어도 순차 검색과 이진 검색은 엄청난 차이가 벌어질 것이다. 또한 find알고리즘은 다음에 설명할 동등성이 아닌 동일성 개념으로 요소를 검색한다는 면에서 셋과는 어울리지 않는다.

멀티셋의 경우 find 멤버 함수로 찾으면 중간 중간을 쿡쿡 찔러가며 검색하므로 중복된 키 중 어떤 것이 검색될 지 알 수 없는데 이는 이진 검색의 일반적인 특성이다. 반면 find 전역 함수는 처음부터 순서대로 검색하므로 항상 첫 번째 요소가 검색된다. 중복된 키 중 첫 번째 또는 마지막 요소를 찾고 싶으면 lower_bound, upper_bound 함수를 사용해야 하며 둘을 한꺼번에 조사하고 싶으면 equal_range 멤버 함수를 사용한다. equal_range는 처음과 끝 반복자의 쌍을 조사하여 리턴한다.

iterator lower_bound(const Key& _Key);

iterator upper_bound(const Key& _Key);

pair <iterator, iterator> equal_range (const Key& _Key);

예를 들어 다음과 같은 정수 멀티셋에서 7을 찾는다고 해 보자. 7이 다섯 개나 중복되어 있는데 호출하는 함수에 따라 어떤 7이 검색될지가 달라진다.

find 전역 함수와 lower_bound가 찾는 키는 우연히 같지만 이 둘의 검색 속도는 엄청난 차이가 있다. upper_bound 함수는 마지막 요소를 찾는 것이 아니라 마지막 요소의 다음을 찾는다는 점을 주의하자.

셋의 활용

어떤 값의 집합을 관리하는데 중복되어서는 안되며 빠른 검색으로 존재 여부를 신속하게 알고 싶을 때 셋을 사용한다. 다음 예제는 이런 예를 보여 준다.

예 제 : stringset

#include <iostream>

#include <string>

#include <set>

using namespace std;

void main()

{

set<string> s;

string name;

char ch;

set<string>::iterator it;

for(;;) {

cout << "1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => ";

cin >> ch;

switch (ch) {

case '1':

cout << "새 이름을 입력 하시오 : ";

cin >> name;

s.insert(name);

break;

case '2':

cout << "삭제할 이름을 입력 하시오 : ";

cin >> name;

s.erase(name);

break;

case '3':

for (it=s.begin();it!=s.end();it++) {

cout << *it << endl;

}

break;

case '4':

cout << "검색할 이름을 입력 하시오 : ";

cin >> name;

cout << name << "이(가) " << (s.find(name) != s.end() ? "있":"없")

<< "습니다." << endl;

break;

case '5':

return;

}

}

}

이 예제의 셋 s는 문자열로 된 어떤 이름의 집합을 관리하는데 사람 이름일 수도 있고 영화 제목이나 책 제목이 될 수도 있다. 아무튼 중복되지 말아야 하는 이름의 목록을 관리하고 싶을 때 셋이 적합하다. 이름을 삽입할 때는 insert 함수만 호출하면 알아서 찾기 편한 위치에 적당히 삽입하며 만약 이미 존재하는 이름이라면 삽입은 거부된다. 삭제하고 싶을 때는 erase를 호출하는데 없는 이름이라면 아무 일도 일어나지 않을 것이다.

이름의 존재 여부를 알고 싶다면 find로 검색해 볼 수 있는데 정렬된 자료를 이진 검색하므로 셋의 크기가 아무리 커도 고속으로 존재 여부를 조사할 수 있다. 셋의 모든 요소를 출력하거나 저장하고 싶다면 begin부터 end까지 순회하면서 반복자가 가리키는 내용을 출력하면 된다. 또는 for_each 같은 알고리즘을 사용할 수도 있다. 콘솔 환경이라 메뉴 방식으로 실행된다.

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 1

새 이름을 입력 하시오 : 박미영

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 1

새 이름을 입력 하시오 : 김한슬

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 1

새 이름을 입력 하시오 : 김한결

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 3

김한결

김한슬

박미영

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 4

검색할 이름을 입력 하시오 : 김한슬

김한슬이(가) 있습니다.

1:삽입, 2:삭제, 3:보기, 4:검색, 5:종료 => 4

검색할 이름을 입력 하시오 : 박종만

박종만이(가) 없습니다.

이 예제처럼 중복되지 않는 값의 집합을 직접 관리하려면 굉장히 많은 코드가 필요하다. 삽입, 삭제시 이미 존재하는 값인지 점검해야 하고 삽입 위치를 선정하려면 일일이 요소들의 대소를 비교해 봐야 한다. 이진 트리를 관리하는 코드도 정교해야 하며 이진 트리 순회만 해도 그리 간단한 작업이 아니다. 이 모든 처리를 셋이 대신하므로 우리는 자료의 관리에는 골치를 썩일 필요없이 사용자와의 인터페이스만 신경쓰면 된다. 메뉴나 출력하고 사용자의 명령을 받아 셋과 중계만 하면 되는 것이다.

이메일 주소 수집기 같은 프로그램도 셋을 쓰기에 아주 적합하다. 웹 사이트를 자동으로 돌아 다니며 이메일을 수집하는 프로그램을 만든다고 해 보자. HTML 페이지에서 @ 문자가 포함되어 있고 이메일 비슷하게 생긴 문자열을 모두 모아야 하는데 이미 수집한 주소는 다시 모을 필요가 없다. 이럴 때 셋을 하나 만들어 놓고 이메일 비슷해 보이는 문자열을 추출하여 무조건 insert만 하면 나머지 작업은 셋이 알아서 처리할 것이다.