22. STL map

* map

- hash_map과 같은 연관 컨테이너 중 하나이다.

- hash_map과 사용법이 대부분 똑같다.

- map의 자료구조는 tree이다(Red-Black tree)

- 최상위 노드(root node), 그 하위 leaf node(자식이 없는 노드), 자식이 존재하면 parent node, 자식은 child node 등으로 부른다.

- map은 많은 자료를 정렬하여 저장하고 있고, 빠른 검색을 필요로 할 때 이용한다.

- map은 내부에서 자동 정렬을 하고, hash_map은 정렬하지 않는다.

(즉, 정렬이 필요하지 않은 곳에서 map 사용은 낭비다)

-> 정렬해야되고, 많은자료를 저장하고, 검색이 빨라야하며, 빈번하게 삽입/삭제가 일어나지 않을 때 map은 아주 유용하다.

# 사용

- 헤더 : #include <map>

- map<key 자료형, value 자료형> 변수명; // map<int, int> map1; => 오름차순 정렬.

- 내림차순 정렬이 필요하다면.

-> map<key 자료형, value 자료형, 비교 함수> 변수명; // map<int, int, greater<int>> map; 

- greater 같은 걸 STL 알고리즘이라고 하는데, 추후 설명하겠다.

- 동적할당은 hash_map을 참조하자.

# 예시

#include <iostream>
#include <map>
#include <string.h>
using namespace std;
 
struct Item {
  char Name[32];
  char Kind;
  int BuyMoney;
  int SkillCd;
};
 
int main() {
  map< char*, Item > Items;
  map< char*, Item >::iterator IterPos;
  typedef pair< char*, Item > ItemPair;
  Item Item1, Item2, Item3;
  strncpy( Item1.Name, "긴칼", 32 );
  Item1.Kind = 1; Item1.BuyMoney = 200; Item1.SkillCd = 0;
  strncpy( Item2.Name, "성스러운 방패", 32 );
  Item2.Kind = 2; Item2.BuyMoney = 1000; Item2.SkillCd = 4;
  strncpy( Item3.Name, "해머", 32 );
  Item3.Kind = 1; Item3.BuyMoney = 500; Item3.SkillCd = 0;
  Items.insert( map< char*, Item >::value_type(Item2.Name, Item2) );
  Items.insert( ItemPair(Item1.Name, Item1) );
  if( false == Items.empty() ) cout << "저장된 아이템 개수 : " << Items.size() << endl;
  
  for(IterPos=Items.begin(); IterPos!=Items.end(); ++IterPos) {
    cout << "이름 : " << IterPos->first << " 가격 : " << IterPos->second.BuyMoney << endl;
  }
  
  IterPos = Items.find("긴칼");
  if(IterPos == Items.end()) {
    cout << "긴칼이 없습니다." << endl;
  }
  
  cout << endl;
  
  cout << "올림차순으로 되어 있는 map" << endl;
  map<string, Item, less<string>> Items2;
  map<string, Item, less<string>>::iterator IterPos2;
  
  Items2.insert(map<string, Item>::value_type(Item2.Name, Item2));
  Items2.insert(ItemPair(Item1.Name, Item1));
  Items2[Item3.Name] = Item3;
  
  for(IterPos2 = Items2.begin(); IterPos2!=Items2.end(); ++IterPos2) {
    cout << "이름 : " << IterPos2->first << ", 가격 : " << IterPos2->second.BuyMoney << endl;
  }
  cout << endl;
  cout << "해머의 가격은 얼마 ? ";
  IterPos2 = Items2.find("해머");
  if(IterPos2 == Items2.end()) cout << "해머는 없습니다." << endl;
  else cout << IterPos2->second.BuyMoney << endl;
  cout <<endl;
  
  IterPos2 = Items2.find("긴칼");
  if(IterPos2 != Items2.end()) Items2.erase(IterPos2);
  
  cout << "Items2에 있는 아이템 갯수 : " << Items2.size() << endl;
  
  return 0;
}

* 결과

저장된 아이템 개수 : 2
이름 : 성스러운 방패 가격 : 1000
이름 : 긴칼 가격 : 200
긴칼이 없습니다.

올림차순으로 되어 있는 map
이름 : 긴칼, 가격 : 200
이름 : 성스러운 방패, 가격 : 1000
이름 : 해머, 가격 : 500

해머의 가격은 얼마 ? 500

Items2에 있는 아이템 갯수 : 2

* 과제

- multimap을 이용해, key를 가격으로 해서 내림차순으로 정렬하는 코드를 작성하라.

#include <iostream>
#include <string.h>
#include <map>
 
using namespace std;
 
struct Item{
  char Name[32];
  char Kind;
  int BuyMoney;
  int SkillCd;
};
 
void print(multimap<int, Item, greater<int>> Items) {
  for(multimap<int, Item>::iterator iterPos = Items.begin(); iterPos != Items.end(); ++iterPos) {
    cout << "돈 : " << iterPos->first << " | 장비명 : " << iterPos->second.Name <<endl;
  }
}
 
int main() {
  multimap<int, Item, greater<int>> Items;
  Item Item1, Item2, Item3, Item4;
  strncpy(Item1.Name, "긴칼", 32);
  Item1.Kind = 1; Item1.BuyMoney = 200; Item1.SkillCd = 0;
  strncpy(Item2.Name, "성스러운 방패", 32);
  Item2.Kind = 2; Item2.BuyMoney = 1000; Item2.SkillCd = 4;
  strncpy(Item3.Name, "해머", 32);
  Item3.Kind = 1; Item3.BuyMoney = 500; Item3.SkillCd = 0;
  strncpy(Item4.Name, "용왕의 투구", 32);
  Item4.Kind = 1; Item4.BuyMoney = 200; Item4.SkillCd = 0;
  Items.insert(multimap<int, Item>::value_type(Item1.BuyMoney, Item1));
  Items.insert(multimap<int, Item>::value_type(Item2.BuyMoney, Item2));
  Items.insert(multimap<int, Item>::value_type(Item3.BuyMoney, Item3));
  Items.insert(multimap<int, Item>::value_type(Item4.BuyMoney, Item4));
  print(Items);
  return 0;
}

# 결과

  
돈 : 1000 | 장비명 : 성스러운 방패
돈 : 500 | 장비명 : 해머
돈 : 200 | 장비명 : 긴칼
돈 : 200 | 장비명 : 용왕의 투구