[C++STL] 연관 컨테이너 - set

• 연관 컨테이너는 특정 정렬 규칙에 따라 저장 원소가 컨테이너에 정렬된다. set, map, multiset, multimap 네 가지 컨터이너가 있고 균형 이진 트리로 구현되어있다. 시퀀스 컨테이너와 달리 모든 연관 컨테이너는 같은 인터페이스(생성자, 멤버 함수, 연산자)를 제공한다.

set은 컨테이너에 원소(key)를 삽입하는 유일한 멤버 함수 insert를 제공한다. 저장된 원소는 모두 자동 정렬되며 원소 중복된 값이 없이 유일하다. 원소의 중복이 필요하다면 multiset을 사용해야 한다. 연관 컨테이너는 균형 이진 트리를 사용하므로 찾기 연산에 뛰어난 성능을 보이며 멤버 함수를 이용한 삽입도 빠르다. 아래는 set의 예제 코드이다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int> s;
	s.insert(50);
	s.insert(30);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); ++iter) 
	{
		cout << *iter << " ";
	}
	cout << endl;
	s.insert(50);
	s.insert(70);
	for (iter = s.begin(); iter != s.end(); ++iter)
	{
		cout << *iter << " ";
	}
	cout << endl;
	return 0;
}

출력 결과는 10, 30, 50, 70, 90 / 10, 30, 50, 70, 90 두번 모두 같은 결과가 출력되는데 중간에 50, 70을 insert()하지만 중복이 허용되지 않기 때문에 반영되지 않는다. 그리고 결과에서 볼 수 있듯이 자동 정렬되며 정렬 기준은 less를 사용한다. 디폴트가 less이고 greater로 바꿔서 사용할 수도 있다. 아래는 greater를 적용한 예제이다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int,greater<int>> s;
	s.insert(50);
	s.insert(30);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	set<int, greater<int>>::iterator iter;
	for (iter = s.begin(); iter != s.end(); ++iter) 
	{
		cout << *iter << " ";
	}
	cout << endl;
	return 0;
}

출력 결과는 90 70 50 30 10 이다.

원소 중복을 허용하지 않는 set 컨테이너는 원소와 일치하는 개수를 반환하는 count() 멤버 함수가 굳이 필요 없지만 연관 컨테이너의 인터페이스가 모두 같으므로 set도 count() 멤버 함수를 제공한다. s.count(50) 이런식으로 호출하고 일치하는 원소가 있다면 1을 없다면 0을 반환한다.

다음은 연관 컨테이너의 핵심 멤버 함수 find()이다. find()는 key를 검색하여 key를 가리키는 반복자를 반환한다. 만약 key가 없으면 끝 표시 반복자를 반환한다. end() 멤버 함수가 끝 표시 반복자를 반환하므로 end() 멤버 함수와 비교해서 검색이 성공했는지 판단한다. 아래는 find()의 예제이다.

#include <iostream>
#include <set>
using namespace std;

int main()
{
	set<int,greater<int>> s;
	s.insert(50);
	s.insert(30);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	set<int, greater<int>>::iterator iter;
	for (iter = s.begin(); iter != s.end(); ++iter) 
	{
		cout << *iter << " ";
	}
	cout << endl;
	set<int>::iterator titer;
	titer = s.find(30);
	if (titer != s.end()) 
	{
		cout << *titer << "가 s에 있다." << endl;
	}
	return 0;
}

set의 멤버 함수 lower_bound()와 upper_bound()는 찾은 key를 순차열 구간으로 반환하는 멤버 함수이다. lower_bound는 찾은 원소의 시작 반복자를 반환하며 upper_bound는 찾은 원소의 다음 원소를 가리키는 반복자이다. 중복 key를 갖지않는 set에서는 큰 의미가 없지만 multiset이나 multimap에서는 유용한게 사용된다. 자세한 내용은 multi 쪽에서 다루도록 하겠다.