인프런 커뮤니티 질문&답변
작성한 질문수
map자료구조에 대해 질문있습니다..
해결된 질문
작성
·
283
0
저번에 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을 검색했는데 어떤방식으로 동작하는지 도통 이해가 되지않습니다.. 이에 질문드립니다..
답변 1
1
일단 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 정의에 문제가 있을 확률이 높습니다.
다시 확인해보시기 바랍니다.
아 2일간 여행을다녀오느라 답변을 지금 확인했네요ㅠㅠ
map[없던키] = 값;
형식이었는데 맵에 키/값이 저장이 안되는 상황입니다.