17. unordered_set: 해시를 이용한 set

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
>
class unordered_set;

// 1.	기본 생성자
//		아무것도 할당되지 않은 상태로 초기화.
unordered_set<int> s1;

// 2.	bucket_count
//		bucket은 항상 N>2인 보다 2^N 이고, 요소의 수보다 크다.
unordered_set<int> s2(16);							// 16개의 요소를 저장 가능한 공간 할당

// 3.	initializer_list
unordered_set<int> s3 = { 1,2,3 };					// 1 2 3
unordered_set<int> s3_b = { { 1,2,3 }, 16 };		// bucket_count

unordered_set<int> s3_2{ 1,2,3 };
unordered_set<int> s3_2b{ { 1,2,3}, 16 };			// bucket_count

unordered_set<int> s3_3({ 1,2,3 });
unordered_set<int> s3_3b({ 1,2,3 }, 16);			// bucket_count

// 4.	iterator
unordered_set<int> s4(s3.begin(), s3.end());		// 1 2 3
unordered_set<int> s4_2(s3.begin(), s3.end(), 16);	// bucket_count

// 5.	copy
unordered_set<int> s5(s4);							// 1 2 3

// 6. move
unordered_set<int> s6(move(s5));					// 1 2 3

unordered_set<int> s;
s.insert(5);	// 5 
s.emplace(3);	// 5 3

s.emplace(3);	// 이미 존재하기 때문에 아무 일도 일어나지 않는다.

s.erase(3);		// 5
s.erase(3);		// 3은 존재하지 않기 때문에 아무 일도 일어나지 않는다.

unordered_set<int> s1{ 1,3,5,7 };
unordered_set<int> s2{ 2,4,6,8 };

s1.merge(s2);	// 1 3 5 7 2 4 6 8
s1.clear();		// empty

unordered_set<int> s{ 1,2,3,4,5 };
auto v1 = s.extract(3);

v1.value();			// 3

unordered_set<int> s{ 1,2,3, 3,7,9 };	// 1 2 3 7 9

cout << s.count(3) << endl;				// 1


if (auto iter = s.find(3); iter != s.end()) {
	cout << *iter << endl;				// 3
}

if (auto iter = s.find(5); iter != s.end()) {
	cout << *iter << endl;				//	iter == past-the-end
}

cout << (s.contains(1)) << endl;		// 1
cout << (s.contains(5)) << endl;		// 0

auto [begin, end] = s.equal_range(3);			// 3~7
for (auto iter = begin; iter != end; iter++) {
	cout << *iter << ' ';		// 3
}

#include<iostream>
#include<unordered_set>

using namespace std;

void print_buckets(unordered_set<int> s) {
	for (int i = 0; i < s.bucket_count(); i++) {
		cout << i << '\t';
		for (auto iter = s.begin(i); iter != s.end(i); iter++) {
			cout << " -> " << *iter;
		}
		cout << endl;
	}
	cout << endl;
}

int main() {
	cout << endl << "## bucket interface" << endl;

    unordered_set<int> s{ 1,5,8,10,13,15,17 };

    print_buckets(s);


    cout << "8은 " << s.bucket(8) << "번 버킷에 저장되어 있다." << endl;
    cout << "3은 " << s.bucket(3) << "번 버킷에 저장되어 있다." << endl;

    cout << s.bucket_count() << endl;		// 8

    cout << s.bucket_size(0) << endl;		// 2
    cout << s.bucket_size(1) << endl;		// 0
    cout << s.bucket_size(2) << endl;		// 1

}

unordered_set<int> s{ 1,5,8,10,13,15,17 };

cout << "적재율 :" << s.load_factor() << endl;
cout << "최대 적재율 : " << s.max_load_factor() << endl;

cout << "\n현재 구조" << endl;
print_buckets(s);

// 최대 적재율 변경
s.max_load_factor(0.5f);
	
cout << "\n 변경된 구조" << endl;
print_buckets(s);


cout << "\n rehash 구조 (8->16)" << endl;
s.rehash(0);	// 
print_buckets(s);