c++ hash,key. set과 map

| hash및 key에 대한 개념

 

hash와 key를 이용하는 이유는 어떤 값으로 다른 값에 접근하고 싶을 때 사용한다. 예를들어

"abc"라는 문자열을 int값으로 접근하고 싶다면. abc에 1이라는 수를 매칭시켜 둘이 짝이 되도록 하는 것이다.

unordered_set과 unorderd_map이 있는데, 정렬되지 않은 set과,map이라는 것이다. 따라서 접근시간은 O(1)이 된다.

set과 map을 이용하면 접근시간은 O(logn)이 되겟지

각각

#include <unordered_set>과 

#include <unordered_map>을 이용한다.

 

 

|unordered_set 이용

#include <unordered_set>

#include <iosteram>

int main(){

    unordered_set<int> s;

    s.insert(1);

    s.insert(2);

    s.insert(3);

    s.insert(2);



   for(auto iter : s)

   {

        cout << s <<endl;

   }

    return 0;

}

 

출력 :

1,3,2 

즉, 정렬은 안된다. 또한 중복을 허용하지 않는다.

정렬 된 것을 찾고 싶다면 #include<set> 하고 set<int> s을 이용.

지우는 것은 s.erase(1)이렇게하면되고

벡터처럼 s.size()와 s.empty()지원

|unordered_map이용

unorderd_map<key,value>이다.

즉 key를 이용해서 value를 찾는것.

map이용시 key값을 기준으로 정렬.

 

#include <unordered_map>

#include <iostream>



int main()

{

    unordered_map<string,int> m;

    m.insert({"abc",1});

    m["bcd"] = 2;

    m.insert(make_pair("cdf",3));  //   m.insert{a,b} , m[a]=b, m.insert(make_pair(a,b))는 같은 표현. 

   //map의 원소가 pair기반이라 그런지, 출력또한 m.first, m.second이렇게 출력



  for(auto iter : m)

  {

      cout << m.first << m.second <<endl;

  }





    return 0;

}

 

출력 : 

abc1

cdf3

bcd2

이것 또한 중복 허용 안되고, 정렬안된다.

중복 제거 기준은 key기준이지 value기준이 아니다.

정렬 되려면 #include <map>쓰고 map<string,int> m 이렇게 하면 됨.

지우는 것도 key기준

m.erase("abc")이런식.

벡터처럼 m.size()와 m.empty()지원

 

|요소 찾기와, 개수찾기

unorderd_set<string> s;

 

s.insert("abc");

s.insert("bcd");

에서

s.count("abc")는 1이나오고,

s.find("ccc")하면 존재하지 않으니 s.end()를 반환한다. s.find는 반복문에서 많이사용됨.

 

|중복을 허용하기 위해서는

 

뭐 따로 #include 더 할필요는 없고,

unordered_set <int> s;

=> unordered_multiset<int>ms;

map<int,string> m;

=> multimap<int,string> mm;

 

이렇게 하면 됨.

 

|.erase함수 사용 Tip

 

unorderd_multiset<string> s;

이고 s안에 여러 문자열이 들어있다고 해보자.

 

이 때

s.erase(s.begin())과 s.erase(*s.begin())둘다 가능하다

즉 erase안에는 iterator와 key값 둘다 가능하다는 것이다.

s.erase(s.begin())하면 s.begin()즉 첫번째 원소만 제거가된다.

s.erase(*s.begin())은 s의 첫번째 원소와 같은 원소가 모두 제거된다.

 

따라서 s에서 딱 정해서 하나의 원소만 제거하고 싶다면 iterator변수를 넣으면 된다.

 

하지만 추가적으로 s.erase(s.find(3))이렇게 3을 찾아서 지우고 싶다면, 가능하다. 하지만 3이 없을 경우 

런타임 에러가 발생할 수 있으니, if(s.find(3)!=s.end()) s.earse(s.find(3)); 이렇게 해줘야한다

 

|map에서 value기준으로 정렬하려면?

일반적으로 map<int,string> m; 이런식으로 선언하면 값일 넣을 때마다 key값 즉, int기준으로 정렬이 된다.

하지만 string기준으로 정렬을 하고싶다면?

vector를 선언해서 옮긴 후, 정렬을 해야한다. 

예를들어,

map<int,string> m;
m[1] = "a";
m[3] = "b";
m[2] = "c";

vector<pair<int,string>> v;

for(auto iter : m)
{
	v.push_back(iter.first,iter.second);
}

sort(v.begin(),v.end(),cmp);

/*
bool cmp(pair<int,string> a, pair<int,string> b)
{
	return a.second < b. second; //string기준으로 오름차순 정렬
}



*/

 이렇게 짜야 m의 value를 기준으로 오름차순으로 정렬이 된다.