21. STL hash_map

* STL 컨테이너에는 크게 sequence 컨테이너, 연관 컨테이너로 나뉜다.

- sequence는 앞서 배웠던, vector, list, deque와 같이 순서 있게 자료를 보관한다.

- 연관 컨테이너는 어떠한 Key와 짝을 이루어 자료를 보관한다. python의 딕셔너리를 생각하자.

(종류는 map, set, hash_map, hash_set 등이 있다. 만약 중복되는 key를 사용하려면 multi를 붙인 걸 사용)

- hash사용 시엔 정렬이 필요 없이 빠른 검색을 원할 때,

- hash없이 사용시엔 정렬 된 상태로 자료 저장시에 사용한다.

- hash_map, hash_set은 표준이 아니라서 gcc에서는 using namespace __gnu_cxx;로 커버한다.

* hash_map의 자료구조는 해시 테이블이다.

- Key를 해시 함수에 대입하여, 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장한다.

(db 테이블이라 생각하면 쉽겠다).

버킷번호	슬롯1	슬롯2	슬롯3
0
1
2

* hash_map<Key 자료형, Value 자료형> 변수 명;

- hash_map<int, float> hash1;

* 동적할당 또한 가능하다.

- hash_map<int, float>* hahsh1 = new hash_map<int, float>;

* 주요 멤버는 앞서 배운 sequence container와 유사하다.

- insert

-> 직접 대입, 원하는 위치 대입, 요소 대입(hash_map)

hash_map<int, float> hashmap1, hashmap2;
hashmap1.insert(hash_map<int, float>::value_type(10, 45.6f));
 
hashmap1.insert(hashmap1.begin(), hash_map<int, float>::value_type(11, 50.2f));
 
hashmap2.insert(hashmap1.begin(), hashmap1.end());

- erase

-> 특정 위치에 있는 요소 삭제, 지정한 구역에 있는 요소 삭제, 지정한 키와 같은 요소 삭제.

hashmap1.erase(hashmap1.begin());
hashmap1.erase(hashmap1.begin(), hashmap1.end());
hashmap1.erase(11);

- 검색

- return된 반복자가 const냐 아니냐는 차이로 2가지 방법이 존재하지만 사용법은 같다.

-> const라면 Value, Key 변경 불가 const가 아니라면 Key만 변경 불가.

hash_map<int, float>::iterator FindIter = hashmap1.find(10);
if(FindIter != hashmap1.end()) {
    FindIter->second = 290.44f;
}

=> second가 Value에 해당한다.

# 활용

#include <iostream>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;
 
struct GameCharacter {
  GameCharacter() { }
  GameCharacter(int CharCd, int Level, int Money) {
    _CharCd = CharCd;
    _Level = Level;
    _Money = Money;
  }
  int _CharCd;
  int _Level;
  int _Money;
};
 
void print(hash_map<int, GameCharacter> Characters) {
  hash_map<int, GameCharacter>::iterator iterPos = Characters.begin();
  for(iterPos; iterPos!=Characters.end(); ++iterPos) {
    cout << "캐릭터 코드 : " << iterPos->second._CharCd << " | 레벨 : " << iterPos->second._Level << " | 돈 : " << iterPos->second._Money << endl;
  }
}
 
 
int main() {
  hash_map<int, GameCharacter> Characters;
  GameCharacter Character1(12, 7, 1000);
  GameCharacter Character2(15,20,111000);
  GameCharacter Character3(300,34,3345000);
  Characters.insert(hash_map<int,GameCharacter>::value_type(12, Character1));
  Characters.insert(hash_map<int ,GameCharacter>::value_type(15, Character2));
  Characters.insert(hash_map<int, GameCharacter>::value_type(300, Character3));
  print(Characters);
  
  int Count = Characters.size();
  cout << "저장 된 요소 수 : " << Count << endl;
  
  hash_map<int, GameCharacter>::iterator FindIter = Characters.find(15);
  cout << endl;
  if(Characters.end() == FindIter) {
    cout << "캐릭터 코드가 20인 캐릭터가 없습니다." << endl;
  } 
  else {
    cout << "캐릭터 코드가 15인 캐릭터를 찾았습니다." << endl;
    cout << "캐릭터 코드 : " << FindIter->second._CharCd << " | 레벨 : " << FindIter->second._Level << " | 돈 : " << FindIter->second._Money << endl;
  }
  
  cout << endl;
  print(Characters);
  cout << endl;
  Characters.erase(15);
  print(Characters);
  
  Characters.erase(Characters.begin(), Characters.end());
  cout << endl;
  if(Characters.empty()) {
    cout << "Characters는 비어있습니다." << endl;
  }
  
  return 0;
}

* 결과

캐릭터 코드 : 12 | 레벨 : 7 | 돈 : 1000
캐릭터 코드 : 15 | 레벨 : 20 | 돈 : 111000
캐릭터 코드 : 300 | 레벨 : 34 | 돈 : 3345000
저장 된 요소 수 : 3

캐릭터 코드가 15인 캐릭터를 찾았습니다.
캐릭터 코드 : 15 | 레벨 : 20 | 돈 : 111000

캐릭터 코드 : 12 | 레벨 : 7 | 돈 : 1000
캐릭터 코드 : 15 | 레벨 : 20 | 돈 : 111000
캐릭터 코드 : 300 | 레벨 : 34 | 돈 : 3345000

캐릭터 코드 : 12 | 레벨 : 7 | 돈 : 1000
캐릭터 코드 : 300 | 레벨 : 34 | 돈 : 3345000

Characters는 비어있습니다.

* lower_bound와 upper_bound

- hash_map에 저장한 요소 중에서 Key 값으로 해당 요소의 시작 위치를 얻을 때 사용하는 멤버이다.

ex) 23, 4, 5, 18, 14, 30이라는 순서로 Key값을 가진 요소가 저장 되어 있다면, 18과 크거나 같은 것을 찾으면 18 14 30이 나온다.

- Key가 있다면 해당 요소 반복자를 리턴한다(lower_bound)

- Key가 있다면 그 요소 다음 위치의 반복자를 리턴한다(upper_bound)

- gcc에서는 lower_bound, upper_bound를 정식 멤버로 등록하지 않기 때문에 에러가 난다.

# 사용

#include <iostream>
#include <hash_map>
using namespace std;
using namespace __gnu_cxx;
 
struct GameCharacter {
  GameCharacter() { }
  GameCharacter(int CharCd, int Level, int Money) {
    _CharCd = CharCd;
    _Level = Level;
    _Money = Money;
  }
  int _CharCd;
  int _Level;
  int _Money;
};
 
void print(hash_map<int, GameCharacter> Characters) {
  hash_map<int, GameCharacter>::iterator iterPos = Characters.begin();
  for(iterPos; iterPos!=Characters.end(); ++iterPos) {
    cout << "캐릭터 코드 : " << iterPos->second._CharCd << " | 레벨 : " << iterPos->second._Level << " | 돈 : " << iterPos->second._Money << endl;
  }
}
 
 
int main() {
  hash_map<int, GameCharacter> Characters;
  GameCharacter Character1(12, 7, 1000);
  GameCharacter Character2(15,20,111000);
  GameCharacter Character3(7,34,3345000);
  GameCharacter Character4(14, 12, 112200);
  GameCharacter Character5(25, 3, 5000);
  Characters.insert(hash_map<int,GameCharacter>::value_type(12, Character1));
  Characters.insert(hash_map<int ,GameCharacter>::value_type(15, Character2));
  Characters.insert(hash_map<int, GameCharacter>::value_type(7, Character3));
  Characters.insert(hash_map<int, GameCharacter>::value_type(14, Character4));
  Characters.insert(hash_map<int, GameCharacter>::value_type(25, Character5));
  cout << "저장한 캐릭터 리스트" << endl;
  print(Characters);
  /*
  cout << "lower_bound(14)" << endl;
  hash_map<int, GameCharacter>::iterator Iter = Characters.lower_bound(14);
  while(Iter!=Characters.end()) {
    cout << "캐릭터 코드 : " << Iter->second._CharCd << " | 레벨 : " << Iter->second._Level << " | 돈 : " << Iter->second._Money << endl;
    ++Iter;
  }
  cout << endl;
  
  cout << "upper_bound(7)" << endl;
  Iter = Characters.upper_bound(7);
  while(Iter!= Characters.end()) {
    cout << "캐릭터 코드 : " << Iter->second._CharCd << " | 렙레 : " << Iter->second._Level << " | 돈 : " << Iter->second._Level << endl;
    ++Iter;
  }
  */
  return 0;
}

* 결과(예상)

캐릭터 코드 : 12 | 레벨 : 7 | 돈 : 1000
캐릭터 코드 : 7 | 레벨 : 34 | 돈 : 3345000
캐릭터 코드 : 15 | 레벨 : 20 | 돈 : 111000
캐릭터 코드 : 14 | 레벨 : 12 | 돈 : 112200
캐릭터 코드 : 25 | 레벨 : 3 | 돈 : 5000

lower_bound(14)
캐릭터 코드 : 14 | 레벨 : 12 | 돈 : 112200
캐릭터 코드 : 25 | 레벨 : 3 | 돈 : 5000

upper_bound(7)
캐릭터 코드 : 15 | 레벨 : 20 | 돈 : 111000
캐릭터 코드 : 14 | 레벨 : 12 | 돈 : 112200
캐릭터 코드 : 25 | 레벨 : 3 | 돈 : 5000

* 참고 : Thinking About C++ STL Programming