C++ - map, set

Map

• Key를 이용해 데이터를 가져옴
• key와 값의 쌍들을 저장
• Key는 중볼될 수 없음
• C++ 맵은 자동 정렬되는 컨테이너 ... ??? <-- unordered map 존재함.
• 이진 탐색 트리(binary search tree) 기반
  • 오름 차순
  • O(logN)
• map은 Hash map이 아님 정렬되는 map임
  • 기대했던 Hash 자료 구조가 아님(C# 의 Dictionary 처럼...)
• EX)

#include <map>

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

  --> 추가 방법 1
  simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
  simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

  --> 추가 방법 2
  simpleScoreMap["Mocha"] = 0;   <-- 대입 하는 문법만으로도 추가 가능.


  int data = simpleScoreMap["Coco"]; <-- 이렇게 읽기만 하더라도 추가

  std::cout << "Current Size : " << simpleScoreMap.size() << std::endl;
}

map 요소 삽입

• 두 데이터를 한 단위로 저장하는 구조

std::pair<std::string, int> student1("Coco", 10);
//pair.first;
//pairs.second;
simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

• insert()
  • 새요소를 map에 삽입한다.
  • 반복자와 bool 값을 한 쌍으로 반환
    • 반복자는 요소를 가리키고
    • bool 값은 삽입 결과를 알려줌
    • Web 방식 예외 처리
  • 키를 중복으로 삽입할 수 없음

simpleScoreMap.insert(std::pari<std::string, int>("Mocha", 100));
// <iterator, tru> 를 반환한다.

simpleScoreMap.insert(std::pari<std::string, int>("Mocha", 0));// 중복 삽입
// <iterator, false>를 반환한다.
// 삽입 실패

operator[]

• key에 대응하는 값을 참조로 반환한다.
• 'map에 키가 없으면 새 요소를 삽입'
  • 이것땜에 실수 하는 경우 있음
• map에 키가 이미 있으면 그 값을 덮어씀

std::map<std::string, int> simpleScoreMap;
simpleScoreMap["Coco"] = 10;// 새 요소를 삽입한다.
simpleScoreMap["Coco"] = 50;// "Coco"의 값을 덮어 쓴다.
// 값이 중복 되어 있는지 확인할 수 없다,,, find 함수로 찾아야 함.

return simpleScoreMap["Coco"];
// "만약 Coco가 없으면 기본값을 삽입해서 반환해 주기에 실수 할 수 있다."

자동 정렬

simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));
simpleScoreMap.insert(std::pair<std::string, int>("Coco", 50));

for(std::map<std::string, int>::iterator it = simpleScoreMap.begin(); it != simpleScoreMap.end(); ++it)
{
  std::cout << "(" << it->first <<", " << it->second << ")" << std::endl;
}

// "map은 vector처럼 순서가 없으니 key에 따라 정렬이 된다."

// OUTPUT>>
//   "Coco", 50
// "Mocha", 100

요소 찾기

#include <map>

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

  simpleScoreMap.insert(std::pair<std::string, int>("Mocha", 100));

  // 찾음
  std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");

  if(it != simpleScoreMap.end())
  {
    it->second = 80;
  }
}

• "iterator로 컨테이너에 공통된 인터페이스를 구현할 수 있다"

find()

• map안에서 key를 찾으면 그에 대응하는 값을 참조로 반환한다.
• 못 찾으면 end()를 반환
  std::map<std::string, int>::iterator it = simpleScoreMap.find("Mocha");

swap(), clear()

• void swap(map& other);
  • 두 map의 키와 값을 서로 맞바꾼다.
• void clear();
  • map을 비운다.

std::map<std::string, int> scoreMap;// ["Mocha", 10], ["Coco", 40]
std::map<std::string, int> anotherScoreMap;// ["Nana", 100]
scoreMap.swap( anotherScoreMap)
// scoreMap : ["Nana", 100]
// anotherScoreMap : ["Mocha", 10], ["Coco", 40]
anotherScoreMap.clear()

erase()

• map의 요소들을 제거한다.

  • void erase(iterator position);
  • size_type erase(const key_type& key);
  • void erase(iterator first, iterator last);

• 삭제 방법 1

std::map<std::string, int>::iterator foundIt = simpleScoreMap.find("Coco");
simpleScoreMap.erase(foundIt);

• 삭제 방법 2

simpleScoreMap.erase("Coco");
// 좀더 편하고 일반적인 방식

EX) 개체를 키로 사용하기

class StudentInfo
{
public:
private:
  std::string mName;
  std::string mStudentID
}

int main()
{
  std::map<StudentInfo, int> scores;

  scores.insert(std::pair<StudentInfo, int>(StudentInfo("Poppy", "a556"), 30));
  scores.insert(std::pair<StudentInfo, int>(StudentInfo("Lulu", "a112"), 70));

  std::cout << scores[StudentInfo("Poppy", "a556")] << std::endl;
}

• 위의 코드가 잘 동작 할 까??

  • NO, Error 발생
  • StudentInfo 가 비교 연산자가 없어서... 왜 비교 연산자가 필요할까??
    • map은 Hash map이 아님 정렬되는 map임
    • "Map은 항상 정렬이 된다. 그래서 Key값 끼리 비교가 가능 해야 한다".

• StudentInfo 클래스의 '<' 연산자 오버로딩을 해주면 된다.

bool StudentInfo::operator<(const StudentInfo& other) const
{
  if(mName == other.mName)
  {
    return mStudentID < other.mStudentID;
  }

  return mName < other.mName;
}

• 요소들을 정렬하는 또 다른 방법
  • map을 만들 때 비교함수(comparer)를 넣을 수도 있음

  struct StudentInfoComparer
  {
    bool operator()(const StudentInfo& left, const StudentInfo& right) const
    {
      return (left.getName() < right.getName());
    }
  }
  std::map<StudentInfo, int, StudentInfoComparer> Scores;
  // operator< 를 구현하는게 더 좋지만 이 방법을 사용 못하는 경우도 있다. 
  // 만약 StudentInfo가 남이 만든 Code이거나 수정 할 수 없을 때는 이 방법이 유용할 수 있다.

장점

• list, vector 보다 탐색 속도가 빠름

단점

• 자동으로 정렬됨.
• 해쉬맵이 아님, 따라서 O(1)이 아님. O(logN)
• C++11에서 해결책이 있음.

Set

• "Set은 map 과 거의 같다"

  • "map에서 값을 뺀것과 같다."

• 역시 정렬되는 컨테이너

• "중복되지 않는 키를 요소로 저장함"

• 역시 이진 탐색 트리 기반

  • 오름 차순

• 장점과 단점도 map과 같음

#include <set>
int main()
{
  std::set<int> scores;
  scores.insert(10);
  scores.insert(20);

  for(std::set<int>::iterator it = scores.begin(); it != scores.end(); ++it)
  {
    std::cout << *it << std::endl;
  }
  return 0;
}