[게임 프로그래머 입문 올인원] STL Container : map (73강)

A. STL Container  : map

1. map

a.  map이란?

🌟 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조

 

표준 헤더 파일 <map>을 포함하여 사용

ex) std::map<int, std::string>은 정수형 키와 문자열 값으로 이루어진 map

 

set이랑 거의 동시에 감

개발 초반이나 매니저를 구현할때 사용

 

b. map의 특징

• 키와 값의 쌍으로 데이터를 저장 (키는 유일)
• 일반적으로 빠른 검색 속도를 제공하는 자료구조
• 내부적으로 레드-블랙 트리(Red-Black Tree)와 같은 균형 이진 탐색 트리가 사용되어 키의 정렬된 상태를 유지
• 따라서 시간복잡도는 O(log n)

 

c. map의 기능 

• 키를 기반으로 한 검색, 추가, 삭제, 수정 등의 연산을 제공
• 데이터의 삽입 시 자동으로 정렬되어 저장

 

d. map이 필요한 이유

1. 키-값 쌍 관리: Map은 키(key)와 값(value)의 쌍을 저장하고 이를 관리하는 자료구조. 이는 데이터를 특정 키에 매핑(mapping)하여 저장하고, 이 키를 통해 해당 값을 검색할 수 있도록 해줌
2. 데이터 검색과 업데이트: 맵은 특정 키를 사용하여 저장된 값을 빠르게 검색. 또한, 맵은 키를 사용하여 해당 값의 업데이트 및 수정도 용이
3. 유연성과 다양한 용도: 데이터베이스에서 특정 항목을 검색, 저장, 설정 구성을 관리, 알고리즘에서 중간 결과를 저장, 빠른 검색이 필요한 경우 등 다양한 상황에서 활용
4. 효율성: 맵은 효율적인 데이터 검색을 위해 해시 테이블(hash table)이나 트리(tree)와 같은 내부 구현을 사용. 이는 많은 데이터에 대해 빠른 검색과 업데이트를 제공
5. 중복 키 관리: 맵은 중복된 키를 관리함. 이는 키가 고유해야 하는 경우에 유용해 여러 값을 저장하는 경우, 맵은 각 키에 대해 해당 값의 집합이나 리스트를 관리할 수 있음

 

e. map의 단점

1) 데이터가 별로 없고, 순회를 주된 목적으로 해야한다면 벡터가 더 나음 (시간 복잡도)

2) C#과의 관계 

 

 

C#에선 Dictionary가 기본이라 C++에서도 map을 거의 사용하지 않음...

 

 

2. map의 연산

a. 추가

key와 value를 짝을 이뤄서 넣어줘야 함 : std::pair<a, b>

 

이렇게 넣어주면 됨

 

---

 

여기부터 아래는 설명 - 

 

기본으로 있지만 만들어보면 이런 느낌

 

만들었다면 key, value를 지정해준다

 

데이터를 넣어준다면 이런 느낌

 

만약 여기서 페어를 auto와 템플릿을 써서 만든다면

 

이것도 당연히 표준에 있음 (그냥 만들어본것)

 

이렇게 코드가 간단해짐!

 

이게 표준에서 제공하는 코드

 

위 코드를 깔끔하게 만들면 첫 번째 사진처럼 된다!

 

b. 찾기

1) find

 

이미 레드-블랙 트리로 정렬이 되어있기 때문에 굉장히 빠르다 : 0(logN)

 

300번 유저를 찾는 코드

 

auto로 간편하게 사용

 

찾은 map의 데이터를 각각 뽑아주고

 

위 코드는 화살표로 치환 가능

 

이렇게 바뀐다~!

 

값이 있는지 없는지 확인해주자

 

2) 임의접근 

 

100번째 키에 해당하는 값을 가져와주세요

 

만약 여기 없는 키값을 넣은 경우엔 값을 가져오는게 아닌 추가해버림

 

뜬금없는 값이 들어가있다

 

즉, 이렇게 됨

 

💥  하지만 언리얼에선 그냥 크래시나버림 -> stl의 기능이 다른 경우가 있다 

 

ex) m.empty()는 stl : 데이터 유무를 판별 / unreal : 데이터를 날림

 

c. 삭제

erase로 삭제하면 됨

 

찾거나 키값으로 삭제

 

d. 순회

만약 map이 순회가 주된 업무면 벡터보다 느림

 

이렇게 하면 됨

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -