[C++] map(맵)

map(맵)

특징

• 연관 컨테이너(Associative Container) 중 하나이다.
  • 연관 컨테이너에는 set, multiset, map, multimap 이 있다.
• string : int 형태로 값을 할당해야 할 때 맵을 사용한다.
• 키(Key)와 값(Value) 형태로 이루어져 있고, 레드-블랙 트리(Red-Black Tree)라는 구조를 내장하고 있다.
  • 노드 기반으로 이루어져 있고, 균형 이진 트리 구조이다.
  • pair 객체 형태로 키(Key)와 값(Value)이 저장된다.
  • Key는 고유한 값이므로 중복이 불가능하다.
    • 중복 Key를 사용하려면 multimap을 사용하면 된다.
  • 삽입, 삭제, 탐색에 대해서 $O(logN)$ 정도의 시간 복잡도를 가진다.
• 집합(Set)과 마찬가지로 삽입이 되면서 자동으로 정렬이 된다.
  • 데이터를 삽입할 때 정렬된 위치에 삽입되게 된다.
    
    • 검색 속도가 빠르다는 장점이 있다.
  • 정렬 대상은 키(Key)를 기준으로 오름차순 정렬한다.
  • 정렬의 기본값은 오름차순(less)이다.
• 저장 공간의 필요에 따라 allocator 객체를 사용한다. (동적 할당을 수행한다.)
• map의 종류에는 unordered_map과 map 2가지가 있으며, map은 정렬을 보장한다.
  • unordered_map에 대해 알아보기 : https://dev-astra.tistory.com/245

맵의 구조

 

헤더 파일

• 맵(Map)을 사용하려면 다음의 헤더 파일을 불러와야 한다.

#include <map>

 

멤버 함수

 

사용 방법

객체 생성

일반적인 방법

map<[data_type_1], [data_type_2]> [name]

 

사용 예

map<int, int> m1;
map<string, int> m2;

 

정렬 방법을 지정하는 방법

• 요소가 삽입될 때, 정렬되는 기준(pred)을 지정한다.
• pred는 map의 정렬 기준인 조건자이다.

map<int> m(pred);    // pred를 통해 정렬 기준(오름차순, 내림차순)을 정한다.

 

다른 맵의 요소를 복사하여 생성하는 방법

map<int> m2(m1);    // m1을 복사한 m2를 생성

 

관련 연산자

• ==, !=, <, >, <=, >= 연산자를 사용할 수 있다.
• [] 연산자를 이용하여 요소를 다룰 수 있다.
  • m[key] = Value; 을 통해서 원소 (Key, Value)를 추가 또는 수정이 가능하다.

 

선언과 동시에 초기화하기

• 다양한 방법으로 객체를 선언과 동시에 초기화할 수 있다.

map<int, string> m0 {
    {1, "1"},                       // way 1
    pair<int, string>(2, "1"),      // way 2, C++17 이상부터 pair(1, "1") 과 같이 사용 가능 (자동 추론)    
    make_pair(3, "1")               // way 3
};

 

• 다음과 같이 일관성 있게 선언하는 것이 좋다.

map<int, string> m1 {
    {1, "1"},
    {2, "2"},
    {3, "3"}
};

 

요소 삽입

• 다양한 방법으로 맵에 요소를 넣을 수 있다.
• 이미 값이 있는 키(Key)에는 값(Value)을 삽입할 수 없다.
• 5번 방법이 권장된다.

// 1. insert() 함수에 pair 객체로 묶은 요소를 인자로 하여 요소 넣기
m1.insert(pair<int, int>(10, 20));
m2.insert(pair<string, int>("Kim", 27));

// 2. insert() 함수에 중괄호({})에 넣은 요소를 인자로 하여 요소 넣기
m1.insert({ 10, 20 });
m2.insert({ "Kim", 27 });

// 3. insert() 함수에 make_pair() 함수를 이용하여 묶은 요소를 인자로 하여 요소 넣기
m1.insert(make_pair(10, 20));
m2.insert(make_pair("Kim", 27));

// 4. emplace() 함수를 이용하여 요소 넣기
m1.emplace(10, 20);
m2.emplace("Kim", 27);

// 5. [] 연산자를 이용하여 넣기 (변경 및 추가 가능)
m1[10] = 20;
m2["Kim"] = 27;

 

요소 수정

• 다음과 같은 방법으로 요소의 값(Value)을 수정할 수 있다.

m1[10] = 77;    // 방법 1-1 : 키(Key)가 10인 값(Value)을 77로 변경
m2["Kim"]++;    // 방법 1-2 : 키(Key)가 "Kim"인 값(Value)을 1 증가시킴.

 

• for 문을 이용하여 다양하게 값(Value)을 한번에 수정할 수 있다.

// 방법 2
for (auto i = m1.begin(); i != m1.end(); i++) {
    i->second = 7;       // m1 맵의 요소들의 값(Value)을 모두 7로 변경함.
    (*i).second = 8;     // m1 맵의 요소들의 값(Value)을 모두 8로 변경함.
}

// 방법 3
for (auto i : m1) {
    i.second = 9;    // m1 맵의 요소들의 값(Value)을 모두 9로 변경함.
}

// 방법 4 : C++17부터 사용 가능 (분기)
for (auto [key, value] : m1) {
    value = 10;    // m1 맵의 요소들의 값(Value)을 모두 10으로 변경함.
}

// 방법 5 : C++17부터 사용 가능 (분기)
for (auto i : m1.cbegin(); i != m1.cend(); i++) {
    auto [key, value] = *i;
    value = 11;    // m1 맵의 요소들의 값(Value)을 모두 11로 변경함.
}

 

• 다음과 같은 분기 기능은 C++17 부터 사용 가능하다.

map<int, string> m {
    {1, "1"},
    {2, "2"},
    {3, "3"}
};

if (auto [iter, success] = m.insert({1, "7"}), success) {
    cout << success << endl;
    cout << iter->first << endl;
    cout << iter->second << endl;
}

 

요소 접근(순회)

• 다음과 같은 방법으로 요소에 접근(순회)할 수 있다.
• Key 값은 first, Value 값은 second로 탐색이 가능하다.

// 방법 1 : for
for (auto i = m1.begin(); i != m1.end(); i++) {
    cout << "(" << i->first << ", " << (*i).second << ")" << '\n';    // 2가지 방법으로 요소에 접근 가능
}

// 방법 2 : range for
for (auto i : m1) {
    cout << "(" << i.first << ", " << i.second << ")" << '\n';
}

 

• 다음과 같이 다양하게 요소에 접근(순회) 할 수 있다.
  • const_iterator를 사용할 경우, cbegin(), cend() 메소드를 이용한다.
  • iterator를 사용할 경우, begin(), end() 메소드를 이용한다.

// 방법 3
for (const pair<const int, string>& pair : m1) {
    cout << "(" << pair.first << ", " << pair.second << ")" << '\n';
}

// 방법 4
for (auto& pair : m2) {
    cout << "(" << pair.first << ", " << pair.second << ")" << '\n';
}

// 방법 5
for (map<int, string>::const_iterator i = m1.cbegin(); i != m1.cend(); i++) { 
    cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}

// 방법 6
for (auto i = m2.cbegin(); i != m2.cend(); i++) {
    cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}

// 방법 7
for (const auto& [key, value] : m1) {
    cout << "(" << key << ", " << value << ")" << '\n';
}

// 방법 8
for (auto i = m2.cbegin(); i != m2.cend(); i++) {
    auto& [key, value] = *i;
    cout << "(" << i->first << ", " << (*i).second << ")" << '\n';
}

 

 

요소 찾기

• find() 메소드를 이용하여 요소를 찾을 수 있다.

map.find([Key]);

• find() 메소드는 요소를 찾지 못하면 end() 이터레이터(Iterator)를 반환한다.

auto search = m1.find(40);
if (search != m1.end()) {
    cout << "Key : " << search->first << ", Value : " << (*search).second << '\n';    // 발견되면 키와 값을 출력
}
else {
    cout << "Not Found." << '\n';    // 발견되지 않으면 발견되지 않았다는 문장 출력
}

 

• C++17부터 다음과 같이 요소를 찾을 수 있다.

if (auto i = m1.find(10); i != m1.end()) {
    cout << i->first << " : ";       // Key 출력
    cout << i->second << endl;       // Value 출력
}

 

해당 키(Key)가 맵에 있는지 확인하기

• count() 메소드를 이용하여 해당 키(Key)가 맵에 있는지 확인할 수 있다.

map.count([Key]);

#include <iostream>
#include <map>
using namespace std;

map<int, string> m {
    {1, "1"},
    {2, "2"},
    {3, "3"}
};

int main() {
    cout << m.count(3) << " " << m.count(10) << '\n';     // 해당 키가 있으면 1, 없으면 0 출력

    return 0;
}

1 0

 

맵 객체의 크기 출력하기

• size() 메소드를 이용하여 맵 객체의 크기를 출력할 수 있다.

cout << m1.size() << '\n';

 

맵 객체의 요소 지우기

• erase() 메소드를 이용하여 맵 객체의 특정 요소를 지울 수 있다.
  • 키(Key)와 값(Value) 모두 지워진다.

map.erase([Key]);

m1.erase(10);    // 키 값이 10인 요소 제거

 

• 또는 다음과 같이 find() 메소드를 활용하여 요소를 지울 수 있다.

auto search = m1.find(10);   
if (search != m1.end()) {
    m1.erase(search);
}

 

맵에 있는 모든 요소 지우기

• clear() 메소드를 이용하여 맵에 있는 모든 요소를 지울 수 있다.

m1.clear()    // 맵에 있는 모든 요소 제거

 

사용 시 주의사항

맵과 참조

• 맵을 사용할 때, 해당 인덱스에 참조만 해도 값(Value)이 생긴다. (맵의 요소가 생긴다.)
  • int 형의 경우 0이 값(Value)으로 들어간다.
  • string 형의 경우 빈 문자열이 값(Value)으로 들어간다.

#include <iostream>
#include <map>
using namespace std;

map<int, int> mp1;
map<string, string> mp2;

int main() {
    // 인덱스에 참조만 하기
    cout << mp1[1] << '\n';    
    cout << mp2["aaa"] << '\n';  

    // 확인하기
    for (auto i : mp1) {
        cout << i.first << " " << i.second << '\n';
    }
    for (auto i : mp2) {
        cout << i.first << " " << i.second << '\n';
    }
    
    return 0;
}

0

1 0
aaa 

 

• 따라서 맵에 요소가 있는지 없는지를 확인하고 맵에 데이터를 할당하는 부분의 로직을 다음과 같이 구축할 수 있다.
  
  • 다만, 이 방법은 해당 키의 값(Value)에 0이 아닌 값이 들어갈 때만 활용이 가능하다.
  • 문제에서 키에 0이 들어가는 경우 활용이 불가능하다.

#include <iostream>
#include <map>
using namespace std;

map<int, int> mp;

int main() {
    if (mp[1] == 0) {    // mp1의 첫 번째 인덱스에 접근하자마자 0이 값(Value)으로 생성된다.
        mp[1] = 2;    // 값(Value)을 2로 변경해준다.
    }
    for (auto i : mp) {
        cout << "Key : " << i.first << ", Value : " << i.second << '\n';
    }
    
    return 0;
}

Key : 1, Value : 2

 

• 만약 문제에서 키의 값(Value)에 0이 들어가는 경우에는 다음과 같이 사용하는 것이 좋다.

#include <iostream>
#include <map>
using namespace std;

map<int, int> mp;

int main() {
    if (mp.find(1) == mp.end()) {    // find() 메소드는 요소를 찾지 못하면 end() 이터레이터를 반환한다.
        mp[1] = 2;
    }
    
    for (auto i : mp) {
        cout << "Key : " << i.first << ", Value : " << i.second << '\n';
    }
    
    return 0;
}

Key : 1, Value : 2

 

map vs. unordered_map

• map과 unordered_map을 모두 사용할 수 있는 경우, unordered_map을 사용하는 것이 시간 복잡도 측면에서 더 효율적이다. (관련 문제 : https://dev-astra.tistory.com/252)
  • map
    • 탐색, 삽입, 삭제 : $O(\log n)$
  •  unordered_map
    • 탐색, 삽입, 삭제 : $O(1)$
    • 최악의 경우 : $O(N)$
• 참고로, map은 다른 연관 컨테이너(multimap, set, multiset 등)에 비해 비교적 빠른 속도를 보인다.

 

사용 예

#include <iostream>
#include <map>

using namespace std;

// [1] 객체 생성 및 초기화
//// 객체만 생성
map<int, string> m1;

//// 객체 생성과 동시에 초기화
map<int, string> m2 {
    { 1, "Lim" },                   // 방법 1
    pair<int, string>(2, "Kuk"),    // 방법 2
    make_pair(3, "Yun")             // 방법 3
};

int main() {
    // [2] 요소 삽입
    m1.insert(pair<int, string>(40, "Me"));   // 방법 1
    m1.insert({ 20, "Lee" });                 // 방법 2
    m1.insert(make_pair(10, "Choi"));         // 방법 3
    m1.emplace(35, "Park");                   // 방법 4
    m1[65] = "Kim";                           // 방법 5
    
    // [3] 요소 접근
    //// 방법 1
    for (auto i = m1.begin(); i != m1.end(); i++) {
        cout << "(" << i->first << ", " << (*i).second << ")" << '\n';    // 2가지 방법으로 요소에 접근 가능
    }
    
    cout << endl;
    
    //// 방법 2
    for (auto i : m2) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    cout << endl;
    
    // [4] 요소 찾기
    auto search1 = m1.find(70);    // 찾기 실패
    auto search2 = m1.find(20);    // 찾기 성공
    
    if (search1 != m1.end()) {
        cout << "Key : " << search1->first << ", Value : " << (*search1).second << '\n';
    }
    else {
        cout << "Not Found." << '\n';
    }
    
    if (search2 != m1.end()) {
        cout << "Key : " << search2->first << ", Value : " << (*search2).second << '\n';
    }
    else {
        cout << "Not Found." << '\n';
    }
    
    //// 해당 키가 맵에 있는지 확인하기
    cout << m1.count(22) << " " << m2.count(20) << '\n';
    
    // [5] 요소 수정
    map<string, int> m3 {
        { "Queen", 2 },
        { "Prince", 3 },
        { "Princess", 4 }
    };
    
    m3["Pince"] = 0;   // 방법 1-1
    m3["Queen"]++;     // 방법 1-2 : 값(Value)을 1 증가 시킴.
    
    // 방법 2
    for (auto i = m3.begin(); i != m3.end(); i++) {
        i->second = 7;       // m3 맵의 요소들의 값(Value)을 모두 7로 변경함.
        (*i).second = 8;     // m3 맵의 요소들의 값(Value)을 모두 8로 변경함.
    }
    
    // 방법 3
    for (auto i : m3) {
        i.second = 9;    // m3 맵의 요소들의 값(Value)을 모두 9로 변경함.
    }
    
    // 방법 4 
    for (auto [key, value] : m3) {
        value = 10;    // m3 맵의 요소들의 값(Value)을 모두 10으로 변경함.
    }
    
    // 방법 5 
    for (auto i = m3.cbegin(); i != m3.cend(); i++) {
        auto [key, value] = *i;   
        value = 11;    // m3 맵의 요소들의 값(Value)을 모두 11로 변경함.
    }
    
    cout << endl;
    
    // [6] 맵 객체의 크기 출력하기
    cout << m1.size() << '\n';
    cout << m2.size() << '\n';
    cout << m3.size() << '\n';
    
    cout << endl;
    
    // [7] 맵 객체의 요소 지우기
    //// 방법 1
    m1.erase(10);
    
    //// 방법 2
    auto search = m1.find(10);
    if (search != m1.end()) {
        m1.erase(search);
    }
    
    cout << endl;
    
    // [8] 맵에 있는 모든 요소 지우기
    m1.clear();
    m2.clear();
    m3.clear();
    
    cout << endl;
    
    // [*] 맵에 요소가 있는지 없는지를 확인하고 맵에 데이터를 할당하기
    //// 방법 1
    if (m1[90] == "") {
        m1[90] = "Koo";
    }
    
    //// 방법 2
    if (m1.find(50) == m1.end()) {
        m1[50] = "Jung";
    }
    
    // 결과 출력
    for (auto i : m1) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    for (auto i : m2) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    for (auto i : m3) {
        cout << "(" << i.first << ", " << i.second << ")" << '\n';
    }
    
    return 0;
}

(10, Choi)
(20, Lee)
(35, Park)
(40, Me)
(65, Kim)

(1, Lim)
(2, Kuk)
(3, Yun)

Not Found.
Key : 20, Value : Lee
0 0

5
3
4



(50, Jung)
(90, Koo)