[STL] set 컨테이너

in STL



이번에 포스팅 할 내용은 set 컨테이너 이다. set 컨테이너는 연관 컨테이너 중 가장 단순한 컨테이너로 Key라 불리는 원소의 집합으로 이루어진 컨테이너이다. 연관 컨테이너(set, multiset, map, multimap)들은 모두 같은 인터페이스를 가진다. 그리고 set은 모든 원소가 유일하다. 즉, 원소가 중복되지 않는다는 것이다. 원소가 중복되게 하려면 multiset을 사용해야 한다. 그리고 set은 균형 이진 트리기 때문에 찾기 연산을 할 때 뛰어난 성능을 지닌다, 물론 삽입 할 때 사용되는 insert() 또한 뛰어난 성능을 보인다. 그리고 연관 컨테이너들은 특정 정렬 기준에 의해 정렬이 된다. 만약 조건자를 명시해주지 않으면(기본 정렬 기준 less) 오름차순으로 자동 정렬 된다. 예시를 보겠다.

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

void main() {
	set<int> s; //기본 조건자인 less를 기준으로 오름차순 정렬
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 10 30 40 50 70 80 90

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	//set은 기본적으로 원소를 중복해서 저장할 수 없다 그래서 아래 삽입 코드는 유효하지 않다.
	s.insert(50);
	s.insert(50);

	//위와 실행 결과가 같음을 보여준다.
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

실행 결과

image

set의 특징인 중복되는 원소를 가질 수 없다 와 조건자를 명시해주지 않으면 기본적으로 오름차순(less)으로 지정되어 자동으로 오름차순으로 정렬된다.

insert 실패 시 반환되는 객체

set은 기본적으로 원소의 중복을 허용하지 않는다. 그래서 set에서 멤버함수 insert()를 사용하면 반환값으로 pair객체를 반환한다. pair개체의 first에는 원소의 삽입 위치, second에는 삽입에 성공했는지의 여부를 bool값으로 저장한다. 예제를 보자.

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

void main() {
	set<int> s; //기본 조건자인 less를 기준으로 오름차순 정렬

	//insert()의 반환값을 받기위한 pair객체 생성 first에는 원소를 가리키는 반복자가 들어가고
	//second에는 삽입의 성공 여부를 bool값으로 반환
	pair<set<int>::iterator, bool> pr;
	pr = s.insert(50); //50 원소 첫번째 삽입
	s.insert(40);
	s.insert(80);

	if (pr.second == true)
		cout<<*pr.first << "삽입 성공" << endl;
	else 
		cout << *pr.first << "이 이미 존재한다. 삽입 실패" << endl;

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;;

	pr = s.insert(50);//50 원소 2번째 삽입

	if (pr.second == true)
		cout << *pr.first << "삽입 성공" << endl;
	else
		cout << *pr.first << "이 이미 존재한다. 삽입 실패" << endl;

	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

어려운 것은 없다. 단지 기억해야 할 것은 set은 원소를 중복 허용하지 않기 때문에 원소를 삽입할 때 삽입된 위치와 삽입의 성공 여부를 pair객체를 통해서 반환하고 pair의 first에는 삽입이 성공 했다면 삽입된 원소의 위치를 가리키고 삽입에 실패했다면 이미 삽입된 원소를 가리킨다. second에는 삽입 성공 여부를 bool값으로 저장한다는 것이다. 그리고 set은 원소를 삽입할 때 삽입하고자하는 원소가 이미 컨테이너 안에 있는지 확인하기 위해 컨테이너의 처음부터 탐색을 실시한다. 이걸 더 빠르게 하기 위해서 insert()에 어디서 부터 탐색할 지를 정해주는 방법이 있다. 예시를 보자.

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

void main() {
	set<int> s; //기본 조건자인 less를 기준으로 오름차순 정렬

	//insert()의 반환값을 받기위한 pair객체 생성 first에는 원소를 가리키는 반복자가 들어가고
	//second에는 삽입의 성공 여부를 bool값으로 반환
	pair<set<int>::iterator, bool> pr;
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	pr=s.insert(90); //90원소 처음 삽입, pr.first는 90을 카리키는 반복자
	//s의 모습 10 30 40 50 70 80 90

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	s.insert(pr.first, 85); //90 원소부터 탐색을 시작하여 85를 삽입
	//s의 모습 10 30 40 50 70 80 85 90

	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

실행 결과

image

딱히 어려운 것은 없다.

set컨테이너의 조건자를 명시하지 않으면 기본적으로 less를 기준으로 정렬이 된다고 했는데 조건자를 greater로 명시하여 내림차순으로 정렬하는 코드를 보이겠다.

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

void main() {
	set<int,greater<int>> s; //조건자를 greater<int>로 명시해서 내림차순으로 정렬됨.

	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 90 80 70 50 40 30 10

	set<int, greater<int>>::iterator iter; //greater<int>를 사용하여 반복자 생성

	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
}

실행 결과

image

딱히 이 코드에 대해서 설명할 건 없다. 단지 처음 컨테이너를 생성할 때 조건자를 명시해줬다는거만 알면 된다.

key_comp() / value_comp()

set은 현재 사용중인 정렬 기준 조건자를 반환하는 key_comp()와 value_comp()를 가지고 있다. 이 때 key_comp()가 반환하는 값을 받기 위해서는 set컨테이너안에 typedef된 key_compare를 사용하고 value_comp()가 반환하는 값을 받기 위해서는 set컨테이너에안에 typedef된 value_compare를 사용하면 된다.그리고 여기서 중요한건 set은 저장 원소인 값(value)이 그대로 비교로 사용되는 키(key)로도 사용이 되므로 set은 value와 key의 값이 같다. 예시 코드를 보자.

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

void main() {
	set<int, less<int>> s_less;//조건자를 less<int>로 명시해서 오름차순으로 정렬됨.
	set<int,greater<int>> s_greater; //조건자를 greater<int>로 명시해서 내림차순으로 정렬됨.

	s_less.insert(50);
	s_less.insert(80);
	s_less.insert(40);
	//s_less의 모습 40 50 80

	s_greater.insert(50);
	s_greater.insert(80);
	s_greater.insert(40);
	//s_greater의 모습 80 50 40

	// l_cmp는 set컨테이너 중 오름차순으로 정렬 된 컨테이너의 key의 정렬 기준을 받을 수 있음
	set<int, less<int>>::key_compare l_cmp = s_less.key_comp();
	cout << l_cmp(10, 20) << endl; //실제로 10 < 20 연산이 가능하다(참)

	// g_cmp는 set컨테이너 중 내림차순으로 정렬 된 컨테이너의 key의 정렬 기준을 받을 수 있음
	set<int, greater<int>>::key_compare g_cmp = s_greater.key_comp();
	cout << g_cmp(10, 20) << endl; //실제로 10 > 20 연산이 가능하다(거짓)

	cout << "key_compare type: " << typeid(s_less.key_comp()).name() << endl;
	cout << "key_compare type: " << typeid(s_greater.key_comp()).name() << endl;
	cout << "value_compare type: " << typeid(s_less.value_comp()).name() << endl;
	cout << "value_compare type: " << typeid(s_greater.value_comp()).name() << endl;
}

실행 결과

image

딱히 어려운 것은 없을 것이다. 여기서 확인하고 넘어가야 할 것은 set의 특성상 저장되는 원소가 바로 key값으로도 사용되기 때문에 value와 key의 형식이 같다는 것이다.

연관 컨테이너의 핵심 인터페이스는 찾기 관련 멤버 함수이다. 찾기 관련 멤버 함수는 정렬 기준으로 트리의 루트부터 자식 노드로 검색을 진행하므로 로그 시간 복잡도로 실행된다. 찾기 관련 멤버함수는 count(), find(),

lower_bound(),upper_bound(),equal_bound()가 있다. 이제 하나하나 설명을 시작해보겠다.

count()

count()는 컨테이너안에 특정한 원소가 몇개 있는지 알려주는 함수이다. set같은 경우는 중복 되는 원소가 없기에 0 아니면 1만 뜬다. 하지만 모든 연관 컨테이너는 같은 인터페이스를 자기므로 set도 우선 가지고는 있다. 예시를 보자.

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

void main() {
	set<int> s;
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 10 30 40 50 80 70 90

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	cout << "원소 50의 갯수 : " << s.count(50) << endl;
	cout << "원소 100의 갯수 : " << s.count(100) << endl;
}

실행 결과

image

어려운 내용은 아니다.

find()

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

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

void main() {
	set<int> s;
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 10 30 40 50 80 70 90

	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	iter=s.find(50); //50의 반복자를 반환 iter에 저장
	if (iter != s.end())
		cout <<*iter <<"이 존재한다" << endl;
	else
		cout << "50이 s안에 없다" << endl;
}

실행 결과

image

실행 결과에서 보이는 것 처럼 end()로 비교하여 찾았는지 못찾았는지 판단이 가능하다. 하지만 여기서 주의할 점이 있다, 연관 컨테이너의 찾기 관련 멤버 함수는 ==를 기준으로 찾기를 하는것이 아닌 현재 컨테이너의 정렬기준을 사용하여 찾기를 수행한다. 예를들어 현재 컨테이너가 less를 기준으로 정렬이 되어있다면 다음과 같은 방식으로 찾기를 수행한다. !(a<b) && !(b<a) 이 조건식이 참이라면 같다고 판단한다.

lower_bound() / upper_bound()

lower_bound()와 upper_bound()는 찾은 키를 순차열 구간으로 반환하는 멤버 함수이다. lower_bound()는 찾은 원소의 시작 반복자를 반환하며 upper_bound()는 찾은 원소의 다음 원소의 반복자를 반환한다. 그렇기에 찾은 원소는 [lower_bound(),upper_bound())로 표현할 수 있으며 lower_bound()와 upper_bound()가 같다면 찾고자 하는 원소가 없는 것이다. 사실 중복 원소가 없는 set컨테이너는 큰 의미가 없지만 중복원소를 혀용하는 multiset,multimap은 큰 역할을 한다. 예시를 보자.

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

void main() {
	set<int> s;
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 10 30 40 50 70 80 90

	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	set<int>::iterator lower_iter;
	set<int>::iterator upper_iter;

	lower_iter = s.lower_bound(30);	//lower_iter은 30을 가리킴
	upper_iter = s.upper_bound(30); //upper_iter은 40을 가리킴

	cout << *lower_iter << endl;
	cout << *upper_iter << endl;


	lower_iter = s.lower_bound(55);	
	upper_iter = s.upper_bound(55);
	if (lower_iter == upper_iter)
		cout << "55가 없다." << endl;
	else
		cout << "55가 있다" << endl;
}

실행 결과

image

실행 결과로 보이는 것 처럼 lower_bound()는 찾은 원소의 반복자를 반환하고, upper_bound()는 찾은 원소의 다음 원소의 반복자를 반환한다.

equal_range()

equal_range()는 lower_bound()와 upper_bound()의 반복자 쌍을 pair객체로 반환한다. 예시를 보자.

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

void main() {
	set<int> s;
	s.insert(50);
	s.insert(30);
	s.insert(80);
	s.insert(40);
	s.insert(10);
	s.insert(70);
	s.insert(90);
	//s의 모습 10 30 40 50 70 80 90

	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;

	//lower_bound()와 upper_bound()가 반환하는 반복자 쌍을 받는 pair 객체
	pair<set<int>::iterator, set<int>::iterator> pr;

	pr = s.equal_range(30);
	cout << *pr.first << endl;
	cout << *pr.second << endl;

	pr = s.equal_range(55);
	if (pr.first == pr.second)
		cout << "55 없음" << endl;
	else
		cout << "55 있음" << endl;
}

실행 결과

image

어려운 코드는 아니다.

위의 코드를 그림으로 표현해보겠다.

image-20220315132122105

다음과 같은 상황인 것이다.


© 2022. by KSC

Powered by sora