C++ Map Conatiner

해당 글은 공부를 하면서 적은 글이기 때문에 틀릴 수 있습니다. 참고용으로만 봐주세요~

 

0. 개요

---

오늘은 list, array, vector에 이어 map에 대해 공부했습니다.

 

1. map 이란?

---

map은 STL 표준 시퀀스 컨테이너인 list, string, vector와 다르게 STL 표준 연관 컨테이너입니다.

( STL 표준 연관 컨테이너로는 map, multimap, set, multiset이 있습니다. MSDN에서 각 컨테이너 사용에 추천되는 경우를 map에 대한 정리글 하단에 접은 글로 적어두었습니다.)

map은 list와 마찬가지로 노드로 구성되어 있고, 노드에 데이터는 key와 value로 쌍으로 구성되어있는 tree 구조입니다.

key값을 이용해 map에서 데이터를 탐색하게되고, key와 쌍을 이루는 value 즉, 원하는 값을 찾을 수 있습니다.

또한 key 값은 고유하며 데이터를 자동으로 정렬하는 데에도 사용됩니다.

이 key값은 상수이며 변경할 수 없고, 중복될 수 없다는 특징이 있습니다.

하지만 value는 직접 변경 할 수 있습니다.

 

tree의 경우 레드-블랙 트리, 이진 트리 등등 다양하게 있습니다.

map은 그중 레드-블랙 트리로 구성되어있습니다.

(레드-블랙 트리는 탐색, 삽입, 삭제가 O(logn)으로 이루어지는 트리입니다.)

 

map의 장점으로는 key를 기준으로 데이터를 정렬하여 저장하기 때문에, 데이터를 검색하는 것이 빠르고 key-value pair로 데이터를 저장하기 때문에 데이터 삽입과 삭제가 빠릅니다. 뿐만 아니라 동일한 key값이 존재할 수 없다는 점 때문에 데이터의 중복을 사전에 방지할 수 있다는 장점이 있습니다.

하지만 map의 단점으로는 데이터를 정렬해 저장하기 때문에 데이터 삽입, 삭제 시 정렬 유지를 위한 추가적인 작업이 필요하다는 것입니다. 이로 인해 삽입과 삭제에 추가적인 연산이 들어갑니다. 또 map은 데이터를 검색할 때, 이진 탐색 알고리즘을 사용하기 때문에 검색 속도가 O(log n)입니다. 이는 추후에 공부할 unordered_map과 비교했을 때, 상대적으로 느리다는 단점이 있습니다.

 

정리하자면 다음과 같습니다.

C++ STL의 map은 key-value 쌍으로 데이터를 저장하는 연관 컨테이너이다.
map은 tree로 구현되어있고 그중 레드-블랙 트리를 사용한다.
map은 key-value 쌍으로 데이터를 저장하기 때문에 key-value를 모두 저장한다.
map은 기본적으로 데이터를 key 값의 오름차순으로 정렬하여 저장한다.
(해당 정렬은 직접 설정해 줄 수 있다.)
map의 key값은 중복되어 사용할 수 없다. 즉, key값은 유일해야 한다.

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

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

시간 복잡도
접근 - O(log n)
          key값으로 데이터를 저장하고, 검색하기 때문에 해당 시간 복잡도로 데이터에 접근할 수 있다.
검색 - O(log n)
          이진 탐색 알고리즘을 사용해 탐색하기 때문에 해당 시간 복잡도를 갖는다.
삽입 및 삭제 - O(log n)
          데이터 삽입, 삭제 시 정렬을 유지해야하기 때문에 추가적인 작업이 필요하다. 때문에 해당 시간 복잡도를 갖는다.

값을 키와 연결하는 조건을 애플리케이션이 충족할 경우 map을 연관 컨테이너로 사용하는 것이 좋고

키가 고유하지 않을 경우 multimap이 적절한 컨테이너로 사용되는게 좋다.

또 단어의 목록만 저장하려는 경우 set이 적절한 컨테이너 일 수 있고

단어가 여러번 중복 발생하는 것을 허용한 경우 multiset이 적절할 수 있습니다.

- MSDN에서 각 조건에 따른 추천하는 연관 컨테이너 입니다.

(어떤 느낌인지는 감이 오지만 아직 set, multimap, multiset에 대한 공부를 하지 않아 정확한 전달이 안되었을 수 있기 때문에 직접 MSDN에 방문해 해당 글을 읽어보시는 것을 추천드립니다.)

 

2. map의 사용법

---

map도 사용하기 위해서는 <map> 헤더를 포함해 주어야 합니다.

namespace또한 마찬가지로 std에 위치해 있습니다.

 

map의 기본 형태는 map<key,value> map_;입니다.

#include <map>
using namespace std;

void main()
{
    map<int, string> map_student;

    return;
}

 

map의 멤버 함수

◈ map.at();

    지정된 Key 값이 있는 요소를 찾습니다.

 

◈ map.begin();

    map의 첫 번째 요소를 가리키는 iterator를 반환합니다.

 

◈ map.end();

    map의 마지막 요소 다음을 가리키는 iterator를 반환합니다.

 

◈ map.cbegin();

    map의 첫번 째요소를 가리키는 const_iterator를 반환합니다.

 

◈ map.cend();

    map의 마지막 요소 바로 다음을 가리키는 const_iterator를 반환합니다.

 

◈ map.clear();

    map의 모든 요소를 지웁니다.

 

◈ map.contains();

    map에 지정된 키가 있는 요소가 있는지 확인합니다.

 

◈ map.count();

    키가 매개 변수에서 지정한 키와 일치하는 map의 요소 수를 반환합니다.

 

◈ map.crbegin();

    역방향 map의 첫 번째 요소를 가리키는 const_iterator를 반환합니다.

 

◈ map.crend();

    역방향 map의 마지막 요소 뒤의 위치를 가리키는 const_iterator를 반환합니다.

 

◈ map.emplace();

    map에 생성된 요소를 삽입합니다.

 

◈ map.emplace_hint()

    배치 힌트를 사용하여 생성된 요소를 해당 map 위치에 삽입합니다.

 

◈ map.empty();

    map이 비어 있으면 true를 반환합니다.

 

◈ map.equal_range();

    iterator 쌍을 반환합니다.

    map에서 지정된 키보다 큰 키가 있는 첫 번째 요소를 가리키는 쌍의 첫 번째 iterator,

    map에서 키보다 크거나 같은 키가 있는 첫 번째 요소를 가리키는 쌍의 두 번째 iterator

 

◈ map.erase();

    map에서 지정된 위치의 요소 또는 요소 범위를 제거합니다.

 

◈ map.find();

    map의 키가 지정된 키와 같은 요소 위치를 가리키는 iterator를 반환합니다.

 

◈ map.get_allocator();

    map을 생성하는 데 사용된 allocator 개체의 복사본을 반환합니다.

 

◈ map.insert();

    요소 또는 요소의 범위를 map의 지정된 위치에 삽입합니다.

 

◈ map.key_comp();

    map에서 키를 정렬하는 데 사용되는 비교 개체의 복사본을 반환합니다.

 

◈ map.lower_bound();

    지정된 키의 값과 같거나 큰 키 값이 있는 첫 번째 요소에 대한 iterator를 반환합니다.

 

◈ map.max_size();

    map의 최대 길이를 반환합니다.

 

◈ map.rbegin();

    역순 map의 첫 번째 요소를 가리키는 iterator를 반환합니다.

 

◈ map.rend();

    역방향 map의 마지막 요소 뒤의 위치를 가리키는 iterator를 반환합니다.

 

◈ map.size();

    map에 있는 요소 수를 반환합니다.

 

◈ map.swap();

    두 map의 요소를 서로 교환합니다.

 

◈ map.upper_bound();

    지정된 키보다 큰 키 값이 있는 map 첫 번째 요소에 대한 iterator를 반환합니다.

 

◈ map.value_comp();

    map에서 요소 값의 정렬에 사용되는 비교 개체의 복사본을 검색합니다.

 

 

참고 문헌

map 클래스

 

[C++/STL] - map