C++ STL Set 컨테이너,멤버 함수 사용

SET 컨테이너

 집합의 의미로 쓰이는 set은 중복 요소가 없으며 균형 이진트리로 구현된 연관형 컨테이너이다. 원소들의 집합으로 되어 있다. Set도 매우 유용하지만 set보다는 보통 multi set을 사용할 때가 더 많았다. set은 절대 중복 원소가 없어야 할 경우에만 사용한다.

 

 

생성자

• set<T> s : 빈 set 생성
• set<T,p<T>> s : p<T> 조건자로 정렬한 빈 s생성

멤버 함수

• size() : s의 원소 개수
• count(x) : 원소 x의 개수 반환
• begin() : 처음을 가리키는 반복자 반환
• rbegin() : 처음을 가리키는 역순차열의 반복자 반환
• end() : 마지막을 가리키는 반복자 반환
• rend() : 마지막을 가리키는 역순차열의 반복자 반환
• clear() : 모은 요소 제거
• empty() : 컨테이너가 비었는지 검사
• equal_range(x) : x의 pair 객체 반환 (first에 lower_bound, second에 upper_bound 반환)
• erase(i) : i가 가리키는 원소 삭제 후 다음 원소를 가리키는 반복자 반환
• find(x) : x의 위치 반환
• insert(x) : x삽입 후 삽입 원소를 가리키는 반복자와 bool값을 가진  pair 객체 반환
• insert(i,x) : i위치부터 x를 삽입 후 x를 가리키는 반복자 반환
• insert(i,i2) : [i, i2)의 원소를 삽입
• key_comp() : key 정렬 기준 조건자 반환
• value_comp() : value 정렬 기준 조건자 반환
• lower_bound(x) : x의 시작 구간을 가리키는 반복자 반환
• upper_bound(x) : x의 마지막 구간을 가리키는 반복자 반환
• max_size() : 해당 컨테이너가 담을 수 있는 최대 원소 개수
• swap(s) : s와 스왑

타입

• iterator
• const_iterator
• allocator_type 메모리 관리 형식
• (const_)reference
• key_type
• value_type
• difference_type
• (const_)pointer

set의 기본 기능과 개념이다. set은 key와 value를 같은 의미로 쓰여 둘은 큰 차이가 없다. 각각의 원소는 key이며 원소의 중복을 허용하지 않는다. 조건자에 따라 원소를 정렬하고 기본으로는 less 정렬을 한다. 연관 컨테이너에서 공통적으로 제공하는 함수들을 제공하고 때문에 set 컨테이너에서는 크게 쓰이지 않는 함수들이 있다. 탐색 시 inorder 탐색을 한다.

set 컨테이너 기본 예

#include <iostream>
#include <set>
using namespace std;
int main(){
	set<int> s;
	for(int i=0;i<10;i++){
		s.insert(i);
	}
	set<int>::iterator iter=s.begin();
	for(iter;iter!=s.end();iter++)
		cout<<*iter<<endl;
	
	return 0;
}

실행 예1

 set 컨테이너 s는 less 기준으로 정렬되며 0~9를 insert 한 코드이다.

 

Pair 객체

 멤버 함수 소개에서 pair 객체가 나왔었다. STL을 처음으로 접했다면 pair객체를 처음 볼 것이다. pair 객체는 말 그대로 쌍 값을 가지는 멤버로 구성되어 있다. first와 second를 멤버로 가진다. insert를 사용할 때 pair객체를 반환하는데 이때 pair객체는 first에는 삽입된 요소의 반복자와 삽입 성공 여부를 나타내는 bool값이 들어있다. 이외에도 반복자가 쌍으로 입력되어 쓰이는 경우도 있다.

pair 객체 insert() 사용 코드

#include <iostream>
#include <set>
using namespace std;
int main(){
	set<int> s;
	pair<set<int>::iterator,bool> pair;
	pair=s.insert(50);
	cout<<pair.second<<endl;
	pair=s.insert(50);
	cout<<pair.second<<endl;
	
	return 0;
}

 

pair 객체 실행 예

 pair 실행 예 코드이다. 처음 50을 삽입했을 땐 성공으로 뜨지만 다시 50을 삽입했을 땐 실패라 입력되는 걸 볼 수 있다.

pair 객체 equal_range() 사용 코드

#include <iostream>
#include <set>
using namespace std;
int main(){
	set<int> s;
	for(int i=0;i<10;i++){
		s.insert(10*i);
	}
	
	pair<set<int>::iterator,set<int>::iterator> iter_pair;
	iter_pair=s.equal_range(45);
	if(iter_pair.first!=iter_pair.second)
		cout<<"존재"<<endl;
	else
		cout<<"존재하지않음"<<endl;
	
	return 0;
}

정렬 기준 조건자

 set컨테이너의 기본 정렬 기준자는 less이다. 아래는 greater 기준자를 이용한 코드이다.

#include <iostream>
#include <set>
using namespace std;
int main(){
	set<int,greater<int>> s;
	
	for(int i=0; i<10;i++)
		s.insert(i);
	
	set<int,greater<int>>::iterator iter;
	for(iter=s.begin();iter!=s.end();iter++){
		cout<<*iter<<endl;
	}
}

greater 조건자 실행 결과

 greater 조건자를 이용하여 실행한 모습이다. 조건자 역시 자료형을 명시해야 하고 반복자 역시 조건자를 명시해야 한다.

set 정리

 set은 연관 컨테이너로 노드 단위로 저장된다. 이와 비슷한 multiset, map, multimap들도 거의 같은 멤버 함수, 기능들을 제공한다. 균형 이진트리로 구현되어 검색 기능에서 매우 탁월한 성능을 보여주어 로그 시간의 시간 복잡도를 가진다. 중복을 허용하지 않으며 수학에서 집합과 같은 의미로 쓰인다. 연관 컨테이너와 같은 인터페이스를 제공해 사실상 필요 없는 멤버 함수들도 있다.