[Data Structure] Map (맵)

Map

📢 (Key-Value)로 이루어진 Pair 들을 특정 순서를 가지고 저장하는 타입

---

Map 특징

• Key-Value 로 이루어진 Pair 들을 저장해요.
• 각각의 Key는 중복 없이 유일해야 해요.
• Insert를 하면 특정 순서대로 Pair들이 정렬이 돼요.
• Red-Black Tree와 같은 Self balancing BST로 구현이 돼요.

⏰ 시간 복잡도

탐색(Search), 삽입(Insert), 제거(Delete)

• 기본적으로 O(logN)만큼의 시간복잡도를 가져요.
• 이는 Map이 레드-블랙 트리로 구현되기 때문이에요.

Pair 특징

• (Key, Value) 형태의 자료형이에요.
• Key값은 first로 Value값은 second접근이 가능해요.

---

🎨 내부 메서드 (C++)

C++ STL 내부에 Map이 존재해요!
#include <map>을 헤더에 추가하시고 사용하면 됩니다.
변수 선언 방법은 아래와 같아요.

map<자료형, 자료형> 변수명;

메소드 이름	역할
begin, end	Map의 처음과 끝의 Iterator 반환
empty	Map 내부가 비어있는지 여부를 반환
size	Map의 크기를 반환
[], at	Map의 특정 Key를 가진 데이터에 접근
insert	Map에 데이터 추가
erase	Map에서 데이터 제거
clear	Map 내부 요소 전부 제거
swap	Map끼리 내부 데이터 교환
find	특정 Key값을 가진 데이터를 반환

🔉 insert

Map에 데이터를 Insert 하는 방법은 2가지예요.

• insert() 사용하기
  newMap.insert(pair<Key 자료형, Value 자료형>(Key,Value));
• [] 사용하기
  newMap[Key] = Value;

---

아래는 위의 메소드를 적용한 예제예요.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> newMap;
    /*---------------Insert Method----------------------*/
    newMap.insert(pair<string, int>("Apple", 1000));
    newMap.insert(pair<string, int>("Grape", 4000));
    newMap["Peach"] = 5000;
    newMap["Banana"] = 2000;
    // insert는 Key가 중복이 되면 에러를 발생
    // []는 Key가 중복이 되면 값을 Update 
    /*--------------------------------------------------*/

    /*---------------Find Method------------------------*/
    cout << newMap.find("Banana")->second << endl;
    cout << newMap.find("Peach")->first << endl;
    /*--------------------------------------------------*/

    /*---------------[], at Method----------------------*/
    cout << newMap["Peach"] << endl;
    cout << newMap.at("Banana") << endl;
    /*--------------------------------------------------*/

    /*---------------Size Method------------------------*/
    cout << newMap.size() << endl;
    /*--------------------------------------------------*/

    /*---------------Begin, End Method------------------*/
    for(auto iter = newMap.begin(); iter != newMap.end(); iter++) {
        cout << iter->first << " ";
        cout << iter->second << endl;
    }
    /*--------------------------------------------------*/

    /*---------------Erase Method-----------------------*/
    newMap.erase("Grape");
    /*--------------------------------------------------*/

    /*---------------Clear Method-----------------------*/
    newMap.clear();
    /*--------------------------------------------------*/
    
    /*---------------Empty Method-----------------------*/
    if(newMap.empty())
        cout << "Map is empty!!" << endl;
    else
        cout << "Map is not empty!!!" << endl;
    /*--------------------------------------------------*/
}