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을 쓰는 것이 올바른 자료구조 선택이다

 

	#include <set>
	#include <queue>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	typedef long long ll;
	struct NODE {
	ll s, e, v;
	NODE(ll s = 0, ll e = 0, ll v = 0) :
	s(s), e(e), v(v) {
	}
	};
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	set<ll> visit;
	queue<NODE> q;
	vector<ll> res;
	for (ll i = 1; i <= 1000000; ++i) {
	if (i*(i + 1) <= 1e12) {
	visit.insert(i*(i + 1));
	q.push(NODE(i, i + 1, i * (i + 1)));
	res.push_back(i*(i + 1));
	}
	}
	while (!q.empty()) {
	NODE now = q.front();
	q.pop();
	NODE next;
	next = now;
	next.s -= 1;
	next.v *= next.s;
	if (next.s >= 1 && visit.find(next.v) == visit.end() && next.v <= 1e12) {
	q.push(next);
	visit.insert(next.v);
	res.push_back(next.v);
	}
	next = now;
	next.e += 1;
	next.v *= next.e;
	if (next.v <= 1e12 && visit.find(next.v) == visit.end()) {
	q.push(next);
	visit.insert(next.v);
	res.push_back(next.v);
	}
	}
	res.push_back(0);
	sort(res.begin(), res.end());
	cout << res.size() << '\n';
	cout << res[n] << '\n';
	return 0;
	}

view raw set.cpp hosted with ❤ by GitHub