map이란?

map은 각 노드가 key와 value 쌍으로 이루어진 트리이다 특히, 중복을 허용하지 않는다.

특징

• map은 key-value 쌍으로 데이터를 저장하기 때문에, key와 value를 모두 저장한다.
• map은 first, second가 있는 pair 객체로 저장되는 데 first- key로 second- value로 저장된다.
• map은 데이터를 key 값의 오름차순으로 정렬하여 저장한다. 만약 내림차순으로 정렬하고 싶은 경우 map <int, int, greater> m; 으로 사용하면 된다.
• map은 key 값이 중복될 수 없다. key 값은 유일해야 한다.
• map은 자료를 저장할 때 내부에서 자동으로 정렬한다.
• C++의 map의 내부 구현은 검색, 삽입, 삭제가 O(logn) 인 레드블랙트리로 구성되어 있다.

장점

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

단점

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

시간복잡도

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)이다.

map의 명령어 및 사용법

기본 선언

#include <map>

//맵 선언
map <key_type, value_type> 이름;
map <string, int> m;

초기화

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(make_pair(key1, value1));
my_map.insert(make_pair(key2, value2));
my_map.insert(make_pair(key3, value3)); 
// insert() 함수를 사용하여 초기화하는 방법

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

map 데이터 검색 (Search)

map에서 데이터를 찾을 때는 iterator을 사용한다.
데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환한다.

if (m.find("a") != m.end()) {
	cout << "find" << endl;
}
else {
	cout << "not find" << endl;
}

map에 데이터 삽입

map은 종복을 허용하지 않는데, insert를 수행할 때 key가 중복되면 insert가 수행되지 않는다.

m.insert({"bob", 100});

반복문 데이터 접근 (first, second)

• 인덱스 기반 반복문 예제
  :인덱스 기반은 iterator을 활용하여 begin()부터 end()까지 찾습니다.

//인덱스기반
for (auto iter = m.begin() ; iter !=  m.end(); iter++)
{
	cout << iter->first << " " << iter->second << endl;
}
cout << endl;

• 범위 기반 반복문 활용한 예제

for (auto iter : m) {
	cout << iter.first << " " << iter.second << endl;
}

map 데이터 삭제

map에서 데이터를 삭제하기 위해 활용할 함수는 erase와 clear이다.

특정 위치의 요소 삭제

m.erase(m.begin() + 2);

key값을 기준으로 요소 삭제

m.erase("bob");

map의 모든 요소 삭제

• erase 함수로 모든 요소 삭제하기 (map의 begin부터 end까지)

m.erase(m.begin(), m.end());

• clear 함수로 모든 요소 삭제하기

m.clear();

멤버함수

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() 함수보다 조금 더 빠르며, 새로운 데이터를 생성하는 데 필요한 인수를 직접 전달할 수 있다는 장점이 있다.