[C++ STL] map

 

1. key-value 쌍으로 다루는게 편할때

2. 이진트리로 구현된다!

그냥 map 하면 key-value 속성이 먼저 떠올라

무조건 hashtable 기반으로 되는줄 아는데 아니다

hastable 기반은 unordered_map이고,

그냥 일반 map은 이진트리로 구성되어 있다.

즉 정렬이 항상 되어 있는 상태이다

 

3.  노드기반 컨테이너이다. 2번을 통해 알 수 있다.

 

4. map[key] 를 통해 value 값 찾기 가능

 

5. key의 중복을 허용하지 않는다!!

 

 

6. 이진트리로 구현되어 있어 정렬 검색 속도 o(logN)임

 

---

[map 정렬 방식]

 

1) key 정렬 : map 생성자에 정렬기준 대입해서 바로 가능

 

map은 자료를 저장할때 내부에서 자동 정렬된다. 이진트리로 구성되어 있으니까 당연하다

그래서 저장할때마다 알아서 정렬을 한다.

 

map은 자료를 저장할때 key를 기준으로 내부에서 자동으로 정렬한다.

default일때는 오름차순.

greater 쓰면 내림차순 ㅇㅇ

// default 오름차순
map<int,int> myMap1;

// 내림차순
map<int,int,greater<int>> myMap2;

 

만약 사용자정의 정렬기준(custom comparator) 를 적용하고 싶으면

map 은 operator( ) , 연산자 ( )를 오버로딩 하는 방식으로 전달해줘야한다

따라서 다음과 같이 구조체 안에 정렬기준을 적어 넘겨줘야한다

 

struct cmp {
    bool operator()(int a, int b) {
        return a < b;
    }
};

 

 

2) value로 정렬 : vector로 바꾼다음 sort함수 이용해서 해야함

 

map만을 사용해서 value 값으로 정렬할 수 없다

map의 세번째 인자로 value 고려하는 정렬기준을 넣는 것도 안된다

map의 세번째 인자는 무조건 key 값 대상이다

 

vector로 변환해준다음,

정렬함수를 인자로 넣어주면

algorithm 파일의 sort 를 통해 value를 기준으로 정렬할 수 있다

 

bool comp(const pair<int, int>& a, const pair<int, int>& b) {
	return a.second < b.second;
}

map<int,int> myMap;

// vector로 변환
vector(myMap.begin(),myMap.end(),comp);

 

여기서 정렬함수를 정의할 때 주의할 점은

 

1. 인자를 pair 객체로 해야할 것(pair 객체들의 vector이니)

2. <algorithm>의 sort 함수는 true 이면 왼쪽에 있는걸 우선순위가 높다고 판단한다는 것(왼쪽에 있는걸 앞에 놓는다)

 

---

[중복된 데이터 추가할때 주의점]

 

여기서 ㅈㄴ 중요한게 있음

operator[]로 추가할때는 중복된 값이 있으면 해당 값을 value로 바꿈

 

하지만 insert( key , value ) 로 할때는 중복된 값이 있으면 업데이트를 안해줌!

 

 

이거 모르면 막 find 쓰고 iterator 써서 자동으로 얘가 알아서 해주는 기능인데도

내가 존재유무를 판별해서 저장하는 귀찮은 코드를 써야한다.

set이랑 동일한 부분이다.

중복을 허용하지 않으니 자동으로 얘가 중복 처리를 제공해주는데

이거 모르면 그냥 적지 않아도 되는 코드를 추가로 적고 있어야한다.