[C++] Map의 Key로 Class/Struct 넣기

오늘은 "호랭이아인교" 병아리 블로그를 운영하는 김드스님의 포스팅을 훔쳐왔다 !! 똑같이 포스팅 해도 된다고 허락을 받았기 때문에 출처를 밝히고 거의 80% 같은 내용을 포스팅한다. 고마워요 김드스님 ~

---

** Map의 Key 값으로 Class/Struct 넣기 **

🎃목표

map의 key값으로 기본적인 데이터 타입(int, string, float, double...)이 아닌 우리가 직접 만든 타입(user defined type)을 넣어보자.

🎃특징

1. Map은 key(키)와 Value(값)이 쌍으로 이루어진 자료구조로 키를 통해 값에 접근 할 수 있도록 만들어져 있다. 
2. map은 key(키)의 중복을 허용하지 않고, value(값)의 중복은 허용한다.  
3. c++의 map은 레드블랙트리를 기반으로 구현이 되어있다. 

🎃문제점

위 의 3번 특징으로 인해 우리가 직접 만든 타입을 그냥 key값으로 사용할 시 컴파일 오류를 발생시킨다.

🎃해결방법

map, set은 균형 이진트리로 구현이 되어 있는 연관 컨테이너로 대소비교가 가능해야한다. 우리가 직접 만든 타입에 대소비교연산을 만들어줘야한다!! 무엇으로 ? operator로 ~

---

** 구현 ** 

class CMapKey
{
public:
    CMapKey(const int pKey1, const int pKey2) : mKey1(pKey1), mKey2(pKey2) {}

public:
    bool operator<(const CMapKey& pOther) const
    {
       return mKey1 < pOther.mKey1 ? true : ((mKey2 < pOther.mKey2) ? true : false);
    }
 }

operator< 를 정의해 주는 것 까지는 좋았는데 위의  opeator<는 Map의 sorting에 쓰일 수는 없다.

생각없이 위와 같은 방식으로 조건을 걸어 주고 코드를 실행했을때 특정 상황에서 터지게 되는데 내 생각에는논리적으로 문제가 없다고 생각을 해서 한참을 고민했다...

다른분이 알려주시지 않았으면 아직도 모를 것 같은데 터지는 부분은 아래 코드이며

template<class _Pr,
class _Ty1,
class _Ty2> inline
constexpr bool _Debug_lt_pred(_Pr&& _Pred, _Ty1&& _Left, _Ty2&& _Right)
noexcept(
    noexcept(_Pred(_Left, _Right))
    && noexcept(_Pred(_Right, _Left))) 
    {
    // test if _Pred(_Left, _Right) and _Pred is strict weak ordering, when the arguments are the cv-same-type
    const auto _Result = static_cast<bool>(_Pred(_Left, _Right));
    if (_Result) {
        _STL_VERIFY(!_Pred(_Right, _Left), "invalid comparator");
    }

    return _Result;
}

 

map은 레드 블랙 트리 구조의 정렬 컨테이너이기 때문에 emplace시에 삽입될 원소의 위치를 찾기 위한 비교를 진행하게 된다. 위 코드에서  noexcept(_Pred(_Left,_Right)) &&noexcept(_Pred(_Right,_Left)))  비교할 왼쪽노드(_Left)와 비교당할 오른쪽 노드(_Right)에 대한 비교를 진행 할때 (_Left)/(_Right)비교 한번, 위치를 바꿔서  (_Right)/(_Left) 비교를 한 번 진행하여 두번의 비교 결과가 일치하면 잘못된 비교"invaild comparator"오류를 뱉는다. 

이해가 쉽게 될 수 있도록 글의 가장 처음에 첨부한 코드의 operator를 예로 들어 설명하자면 Key값이 int key1, int key2인 두개의 노드를 비교함에 있어

A Node	mKey1 = 2, mKey2 = 5	(2, 5)
B Node	mKey1 = 1, mKey2 = 6	(1, 6)

🔹operator< (A, B)

1.1.  mKey1 < pOther.mKey1 → ( 2 < 1) : false

1.2. mKey2 < pOther.mKey2 → ( 5 < 6 ) : true

return true;

🔹operator< (B, A)

2.1.  mKey1 < pOther.mKey1 → ( 1 < 2) : true 

return true;

---

해당 비교식에서는 operator< (A, B) 와 operator< (B, A)가 모두 true로 같기 때문에 대소비교를 할 수 없고 그래서 삽입 시에 터지는 코드가 되는 것이다.

Map은 삽입 시에 양쪽 비교를 통해 해당 정렬이 안전한 지에 대한 검사를 하기 때문에 발생한 문제 였고 아래와 같이 CMapKey class의 operator를 바꿔줌으로써 문제를 해결했다.

bool operator<(const CMapKey& pOther) const
{
    if (mKey1 == pOther.mKey1)
    {
        return mKey2 < pOther.mKey2;
    }

    return mKey1 < pOther.mKey1;
}

 

** 출처 **

호랭이아인교 (tistory.com)