set 컨테이너

Red black tree 기반의 균형 이진트리로 구성되어 있다. key, value 중 key 값으로만 구성되어 있고, key의 중복은 없다. 기본 정렬은 오름차순으로 선언 시 바꿀 수 있다. 템플릿 인자 2번째에 사용자 정의 정렬 함수를 넣어줄 수 있다.

 

그리고 insert 함수는 pair<template<T>, bool> 반환형을 가지고 있는데, bool 값을 보고 값이 중복되는지 아닌지를 확인할 수 있다

#include <set>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

struct cmp {
	bool operator()(const int &u, const int &v) {
		return u > v;
	}
};

int main(void) {
	set<int, cmp> s1;
	s1.insert(10);
	s1.insert(20);

	for (set<int>::iterator it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << '\n';
	}

	pair<set<int>::iterator, bool> pr;
	pr = s1.insert(30);
	cout << *pr.first << ' ' << pr.second << '\n';

	pr = s1.insert(20);
	cout << *pr.first << ' ' << pr.second << '\n';

	return 0;
}

 

set을 효율적으로 쓸 수 있는 상황은 중복을 피하면서 key 값의 범위로 연속적이지 않는 것이다. 예를 들어 10^12까지 모든 값들이 들어오지는 않지만 범위가 저렇게 설정되어 있고, 방문 여부를 따져야 한다면(중복을 피한다) set을 쓰는 것이 올바른 자료구조 선택이다