map자료구조에 대해 질문있습니다..

Question

저번에 Bfs를 길찾기에 적용하는 강의를 듣고 코드를 따라쳤는데 안되더라구요. 길찾기가 너무 엉뚱하게 되었습니다. 그래서 몇시간동안 골머리를 썩다가 빨간 동그라미를 쳐놓은 부분의 조건을 y == other.y로 해놨었더라고요;; 일단 operator<를 선언해줘야 하는것도 처음엔 이해가 되지 않았는데 map자료형이 자료를 저장할때마다 정렬하기 때문인가 싶어서 넘어갔습니다.   근데 제가 오타를 찾기위해서 디버깅을 하는도중에 map에 값의 삽입이 이상하게 동작하더라고요.. 저 parent가 nextPos라는 key값을 가지고 있지 않은데도 불구하고 값을 저장하지 않더라고요..   ex) parent의 사이즈는 1이고 parent[Pos{1,1}] == Pos{1,1} 였습니다. 여기서 parent[Pos{1,2}] = Pos{1,1}; 를 했음에도 불구하고 parent는 바뀐거 없이 그대로였습니다.. 또 이해할수가없는게 parent[Pos{1,3}] = Pos{1,2}; 를 실행하면 parent에 값이 삽입되는게 아니라 parent[Pos{1,1}] 의 value가  Pos{1,2}가 되어버리더군요.. ㅠㅠ 사이즈는 그대로 1이었습니다.   구글에 map을 검색했는데 어떤방식으로 동작하는지 도통 이해가 되지않습니다.. 이에 질문드립니다..

Rookiss · Answer

일단 operator<를 선언해줘야 하는것도 처음엔 이해가 되지 않았는데 map자료형이 자료를 저장할때마다 정렬하기 때문인가 싶어서 넘어갔습니다. 네 맞습니다.  map은 Red-Black Tree 방식이고 데이터를 넣어주거나 삭제할 때 트리가 다시 균형을 맞추기 위해 이리 저리 데이터 위치를 변경시켜야 하고 그것을 < 비교를 이용해 합니다. 따라서 맵에 넣는 데이터는 operator<를 지원해야 합니다. 저 parent가 nextPos라는 key값을 가지고 있지 않은데도 불구하고 값을 저장하지 않더라고요.. 질문이 이해가 안 갑니다. 혹시 key값이 없는데 데이터가 저장된게 이상한건가요? C++ map에서 map[키] = 값;을 하면 해당 키를 들고 있건 말건 상관없이 데이터를 덮어 씁니다. 여기서 parent[Pos{1,2}] = Pos{1,1}; 를 했음에도 불구하고 parent는 바뀐거 없이 그대로였습니다.. 이건 아까 operator<를 잘못 만들어줘서 그런 것 같습니다. 저렇게 작동하는건 정상적인 상황이 아니고 struct Pos 정의에 문제가 있을 확률이 높습니다. 다시 확인해보시기 바랍니다.