[C++] Map, Set 사용하고 구조체까지 넣어보기

Map이란?

• key - value로 구성된 레드블랙트리이다.
• key와 value는 pair 객체 형태로 저장된다.
• key의 중복은 허용되지 않는다. multimap의 경우 중복 key를 허용한다.
• 삽입되면서 키를 기준으로 자동으로 정렬된다. 디폴트로 오름차순이다.

Map 선언과 원소의 접근법

• map<key type, value type, compare<key type>> 변수이름으로 선언한다. 이때 compare에 less를 주면 오름차순으로, greater을 주면 내림차순으로 정렬한다. 디폴트로는 오름차순으로 선언된다.
• m[key] = val;처럼 []를 사용하여 원소를 추가, 수정이 가능하다. []를 사용하여 원소를 추가하는 경우 value가 새로 만들어진 건지, 기존 값이 변경된 건지 구분할 수 없다.
• map.begin() 으로 맵의 시작 iterator을 반환할 수 있다. map.end()는 맵의 끝 다음 itearator을 반환하므로 주의가 필요하다.

Map 원소 삽입 및 삭제

• m.insert({1, 2})와 같이 원소를 삽입할 수 있다.
  • 이때 리턴값으로 pair을 반환한다.
  • 삽입 성공 시 첫 번째 iterator는 삽입된 원소의 iterator를 반환하고 두 번째 iterator는 true를 반환한다.
  • 삽입 실패 시 첫 번째 iterator는 중복된 키의 원소의 iterator를 반환하고 두 번째 iterator는 false를 반환한다. 이를 이용하여 삽입의 성공, 실패를 구분할 수 있다.
  • m.insert(pair<int, int>(1, 2))와 같이 insert 할 수도 있다.
• m.erase(iter) : iter이 가리키는 원소를 제거하고 다음 원소를 가리키는 iterator를 리턴한다. iter은 반복자가 될 수도 있고, 키를 지정하여 삭제할 수 있다.

Map 탐색 및 순회

• m.count(k) : 키값 k의 원소 수를 반환하며 주로 멀티 맵에서 쓰인다.
• m.find(k) : k와 같은 키를 가진 원소의 iterator를 리턴한다. 존재하지 않는 경우 end(())를 리턴한다.
• 맵을 순회할 때는 벡터처럼 for(int i=0; ) 이런 식으로 index로 접근해서는 안된다. map [i]는 i 번째 index의 원소가 아닌 key가 i인 value를 뜻하기 때문이다. 따라서 iterator로 접근해야 한다. for((map<int, int>::iterator iter = map.begin()); )과 같은 방식으로 순회해야 한다.

---

Set

• map과 거의 똑같지만 value는 존재하지 않고 key만 존재하는 balanced binary tree이다.
  • balanced tree란 레드블랙트리처럼 서치 트리이지만 원소의 추가, 삭제에도 트리의 높이가 변하지 않는 트리이다.
• map과 똑같은 메서드를 가진다.

---

Set, Map은 언제 사용할까?

집합과 맵의 큰 특징은 탐색이 빠르고, 삽입 시 정렬이 자동으로 된다는 것이다. 탐색이 빠른 점을 이용해 탐색이 빈번한 알고리즘은 벡터를 이용해서 구현하는 것보다 편리하다. 특히 특정 키에 대해 원소를 계속 삽입해야 한다면 벡터보다 맵을 사용하는 편이 좋다. 또 삽입 시 정렬이 된다는 점에서 삽입할 때마다 정렬이 필요한 알고리즘에서 많이 사용한다. 두 가지 특징을 기억해 뒀다가 잘 써먹어야 한다.

---

Set, Map에 구조체 및 객체 저장

set과 map은 균형 이진 탐색 트리이다. 따라서 키값은 대소비교가 가능해야 한다. 따라서 클래스나 구조체 내부에 operator <를 재정의 하여 구조체 및 객체를 비교 가능하게 정의하면 set, map에 구조체 및 객체를 저장할 수 있다.

class Human
{
private:
    int age;
    int height;
public:
    Human(int _age, int _height) : age(_age), height(_height){}
    bool operator<(const Human& rhs) const    //이게 핵심!
    {
        if (age != rhs.age)
        {
            return age < rhs.age;
        }

        return height < rhs.height;
    }
};

비교 전용 구조체를 만들어 () 연산자를 오버로딩하여 set, map에 넣을 구조체의 비교 기준을 정의한다. 그리고 set 사용 시 두 번째 파라미터로, map은 세 번째 파라미터로 비교 전용 구조체를 넘겨준다.

  struct Student {
    string name;
    int grade;
  };

  struct cmp {
    bool operator () (const Student& stu1, const Student& stu2) const {
        if (stu1.name == stu2.name)
            return stu1.grade < stu2.grade;
        return stu1.name < stu2.name;
    }
  };

  int main()
  {
    set<Student, cmp> students;

    students.insert({ "ryan", 5 });
    students.insert({ "muzi", 3 });
    students.insert({ "muzi", 1 });
    students.insert({ "apeach", 1 });
    students.insert({ "apeach", 1 });

    for (auto& stu : students)
        cout << stu.name << " : " << stu.grade << endl;
  }