[C++/STL] - map

1. map 이란

STL의 map은 key-value 쌍으로 데이터를 저장하는 연관 컨테이너이다. map은 C++에서 트리로 구현되어 있으며, 레드-블랙 트리를 사용한다.

2. 특징

• map은 key-value 쌍으로 데이터를 저장하기 때문에, key와 value를 모두 저장한다.
• map은 데이터를 key 값의 오름차순으로 정렬하여 저장한다.
• map은 key 값이 중복될 수 없다. key 값은 유일해야 한다.

3. 장단점

장점 :

• map은 key를 기준으로 데이터를 정렬하여 저장하기 때문에, 데이터를 검색하는데 있어서 매우 빠르다.
• map은 key-value 쌍으로 데이터를 저장하기 때문에, 데이터를 빠르게 삽입하고 삭제할 수 있다.
• map은 데이터를 저장할 때, key 값이 중복될 수 없다. 이를 통해 데이터의 중복을 방지할 수 있다.

단점 :

• map은 데이터를 정렬하여 저장하기 때문에, 데이터를 삽입하거나 삭제할 때, 정렬을 유지하기 위한 추가적인 작업이 필요하다. 이로 인해 삽입 및 삭제 연산이 느릴 수 있다.
• map은 데이터를 검색할 때, 이진 탐색 알고리즘을 사용하기 때문에, 검색 속도가 O(log n)이다. 이는 unordered_map과 비교했을 때, 상대적으로 느리다.

4. 시간복잡도

1. 접근 - O(log n)
   map은 key값으로 데이터를 저장하기 때문에, key값을 알고 있다면 O(log n)의 시간복잡도로 해당 데이터에 접근할 수 있다.
2. 검색 - O(log n)
   map에서 데이터를 검색하는 경우, 이진 탐색 알고리즘을 사용하기 때문에 O(log n)의 시간복잡도를 갖는다.
3. 삽입 및 삭제 - O(log n)
   map에서 데이터를 삽입하거나 삭제하는 경우, 데이터를 정렬하여 저장하기 때문에 정렬을 유지하기 위한 추가적인 작업이 필요하다. 따라서, 삽입 및 삭제 연산의 시간복잡도는 O(log n)이다.

5. 사용법

1) 초기화

map<key_type, value_type> my_map; 
//default constructor를 사용하여 초기화하는 방법

map<key_type, value_type> my_map = {
    {key1, value1},
    {key2, value2},
    {key3, value3},
    ...
}; // initializer list를 사용하여 초기화하는 방법

map<key_type, value_type> my_map;
my_map.insert(std::make_pair(key1, value1));
my_map.insert(std::make_pair(key2, value2));
my_map.insert(std::make_pair(key3, value3)); 
// insert() 함수를 사용하여 초기화하는 방법

map<key_type, value_type> old_map;
//...
map<key_type, value_type> new_map(old_map);
// copy constructor를 사용하여 초기화하는 방법

2) 멤버 함수

Iterators
begin() : 첫 번째 원소를 가리키는 반복자를 리턴한다.
cbegin() : 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
end() : 마지막 원소를 가리키는 반복자를 리턴한다.
cend() : 마지막 원소를 가리키는 상수 반복자를 리턴한다.
rbegin() : 역 순차열의 첫 번째 원소를 가리키는 반복자를 리턴한다.
crbegin() : 역 순차열의 첫 번째 원소를 가리키는 상수 반복자를 리턴한다.
rend() : 역 순차열의 마지막 원소를 가리키는 반복자를 리턴한다.
crend() : 역 순차열의 마지막 원소를 가리키는 상수 반복자를 리턴한다.
upper_bound(key) : map에서 해당 key 이상인 첫번째 원소를 가리키는 iterator를 반환하는 함수
lower_bound(key) : map에서 해당 key보다 큰 첫번째 원소를 가리키는 iterator를 반환하는 함수
equal_range() : map에서 해당 key와 일치하는 범위의 시작과 끝을 가리키는 pair<iterator, iterator>를 반환하는 함수

Element access
at(key) : map에서 해당 key에 대응하는 value를 반환하는 함수. operator[]와 달리, 해당 key가 존재하지 않을 경우 예외를 발생시킨다.
operator[key] : map에서 해당 key에 대응하는 value를 반환하는 함수

Capacity
empty() : map이 비어있는지 확인하는 함수
size() : 원소의 개수를 리턴한다.
max_size() : 담을 수 있는 원소의 최대 개수를 리턴한다.

Modifiers
insert() : map에 새로운 원소를 삽입하는 함수
erase(key) : map에서 해당 key를 가지는 원소를 제거하는 함수
erase(iterator pos) : pos위치의 원소 제거
erase(iterator first, iterator last) : first부터 last까지 제거
clear() : map의 모든 원소를 제거하는 함수
count() : map에서 해당 key를 가지는 원소의 개수를 반환하는 함수. map에서는 중복된 key를 가질 수 없으므로, 해당 key를 가지는 원소가 존재하면 1을 반환하며, 존재하지 않으면 0을 반환한다.
find(key) : map에서 해당 key를 가지는 원소를 탐색하는 함수. 해당 key를 가진 원소가 없을 경우 end()를 반환한다.
emplace() : map에 새로운 원소를 삽입하는 함수. 기존의 insert() 함수보다 조금 더 빠르며, 새로운 데이터를 생성하는 데 필요한 인수를 직접 전달할 수 있다는 장점이 있다.