STL map

vector와 list에는 큰 단점이 하나 존재하는데 바로

"원하는 조건에 해당하는 데이터를 찾는 속도가 느리다!"

 

그렇다면 이런 상황에서는 뭘 사용해야할까?

 

map 

- 균형 이진 트리로 데이터를 저장하는 자료구조

 

c++의 map은 python과 C#의 dictionary라고 생각하면 된다

map을 생성할때 key와 value를 넣고 나중에 key로 value를 꺼내는 형식임

// map<KeyType, valueType> m;
map<int, int> m;

// 데이터 생성
m.emplace(1, 2); // key = 1, value = 2
m.emplace(5, 23);
m.insert(make_pair(2, 100)); // key = 2,  value = 100 : key값이 이미 사용중이면 작동 안함

// 데이터 출력
cout << m[2] << endl; // key가 2인 value 출력

map<int,int>::iterator it = m.find(5);
cout << it->second << endl; // first - key , second - value

 

map의 경우 균형 이진 트리로 구성되어 있어서 찾는 속도가 굉장히 빠른데

 

균형이진트리란

"오른쪽 서브트리의 높이"와 "왼쪽 서브트리의 높이" 차이가 1이하이면서

루트 노드보다 "작은 값은 왼쪽 자식", "큰 값은 오른쪽 자식"이 되는 트리임

 

이러한 특징 때문에 1~100 까지의 key가 있을때

최대 7번의 시도면 데이터를 찾을 수 있을 정도로 접근이 빠름

 

[ ]연산자 사용시 주의사항

m[5] = 500; // 5라는 키값이 있으면 데이터를 500으로 바꾸고 없으면 생성

// 대입을 하지 않더라도 (key/ Value) 형태의 데이터가 추가된다!
m.clear();
for (int i = 0; i < 10; i++)
{
    cout << m[i] << endl;
}
// m[i]라는 key가 없으면 m[i]를 생성하므로 주의해야함!