Map

개념

원소가 삽입될 때 자동으로 정렬된다.
이때 정렬되는 기준은 킷값이다.

C++에서 map은 레드-블랙 트리(red-black tree)라는 자료구조를 이용하여 구현.
이 자료구조는 원소들을 이진 검색 트리(binary search tree)로 저장하면서, 각 노드에 색을 추가하여 불균형한 경우 자동으로 균형을 맞추는 알고리즘이다.

이를 통해 탐색, 삽입, 삭제 등의 연산에서 평균 시간 복잡도가 O(log n)을 보장한다.

킷값이 아닌 값을 기준으로 정렬이 필요할 때는, vector에 복사하여 정렬하는 기법을 쓴다.

예시

 vector<pair<int,int>> vec(map.begin(), map.end());
 sort(vec.begin(), vec.end(), compare);

예시

맵은 중복되는 자료를 허용하지 않는다.
이러한 특징을 이용하여, 킷값이 가지고 있는 값의 개수를 구할 수 있다.

 for(int i = 0; i < Numbers.size(); i++)
 	{
        map[Numbers[i]]++;
    }

map 클래스의 맴버 함수는 다음과 같다.

std::map::begin() : 맵의 시작점(iterator)을 반환한다.
std::map::end() : 맵의 끝점(iterator)을 반환한다.
std::map::size() : 맵의 크기(저장된 쌍의 수)를 반환한다.
std::map::empty() : 맵이 비어있는지 여부를 반환한다.
std::map::insert() : 맵에 쌍을 삽입한다.
std::map::erase() : 맵에서 지정한 쌍을 제거한다.
std::map::clear() : 맵의 모든 쌍을 제거한다.
std::map::find() : 지정한 키에 대한 반복자(이터레이터)를 반환한다.
std::map::count() : 지정한 키에 대한 맵 내의 쌍의 개수를 반환한다.
std::map::operator[] : 맵 내에서 키를 사용하여 값을 참조하거나, 새로운 쌍을 삽입한다.

map 클래스의 멤버 변수는 다음과 같다.

std::map::key_type : 맵의 키(key)의 데이터 타입이다.
std::map::mapped_type : 맵의 값(value)의 데이터 타입이다.
std::map::value_type : 맵에 저장되는 쌍(pair)의 데이터 타입이다. 쌍은 키(key)와 값(value)의 묶음으로 이루어진다.
std::map::size_type : 맵의 크기를 나타내는 데이터 타입이다. 보통 unsigned int나 unsigned long 등과 같은 정수형(unsigned integral type)이다.