C++ set, map(hash)

예시코드)
https://github.com/GbLeem/CPP_Study/tree/main/NoCode
67.cpp ~ 72.cpp

<까먹지 말기>
함수 앞의 const : 리턴 값을 상수화
함수 뒤의 const : 멤버 변수를 수정하지 않을거임

std::set

• 순서 없는 정보들의 집합
• red-black tree or balanced binary search tree로 구현
  • child 노드의 왼쪽에는 자신보다 작은 것, 오른쪽에는 큰 것 오는 구조
• 시간 복잡도
  • find : O(logN)
  • insert/delete : O(logN)
• set은 중복을 허락하지 않는다. <-> multi_set : 중복이 있는 set
• set은 스스로 내부적으로 정렬되어있다. <-> unordered_set : 정렬 특성이 없는 set

#include<iostream>
#include<set>

int main()
{
	std::set<int>nums{ 1,2,3,4,5 };
	
	nums.emplace(3);
	nums.emplace(3);
	nums.emplace(3);
	nums.emplace(3);
	//1 2 3 4 5 출력

	nums.emplace(-1);
	nums.emplace(100);
	nums.emplace(2);
	//-1 1 2 3 4 5 100 출력

	for (const int num : nums)
	{
		std::cout << num << " "; 
	}
	std::cout << std::endl;

	return 0;
}

• 구조체 이용

#include<iostream>
#include<set>

struct customFn
{
	bool operator() (const int lhs, const int rhs) const
	{
		return lhs > rhs; //내림차순 정렬
	}
};
int main()
{
	std::set<int, customFn>nums{ 1,2,3,4,5 };

	nums.emplace(-1);
	nums.emplace(100);
	nums.emplace(2);
	//100 5 4 3 2 1 -1 출력

	for (const int num : nums)
	{
		std::cout << num << " ";
	}
	std::cout << std::endl;

	return 0;
}

• 클래스 이용
  • set의 경우 비교 오퍼레이터가 있어야 set을 구성할 수 있으므로 operator 정의해주기

#include<iostream>
#include<set>
#include<string>

class Cat
{
public:
	Cat(int age, std::string name)
		:mAge(age)
		,mName(name)
	{}

	void speak() const
	{
		std::cout << mAge << " " << mName << std::endl;
	}

	int age() const
	{
		return mAge;
	}
	
	const std::string& name() const
	{
		return mName;
	}
private:
	int mAge;
	std::string mName;
};
bool operator < (const Cat &cat1, const Cat &cat2) //operator 정의
{
	return cat1.age() < cat2.age();
}

int main()
{
	std::set<Cat> cats; 
	cats.emplace(1, "kitty");
	cats.emplace(2, "nabi");
	cats.emplace(2, "meow"); //set의 특징에 의해 set에 들어오지 않음(2 중복)

	for (const auto &cat : cats)
	{
		cat.speak();
	}
	std::cout << std::endl;
}

std::multiset

• multiset의 특징
  • 중복을 허용하는 set
  • set이기 때문에 정렬하는 특성은 가지고 있다.
• 기본 예시 코드

#include<iostream>
#include<set>

int main()
{
	std::multiset<int> nums{ 1,2,7,7,4,5,5 }; 

	for (const auto& num : nums)
	{
		std::cout << num << " "; //1 2 4 5 5 7 7 출력
	}
	std::cout << std::endl;
}

std::map

• set에 key value concept를 추가한 형태 (key, value 쌍으로 구성)
• tree를 구성할 때 key값을 기준으로 구성된다.
• 중복 허용 x
• numPairs[1] = 1001; key 값을 통해 value값을 바꿀 수 있다.
• numPairs[6]; 지정하지 않은 key값인 6에 접근을 하는 경우 원치 않은 동작 발생
• .first를 통해 key 값, .second를 통해 value 값을 얻을 수 있다.

#include<iostream>
#include<map>
#include<string>

int main()
{
	std::map<int, int> numPairs;
	std::map<int, std::string> nameLists;

	numPairs.emplace(1, 101);
	numPairs.emplace(2, 102);
	numPairs.emplace(3, 103);
	numPairs.emplace(4, 104);
	numPairs.emplace(5, 105);
	numPairs.emplace(5, 505); //중복 허용 x
    
	for (const auto &num:numPairs)
	{
		std::cout << num.first<< " " << num.second << std::endl;
	}

	//int와 string 짝으로도 사용 가능
	nameLists.emplace(1, "cat");
	nameLists.emplace(3, "dog");
	nameLists.emplace(2, "person");

	for (const auto& name : nameLists)
	{
		std::cout << name.first << ", " << name.second << std::endl; 
        //1, cat 2, person 3, dog 출력
	}

	return 0;
}

std::unordered_set

• insert, delete, find : O(1)의 시간 복잡도
  • find : 키 값의 hash 값을 구함 -> hash 값으로 bucket count 값 구함 -> 해당 count에 키 값이 있는지 확인 -> O(1)
  • 값을 계속해서 넣다보면 bucket count가 늘어나고 확보된 bucket count를 초과하는 경우 rehasing이 일어난다 -> O(n)
  • reserve()를 통해 미리 공간을 확보해 두는 것이 좋다.
  • max_load_factor()로 최대 공간을 정해둘 수 있다.
• hash set을 이용한다.
• heap 공간에 저장된다.
  • hash 값들은 큰 값이기 때문에 bucket에 넣어두고 가져와서 쓰는 방식이다.
• cf) hash function
  • 특정 key 값을 넣으면 해당 key 값에는 하나의 value 값만 나오는 구조이다.
  • 다른 key 값에서 같은 value가 나올 경우는 매우 희박해야 한다.

#include<iostream>
#include<string>
#include<unordered_set>>

int main()
{
	std::unordered_set<std::string> uordSet; //heap 공간에 저장
	uordSet.reserve(1000);

	uordSet.emplace("abc");
	uordSet.emplace("def");
	uordSet.emplace("gji");
	uordSet.emplace("jkl");

	std::cout << "bucket: " << uordSet.bucket_count() << std::endl; // bucket count

	std::cout << "abc: " << std::hash<std::string>{}("abc") << "bucket num: " << uordSet.bucket("abc") << std::endl;
	std::cout << "def: " << std::hash<std::string>{}("def") << "bucket num: " << uordSet.bucket("def") << std::endl;
	std::cout << "gji: " << std::hash<std::string>{}("gji") << "bucket num: " << uordSet.bucket("gji") << std::endl;
	std::cout << "jkl: " << std::hash<std::string>{}("jkl") << "bucket num: " << uordSet.bucket("jkl") << std::endl;

	uordSet.find("abc"); 
	uordSet.erase("abc");

	return 0;
}

hash set

• Cat hash를 만들기

#include<iostream>
#include<string>
#include<unordered_set>

//Cat class
class Cat
{
public:
	Cat(int age, std::string name)
		:mAge(age)
		, mName(name)
	{}

	void speak() const
	{
		std::cout << mAge << " " << mName << std::endl;
	}

	int age() const
	{
		return mAge;
	}
	const std::string& name() const
	{
		return mName;
	}
private:
	int mAge;
	std::string mName;
};

//Cat hash
struct CatHash 
{
	std::size_t operator()(Cat const& c) const noexcept
	{
		std::size_t h1 = std::hash<int>{}(c.age());
		std::size_t h2 = std::hash<std::string>{}(c.name());
		return h1 ^ h2;
	}
};

//Cat hash namespace version
namespace std 
{
	template<>
	struct hash<Cat>
	{
		std::size_t operator()(Cat const& c) const noexcept
		{
			std::size_t h1 = std::hash<int>{}(c.age());
			std::size_t h2 = std::hash<std::string>{}(c.name());
			return h1 ^ h2;
		}
	};
}


bool operator ==(const Cat& c1, const Cat& c2) //equality 정의
{
	return (c1.age() == c2.age() && c1.name() == c2.name());
}

int main()
{
	Cat kitty{ 1,"kitty" };
	Cat nabi{ 2,"nabi" };

	std::unordered_set<Cat, CatHash>cats;
	//std::unordered_multiset<Cat, CatHash>cats; 중복 허용

	//std::unordered_set<Cat>cats; //namespace 사용 version

	cats.emplace(kitty);
	cats.emplace(nabi);
	cats.emplace(2, "nabi");

	for (const auto& cat : cats)
	{
		cat.speak();
	}
    //1 kitty 2 nabi 출력
    
	return 0;
}

std::unordered_map

• key와 value 쌍으로 구성 + hash로 구성
• find, insert, delete : O(1)

#include<iostream>
#include<unordered_map>
#include<string>

int main()
{
	std::unordered_map<int, std::string> idNames;
	//std::unordered_multimap<int, std::string> idNames; 중복 허용
	idNames.emplace(1234, "Leem");
	idNames.emplace(1111, "Kim");
	idNames.emplace(9999, "Park");

	idNames.emplace(1111, "KIMKIM"); //중복 제거
	idNames[1111] = "KIM";

	for (const auto& name : idNames)
	{
		std::cout << name.first << " " << name.second << std::endl;
	}
}

정리

	구성	시간 복잡도	필요한 operator	sorted여부	value값 고려 여부	rehasing 여부
set	tree	O(logN)	comparison	o	x	x
map	tree	O(logN)	comparison	o	o	x
unordered_set	hash	O(1)	hash function & equality	x	x	o
unordered_map	hash	O(1)	hash function & equality	x	o	o

• multi- 붙어있지 않으면 중복을 제거해 준다는 공통점 존재
• tip) unordered_map을 가장 많이 사용한다.